Bug 1350770: Cache the most recent nsGenConNode to speed up future insertions. r=xidorn
authorDavid Major <dmajor@mozilla.com>
Tue, 28 Mar 2017 10:04:48 -0400
changeset 350123 ae69e36301a0cb84d3d688e0d2657fc3a16297a2
parent 350122 ad9e2f221bbebff1e218f44d188ab4489d0278fa
child 350124 f474083089c365c601509fc1ef2517e1d18bb7ca
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() : mSize(0), mLastInserted(nullptr) {}
   ~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___ */