Bug 1350770: Cache the most recent nsGenConNode to speed up future insertions. r=xidorn
☠☠ backed out by e0b2e9f5bc10 ☠ ☠
authorDavid Major <dmajor@mozilla.com>
Tue, 28 Mar 2017 09:38:07 -0400
changeset 350120 5544a84d59a4f6ce76dc269a20b94afa6c171976
parent 350119 87ac6abe1de2828da6a1fe85c6a0e85b857479e7
child 350121 e0b2e9f5bc107854995ee76042453eb44b1e4919
push id31568
push userkwierso@gmail.com
push dateTue, 28 Mar 2017 20:31:07 +0000
treeherdermozilla-central@272ce6c25721 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersxidorn
bugs1350770
milestone55.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1350770: Cache the most recent nsGenConNode to speed up future insertions. r=xidorn
layout/base/nsGenConList.cpp
layout/base/nsGenConList.h
--- a/layout/base/nsGenConList.cpp
+++ b/layout/base/nsGenConList.cpp
@@ -14,16 +14,17 @@ void
 nsGenConList::Clear()
 {
   // Delete entire list.
   mNodes.Clear();
   while (nsGenConNode* node = mList.popFirst()) {
     delete node;
   }
   mSize = 0;
+  mLastInserted = nullptr;
 }
 
 bool
 nsGenConList::DestroyNodesFor(nsIFrame* aFrame)
 {
   // This algorithm relies on the invariant that nodes of a frame are
   // put contiguously in the linked list. This is guaranteed because
   // each frame is mapped to only one (nsIContent, pseudoType) pair,
@@ -36,16 +37,19 @@ nsGenConList::DestroyNodesFor(nsIFrame* 
   MOZ_ASSERT(node->mPseudoFrame == aFrame);
 
   while (node && node->mPseudoFrame == aFrame) {
     nsGenConNode* nextNode = Next(node);
     Destroy(node);
     node = nextNode;
   }
 
+  // Modification of the list invalidates the cached pointer.
+  mLastInserted = nullptr;
+
   return true;
 }
 
 /**
  * Compute the type of the pseudo and the content for the pseudo that
  * we'll use for comparison purposes.
  * @param aContent the content to use is stored here; it's the element
  * that generated the ::before or ::after content, or (if not for generated
@@ -103,16 +107,21 @@ nsGenConList::NodeAfter(const nsGenConNo
 }
 
 void
 nsGenConList::Insert(nsGenConNode* aNode)
 {
   // Check for append.
   if (mList.isEmpty() || NodeAfter(aNode, mList.getLast())) {
     mList.insertBack(aNode);
+  } else if (mLastInserted && mLastInserted != mList.getLast() &&
+             NodeAfter(aNode, mLastInserted) &&
+             NodeAfter(Next(mLastInserted), aNode)) {
+    // Fast path for inserting many consecutive nodes in one place
+    mLastInserted->setNext(aNode);
   } else {
     // Binary search.
 
     // the range of indices at which |aNode| could end up.
     // (We already know it can't be at index mSize.)
     uint32_t first = 0, last = mSize - 1;
 
     // A cursor to avoid walking more than the length of the list.
@@ -137,16 +146,18 @@ nsGenConList::Insert(nsGenConNode* aNode
       } else {
         last = test;
       }
     }
     curNode->setPrevious(aNode);
   }
   ++mSize;
 
+  mLastInserted = aNode;
+
   // Set the mapping only if it is the first node of the frame.
   // The DEBUG blocks below are for ensuring the invariant required by
   // nsGenConList::DestroyNodesFor. See comment there.
   if (IsFirst(aNode) ||
       Prev(aNode)->mPseudoFrame != aNode->mPseudoFrame) {
 #ifdef DEBUG
     if (nsGenConNode* oldFrameFirstNode = mNodes.Get(aNode->mPseudoFrame)) {
       MOZ_ASSERT(Next(aNode) == oldFrameFirstNode,
--- a/layout/base/nsGenConList.h
+++ b/layout/base/nsGenConList.h
@@ -81,17 +81,17 @@ protected:
 };
 
 class nsGenConList {
 protected:
   mozilla::LinkedList<nsGenConNode> mList;
   uint32_t mSize;
 
 public:
-  nsGenConList() : mSize(0) {}
+  nsGenConList() : mLastInserted(nullptr), mSize(0) {}
   ~nsGenConList() { Clear(); }
   void Clear();
   static nsGenConNode* Next(nsGenConNode* aNode) {
     MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
     return aNode->getNext();
   }
   static nsGenConNode* Prev(nsGenConNode* aNode) {
     MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
@@ -122,11 +122,15 @@ private:
   {
     MOZ_ASSERT(aNode, "aNode cannot be nullptr!");
     delete aNode;
     mSize--;
   }
 
   // Map from frame to the first nsGenConNode of it in the list.
   nsDataHashtable<nsPtrHashKey<nsIFrame>, nsGenConNode*> mNodes;
+
+  // A weak pointer to the node most recently inserted, used to avoid repeated
+  // list traversals in Insert().
+  nsGenConNode* mLastInserted;
 };
 
 #endif /* nsGenConList_h___ */