Bug 91306 – Iterating backwards over HTMLCollection is O(n^2)

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[Ryosuke Niwa]

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.

[Ryosuke Niwa]

Created attachment 152400 [details]
Fixes the bug

[Ryosuke Niwa]

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?

[Ryosuke Niwa]

Created attachment 152402 [details]
Fixed a bug

[Ryosuke Niwa]

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.

[Ryosuke Niwa]

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.

[Ojan Vafai]

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?

[Anders Carlsson]

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 ...

[Ryosuke Niwa]

Committed r122660: <http://trac.webkit.org/changeset/122660>

[Ryosuke Niwa]

(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.

[Ojan Vafai]

(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.

[Ryosuke Niwa]

(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.

[Ojan Vafai]

(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.

[Ryosuke Niwa]

(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.