Find cached display items directly during painting

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

Index: third_party/WebKit/Source/platform/graphics/paint/PaintController.h
diff --git a/third_party/WebKit/Source/platform/graphics/paint/PaintController.h b/third_party/WebKit/Source/platform/graphics/paint/PaintController.h
index fd1d11f42b68261d93e692d247cbd0d5bf5a7a6d..28324670645b376f8e760f71a4ddbeda6c121aeb 100644
--- a/third_party/WebKit/Source/platform/graphics/paint/PaintController.h
+++ b/third_party/WebKit/Source/platform/graphics/paint/PaintController.h
@@ -75,6 +75,8 @@ public:
 
         if (displayItemConstructionIsDisabled())
             return;
+
+        ensureNewDisplayItemListInitialCapacity();
         DisplayItemClass& displayItem = m_newDisplayItemList.allocateAndConstruct<DisplayItemClass>(std::forward<Args>(args)...);
         processNewItem(displayItem);
     }
@@ -95,6 +97,14 @@ public:
             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();
@@ -148,16 +158,34 @@ public:
 
 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&);
 
@@ -172,10 +200,14 @@ private:
     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
@@ -184,8 +216,6 @@ private:
     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;
@@ -209,15 +239,31 @@ private:
 
     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;