Bug 1439809 - Store the display list index on the display items during PreProcessDisplayList so that we can do lookup without a hashtable. r?mstange draft
authorMatt Woodrow <mwoodrow@mozilla.com>
Fri, 20 Apr 2018 12:47:32 +1200
changeset 785404 2efe9cb8a4ab1a3e09bb36c9c17422660531aa9b
parent 785403 dcf87f8c661a884641985f33a221971ef2160a74
push id107220
push usermwoodrow@mozilla.com
push dateFri, 20 Apr 2018 00:53:54 +0000
reviewersmstange
bugs1439809
milestone61.0a1
Bug 1439809 - Store the display list index on the display items during PreProcessDisplayList so that we can do lookup without a hashtable. r?mstange MozReview-Commit-ID: auu9MllRul
layout/painting/RetainedDisplayListBuilder.cpp
layout/painting/RetainedDisplayListHelpers.h
layout/painting/nsDisplayList.h
--- a/layout/painting/RetainedDisplayListBuilder.cpp
+++ b/layout/painting/RetainedDisplayListBuilder.cpp
@@ -110,42 +110,42 @@ RetainedDisplayListBuilder::PreProcessDi
       (aList->mDAG.mNodesInfo.Length() * kMaxEdgeRatio)) {
     return false;
 
   }
 
   nsDisplayList saved;
   aList->mOldItems.SetCapacity(aList->Count());
   MOZ_ASSERT(aList->mOldItems.IsEmpty());
