Do not cause unnecessary node lists invalidation on id/name attribute change

Do not cause unnecessary node lists invalidation on id/name attribute change

Do not cause unnecessary node lists invalidation on id/name attribute change.
Invalidation now occurs only if there are node lists with a *valid* id / name
cache.

I see a 12% speed up on Dromaeo's dom-attr test. This patch should fix the
performance regression by r166263, which made getElementsByTagName() return an
HTMLCollection instead of a NodeList. According to the profiler, the
performance impact is mainly due to node lists cache invalidation. This is
because HTMLCollection has an id / name cache, while NodeList doesn't.

This CL also improves the id / name cache API naming on HTMLCollection for
clarity.

R=abarth, adamk
BUG=340325
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=167115

[Inactive, 2014-02-11 13:59:23]

fast/dom/collection-nameditem-move-between-documents.html is failing in debug
mode. I will investigate and fix, sorry about that.

[Inactive, 2014-02-11 16:23:10]

On 2014/02/11 13:59:23, Chris Dumez wrote:
> fast/dom/collection-nameditem-move-between-documents.html is failing in debug
> mode. I will investigate and fix, sorry about that.

This is now fixed, PTAL.

[eseidel, 2014-02-12 01:55:24]

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/Document.h
File Source/core/dom/Document.h (right):

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/Documen...
Source/core/dom/Document.h:1384:
m_nodeListCounts[InvalidateOnIdNameAttrChange]++;
This seems about the same size as just keeping a list of the pointers.  I wonder
what the tradeoff would be there.

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
File Source/core/dom/NodeRareData.h (right):

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
Source/core/dom/NodeRareData.h:176: if (oldDocument == newDocument) {
Really?  This seems like an odd case?

[Inactive, 2014-02-12 02:21:41]

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/Document.h
File Source/core/dom/Document.h (right):

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/Documen...
Source/core/dom/Document.h:1384:
m_nodeListCounts[InvalidateOnIdNameAttrChange]++;
On 2014/02/12 01:55:24, eseidel wrote:
> This seems about the same size as just keeping a list of the pointers.  I
wonder
> what the tradeoff would be there.

You mean an array of linked lists (whose items would be LiveNodeListBase
pointers) instead of an array of integers? My worry is that this could grow to
use quite a bit more memory if we have more than one LiveNodeListBase per
invalidation type.

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/Documen...
Source/core/dom/Document.h:1389:
ASSERT(m_nodeListCounts[InvalidateOnIdNameAttrChange] > 0);
You mentioned having good assertions an IRC. There is this one to make sure we
don't decrement more than we should.

And there is a pre-existing assertion in the Document destructor to make sure we
decrement enough (i.e. No list is still registered when the document is
destroyed):
for (unsigned i = 0; i < WTF_ARRAY_LENGTH(m_nodeListCounts); i++)
        ASSERT(!m_nodeListCounts[i]);

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
File Source/core/dom/NodeRareData.h (right):

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
Source/core/dom/NodeRareData.h:176: if (oldDocument == newDocument) {
On 2014/02/12 01:55:24, eseidel wrote:
> Really?  This seems like an odd case?

Right, I need to check the callers to see if this actually happens, I kept the
condition because it was already there, I merely refactor the code to do an
early return.

[Inactive, 2014-02-12 02:38:47]

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
File Source/core/dom/NodeRareData.h (right):

https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
Source/core/dom/NodeRareData.h:176: if (oldDocument == newDocument) {
On 2014/02/12 02:21:41, Chris Dumez wrote:
> On 2014/02/12 01:55:24, eseidel wrote:
> > Really?  This seems like an odd case?
> 
> Right, I need to check the callers to see if this actually happens, I kept the
> condition because it was already there, I merely refactor the code to do an
> early return.

After a quick check, it looks like all the callers already make sure that
oldDocument is different than newDocument before calling this method. I will
address this in a separate CL.

[Inactive, 2014-02-12 14:12:02]

On 2014/02/12 02:38:47, Chris Dumez wrote:
>
https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
> File Source/core/dom/NodeRareData.h (right):
> 
>
https://codereview.chromium.org/159503003/diff/200001/Source/core/dom/NodeRar...
> Source/core/dom/NodeRareData.h:176: if (oldDocument == newDocument) {
> On 2014/02/12 02:21:41, Chris Dumez wrote:
> > On 2014/02/12 01:55:24, eseidel wrote:
> > > Really?  This seems like an odd case?
> > 
> > Right, I need to check the callers to see if this actually happens, I kept
the
> > condition because it was already there, I merely refactor the code to do an
> > early return.
> 
> After a quick check, it looks like all the callers already make sure that
> oldDocument is different than newDocument before calling this method. I will
> address this in a separate CL.

I rebased the patch now that https://codereview.chromium.org/159913004/ landed.
It makes this CL slightly smaller.

[Inactive, 2014-02-12 18:26:07]

Added some comments to clarify the reasoning behind my changes.

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/Documen...
File Source/core/dom/Document.cpp (left):

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/Documen...
Source/core/dom/Document.cpp:3563: if (list->hasIdNameCache())
We only want to cause invalidation if the NodeList has a *valid* id/name cache
so checking that the list can have an id/name cache when registering it is not
good enough.

We prefer to let the node list increment / decrement the document's
m_nodeListCounts[InvalidateOnIdNameAttrChange] when the id/name cache becomes
valid / invalidated.

This avoid iterating over all the node lists when an id or name attribute
changes and none of the HTMLCollections have a *valid* id/name cache.

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/LiveNod...
File Source/core/dom/LiveNodeList.cpp (right):

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/LiveNod...
Source/core/dom/LiveNodeList.cpp:40: invalidateCache(&oldDocument);
We need to pass the oldDocument to invalidateCache() because the node list has
already been moved to the newDocument (document() will return the newDocument)
and the node list needs to possible unregister its id/name cache from the
oldDocument.

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/NodeRar...
File Source/core/dom/NodeRareData.h (left):

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/NodeRar...
Source/core/dom/NodeRareData.h:177: invalidateCaches();
We no longer need this as LiveNodeListBase::didMoveToDocument() takes care of
invalidating the node list cache. This avoids iterating over the NodeLists twice
(once in invalidateCaches() and once in this method).

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/NodeRar...
File Source/core/dom/NodeRareData.h (right):

https://codereview.chromium.org/159503003/diff/290001/Source/core/dom/NodeRar...
Source/core/dom/NodeRareData.h:181: list->didMoveToDocument(oldDocument,
newDocument);
didMoveToDocument() invalidates the nodelist cache, unregisters it from the
oldDocument and registers it to the new Document.

I think it is cleaner to let the node list register / unregister itself from the
documents. The node list already takes care by itself of unregistering itself
from the Document.

https://codereview.chromium.org/159503003/diff/290001/Source/core/html/HTMLCo...
File Source/core/html/HTMLCollection.h (left):

https://codereview.chromium.org/159503003/diff/290001/Source/core/html/HTMLCo...
Source/core/html/HTMLCollection.h:73: bool hasNameCache() const { return
m_isNameCacheValid; }
Just a naming update to make it clear that:
- the cache contains both id and names.
- this returns true only if the id/name cache is *valid*.

This was confusing because LiveNodeListBase::hasIdNameCache() returns True if
the node list has an id/name cache, even if it is not valid.

[Inactive, 2014-02-13 18:59:06]

Any more feedback on this? I'd hate to go back to using NodeLists because of
this perf regression.

[eseidel, 2014-02-13 19:39:32]

lgtm

Sorry to be slow.

[commit-bot: I haz the power, 2014-02-13 19:39:43]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ch.dumez@samsung.com/159503003/290001

[commit-bot: I haz the power, 2014-02-13 19:39:47]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-02-13 19:39:48]

Failed to apply patch for Source/core/dom/LiveNodeList.cpp:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file Source/core/dom/LiveNodeList.cpp
  Hunk #1 FAILED at 35.
  1 out of 1 hunk FAILED -- saving rejects to file
Source/core/dom/LiveNodeList.cpp.rej

Patch:       Source/core/dom/LiveNodeList.cpp
Index: Source/core/dom/LiveNodeList.cpp
diff --git a/Source/core/dom/LiveNodeList.cpp b/Source/core/dom/LiveNodeList.cpp
index
08d9d86b82f384a48cdadda44e60c1f85896c474..1f51dcf09b098169db36dea823059ae1a42a1c06
100644
--- a/Source/core/dom/LiveNodeList.cpp
+++ b/Source/core/dom/LiveNodeList.cpp
@@ -35,13 +35,20 @@ ContainerNode& LiveNodeListBase::rootNode() const
     return *m_ownerNode;
 }
 
+void LiveNodeListBase::didMoveToDocument(Document& oldDocument, Document&
newDocument)
+{
+    invalidateCache(&oldDocument);
+    oldDocument.unregisterNodeList(this);
+    newDocument.registerNodeList(this);
+}
+
 void LiveNodeListBase::invalidateIdNameCacheMaps() const
 {
     ASSERT(hasIdNameCache());
     static_cast<const HTMLCollection*>(this)->invalidateIdNameCacheMaps();
 }
 
-void LiveNodeList::invalidateCache() const
+void LiveNodeList::invalidateCache(Document*) const
 {
     m_collectionIndexCache.invalidate();
 }

[Inactive, 2014-02-13 19:45:44]

On 2014/02/13 19:39:32, eseidel wrote:
> lgtm
> 
> Sorry to be slow.

Thanks, I know this sort of patch takes time to review.

[Inactive, 2014-02-13 19:55:27]

The CQ bit was checked by ch.dumez@samsung.com

[commit-bot: I haz the power, 2014-02-13 19:55:51]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ch.dumez@samsung.com/159503003/510001

[commit-bot: I haz the power, 2014-02-13 21:19:43]

Change committed as 167115