Bug 91306

Summary: Iterating backwards over HTMLCollection is O(n^2)
Product: WebKit Reporter: Ryosuke Niwa <rniwa>
Component: DOMAssignee: Ryosuke Niwa <rniwa>
Status: RESOLVED FIXED    
Severity: Normal CC: darin, haraken, kling, koivisto, ojan, sam
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 89919, 91320, 91334    
Attachments:
Description Flags
Fixes the bug
none
Fixed a bug
andersca: review+
demo none

Description Ryosuke Niwa 2012-07-13 19:05:16 PDT
Code like this:

var children = container.children;
for (var i = children.length; i > 0;i--)
    children[i - 1].class = 'hi';

exhibit O(n^2) behavior.
Comment 1 Ryosuke Niwa 2012-07-13 19:37:12 PDT
Created attachment 152400 [details]
Fixes the bug
Comment 2 Ryosuke Niwa 2012-07-13 19:49:51 PDT
Comment on attachment 152400 [details]
Fixes the bug

View in context: https://bugs.webkit.org/attachment.cgi?id=152400&action=review

> Source/WebCore/html/HTMLCollection.cpp:245
> +    return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traverseNextNode(base);

Oops, this won't fly, will it?
Comment 3 Ryosuke Niwa 2012-07-13 19:50:29 PDT
Created attachment 152402 [details]
Fixed a bug
Comment 4 Ryosuke Niwa 2012-07-13 19:51:27 PDT
Created attachment 152403 [details]
demo

Open it on Safari/Chrome without my patch. It'll take 4s or so to run. With my patch, it takes 5ms.
Comment 5 Ryosuke Niwa 2012-07-13 21:01:49 PDT
Comment on attachment 152402 [details]
Fixed a bug

View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review

> Source/WebCore/html/HTMLCollection.cpp:321
> -    if (!isItemCacheValid() || cachedItemOffset() > index) {
> +    if (shouldSearchFromFirstItem(offset)) {

Now, there's one more optimization we can implement when the length cache is available
and the distance to the last item is less than the distance to the cached item but we can implement
that optimization in a follow up patch instead.
Comment 6 Ojan Vafai 2012-07-13 23:21:18 PDT
Comment on attachment 152402 [details]
Fixed a bug

View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review

> Source/WebCore/html/HTMLCollection.cpp:240
> +template<bool forward>

Why use templates here and below instead of just adding an extra argument to nextNode and to itemBeforeOrAfter?
Comment 7 Anders Carlsson 2012-07-14 00:01:22 PDT
Comment on attachment 152402 [details]
Fixed a bug

View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review

> Source/WebCore/html/HTMLCollection.cpp:245
> +    if (forward)
> +        return onlyIncludeDirectChildren ? previous->nextSibling() : previous->traverseNextNode(base);
> +    return onlyIncludeDirectChildren ? previous->previousSibling() : previous->traversePreviousNode(base);

This is one of the cases where i prefer

if (forward)
    return ...
else
    return ...
Comment 8 Ryosuke Niwa 2012-07-14 00:09:02 PDT
Committed r122660: <http://trac.webkit.org/changeset/122660>
Comment 9 Ryosuke Niwa 2012-07-14 00:29:16 PDT
(In reply to comment #6)
> (From update of attachment 152402 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review
> 
> > Source/WebCore/html/HTMLCollection.cpp:240
> > +template<bool forward>
> 
> Why use templates here and below instead of just adding an extra argument to nextNode and to itemBeforeOrAfter?

I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward.
Comment 10 Ojan Vafai 2012-07-14 09:11:17 PDT
(In reply to comment #9)
> (In reply to comment #6)
> > (From update of attachment 152402 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=152402&action=review
> > 
> > > Source/WebCore/html/HTMLCollection.cpp:240
> > > +template<bool forward>
> > 
> > Why use templates here and below instead of just adding an extra argument to nextNode and to itemBeforeOrAfter?
> 
> I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward.

This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated.
Comment 11 Ryosuke Niwa 2012-07-14 11:31:20 PDT
(In reply to comment #10)
> (In reply to comment #9)
> > I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward.
> 
> This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated.

The last time we profiled DynamicNodeList, the equivalent code was very performance critical so much so that that was one of very few places where inlining traverseNextNode and traversePreviousNode would have benefited us. While adding a function call here may not show up as a statistically significant slow own by itself, these tiny cost adds up and gradually slow us down.
Comment 12 Ojan Vafai 2012-07-15 09:46:02 PDT
(In reply to comment #11)
> (In reply to comment #10)
> > (In reply to comment #9)
> > > I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward.
> > 
> > This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated.
> 
> The last time we profiled DynamicNodeList, the equivalent code was very performance critical so much so that that was one of very few places where inlining traverseNextNode and traversePreviousNode would have benefited us. While adding a function call here may not show up as a statistically significant slow own by itself, these tiny cost adds up and gradually slow us down.

I don't understand this last sentence. If it slows us down enough to matter, it should show up in benchmarks or profiles. This is a different case than something like ref/deref where the cost is scattered throughout the entire codebase and thus would never show up in a profile (although, it does show up in benchmarks!). When the cost is all in a single loop (on the javascript side), you should be able to see something significant. I'm pretty sure dromaeo benchmarks hammer this code pretty hard.

I believe you that this code is performance critical, I just don't think we should complicate the code in places where we haven't proven that it matters.
Comment 13 Ryosuke Niwa 2012-07-15 18:36:40 PDT
(In reply to comment #12)
> (In reply to comment #11)
> > (In reply to comment #10)
> > > (In reply to comment #9)
> > > > I was afraid that compilers are actually going to create nextNode and itemBeforeOrAfter instead of inlining them and constant-propagete the value of forward.
> > > 
> > > This sounds like a premature optimization to me. Unless you actually see an improvement on a benchmark or real website, I don't think this is worth making the code more complicated.
> > 
> > The last time we profiled DynamicNodeList, the equivalent code was very performance critical so much so that that was one of very few places where inlining traverseNextNode and traversePreviousNode would have benefited us. While adding a function call here may not show up as a statistically significant slow own by itself, these tiny cost adds up and gradually slow us down.
> 
> I don't understand this last sentence. If it slows us down enough to matter, it should show up in benchmarks or profiles. 

The equivalent code in DynamicNodeList shows up in profile result on Dromaeo.

> This is a different case than something like ref/deref where the cost is scattered throughout the entire codebase and thus would never show up in a profile (although, it does show up in benchmarks!).

It's exactly like that. Adding a single function call is usually cheap but if you keep adding lots of function calls, then it'll eventually slow us down.