Bug 103017 - [Shadow] Attaching children of a shadow host takes O(N^2) where N is the number of host children
Summary: [Shadow] Attaching children of a shadow host takes O(N^2) where N is the numb...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Shinya Kawanaka
URL:
Keywords:
Depends on:
Blocks: 103016
  Show dependency tree / graph
 
Reported: 2012-11-21 21:44 PST by Shinya Kawanaka
Modified: 2012-11-26 01:08 PST (History)
4 users (show)

See Also:

Attachments
Patch (4.55 KB, patch)
2012-11-22 00:40 PST, Shinya Kawanaka 		no flags Details | Formatted Diff | Diff
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
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.