Move caching out of LiveNodeListBase and into a new CollectionIndexCache class

Move caching out of LiveNodeListBase and into a new CollectionIndexCache class.

This improves Bindings/node-list-access.html's score by 4-5% on my Linux
desktop. This is due to CollectionIndexCache being templated, which gets rid of
isLiveNodeListType() branches in hot code paths.

Further separation between LiveNodeList / HTMLCollection can be done but I kept
this patch minimal to facilitate review.

This patch is based on WebKit r158758 by <antti@apple.com>;.

R=adamk, esprehn

Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=166261

[Inactive, 2014-01-25 02:40:49]

Second attempt, this time I kept the change as minimal as possible by not
splitting HTMLCollection / LiveNodeList / LiveNodeListBase.

[Inactive, 2014-01-29 13:56:37]

On 2014/01/25 02:40:49, Chris Dumez wrote:
> Second attempt, this time I kept the change as minimal as possible by not
> splitting HTMLCollection / LiveNodeList / LiveNodeListBase.

Could you please review when you get a chance? I have several patches pending
depending on this one.

[adamk, 2014-01-29 16:57:00]

lgtm, but I'd really like esprehn's OK too as 1) I'm not as familiar with this
LiveNodeList code and 2) he originally asked for the patch to be split.

[Inactive, 2014-01-29 20:13:43]

On 2014/01/29 16:57:00, adamk wrote:
> lgtm, but I'd really like esprehn's OK too as 1) I'm not as familiar with this
> LiveNodeList code and 2) he originally asked for the patch to be split.

Ok thanks. I'll let Esprehn take a look.

[esprehn, 2014-01-30 05:19:59]

lgtm, I'll admit I don't entirely understand all this stuff does, but it seems
reasonable.

Why couldn't we just templatize LiveNodeListBase tough?

[Inactive, 2014-01-30 20:18:20]

On 2014/01/30 05:19:59, esprehn wrote:
> lgtm, I'll admit I don't entirely understand all this stuff does, but it seems
> reasonable.
> 
> Why couldn't we just templatize LiveNodeListBase tough?

Wouldn't this create a circular dependency? HTMLCollection would inherit
LiveNodeListBase<HTMLCollection> and LiveNodeList would inherit
LiveNodeListBase<LiveNodeList>. LiveNodeListBase for start depending on
HTMLCollection / LiveNodeListBase and vice-versa.

In any case I do prefer the approach in this patch because:
1. If we templatize LiveNodeListBase, we no longer have a common base type for
HTMLCollection and LiveNodeList. One would have LiveNodeListBase<HTMLCollection>
as parent and the other LiveNodeListBase<LiveNodeList>. We currently rely on
HTMLCollection / LiveNodeList having a common base type in the rest of the code,
for example for caching / cache invalidation (in NodeRareData.h).
2. The idea is also to move the Node/Index caching out of LiveNodeListBase to
decrease the complexity of this code.

[Inactive, 2014-01-31 22:38:45]

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

[commit-bot: I haz the power, 2014-01-31 22:38:55]

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

[commit-bot: I haz the power, 2014-01-31 22:38:57]

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

[commit-bot: I haz the power, 2014-01-31 22:38:58]

Failed to apply patch for Source/core/html/HTMLCollection.h:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file Source/core/html/HTMLCollection.h
  Hunk #1 FAILED at 38.
  1 out of 2 hunks FAILED -- saving rejects to file
Source/core/html/HTMLCollection.h.rej

Patch:       Source/core/html/HTMLCollection.h
Index: Source/core/html/HTMLCollection.h
diff --git a/Source/core/html/HTMLCollection.h
b/Source/core/html/HTMLCollection.h
index
077bf2acb0ac13b360e72a4d8ebcee61939c86b7..591b51e71bc202e7ee86c9ea8125649208bb00ff
100644
--- a/Source/core/html/HTMLCollection.h
+++ b/Source/core/html/HTMLCollection.h
@@ -38,31 +38,20 @@ public:
     virtual void invalidateCache() const OVERRIDE;
 
     // DOM API
