Find cached display items directly during painting

third_party/WebKit/Source/platform/graphics/paint/PaintController.h

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef PaintController_h
 #define PaintController_h
 
 #include "platform/PlatformExport.h"
 #include "platform/RuntimeEnabledFeatures.h"
 #include "platform/geometry/IntRect.h"
@@ skipping 57 matching lines @@
     template <typename DisplayItemClass, typename... Args>
     void createAndAppend(Args&&... args)
     {
         static_assert(WTF::IsSubclass<DisplayItemClass, DisplayItem>::value,
             "Can only createAndAppend subclasses of DisplayItem.");
         static_assert(sizeof(DisplayItemClass) <= kMaximumDisplayItemSize,
             "DisplayItem subclass is larger than kMaximumDisplayItemSize.");
 
         if (displayItemConstructionIsDisabled())
             return;
+
+        ensureNewDisplayItemListInitialCapacity();
         DisplayItemClass& displayItem = m_newDisplayItemList.allocateAndConstruct<DisplayItemClass>(std::forward<Args>(args)...);
         processNewItem(displayItem);
     }
 
     // Creates and appends an ending display item to pair with a preceding
     // beginning item iff the display item actually draws content. For no-op
     // items, rather than creating an ending item, the begin item will
     // instead be removed, thereby maintaining brevity of the list. If display
     // item construction is disabled, no list mutations will be performed.
     template <typename DisplayItemClass, typename... Args>
     void endItem(Args&&... args)
     {
         if (displayItemConstructionIsDisabled())
             return;
         if (lastDisplayItemIsNoopBegin())
             removeLastDisplayItem();
         else
             createAndAppend<DisplayItemClass>(std::forward<Args>(args)...);
     }
 
+    // Tries to find the cached drawing display item corresponding to the given parameters. If found,
+    // appends the cached display item to the new display list and returns true. Otherwise returns false.
+    bool useCachedDrawingIfPossible(const DisplayItemClient&, DisplayItem::Type);
+
+    // Tries to find the cached subsequence corresponding to the given parameters. If found, copies the
+    // cache subsequence to the new display list and returns true. Otherwise returns false.
+    bool useCachedSubsequenceIfPossible(const DisplayItemClient&);
+
     // True if the last display item is a begin that doesn't draw content.
     bool lastDisplayItemIsNoopBegin() const;
     void removeLastDisplayItem();
 
     void beginSkippingCache() { ++m_skippingCacheCount; }
     void endSkippingCache() { DCHECK(m_skippingCacheCount > 0); --m_skippingCacheCount; }
     bool skippingCache() const { return m_skippingCacheCount; }
 
     // Must be called when a painting is finished.
     // offsetFromLayoutObject is the offset between the space of the GraphicsLayer which owns this
@@ skipping 33 matching lines @@
 #ifndef NDEBUG
     void showDebugData() const;
 #endif
 
 #if DCHECK_IS_ON()
     void assertDisplayItemClientsAreLive();
 #endif
 
 protected:
     PaintController()
-        : m_newDisplayItemList(kInitialDisplayItemListCapacityBytes)
+        : m_newDisplayItemList(0)
         , m_constructionDisabled(false)
         , m_subsequenceCachingDisabled(false)
         , m_textPainted(false)
         , m_imagePainted(false)
         , m_skippingCacheCount(0)
         , m_numCachedNewItems(0)
-    { }
+#if DCHECK_IS_ON()
+        , m_numSequentialMatches(0)

[pdr., 2016/07/12 02:19:52]

This patch adds a lot of new state (7 members) and complexity that's specific to
cache lookups. Do you think it is possible to package that up and hide it in a
class/struct?

Maybe something like "class CachedDisplayItemLookup" with a lifetime that's
restricted to the paint phase (i.e., the dtor resets the list iterators, etc)?

[Xianzhu, 2016/07/12 17:56:47]

Actually most of the fields and methods of PaintController are for paint phase
only, not just the cache lookup ones, so I'd like to make the whole
PaintController live in paint phase only, like the following:

   GraphicsLayer /* or some other class */ {
     PaintArtifact m_currentPaintArtifact;
   }

   GraphicsLayer::paint() {
      PaintController paintController(m_currentPaintArtifact);
      GraphicsContext context(paintController);
      paint the contents;
      m_currentPaintArtifact = paintController.commit();
   }

So for this CL I'd like to keep the fields as-is.

[jbroman, 2016/07/12 19:05:49]

I'd assumed there might be information we wish to store from frame to frame
aside from the artifact itself. If not, making PaintController ephemeral sounds
reasonable.

[pdr., 2016/07/12 20:09:35]

This plan sounds good to me.

[Xianzhu, 2016/07/13 00:28:21]

We need to store m_currentCacheGeneration besides m_currentPaintArtifact
crossing frames. We can make m_currentCacheGeneration a field of PaintArtifact.
m_textPainted and m_imagePainted can be stored in GraphicsLayer. Other fields
can all live within a paint phase. 

+        , m_numOutOfOrderMatches(0)
+        , m_numIndexedItems(0)
+#endif
+    {
+        resetCurrentListIterators();
+    }
 
 private:
