Bug 1554461 - Use an array to store nsContinuationStates when the number of them is low. r=jfkthame
authorCameron McCormack <cam@mcc.id.au>
Fri, 31 May 2019 11:42:42 +0000
changeset 476484 fe12bde5e16bd1e0cfd0dd2edcc998c6edc6f557
parent 476483 4f56db8e65a66117845de2276a1ce77e060ea9cd
child 476485 0d0bf5d84a3cb5852047338e8f2e020e1a9b1b62
push id36095
push userdvarga@mozilla.com
push dateSat, 01 Jun 2019 09:40:47 +0000
treeherdermozilla-central@219a897031a3 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjfkthame
bugs1554461
milestone69.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 1554461 - Use an array to store nsContinuationStates when the number of them is low. r=jfkthame Differential Revision: https://phabricator.services.mozilla.com/D32617
layout/base/nsBidiPresUtils.cpp
layout/base/nsBidiPresUtils.h
--- a/layout/base/nsBidiPresUtils.cpp
+++ b/layout/base/nsBidiPresUtils.cpp
@@ -1351,33 +1351,34 @@ nsBidiLevel nsBidiPresUtils::GetFrameEmb
 nsBidiLevel nsBidiPresUtils::GetFrameBaseLevel(nsIFrame* aFrame) {
   nsIFrame* firstLeaf = aFrame;
   while (!IsBidiLeaf(firstLeaf)) {
     firstLeaf = firstLeaf->PrincipalChildList().FirstChild();
   }
   return firstLeaf->GetBaseLevel();
 }
 
-void nsBidiPresUtils::IsFirstOrLast(
-    nsIFrame* aFrame, const nsContinuationStates* aContinuationStates,
-    bool aSpanDirMatchesLineDir, bool& aIsFirst /* out */,
-    bool& aIsLast /* out */) {
+void nsBidiPresUtils::IsFirstOrLast(nsIFrame* aFrame,
+                                    nsContinuationStates* aContinuationStates,
+                                    bool aSpanDirMatchesLineDir,
+                                    bool& aIsFirst /* out */,
+                                    bool& aIsLast /* out */) {
   /*
    * Since we lay out frames in the line's direction, visiting a frame with
    * 'mFirstVisualFrame == nullptr', means it's the first appearance of one
    * of its continuation chain frames on the line.
    * To determine if it's the last visual frame of its continuation chain on
    * the line or not, we count the number of frames of the chain on the line,
    * and then reduce it when we lay out a frame of the chain. If this value
    * becomes 1 it means that it's the last visual frame of its continuation
    * chain on this line.
    */
 
   bool firstInLineOrder, lastInLineOrder;
-  nsFrameContinuationState* frameState = aContinuationStates->GetEntry(aFrame);
+  nsFrameContinuationState* frameState = aContinuationStates->Get(aFrame);
   nsFrameContinuationState* firstFrameState;
 
   if (!frameState->mFirstVisualFrame) {
     // aFrame is the first visual frame of its continuation chain
     nsFrameContinuationState* contState;
     nsIFrame* frame;
 
     frameState->mFrameCount = 1;
@@ -1385,39 +1386,38 @@ void nsBidiPresUtils::IsFirstOrLast(
 
     /**
      * Traverse continuation chain of aFrame in both backward and forward
      * directions while the frames are on this line. Count the frames and
      * set their mFirstVisualFrame to aFrame.
      */
     // Traverse continuation chain backward
     for (frame = aFrame->GetPrevContinuation();
-         frame && (contState = aContinuationStates->GetEntry(frame));
+         frame && (contState = aContinuationStates->Get(frame));
          frame = frame->GetPrevContinuation()) {
       frameState->mFrameCount++;
       contState->mFirstVisualFrame = aFrame;
     }
     frameState->mHasContOnPrevLines = (frame != nullptr);
 
     // Traverse continuation chain forward
     for (frame = aFrame->GetNextContinuation();
-         frame && (contState = aContinuationStates->GetEntry(frame));
+         frame && (contState = aContinuationStates->Get(frame));
          frame = frame->GetNextContinuation()) {
       frameState->mFrameCount++;
       contState->mFirstVisualFrame = aFrame;
     }
     frameState->mHasContOnNextLines = (frame != nullptr);
 
     firstInLineOrder = true;
     firstFrameState = frameState;
   } else {
     // aFrame is not the first visual frame of its continuation chain
     firstInLineOrder = false;
-    firstFrameState =
-        aContinuationStates->GetEntry(frameState->mFirstVisualFrame);
+    firstFrameState = aContinuationStates->Get(frameState->mFirstVisualFrame);
   }
 
   lastInLineOrder = (firstFrameState->mFrameCount == 1);
 
   if (aSpanDirMatchesLineDir) {
     aIsFirst = firstInLineOrder;
     aIsLast = lastInLineOrder;
   } else {
@@ -1502,17 +1502,17 @@ void nsBidiPresUtils::RepositionRubyCont
     LogicalRect rect = child->GetLogicalRect(aFrameWM, dummyContainerSize);
     rect.IStart(aFrameWM) += residualISize / 2;
     child->SetRect(aFrameWM, rect, dummyContainerSize);
   }
 }
 
 /* static */
 nscoord nsBidiPresUtils::RepositionRubyFrame(
-    nsIFrame* aFrame, const nsContinuationStates* aContinuationStates,
+    nsIFrame* aFrame, nsContinuationStates* aContinuationStates,
     const WritingMode aContainerWM, const LogicalMargin& aBorderPadding) {
   LayoutFrameType frameType = aFrame->Type();
   MOZ_ASSERT(RubyUtils::IsRubyBox(frameType));
 
   nscoord icoord = 0;
   WritingMode frameWM = aFrame->GetWritingMode();
   bool isLTR = frameWM.IsBidiLTR();
   nsSize frameSize = aFrame->GetSize();
@@ -1565,17 +1565,17 @@ nscoord nsBidiPresUtils::RepositionRubyF
     icoord += aFrame->ISize(aContainerWM);
   }
   return icoord;
 }
 
 /* static */
 nscoord nsBidiPresUtils::RepositionFrame(
     nsIFrame* aFrame, bool aIsEvenLevel, nscoord aStartOrEnd,
-    const nsContinuationStates* aContinuationStates, WritingMode aContainerWM,
+    nsContinuationStates* aContinuationStates, WritingMode aContainerWM,
     bool aContainerReverseDir, const nsSize& aContainerSize) {
   nscoord lineSize =
       aContainerWM.IsVertical() ? aContainerSize.height : aContainerSize.width;
   NS_ASSERTION(lineSize != NS_UNCONSTRAINEDSIZE,
                "Unconstrained inline line size in bidi frame reordering");
   if (!aFrame) return 0;
 
   bool isFirst, isLast;
@@ -1666,17 +1666,17 @@ nscoord nsBidiPresUtils::RepositionFrame
                                   : frameStartOrEnd;
   aFrame->SetRect(aContainerWM, rect, aContainerSize);
 
   return icoord + margin.IStartEnd(aContainerWM);
 }
 
 void nsBidiPresUtils::InitContinuationStates(
     nsIFrame* aFrame, nsContinuationStates* aContinuationStates) {
-  aContinuationStates->PutEntry(aFrame);
+  aContinuationStates->Insert(aFrame);
   if (!IsBidiLeaf(aFrame) || RubyUtils::IsRubyBox(aFrame->Type())) {
     // Continue for child frames
     for (nsIFrame* frame : aFrame->PrincipalChildList()) {
       InitContinuationStates(frame, aContinuationStates);
     }
   }
 }
 
--- a/layout/base/nsBidiPresUtils.h
+++ b/layout/base/nsBidiPresUtils.h
@@ -7,16 +7,17 @@
 #ifndef nsBidiPresUtils_h___
 #define nsBidiPresUtils_h___
 
 #include "gfxContext.h"
 #include "nsBidi.h"
 #include "nsBidiUtils.h"
 #include "nsHashKeys.h"
 #include "nsCoord.h"
+#include "nsTArray.h"
 
 #ifdef DrawText
 #  undef DrawText
 #endif
 
 struct BidiParagraphData;
 struct BidiLineData;
 class gfxContext;
@@ -63,20 +64,60 @@ struct nsFrameContinuationState : public
 
   /**
    * TRUE if this frame is the first visual frame of its continuation chain on
    * this line and the chain has some frames left for next lines.
    */
   bool mHasContOnNextLines{false};
 };
 
