Bug 61268 – REGRESSION (r45620): Node list caches never deleted

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

[Antti Koivisto]

We have

struct NodeListsNodeData {
...
    RefPtr<DynamicNodeList::Caches> m_childNodeListCaches;
...

and

bool NodeListsNodeData::isEmpty() const
{
...
    if (m_childNodeListCaches->refCount())
        return false;
...

The condition is always true and as a result node list caches are never empty and so never destroyed. This is bad for DOM modification performance as maintaing the caches is costly.

[Antti Koivisto]

<rdar://problem/9467379>

[Antti Koivisto]

Created attachment 94468 [details]
patch

[Oliver Hunt]

Comment on attachment 94468 [details]
patch

r=me

[Darin Adler]

Comment on attachment 94468 [details]
patch

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

How did you test? A while ago Ojan(?) added a harness that could be used for performance tests to prove operations didn’t have an O(n^2) component or something along those lines. Did you check into adding a test using that machinery? I’d like to see at least a manual test.

> Source/WebCore/dom/Node.cpp:1041
> +void Node::clearNodeListsIfPossible()

I think this name is confusing. While the function is called “clear node lists”, it does’t actually clear any node lists. In fact it only does work at all when there are no node lists!

> Source/WebCore/dom/Node.cpp:1047
> +    NodeRareData* data = rareData();
> +    if (!data->nodeLists()->isEmpty())
> +        return;

Might be nice to inline this part of the function so the common case doesn’t require another level of function call overhead. But maybe not.

> Source/WebCore/dom/Node.cpp:2540
> +            m_childNodeListCaches.clear();

Can this cause another kind of churn as the caches object is deleted and recreated?

[Antti Koivisto]

(In reply to comment #4)
> (From update of attachment 94468 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=94468&action=review
> 
> How did you test? A while ago Ojan(?) added a harness that could be used for performance tests to prove operations didn’t have an O(n^2) component or something along those lines. Did you check into adding a test using that machinery? I’d like to see at least a manual test.

I checked it fixed the problem in gdb and with a manual performance test case (attached). This is not really O(n^2), more like 2x, but I'll check the harness.

> > Source/WebCore/dom/Node.cpp:1041
> > +void Node::clearNodeListsIfPossible()
> 
> I think this name is confusing. While the function is called “clear node lists”, it does’t actually clear any node lists. In fact it only does work at all when there are no node lists!

This is somewhat consistent with the existing naming (calls RareData::clearNodeLists()). The could certainly use wider renaming.

(It could also use a lot more optimization. The whole thing is pretty primitive.)

> > Source/WebCore/dom/Node.cpp:1047
> > +    NodeRareData* data = rareData();
> > +    if (!data->nodeLists()->isEmpty())
> > +        return;
> 
> Might be nice to inline this part of the function so the common case doesn’t require another level of function call overhead. But maybe not.

True. I'll do that.
 
> > Source/WebCore/dom/Node.cpp:2540
> > +            m_childNodeListCaches.clear();
> 
> Can this cause another kind of churn as the caches object is deleted and recreated?

I don't think so. Only thing that is actually cached is the last index and the corresponding node. Reconstructing the cache vs. starting with invalidated cache should have little actual cost difference.

[Antti Koivisto]

Created attachment 94480 [details]
perf test

[Antti Koivisto]

http://trac.webkit.org/changeset/87147