+    friend class PaintControllerTest;
+    friend class PaintControllerPaintTestBase;
+
+    void ensureNewDisplayItemListInitialCapacity()
+    {
+        if (m_newDisplayItemList.isEmpty()) {
+            // TODO(wangxianzhu): Consider revisiting this heuristic.
+            m_newDisplayItemList = DisplayItemList(m_currentPaintArtifact.getDisplayItemList().isEmpty() ? kInitialDisplayItemListCapacityBytes : m_currentPaintArtifact.getDisplayItemList().usedCapacityInBytes());
+        }
+    }
+
     // Set new item state (cache skipping, etc) for a new item.
     void processNewItem(DisplayItem&);
 
 #ifndef NDEBUG
     WTF::String displayItemListAsDebugString(const DisplayItemList&) const;
 #endif
 
     // Indices into PaintList of all DrawingDisplayItems and BeginSubsequenceDisplayItems of each client.
     // Temporarily used during merge to find out-of-order display items.
     using DisplayItemIndicesByClientMap = HashMap<const DisplayItemClient*, Vector<size_t>>;
 
     static size_t findMatchingItemFromIndex(const DisplayItem::Id&, const DisplayItemIndicesByClientMap&, const DisplayItemList&);
     static void addItemToIndexIfNeeded(const DisplayItem&, size_t index, DisplayItemIndicesByClientMap&);
 
-    struct OutOfOrderIndexContext;
-    DisplayItemList::iterator findOutOfOrderCachedItem(const DisplayItem::Id&, OutOfOrderIndexContext&);
-    DisplayItemList::iterator findOutOfOrderCachedItemForward(const DisplayItem::Id&, OutOfOrderIndexContext&);
-    void copyCachedSubsequence(const DisplayItemList& currentList, DisplayItemList::iterator& currentIt, DisplayItemList& updatedList, SkPictureGpuAnalyzer&);
+    DisplayItemList::iterator findCachedItem(const DisplayItem::Id&);
+    DisplayItemList::iterator findOutOfOrderCachedItemForward(const DisplayItem::Id&);
+    void copyCachedSubsequence(DisplayItemList::iterator&);
+
+    // Resets the iterators (e.g. m_nextItemToMatch) of m_currentPaintArtifact.getDisplayItemList()
+    // to their initial values. This should be called when the DisplayItemList in m_currentPaintArtifact
+    // is newly created, or is changed causing the previous iterators to be invalid.
+    void resetCurrentListIterators();
 
 #if DCHECK_IS_ON()
     // The following two methods are for checking under-invalidations
     // (when RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled).
     void checkUnderInvalidation(DisplayItemList::iterator& newIt, DisplayItemList::iterator& currentIt);
     void checkCachedDisplayItemIsUnchanged(const char* messagePrefix, const DisplayItem& newItem, const DisplayItem& oldItem);
 #endif
 
-    void updateCacheGeneration();
-
     // The last complete paint artifact.
     // In SPv2, this includes paint chunks as well as display items.
     PaintArtifact m_currentPaintArtifact;
 
     // Data being used to build the next paint artifact.
     DisplayItemList m_newDisplayItemList;
     PaintChunker m_newPaintChunks;
 
     // Allow display item construction to be disabled to isolate the costs of construction
     // in performance metrics.
     bool m_constructionDisabled;
 
     // Allow subsequence caching to be disabled to test the cost of display item caching.
     bool m_subsequenceCachingDisabled;
 
     // Indicates this PaintController has ever had text. It is never reset to false.
     bool m_textPainted;
     bool m_imagePainted;
 
     int m_skippingCacheCount;
 
     int m_numCachedNewItems;
 
+    // Stores indices to valid DrawingDisplayItems in current display list that have not been
+    // matched by CachedDisplayItems during sequential matching. The indexed items will be
+    // matched by later out-of-order requests of cached display items. This ensures that when
+    // out-of-order cached display items are requested, we only traverse at most once over
+    // the current display list looking for potential matches. Thus we can ensure that the
+    // algorithm runs in linear time.
+    DisplayItemIndicesByClientMap m_outOfOrderItemIndices;
+
+    // The next item in the current list for sequential match.
+    DisplayItemList::iterator m_nextItemToMatch;
+
+    // The next item in the current list to be indexed for out-of-order cache requests.
+    DisplayItemList::iterator m_nextItemToIndex;
+
+    DisplayItemClient::CacheGenerationOrInvalidationReason m_currentCacheGeneration;
+
 #if DCHECK_IS_ON()
-    // This is used to check duplicated ids during add(). We could also check
-    // during commitNewDisplayItems(), but checking during add() helps developer
-    // easily find where the duplicated ids are from.
+    int m_numSequentialMatches;
+    int m_numOutOfOrderMatches;
+    int m_numIndexedItems;
+
+    // This is used to check duplicated ids during createAndAppend().
     DisplayItemIndicesByClientMap m_newDisplayItemIndicesByClient;
 #endif
 
-    DisplayItemClient::CacheGenerationOrInvalidationReason m_currentCacheGeneration;
-
 #if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
     // A stack recording subsequence clients that are currently painting.
     Vector<const DisplayItemClient*> m_currentSubsequenceClients;
 #endif
 };
 
 } // namespace blink
 
 #endif // PaintController_h