-  size_t i = 0;
   while (nsDisplayItem* item = aList->RemoveBottom()) {
     if (item->HasDeletedFrame() || !item->CanBeReused()) {
       // If we haven't yet initialized the DAG, then we can
       // just drop this item. Otherwise we need to keep it
       // around to preserve indices, and merging will
       // get rid of it.
       if (initializeDAG) {
         item->Destroy(&mBuilder);
       } else {
+        size_t i = aList->mOldItems.Length();
         aList->mOldItems.AppendElement(OldItemInfo(item));
+        item->SetMergeListIndex(aList, i);
       }
       continue;
     }
 
+    size_t i = aList->mOldItems.Length();
     aList->mOldItems.AppendElement(OldItemInfo(item));
+    item->SetMergeListIndex(aList, i);
     if (initializeDAG) {
       if (i == 0) {
         aList->mDAG.AddNode(Span<const MergedListIndex>());
       } else {
         MergedListIndex previous(i - 1);
         aList->mDAG.AddNode(Span<const MergedListIndex>(&previous, 1));
       }
-
-      aList->mKeyLookup.Put({ item->Frame(), item->GetPerFrameKey() }, i);
-      i++;
     }
 
     nsIFrame* f = item->Frame();
 
     if (item->GetChildren()) {
       if (!PreProcessDisplayList(item->GetChildren(), SelectAGRForFrame(f, aAGR))) {
         mBuilder.MarkFrameForDisplayIfVisible(f, mBuilder.RootReferenceFrame());
         mBuilder.MarkFrameModifiedDuringBuilding(f);
@@ -235,42 +235,48 @@ OldItemInfo::Discard(RetainedDisplayList
 {
   MOZ_ASSERT(!IsUsed());
   mUsed = mDiscarded = true;
   mDirectPredecessors = Move(aDirectPredecessors);
   mItem->Destroy(aBuilder->Builder());
   mItem = nullptr;
 }
 
+bool
+OldItemInfo::IsChanged() {
+  return !mItem || mItem->HasDeletedFrame() || !mItem->CanBeReused();
+}
+
 /**
  * A C++ implementation of Markus Stange's merge-dags algorthim.
  * https://github.com/mstange/merge-dags
  *
  * MergeState handles combining a new list of display items into an existing
  * DAG and computes the new DAG in a single pass.
  * Each time we add a new item, we resolve all dependencies for it, so that the resulting
  * list and DAG are built in topological ordering.
  */
 class MergeState {
 public:
-  MergeState(RetainedDisplayListBuilder* aBuilder, RetainedDisplayList&& aOldList)
+  MergeState(RetainedDisplayListBuilder* aBuilder, RetainedDisplayList& aOldList)
     : mBuilder(aBuilder)
+    , mOldList(&aOldList)
     , mOldItems(Move(aOldList.mOldItems))
     , mOldDAG(Move(*reinterpret_cast<DirectedAcyclicGraph<OldListUnits>*>(&aOldList.mDAG)))
     , mResultIsModified(false)
   {
-    mOldKeyLookup.SwapElements(aOldList.mKeyLookup);
     mMergedDAG.EnsureCapacityFor(mOldDAG);
   }
 
   MergedListIndex ProcessItemFromNewList(nsDisplayItem* aNewItem, const Maybe<MergedListIndex>& aPreviousItem) {
     OldListIndex oldIndex;
-    if (mOldKeyLookup.Get({ aNewItem->Frame(), aNewItem->GetPerFrameKey() }, &oldIndex.val)) {
+    if (!HasModifiedFrame(aNewItem) &&
+        HasMatchingItemInOldList(aNewItem, &oldIndex.val)) {
       nsDisplayItem* oldItem = mOldItems[oldIndex.val].mItem;
-      if (oldItem && !IsChanged(oldItem)) {
+      if (!mOldItems[oldIndex.val].IsChanged()) {
         MOZ_ASSERT(!mOldItems[oldIndex.val].IsUsed());
         if (aNewItem->GetChildren()) {
           Maybe<const ActiveScrolledRoot*> containerASRForChildren;
           if (mBuilder->MergeDisplayLists(aNewItem->GetChildren(),
                                           oldItem->GetChildren(),
                                           aNewItem->GetChildren(),
                                           containerASRForChildren)) {
             mResultIsModified = true;
@@ -299,23 +305,35 @@ public:
       AutoTArray<MergedListIndex, 2> directPredecessors =
         ResolveNodeIndexesOldToMerged(mOldDAG.GetDirectPredecessors(OldListIndex(i)));
       ProcessOldNode(OldListIndex(i), Move(directPredecessors));
     }
 
     RetainedDisplayList result;
     result.AppendToTop(&mMergedItems);
     result.mDAG = Move(mMergedDAG);
-    result.mKeyLookup.SwapElements(mMergedKeyLookup);
     return result;
   }
 
-  bool IsChanged(nsDisplayItem* aItem) {
-    return aItem->HasDeletedFrame() || !aItem->CanBeReused() ||
-           AnyContentAncestorModified(aItem->FrameForInvalidation());
+  bool HasMatchingItemInOldList(nsDisplayItem* aItem, size_t* aOutIndex)
+  {
+    nsIFrame::DisplayItemArray* items = aItem->Frame()->GetProperty(nsIFrame::DisplayItems());
+    // Look for an item that matches aItem's frame and per-frame-key, but isn't the same item.
+    for (nsDisplayItem* i : *items) {
+      if (i != aItem && i->Frame() == aItem->Frame() &&
+          i->GetPerFrameKey() == aItem->GetPerFrameKey()) {
+        *aOutIndex = i->GetMergeListIndex(mOldList);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool HasModifiedFrame(nsDisplayItem* aItem) {
+    return AnyContentAncestorModified(aItem->FrameForInvalidation());
   }
 
   void UpdateContainerASR(nsDisplayItem* aItem)
   {
     const ActiveScrolledRoot* itemClipASR =
       aItem->GetClipChain() ? aItem->GetClipChain()->mASR : nullptr;
 
     const ActiveScrolledRoot* finiteBoundsASR = ActiveScrolledRoot::PickDescendant(
@@ -330,23 +348,22 @@ public:
 
   MergedListIndex AddNewNode(nsDisplayItem* aItem,
                              const Maybe<OldListIndex>& aOldIndex,
                              Span<const MergedListIndex> aDirectPredecessors,
                              const Maybe<MergedListIndex>& aExtraDirectPredecessor) {
     UpdateContainerASR(aItem);
     mMergedItems.AppendToTop(aItem);
     MergedListIndex newIndex = mMergedDAG.AddNode(aDirectPredecessors, aExtraDirectPredecessor);
-    mMergedKeyLookup.Put({ aItem->Frame(), aItem->GetPerFrameKey() }, newIndex.val);
     return newIndex;
   }
 
   void ProcessOldNode(OldListIndex aNode, nsTArray<MergedListIndex>&& aDirectPredecessors) {
     nsDisplayItem* item = mOldItems[aNode.val].mItem;
-    if (IsChanged(item)) {
+    if (mOldItems[aNode.val].IsChanged() || HasModifiedFrame(item)) {
       mOldItems[aNode.val].Discard(mBuilder, Move(aDirectPredecessors));
       mResultIsModified = true;
     } else {
       if (item->GetChildren()) {
         Maybe<const ActiveScrolledRoot*> containerASRForChildren;
         nsDisplayList empty;
         if (mBuilder->MergeDisplayLists(&empty, item->GetChildren(), item->GetChildren(),
                                         containerASRForChildren)) {
@@ -424,33 +441,31 @@ public:
       } else {
         result.AppendElement(oldItem.mIndex);
       }
     }
     return result;
   }
 
   RetainedDisplayListBuilder* mBuilder;
+  RetainedDisplayList* mOldList;
   Maybe<const ActiveScrolledRoot*> mContainerASR;
   nsTArray<OldItemInfo> mOldItems;
   DirectedAcyclicGraph<OldListUnits> mOldDAG;
   // Unfortunately we can't use strong typing for the hashtables
   // since they internally encode the type with the mOps pointer,
   // and assert when we try swap the contents
-  nsDataHashtable<DisplayItemHashEntry, size_t> mOldKeyLookup;
   nsDisplayList mMergedItems;
   DirectedAcyclicGraph<MergedListUnits> mMergedDAG;
-  nsDataHashtable<DisplayItemHashEntry, size_t> mMergedKeyLookup;
   bool mResultIsModified;
 };
 
 void RetainedDisplayList::ClearDAG()
 {
   mDAG.Clear();
-  mKeyLookup.Clear();
 }
 
 /**
  * Takes two display lists and merges them into an output list.
  *
  * Display lists wthout an explicit DAG are interpreted as linear DAGs (with a maximum
  * of one direct predecessor and one direct successor per node). We add the two DAGs
  * together, and then output the topological sorted ordering as the final display list.
@@ -459,17 +474,17 @@ void RetainedDisplayList::ClearDAG()
  * object) to use for future merges.
  */
 bool
 RetainedDisplayListBuilder::MergeDisplayLists(nsDisplayList* aNewList,
                                               RetainedDisplayList* aOldList,
                                               RetainedDisplayList* aOutList,
                                               mozilla::Maybe<const mozilla::ActiveScrolledRoot*>& aOutContainerASR)
 {
-  MergeState merge(this, Move(*aOldList));
+  MergeState merge(this, *aOldList);
 
   Maybe<MergedListIndex> previousItemIndex;
   while (nsDisplayItem* item = aNewList->RemoveBottom()) {
     previousItemIndex = Some(merge.ProcessItemFromNewList(item, previousItemIndex));
   }
 
   *aOutList = Move(merge.Finalize());
   aOutContainerASR = merge.mContainerASR;
--- a/layout/painting/RetainedDisplayListHelpers.h
+++ b/layout/painting/RetainedDisplayListHelpers.h
@@ -184,16 +184,18 @@ struct OldItemInfo {
   }
 
   bool IsDiscarded()
   {
     MOZ_ASSERT(IsUsed());
     return mDiscarded;
   }
 
+  bool IsChanged();
+
   nsDisplayItem* mItem;
   bool mUsed;
   bool mDiscarded;
   MergedListIndex mIndex;
   nsTArray<MergedListIndex> mDirectPredecessors;
 };
 
 #endif // RETAINEDDISPLAYLISTHELPERS_H_
--- a/layout/painting/nsDisplayList.h
+++ b/layout/painting/nsDisplayList.h
@@ -2842,16 +2842,30 @@ public:
       const ActiveScrolledRoot* aASR) const;
 
   void SetDisplayItemData(mozilla::DisplayItemData* aDID) {
     mDisplayItemData = aDID;
   }
 
   mozilla::DisplayItemData* GetDisplayItemData() { return mDisplayItemData; }
 
+  // Set the nsDisplayList that this item belongs to, and what
+  // index it is within that list. Temporary state for merging
+  // used by RetainedDisplayListBuilder.
+  void SetMergeListIndex(nsDisplayList* aList, uint32_t aIndex)
+  {
+    mMergeList = reinterpret_cast<uintptr_t>(aList);
+    mMergeListIndex = aIndex;
+  }
+  uint32_t GetMergeListIndex(nsDisplayList* aList)
+  {
+    MOZ_ASSERT(mMergeList == reinterpret_cast<uintptr_t>(aList));
+    return mMergeListIndex;
+  }
+
 protected:
   nsDisplayItem() = delete;
 
   typedef bool (*PrefFunc)(void);
   bool ShouldUseAdvancedLayer(LayerManager* aManager, PrefFunc aFunc) const;
   bool CanUseAdvancedLayer(LayerManager* aManager) const;
 
   nsIFrame* mFrame;
@@ -2866,16 +2880,20 @@ protected:
   RefPtr<mozilla::DisplayItemData> mDisplayItemData;
   // This is the rectangle that needs to be painted.
   // Display item construction sets this to the dirty rect.
   // nsDisplayList::ComputeVisibility sets this to the visible region
   // of the item by intersecting the current visible region with the bounds
   // of the item. Paint implementations can use this to limit their drawing.
   // Guaranteed to be contained in GetBounds().
   nsRect    mVisibleRect;
+
+  mozilla::DebugOnly<uintptr_t> mMergeList;
+  uint32_t mMergeListIndex;
+
   bool      mForceNotVisible;
   bool      mDisableSubpixelAA;
   bool      mReusedItem;
   bool      mBackfaceHidden;
 #ifdef MOZ_DUMP_PAINTING
   // True if this frame has been painted.
   bool      mPainted;
 #endif
@@ -3432,30 +3450,28 @@ private:
  */
 class RetainedDisplayList : public nsDisplayList {
 public:
   RetainedDisplayList() {}
   RetainedDisplayList(RetainedDisplayList&& aOther)
   {
     AppendToTop(&aOther);
     mDAG = mozilla::Move(aOther.mDAG);
-    mKeyLookup.SwapElements(aOther.mKeyLookup);
   }
   ~RetainedDisplayList()
   {
     MOZ_ASSERT(mOldItems.IsEmpty(), "Must empty list before destroying");
   }
 
   RetainedDisplayList& operator=(RetainedDisplayList&& aOther)
   {
     MOZ_ASSERT(!Count(), "Can only move into an empty list!");
     MOZ_ASSERT(mOldItems.IsEmpty(), "Can only move into an empty list!");
     AppendToTop(&aOther);
     mDAG = mozilla::Move(aOther.mDAG);
-    mKeyLookup.SwapElements(aOther.mKeyLookup);
     return *this;
   }
 
   void DeleteAll(nsDisplayListBuilder* aBuilder)
   {
     for (OldItemInfo& i : mOldItems) {
       if (i.mItem) {
         i.mItem->Destroy(aBuilder);
@@ -3463,17 +3479,16 @@ public:
     }
     mOldItems.Clear();
     nsDisplayList::DeleteAll(aBuilder);
   }
 
   void ClearDAG();
 
   DirectedAcyclicGraph<MergedListUnits> mDAG;
-  nsDataHashtable<DisplayItemHashEntry, size_t> mKeyLookup;
 
   // Temporary state initialized during the preprocess pass
   // of RetainedDisplayListBuilder and then used during merging.
   nsTArray<OldItemInfo> mOldItems;
 };
 
 class nsDisplayImageContainer : public nsDisplayItem {
 public: