Bug 61268 - REGRESSION (r45620): Node list caches never deleted
Summary: REGRESSION (r45620): Node list caches never deleted
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: DOM (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2011-05-23 02:51 PDT by Antti Koivisto
Modified: 2011-05-24 07:48 PDT (History)
2 users (show)

See Also:


Attachments
patch (6.66 KB, patch)
2011-05-23 13:03 PDT, Antti Koivisto
oliver: review+
Details | Formatted Diff | Diff
perf test (1.57 KB, text/html)
2011-05-23 13:46 PDT, Antti Koivisto
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description Antti Koivisto 2011-05-23 02:51:21 PDT
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.
Comment 1 Antti Koivisto 2011-05-23 12:45:12 PDT
<rdar://problem/9467379>
Comment 2 Antti Koivisto 2011-05-23 13:03:24 PDT
Created attachment 94468 [details]
patch
Comment 3 Oliver Hunt 2011-05-23 13:09:52 PDT
Comment on attachment 94468 [details]
patch

r=me
Comment 4 Darin Adler 2011-05-23 13:16:38 PDT
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?
Comment 5 Antti Koivisto 2011-05-23 13:37:24 PDT
(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.
Comment 6 Antti Koivisto 2011-05-23 13:46:32 PDT
Created attachment 94480 [details]
perf test
Comment 7 Antti Koivisto 2011-05-24 07:48:53 PDT
http://trac.webkit.org/changeset/87147