-/*
- * Following type is used to pass needed hashtable to reordering methods
- */
-typedef nsTHashtable<nsFrameContinuationState> nsContinuationStates;
+// A table of nsFrameContinuationState objects.
+//
+// This state is used between calls to nsBidiPresUtils::IsFirstOrLast.
+struct nsContinuationStates {
+  static constexpr size_t kArrayMax = 32;
+
+  // We use the array to gather up all the continuation state objects.  If in
+  // the end there are more than kArrayMax of them, we convert it to a hash
+  // table for faster lookup.
+  bool mUseTable = false;
+  AutoTArray<nsFrameContinuationState, kArrayMax> mValues;
+  nsTHashtable<nsFrameContinuationState> mTable;
+
+  void Insert(nsIFrame* aFrame) {
+    if (MOZ_UNLIKELY(mUseTable)) {
+      mTable.PutEntry(aFrame);
+      return;
+    }
+    if (MOZ_LIKELY(mValues.Length() < kArrayMax)) {
+      mValues.AppendElement(aFrame);
+      return;
+    }
+    for (const auto& entry : mValues) {
+      mTable.PutEntry(entry.GetKey());
+    }
+    mTable.PutEntry(aFrame);
+    mValues.Clear();
+    mUseTable = true;
+  }
+
+  nsFrameContinuationState* Get(nsIFrame* aFrame) {
+    MOZ_ASSERT(mValues.IsEmpty() != mTable.IsEmpty(),
+               "expect entries to either be in mValues or in mTable");
+    if (mUseTable) {
+      return mTable.GetEntry(aFrame);
+    }
+    for (size_t i = 0, len = mValues.Length(); i != len; ++i) {
+      if (mValues[i].GetKey() == aFrame) {
+        return &mValues[i];
+      }
+    }
+    return nullptr;
+  }
+};
 
 /**
  * A structure representing a logical position which should be resolved
  * into its visual position during BiDi processing.
  */
 struct nsBidiPositionResolve {
   // [in] Logical index within string.
   int32_t logicalIndex;
@@ -404,17 +445,17 @@ class nsBidiPresUtils {
   static void RepositionRubyContentFrame(
       nsIFrame* aFrame, mozilla::WritingMode aFrameWM,
       const mozilla::LogicalMargin& aBorderPadding);
 
   /*
    * Position ruby frames. Called from RepositionFrame.
    */
   static nscoord RepositionRubyFrame(
-      nsIFrame* aFrame, const nsContinuationStates* aContinuationStates,
+      nsIFrame* aFrame, nsContinuationStates* aContinuationStates,
       const mozilla::WritingMode aContainerWM,
       const mozilla::LogicalMargin& aBorderPadding);
 
   /*
    * Position aFrame and its descendants to their visual places. Also if aFrame
    * is not leaf, resize it to embrace its children.
    *
    * @param aFrame               The frame which itself and its children are
@@ -425,21 +466,22 @@ class nsBidiPresUtils {
    *                             without considering its inline margin. If the
    *                             container is reordering frames in reverse
    *                             direction, it's the distance to the end,
    *                             otherwise, it's the distance to the start.
    * @param aContinuationStates  A map from nsIFrame* to
    *                             nsFrameContinuationState
    * @return                     The isize aFrame takes, including margins.
    */
-  static nscoord RepositionFrame(
-      nsIFrame* aFrame, bool aIsEvenLevel, nscoord aStartOrEnd,
-      const nsContinuationStates* aContinuationStates,
-      mozilla::WritingMode aContainerWM, bool aContainerReverseOrder,
-      const nsSize& aContainerSize);
+  static nscoord RepositionFrame(nsIFrame* aFrame, bool aIsEvenLevel,
+                                 nscoord aStartOrEnd,
+                                 nsContinuationStates* aContinuationStates,
+                                 mozilla::WritingMode aContainerWM,
+                                 bool aContainerReverseOrder,
+                                 const nsSize& aContainerSize);
 
   /*
    * Initialize the continuation state(nsFrameContinuationState) to
    * (nullptr, 0) for aFrame and its descendants.
    *
    * @param aFrame               The frame which itself and its descendants will
    *                             be initialized
    * @param aContinuationStates  A map from nsIFrame* to
@@ -468,17 +510,17 @@ class nsBidiPresUtils {
    *                                    direction of aFrame is the same
    *                                    as its container
    * @param[out] aIsFirst              TRUE means aFrame is first frame
    *                                    or continuation
    * @param[out] aIsLast               TRUE means aFrame is last frame
    *                                    or continuation
    */
   static void IsFirstOrLast(nsIFrame* aFrame,
-                            const nsContinuationStates* aContinuationStates,
+                            nsContinuationStates* aContinuationStates,
                             bool aSpanInLineOrder /* in */,
                             bool& aIsFirst /* out */, bool& aIsLast /* out */);
 
   /**
    *  Adjust frame positions following their visual order
    *
    *  @param aFirstChild the first kid
    *  @return total inline size