Bug 103017

Summary: [Shadow] Attaching children of a shadow host takes O(N^2) where N is the number of host children
Product: WebKit Reporter: Shinya Kawanaka <shinyak>
Component: DOMAssignee: Shinya Kawanaka <shinyak>
Status: RESOLVED FIXED    
Severity: Normal CC: dglazkov, ojan, webcomponents-bugzilla, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 103016    
Attachments:
Description Flags
Patch none

Shinya Kawanaka
Reported 2012-11-21 21:44:12 PST
We would like make this O(N). According to my micro benchmark: #host children -> distribution time 100 -> 67 [us] 200 -> 203 [us] 300 -> 497 [us] 400 -> 1331 [us] 500 -> 2084 [us]
Attachments
Patch (4.55 KB, patch)
2012-11-22 00:40 PST, Shinya Kawanaka 		no flags
DetailsFormatted DiffDiff
View All Add attachment proposed patch, testcase, etc.
Shinya Kawanaka
Comment 1 2012-11-21 21:44:51 PST
I would like to upload benchmarks later.
Shinya Kawanaka
Comment 2 2012-11-21 22:46:43 PST
InsertionPoint::nextTo() takes O(N). and it's called in NodeRenderingContext::nextRenderer(), which is called O(N) times. So Element::attach() will be O(N^2).
Shinya Kawanaka
Comment 3 2012-11-21 22:54:32 PST
> #host children -> distribution time > 100 -> 67 [us] > 200 -> 203 [us] > 300 -> 497 [us] > 400 -> 1331 [us] > 500 -> 2084 [us] Sorry, this is not correct. distribution is O(N).
Shinya Kawanaka
Comment 4 2012-11-22 00:40:41 PST
Created attachment 175610 [details] Patch
WebKit Review Bot
Comment 5 2012-11-22 06:40:27 PST
Comment on attachment 175610 [details] Patch Attachment 175610 [details] did not pass chromium-ews (chromium-xvfb): Output: http://queues.webkit.org/results/14966355 New failing tests: platform/chromium-linux/fast/text/international/complex-joining-using-gpos.html
Shinya Kawanaka
Comment 6 2012-11-25 18:26:20 PST
It seems just a flake. Let me add cq+ again.
WebKit Review Bot
Comment 7 2012-11-26 01:08:05 PST
Comment on attachment 175610 [details] Patch Clearing flags on attachment: 175610 Committed r135689: <http://trac.webkit.org/changeset/135689>
WebKit Review Bot
Comment 8 2012-11-26 01:08:10 PST
All reviewed patches have been landed. Closing bug.
Note You need to log in before you can comment on or make changes to this bug.