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)
+        , 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