Bug 76003 – REGRESSION (r104210): WebProcess spins at 100% CPU for several minutes when loading an internal Apple site

• Component: DOM
• Status: RESOLVED FIXED

[Mark Rowe (bdash)]

After r104210 we're seeing WebProcess spin at 100% CPU for several minutes after loading pages on an internal Apple site. A sample shows that almost all of the time is being spent in DynamicSubtreeNodeList::length below calls to WebCore::JSNodeList::getOwnPropertySlotByIndex.  I'll attach a reduction that demonstrates the regression.

<rdar://problem/10672251>

[Mark Rowe (bdash)]

Created attachment 121927 [details]
Reduction (may hang your browser for 30+ seconds!)

This reduction demonstrates the issue. The iteration step took ~200ms pre-r104210 but now takes around 30 seconds.

[Ryosuke Niwa]

(In reply to comment #0)
> After r104210 we're seeing WebProcess spin at 100% CPU for several minutes after loading pages on an internal Apple site. A sample shows that almost all of the time is being spent in DynamicSubtreeNodeList::length below calls to WebCore::JSNodeList::getOwnPropertySlotByIndex.  I'll attach a reduction that demonstrates the regression.

According to my research people rarely modified DOM while hanging onto node list. This regression is the most pathological case where you're looping over node list and modifying DOM.

I suppose such code wasn't as unusual as I initially thought but you can get the same hang even before r104210 if you had modified the class name of any element inside the loop; e.g. element.className = 'hide';

[Ryosuke Niwa]

Oh man... JSNodeList::getOwnPropertySlotByIndex is always calling NodeList::length() before calling NodeList::item(). This would mean that we'll end up iterating through the entire subtree whenever we call DynamicSubtreeNodeList::item from JavaScript unless the length is cached :(

[Ryosuke Niwa]

Could you tell me what getOwnPropertySlotByIndex is doing and if there's way to avoid calling length there?

I'm guessing that we just need to verify that the specified index exists. Is that right? In that case, we can probably add new methods like isIndexValid(unsigned) that only looks for the specified index.

[Mark Rowe (bdash)]

Perhaps I'm missing something, but how would isIndexValid help? It seems as though you'd still have to walk over the subtree in order to return an answer.

[Oliver Hunt]

(In reply to comment #2)
> (In reply to comment #0)
> > After r104210 we're seeing WebProcess spin at 100% CPU for several minutes after loading pages on an internal Apple site. A sample shows that almost all of the time is being spent in DynamicSubtreeNodeList::length below calls to WebCore::JSNodeList::getOwnPropertySlotByIndex.  I'll attach a reduction that demonstrates the regression.
> 
> According to my research people rarely modified DOM while hanging onto node list. This regression is the most pathological case where you're looping over node list and modifying DOM.
> 
> I suppose such code wasn't as unusual as I initially thought but you can get the same hang even before r104210 if you had modified the class name of any element inside the loop; e.g. element.className = 'hide';

To me it seems like a fairly obvious pattern to get a nodelist and then iterate over that list modifying attributes.  This seems like a fairly significant reason for them to exist at all.

[Ryosuke Niwa]

Created attachment 121977 [details]
reduction for pre r104210

(In reply to comment #6)
> To me it seems like a fairly obvious pattern to get a nodelist and then iterate over that list modifying attributes.  This seems like a fairly significant reason for them to exist at all.

According to my study on the bug 73853, this accounts for less than 1% of the real world usage of node list API. Also this behavior existed prior to r104210 as well. You just need to touch the right attribute.

[Ryosuke Niwa]

If we want to optimize for this case and keep caches as long as we can, then we should completely abandon (revert) the approach took in r104263.

[Mark Rowe (bdash)]

I don't agree with your retitling of this bug. It hides the most important fact here: that the change in r104210 broke a real-world website.

[Ryosuke Niwa]

(In reply to comment #9)
> I don't agree with your retitling of this bug. It hides the most important fact here: that the change in r104210 broke a real-world website.

I knew I was regressing the performance on some websites as a trade off, and the example I gave here demonstrates that the same behavior can be replicated prior to r104210. I don't think I need to demonstrate the fact some websites would be hitting the case I posted.

[Ryosuke Niwa]

(In reply to comment #5)
> Perhaps I'm missing something, but how would isIndexValid help? It seems as though you'd still have to walk over the subtree in order to return an answer.

At least then we wouldn't have to traverse through the entire subtree on every iteration of the loop.

[Mark Rowe (bdash)]

(In reply to comment #10)
> (In reply to comment #9)
> > I don't agree with your retitling of this bug. It hides the most important fact here: that the change in r104210 broke a real-world website.
> 
> I knew I was regressing the performance on some websites as a trade off, and the example I gave here demonstrates that the same behavior can be replicated prior to r104210. I don't think I need to demonstrate the fact some websites would be hitting the case I posted.

Existing websites are much less likely to be doing something along the lines of your posted example because it already had terrible performance in shipping versions of WebKit. Existing websites could easily be doing something along the lines of the reduction because until r104210 it was sufficiently fast.

When your trade-off makes code that formerly ran in O(N) time now run in O(N ** 2) time, perhaps it's not the right one.

[Ryosuke Niwa]

(In reply to comment #12)
> Existing websites are much less likely to be doing something along the lines of your posted example because it already had terrible performance in shipping versions of WebKit. Existing websites could easily be doing something along the lines of the reduction because until r104210 it was sufficiently fast.
>
> When your trade-off makes code that formerly ran in O(N) time now run in O(N ** 2) time, perhaps it's not the right one.

I completely disagree with either one of your points but I'm rolling out r104210 anyway to improve the node lists performance.

[Ryosuke Niwa]

Comment on attachment 121927 [details]
Reduction (may hang your browser for 30+ seconds!)

Now that the patch has been rolled out in http://trac.webkit.org/changeset/104674, this reduction is obsolete.

[Mark Rowe (bdash)]

Thanks for fixing this issue.