Bug 1201692. Add a fast path to ExplicitChildIterator::Seek for the common case of seeking an actual DOM child of the parent node. r=wchen
authorBoris Zbarsky <bzbarsky@mit.edu>
Tue, 08 Sep 2015 21:23:55 -0400
changeset 261469 a1e45a92a376
parent 261468 947d0307ed77
child 261470 06038b476e9b
push id29345
push usercbook@mozilla.com
push date2015-09-09 12:06 +0000
treeherdermozilla-central@dd9e40b46959 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerswchen
bugs1201692
milestone43.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 1201692. Add a fast path to ExplicitChildIterator::Seek for the common case of seeking an actual DOM child of the parent node. r=wchen
dom/base/ChildIterator.cpp
dom/base/ChildIterator.h
dom/base/ShadowRoot.cpp
--- a/dom/base/ChildIterator.cpp
+++ b/dom/base/ChildIterator.cpp
@@ -185,16 +185,40 @@ FlattenedChildIterator::Init(bool aIgnor
         MOZ_ASSERT(child->GetBindingParent());
         mXBLInvolved = true;
         break;
       }
     }
   }
 }
 
+void
+ExplicitChildIterator::Seek(nsIContent* aChildToFind)
+{
+  if (aChildToFind->GetParent() == mParent &&
+      !aChildToFind->IsRootOfAnonymousSubtree()) {
+    // Fast path: just point ourselves to aChildToFind, which is a
+    // normal DOM child of ours.
+    MOZ_ASSERT(!ShadowRoot::IsShadowInsertionPoint(aChildToFind));
+    MOZ_ASSERT(!nsContentUtils::IsContentInsertionPoint(aChildToFind));
+    mChild = aChildToFind;
+    mIndexInInserted = 0;
+    mShadowIterator = nullptr;
+    mDefaultChild = nullptr;
+    mIsFirst = false;
+    return;
+  }
+
+  // Can we add more fast paths here based on whether the parent of aChildToFind
+  // is a shadow insertion point or content insertion point?
+
+  // Slow path: just walk all our kids.
+  Seek(aChildToFind, nullptr);
+}
+
 nsIContent*
 ExplicitChildIterator::Get()
 {
   MOZ_ASSERT(!mIsFirst);
 
   if (mIndexInInserted) {
     MatchedNodes assignedChildren = GetMatchedNodesForPoint(mChild);
     return assignedChildren[mIndexInInserted - 1];
--- a/dom/base/ChildIterator.h
+++ b/dom/base/ChildIterator.h
@@ -55,26 +55,34 @@ public:
   ExplicitChildIterator(ExplicitChildIterator&& aOther)
     : mParent(aOther.mParent), mChild(aOther.mChild),
       mDefaultChild(aOther.mDefaultChild),
       mShadowIterator(Move(aOther.mShadowIterator)),
       mIndexInInserted(aOther.mIndexInInserted), mIsFirst(aOther.mIsFirst) {}
 
   nsIContent* GetNextChild();
 
-  // Looks for aChildToFind respecting insertion points until aChildToFind
+  // Looks for aChildToFind respecting insertion points until aChildToFind is
+  // found.  This version can take shortcuts that the two-argument version
+  // can't, so can be faster (and in fact can be O(1) instead of O(N) in many
+  // cases).
+  void Seek(nsIContent* aChildToFind);
+
+  // Looks for aChildToFind respecting insertion points until aChildToFind is found.
   // or aBound is found. If aBound is nullptr then the seek is unbounded. Returns
   // whether aChildToFind was found as an explicit child prior to encountering
   // aBound.
-  bool Seek(nsIContent* aChildToFind, nsIContent* aBound = nullptr)
+  bool Seek(nsIContent* aChildToFind, nsIContent* aBound)
   {
     // It would be nice to assert that we find aChildToFind, but bz thinks that
     // we might not find aChildToFind when called from ContentInserted
     // if first-letter frames are about.
 
+    // We can't easily take shortcuts here because we'd have to have a way to
+    // compare aChildToFind to aBound.
     nsIContent* child;
     do {
       child = GetNextChild();
     } while (child && child != aChildToFind && child != aBound);
 
     return child == aChildToFind;
   }
 
--- a/dom/base/ShadowRoot.cpp
+++ b/dom/base/ShadowRoot.cpp
@@ -311,17 +311,17 @@ ShadowRoot::DistributeSingleNode(nsICont
         isIndexFound = true;
         break;
       }
     }
 
     if (!isIndexFound) {
       // We have still not found an index in the insertion point,
       // thus it must be at the end.
-      MOZ_ASSERT(childIterator.Seek(aContent),
+      MOZ_ASSERT(childIterator.Seek(aContent, nullptr),
                  "Trying to match a node that is not a candidate to be matched");
       insertionPoint->AppendMatchedNode(aContent);
     }
 
     // Handle the case where the parent of the insertion point is a ShadowRoot
     // that is projected into the younger ShadowRoot's shadow insertion point.
     // The node distributed into the insertion point must be reprojected
     // to the shadow insertion point.