Bug 928403 - optimize nsFrameConstructorState::ProcessFrameInsertions, r=roc
authorOlli Pettay <Olli.Pettay@helsinki.fi>
Tue, 22 Oct 2013 15:06:01 +0300
changeset 165483 6bb23207bdbb299ed789d8bd5a812956feee57f5
parent 165482 b58ac61431bc20e0077e34b20e28a281302633b1
child 165484 82b31924a8bb8d730201ed0ea44abee89da0efda
push id3066
push userakeybl@mozilla.com
push dateMon, 09 Dec 2013 19:58:46 +0000
treeherdermozilla-beta@a31a0dce83aa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersroc
bugs928403
milestone27.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 928403 - optimize nsFrameConstructorState::ProcessFrameInsertions, r=roc
layout/base/nsCSSFrameConstructor.cpp
layout/base/nsLayoutUtils.cpp
layout/base/nsLayoutUtils.h
testing/mochitest/b2g.json
--- a/layout/base/nsCSSFrameConstructor.cpp
+++ b/layout/base/nsCSSFrameConstructor.cpp
@@ -1236,33 +1236,77 @@ nsFrameConstructorState::ProcessFrameIns
     // We need to make sure the 'append to the end of document' case is fast.
     // So first test the last child of the containing block
     nsIFrame* lastChild = childList.LastChild();
 
     // CompareTreePosition uses placeholder hierarchy for out of flow frames,
     // so this will make out-of-flows respect the ordering of placeholders,
     // which is great because it takes care of anonymous content.
     nsIFrame* firstNewFrame = aFrameItems.FirstChild();  
+
+    // Cache the ancestor chain so that we can reuse it if needed.
+    nsAutoTArray<nsIFrame*, 20> firstNewFrameAncestors;
+    nsIFrame* notCommonAncestor = nullptr;
+    if (lastChild) {
+      notCommonAncestor = nsLayoutUtils::FillAncestors(firstNewFrame,
+                                                       containingBlock,
+                                                       &firstNewFrameAncestors);
+    }
+
     if (!lastChild ||
-        nsLayoutUtils::CompareTreePosition(lastChild, firstNewFrame, containingBlock) < 0) {
+        nsLayoutUtils::CompareTreePosition(lastChild, firstNewFrame,
+                                           firstNewFrameAncestors,
+                                           notCommonAncestor ?
+                                             containingBlock : nullptr) < 0) {
       // no lastChild, or lastChild comes before the new children, so just append
       rv = mFrameManager->AppendFrames(containingBlock, aChildListID, aFrameItems);
     } else {
-      // try the other children
-      nsIFrame* insertionPoint = nullptr;
+      // Try the other children. First collect them to an array so that a
+      // reasonable fast binary search can be used to find the insertion point.
+      nsAutoTArray<nsIFrame*, 128> children;
       for (nsIFrame* f = childList.FirstChild(); f != lastChild;
            f = f->GetNextSibling()) {
+        children.AppendElement(f);
+      }
+
+      nsIFrame* insertionPoint = nullptr;
+      int32_t imin = 0;
+      int32_t max = children.Length();
+      while (max > imin) {
+        int32_t imid = imin + ((max - imin) / 2);
+        nsIFrame* f = children[imid];
         int32_t compare =
-          nsLayoutUtils::CompareTreePosition(f, firstNewFrame, containingBlock);
+          nsLayoutUtils::CompareTreePosition(f, firstNewFrame, firstNewFrameAncestors,
+                                             notCommonAncestor ? containingBlock : nullptr);
         if (compare > 0) {
-          // f comes after the new children, so stop here and insert after
-          // the previous frame
+          // f is after the new frame.
+          max = imid;
+          insertionPoint = imid > 0 ? children[imid - 1] : nullptr;
+        } else if (compare < 0) {
+          // f is before the new frame.
+          imin = imid + 1;
+          insertionPoint = f;
+        } else {
+          // This is for the old behavior. Should be removed once it is
+          // guaranteed that CompareTreePosition can't return 0!
+          // See bug 928645.
+          NS_WARNING("Something odd happening???");
+          insertionPoint = nullptr;
+          for (uint32_t i = 0; i < children.Length(); ++i) {
+            nsIFrame* f = children[i];
+            if (nsLayoutUtils::CompareTreePosition(f, firstNewFrame,
+                                                   firstNewFrameAncestors,
+                                                   notCommonAncestor ?
+                                                     containingBlock : nullptr) > 0) {
+              break;
+            }
+            insertionPoint = f;
+          }
           break;
         }
-        insertionPoint = f;
       }
       rv = mFrameManager->InsertFrames(containingBlock, aChildListID,
                                        insertionPoint, aFrameItems);
     }
   }
 
   NS_POSTCONDITION(aFrameItems.IsEmpty(), "How did that happen?");
 
