Subtree caching implementation in blink-core

Source/platform/graphics/paint/DisplayItemList.cpp

Index: Source/platform/graphics/paint/DisplayItemList.cpp
diff --git a/Source/platform/graphics/paint/DisplayItemList.cpp b/Source/platform/graphics/paint/DisplayItemList.cpp
index 9c8fad763e60b0b3cbb4dbcea05602878a2bd54c..03b0ce50bbf8943f60766cdc54d5e63c4073bfba 100644
--- a/Source/platform/graphics/paint/DisplayItemList.cpp
+++ b/Source/platform/graphics/paint/DisplayItemList.cpp
@@ -91,7 +91,9 @@ void DisplayItemList::processNewItem(DisplayItem* displayItem)
 #endif
         ASSERT_NOT_REACHED();
     }
-    addItemToIndexIfNeeded(*displayItem, m_newDisplayItems.size() - 1, m_newDisplayItemIndicesByClient);
+    // TODO: Do we need to check duplicated ids for other types?
+    if (displayItem->isCached() || displayItem->isCacheable())
+        addItemToIndex(*displayItem, m_newDisplayItems.size() - 1, m_newDisplayItemIndicesByClient);
 #endif // ENABLE(ASSERT)
 
     ASSERT(!displayItem->skippedCache()); // Only DisplayItemList can set the flag.
@@ -119,6 +121,8 @@ void DisplayItemList::invalidate(DisplayItemClient client)
     ASSERT(m_newDisplayItems.isEmpty());
     updateValidlyCachedClientsIfNeeded();
     m_validlyCachedClients.remove(client);
+    updateSubtreeIndicesByClientIfNeeded();
+    m_subtreeIndicesByClient.remove(client);
 }
 
 void DisplayItemList::invalidateAll()
@@ -129,6 +133,8 @@ void DisplayItemList::invalidateAll()
     m_currentDisplayItems.clear();
     m_validlyCachedClients.clear();
     m_validlyCachedClientsDirty = false;
+    m_subtreeIndicesByClient.clear();
+    m_subtreeIndicesByClientDirty = false;
 }
 
 bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
@@ -139,6 +145,16 @@ bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
     return m_validlyCachedClients.contains(client);
 }
 