+    unsigned length() const { return m_collectionIndexCache.nodeCount(*this); }
+    Node* item(unsigned offset) const { return
m_collectionIndexCache.nodeAt(*this, offset); }
     virtual Node* namedItem(const AtomicString& name) const;
 
     // Non-DOM API
     void namedItems(const AtomicString& name, Vector<RefPtr<Node> >&) const;
-    bool isEmpty() const
-    {
-        if (isLengthCacheValid())
-            return !cachedLength();
-        if (cachedItem())
-            return false;
-        return !item(0);
-    }
-    bool hasExactlyOneItem() const
-    {
-        if (isLengthCacheValid())
-            return cachedLength() == 1;
-        if (cachedItem())
-            return !cachedItemOffset() && !item(1);
-        return item(0) && !item(1);
-    }
+    bool isEmpty() const { return m_collectionIndexCache.isEmpty(*this); }
+    bool hasExactlyOneItem() const { return
m_collectionIndexCache.hasExactlyOneNode(*this); }
 
     virtual Element* virtualItemAfter(Element*) const;
 
+    // CollectionIndexCache API.
     Element* traverseToFirstElement(const ContainerNode& root) const;
-    Element* traverseForwardToOffset(unsigned offset, Element& currentElement,
unsigned& currentOffset, const ContainerNode& root) const;
+    Element* traverseForwardToOffset(unsigned offset, Node& currentElement,
unsigned& currentOffset, const ContainerNode& root) const;
 
 protected:
     HTMLCollection(ContainerNode* base, CollectionType, ItemAfterOverrideType);
@@ -92,6 +81,7 @@ private:
     mutable unsigned m_isNameCacheValid : 1;
     mutable NodeCacheMap m_idCache;
     mutable NodeCacheMap m_nameCache;
+    mutable CollectionIndexCache<HTMLCollection> m_collectionIndexCache;
 
     friend class LiveNodeListBase;
 };

[commit-bot: I haz the power, 2014-01-31 22:39:03]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-01-31 22:39:03]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-01-31 22:39:06]

CQ bit was unchecked on CL. Ignoring.

[Inactive, 2014-01-31 23:41:43]

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

[commit-bot: I haz the power, 2014-01-31 23:42:06]

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

[commit-bot: I haz the power, 2014-02-01 01:36:15]

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

[commit-bot: I haz the power, 2014-02-01 01:36:15]

Retried try job too often on linux_blink for step(s) webkit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=linux_blin...

[commit-bot: I haz the power, 2014-02-01 01:36:21]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-02-01 01:36:22]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-02-01 01:36:25]

CQ bit was unchecked on CL. Ignoring.

[Inactive, 2014-02-01 01:37:59]

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

[commit-bot: I haz the power, 2014-02-01 01:38:29]

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

[commit-bot: I haz the power, 2014-02-01 02:58:31]

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

[commit-bot: I haz the power, 2014-02-01 02:58:32]

Retried try job too often on linux_blink for step(s) webkit_tests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=linux_blin...

[commit-bot: I haz the power, 2014-02-01 02:58:32]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-02-01 02:58:34]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-02-01 02:58:35]

CQ bit was unchecked on CL. Ignoring.

[Inactive, 2014-02-01 21:03:00]

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

[commit-bot: I haz the power, 2014-02-01 21:03:12]

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

[commit-bot: I haz the power, 2014-02-01 21:54:35]

Change committed as 166261

[commit-bot: I haz the power, 2014-02-01 21:54:39]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-02-01 21:54:39]

CQ bit was unchecked on CL. Ignoring.

[commit-bot: I haz the power, 2014-02-01 21:54:41]

CQ bit was unchecked on CL. Ignoring.