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

Description Shinya Kawanaka 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]
Comment 1 Shinya Kawanaka 2012-11-21 21:44:51 PST 
I would like to upload benchmarks later.
Comment 2 Shinya Kawanaka 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).
Comment 3 Shinya Kawanaka 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).
Comment 4 Shinya Kawanaka 2012-11-22 00:40:41 PST 
Created attachment 175610 [details]
Patch
Comment 5 WebKit Review Bot 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
Comment 6 Shinya Kawanaka 2012-11-25 18:26:20 PST 
It seems just a flake. Let me add cq+ again.
Comment 7 WebKit Review Bot 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>
Comment 8 WebKit Review Bot 2012-11-26 01:08:10 PST 
All reviewed patches have been landed.  Closing bug.