+bool DisplayItemList::subtreeCacheIsValid(DisplayItemClient client, DisplayItem::Type beginSubtreeType) const
+{
+    ASSERT(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
+    ASSERT(DisplayItem::isBeginSubtreeType(beginSubtreeType));
+    if (skippingCache())
+        return false;
+    updateSubtreeIndicesByClientIfNeeded();
+    return findMatchingItemFromIndex(DisplayItem::Id(client, beginSubtreeType, 0), m_subtreeIndicesByClient, m_currentDisplayItems) != kNotFound;
+}
+
 size_t DisplayItemList::findMatchingItemFromIndex(const DisplayItem::Id& id, const DisplayItemIndicesByClientMap& displayItemIndicesByClient, const DisplayItems& list)
 {
     DisplayItemIndicesByClientMap::const_iterator it = displayItemIndicesByClient.find(id.client);
@@ -156,15 +172,9 @@ size_t DisplayItemList::findMatchingItemFromIndex(const DisplayItem::Id& id, con
     return kNotFound;
 }
 
-void DisplayItemList::addItemToIndexIfNeeded(const DisplayItem& displayItem, size_t index, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
+void DisplayItemList::addItemToIndex(const DisplayItem& displayItem, size_t index, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
 {
-    if (!displayItem.isCacheable())
-        return;
-
-    DisplayItemIndicesByClientMap::iterator it = displayItemIndicesByClient.find(displayItem.client());
-    Vector<size_t>& indices = it == displayItemIndicesByClient.end() ?
-        displayItemIndicesByClient.add(displayItem.client(), Vector<size_t>()).storedValue->value : it->value;
-    indices.append(index);
+    displayItemIndicesByClient.add(displayItem.client(), Vector<size_t>()).storedValue->value.append(index);
 }
 
 struct DisplayItemList::OutOfOrderIndexContext {
@@ -178,20 +188,25 @@ DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItem(DisplayItems::i
 {
     ASSERT(clientCacheIsValid(id.client));
 
-    // Skip indexing of copied items.
-    if (currentIt - context.nextItemToIndex > 0)
-        context.nextItemToIndex = currentIt;
-
     size_t foundIndex = findMatchingItemFromIndex(id, context.displayItemIndicesByClient, m_currentDisplayItems);
     if (foundIndex != kNotFound)
         return m_currentDisplayItems.begin() + foundIndex;
 
-    return findOutOfOrderCachedItemForward(id, context);
+    // We added indices to all BeginSubtree display items into context.displayItemIndicesByClient
+    // at the beginning of the merge algorithm, so don't need to find forward.
+    if (DisplayItem::isBeginSubtreeType(id.type))
+        return m_currentDisplayItems.end();
+
+    return findOutOfOrderCachedItemForward(currentIt, id, context);
 }
 
 // Find forward for the item and index all skipped indexable items.
-DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItemForward(const DisplayItem::Id& id, OutOfOrderIndexContext& context)
+DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItemForward(DisplayItems::iterator currentIt, const DisplayItem::Id& id, OutOfOrderIndexContext& context)
 {
+    // Items before currentIt should have been copied. Skip indexing of them.
+    if (currentIt - context.nextItemToIndex > 0)
+        context.nextItemToIndex = currentIt;
+
     DisplayItems::iterator currentEnd = m_currentDisplayItems.end();
     for (; context.nextItemToIndex != currentEnd; ++context.nextItemToIndex) {
         const DisplayItem& item = *context.nextItemToIndex;
@@ -200,7 +215,8 @@ DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItemForward(const Di
             if (id.matches(item))
                 return context.nextItemToIndex++;
 
-            addItemToIndexIfNeeded(item, context.nextItemToIndex - m_currentDisplayItems.begin(), context.displayItemIndicesByClient);
+            if (item.isDrawing() && !item.skippedCache())
+                addItemToIndex(item, context.nextItemToIndex - m_currentDisplayItems.begin(), context.displayItemIndicesByClient);
         }
     }
     return currentEnd;
@@ -253,6 +269,7 @@ void DisplayItemList::commitNewDisplayItems(DisplayListDiff*)
 #endif
         m_currentDisplayItems.swap(m_newDisplayItems);
         m_validlyCachedClientsDirty = true;
+        m_subtreeIndicesByClientDirty = true;
         m_numCachedItems = 0;
         return;
     }
@@ -265,13 +282,14 @@ void DisplayItemList::commitNewDisplayItems(DisplayListDiff*)
     // out-of-order CachedDisplayItems occur, we only traverse at most once over m_currentDisplayItems
     // looking for potential matches. Thus we can ensure that the algorithm runs in linear time.
     OutOfOrderIndexContext outOfOrderIndexContext(m_currentDisplayItems.begin());
+    outOfOrderIndexContext.displayItemIndicesByClient.swap(m_subtreeIndicesByClient);
 
 #if ENABLE(ASSERT)
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled()) {
         // Under-invalidation checking requires a full index of m_currentDisplayItems.
         size_t i = 0;
         for (const auto& item : m_currentDisplayItems) {
-            addItemToIndexIfNeeded(item, i, outOfOrderIndexContext.displayItemIndicesByClient);
+            addItemToIndex(item, i, outOfOrderIndexContext.displayItemIndicesByClient);
             ++i;
         }
     }
@@ -295,23 +313,18 @@ void DisplayItemList::commitNewDisplayItems(DisplayListDiff*)
             ASSERT(newDisplayItem.isCached());
             ASSERT(clientCacheIsValid(newDisplayItem.client()));
             if (!isSynchronized) {
-                DisplayItems::iterator foundIt = findOutOfOrderCachedItem(currentIt, newDisplayItemId, outOfOrderIndexContext);
-
-                if (foundIt == currentEnd) {
+                currentIt = findOutOfOrderCachedItem(currentIt, newDisplayItemId, outOfOrderIndexContext);
+                if (currentIt == currentEnd) {
 #ifndef NDEBUG
                     showDebugData();
                     WTFLogAlways("%s not found in m_currentDisplayItems\n", newDisplayItem.asDebugString().utf8().data());
 #endif
                     ASSERT_NOT_REACHED();
-
-                    // If foundIt == currentEnd, it means that we did not find the cached display item. This should be impossible, but may occur
-                    // if there is a bug in the system, such as under-invalidation, incorrect cache checking or duplicate display ids. In this case,
+                    // We did not find the cached display item. This should be impossible, but may occur if there is a bug in
+                    // the system, such as under-invalidation, incorrect cache checking or duplicate display ids. In this case,
                     // attempt to recover rather than crashing or bailing on display of the rest of the display list.
                     continue;
                 }
-
-                ASSERT(foundIt != currentIt); // because we are in 'if (!isSynchronized)'
-                currentIt = foundIt;
             }
 
             if (newDisplayItem.isCachedDrawing()) {
@@ -343,6 +356,7 @@ void DisplayItemList::commitNewDisplayItems(DisplayListDiff*)
 
     m_newDisplayItems.clear();
     m_validlyCachedClientsDirty = true;
+    m_subtreeIndicesByClientDirty = true;
     m_currentDisplayItems.swap(updatedList);
     m_numCachedItems = 0;
 }
@@ -390,6 +404,20 @@ void DisplayItemList::updateValidlyCachedClientsIfNeeded() const
     }
 }
 
+void DisplayItemList::updateSubtreeIndicesByClientIfNeeded() const
+{
+    if (!m_subtreeIndicesByClientDirty)
+        return;
+
+    m_subtreeIndicesByClient.clear();
+    m_subtreeIndicesByClientDirty = false;
+
+    for (DisplayItems::const_iterator it = m_currentDisplayItems.begin(); it != m_currentDisplayItems.end(); ++it) {
+        if (it->isBeginSubtree() && !it->skippedCache())
+            addItemToIndex(*it, it - m_currentDisplayItems.begin(), m_subtreeIndicesByClient);
+    }
+}
+
 void DisplayItemList::appendToWebDisplayItemList(WebDisplayItemList* list)
 {
     for (const DisplayItem& item : m_currentDisplayItems)