--- a/layout/base/nsLayoutUtils.cpp
+++ b/layout/base/nsLayoutUtils.cpp
@@ -997,19 +997,21 @@ nsLayoutUtils::DoCompareTreePosition(nsI
   if (index1 < 0 || index2 < 0) {
     // one of them must be anonymous; we can't determine the order
     return 0;
   }
 
   return index1 - index2;
 }
 
-static nsIFrame* FillAncestors(nsIFrame* aFrame,
-                               nsIFrame* aStopAtAncestor,
-                               nsTArray<nsIFrame*>* aAncestors)
+// static
+nsIFrame*
+nsLayoutUtils::FillAncestors(nsIFrame* aFrame,
+                             nsIFrame* aStopAtAncestor,
+                             nsTArray<nsIFrame*>* aAncestors)
 {
   while (aFrame && aFrame != aStopAtAncestor) {
     aAncestors->AppendElement(aFrame);
     aFrame = nsLayoutUtils::GetParentOrPlaceholderFor(aFrame);
   }
   return aFrame;
 }
 
@@ -1031,42 +1033,56 @@ nsLayoutUtils::DoCompareTreePosition(nsI
                                      nsIFrame* aFrame2,
                                      int32_t aIf1Ancestor,
                                      int32_t aIf2Ancestor,
                                      nsIFrame* aCommonAncestor)
 {
   NS_PRECONDITION(aFrame1, "aFrame1 must not be null");
   NS_PRECONDITION(aFrame2, "aFrame2 must not be null");
 
+  nsAutoTArray<nsIFrame*,20> frame2Ancestors;
+  nsIFrame* nonCommonAncestor =
+    FillAncestors(aFrame2, aCommonAncestor, &frame2Ancestors);
+
+  return DoCompareTreePosition(aFrame1, aFrame2, frame2Ancestors,
+                               aIf1Ancestor, aIf2Ancestor,
+                               nonCommonAncestor ? aCommonAncestor : nullptr);
+}
+
+// static
+int32_t
+nsLayoutUtils::DoCompareTreePosition(nsIFrame* aFrame1,
+                                     nsIFrame* aFrame2,
+                                     nsTArray<nsIFrame*>& aFrame2Ancestors,
+                                     int32_t aIf1Ancestor,
+                                     int32_t aIf2Ancestor,
+                                     nsIFrame* aCommonAncestor)
+{
+  NS_PRECONDITION(aFrame1, "aFrame1 must not be null");
+  NS_PRECONDITION(aFrame2, "aFrame2 must not be null");
+
   nsPresContext* presContext = aFrame1->PresContext();
   if (presContext != aFrame2->PresContext()) {
     NS_ERROR("no common ancestor at all, different documents");
     return 0;
   }
 
   nsAutoTArray<nsIFrame*,20> frame1Ancestors;
-  if (!FillAncestors(aFrame1, aCommonAncestor, &frame1Ancestors)) {
+  if (aCommonAncestor &&
+      !FillAncestors(aFrame1, aCommonAncestor, &frame1Ancestors)) {
     // We reached the root of the frame tree ... if aCommonAncestor was set,
     // it is wrong
-    aCommonAncestor = nullptr;
-  }
-
-  nsAutoTArray<nsIFrame*,20> frame2Ancestors;
-  if (!FillAncestors(aFrame2, aCommonAncestor, &frame2Ancestors) &&
-      aCommonAncestor) {
-    // We reached the root of the frame tree ... aCommonAncestor was wrong.
-    // Try again with no hint.
     return DoCompareTreePosition(aFrame1, aFrame2,
                                  aIf1Ancestor, aIf2Ancestor, nullptr);
   }
 
   int32_t last1 = int32_t(frame1Ancestors.Length()) - 1;
-  int32_t last2 = int32_t(frame2Ancestors.Length()) - 1;
+  int32_t last2 = int32_t(aFrame2Ancestors.Length()) - 1;
   while (last1 >= 0 && last2 >= 0 &&
-         frame1Ancestors[last1] == frame2Ancestors[last2]) {
+         frame1Ancestors[last1] == aFrame2Ancestors[last2]) {
     last1--;
     last2--;
   }
 
   if (last1 < 0) {
     if (last2 < 0) {
       NS_ASSERTION(aFrame1 == aFrame2, "internal error?");
       return 0;
@@ -1076,17 +1092,17 @@ nsLayoutUtils::DoCompareTreePosition(nsI
   }
 
   if (last2 < 0) {
     // aFrame2 is an ancestor of aFrame1
     return aIf2Ancestor;
   }
 
   nsIFrame* ancestor1 = frame1Ancestors[last1];
-  nsIFrame* ancestor2 = frame2Ancestors[last2];
+  nsIFrame* ancestor2 = aFrame2Ancestors[last2];
   // Now we should be able to walk sibling chains to find which one is first
   if (IsFrameAfter(ancestor2, ancestor1))
     return -1;
   if (IsFrameAfter(ancestor1, ancestor2))
     return 1;
   NS_WARNING("Frames were in different child lists???");
   return 0;
 }
--- a/layout/base/nsLayoutUtils.h
+++ b/layout/base/nsLayoutUtils.h
@@ -258,28 +258,48 @@ public:
    */
   static int32_t CompareTreePosition(nsIFrame* aFrame1,
                                      nsIFrame* aFrame2,
                                      nsIFrame* aCommonAncestor = nullptr)
   {
     return DoCompareTreePosition(aFrame1, aFrame2, -1, 1, aCommonAncestor);
   }
 
+  static int32_t CompareTreePosition(nsIFrame* aFrame1,
+                                     nsIFrame* aFrame2,
+                                     nsTArray<nsIFrame*>& aFrame2Ancestors,
+                                     nsIFrame* aCommonAncestor = nullptr)
+  {
+    return DoCompareTreePosition(aFrame1, aFrame2, aFrame2Ancestors,
+                                 -1, 1, aCommonAncestor);
+  }
+
   /*
    * More generic version of |CompareTreePosition|.  |aIf1Ancestor|
    * gives the value to return when 1 is an ancestor of 2, and likewise
    * for |aIf2Ancestor|.  Passing (-1, 1) gives preorder traversal
    * order, and (1, -1) gives postorder traversal order.
    */
   static int32_t DoCompareTreePosition(nsIFrame* aFrame1,
                                        nsIFrame* aFrame2,
                                        int32_t aIf1Ancestor,
                                        int32_t aIf2Ancestor,
                                        nsIFrame* aCommonAncestor = nullptr);
 
+  static nsIFrame* FillAncestors(nsIFrame* aFrame,
+                                 nsIFrame* aStopAtAncestor,
+                                 nsTArray<nsIFrame*>* aAncestors);
+
+  static int32_t DoCompareTreePosition(nsIFrame* aFrame1,
+                                       nsIFrame* aFrame2,
+                                       nsTArray<nsIFrame*>& aFrame2Ancestors,
+                                       int32_t aIf1Ancestor,
+                                       int32_t aIf2Ancestor,
+                                       nsIFrame* aCommonAncestor);
+
   /**
    * LastContinuationWithChild gets the last continuation in aFrame's chain
    * that has a child, or the first continuation if the frame has no children.
    */
   static nsIFrame* LastContinuationWithChild(nsIFrame* aFrame);
 
   /**
    * GetLastSibling simply finds the last sibling of aFrame, or returns nullptr if