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 2947afd84b91892ae388df0b67a981c1e7c63d68..3a79ddbddea3313b57ec5bba534ed5f6175a9211 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,7 @@ void DisplayItemList::invalidate(DisplayItemClient client)
     ASSERT(m_newDisplayItems.isEmpty());
     updateValidlyCachedClientsIfNeeded();
     m_validlyCachedClients.remove(client);
+    m_subtreeIndicesByClient.remove(client);
 }
 
 void DisplayItemList::invalidateAll()
@@ -129,6 +132,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 +144,15 @@ bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
     return m_validlyCachedClients.contains(client);
 }
 
+bool DisplayItemList::subtreeCacheIsValid(DisplayItemClient client, DisplayItem::Type type) const
+{
+    ASSERT(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
+    if (skippingCache())
+        return false;
+    updateSubtreeIndicesByClientIfNeeded();
+    return findMatchingItemFromIndex(DisplayItem::Id(client, type, 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);
@@ -157,15 +171,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 {
@@ -187,6 +195,10 @@ DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItem(DisplayItems::i
     if (foundIndex != kNotFound)
         return m_currentDisplayItems.begin() + foundIndex;
 
+    // We have indexed all BeginSubtree display items, so don't need to find forward.
+    if (DisplayItem::isBeginSubtreeType(id.type))
+        return m_currentDisplayItems.end();
+
     return findOutOfOrderCachedItemForward(id, context);
 }
 
@@ -201,7 +213,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;
@@ -254,6 +267,7 @@ void DisplayItemList::commitNewDisplayItems(DisplayListDiff*)
 #endif
         m_currentDisplayItems.swap(m_newDisplayItems);
         m_validlyCachedClientsDirty = true;
+        m_subtreeIndicesByClientDirty = true;
         m_numCachedItems = 0;
         return;
     }
@@ -266,13 +280,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;
         }
     }
@@ -296,23 +311,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()) {
@@ -344,6 +354,7 @@ void DisplayItemList::commitNewDisplayItems(DisplayListDiff*)
 
     m_newDisplayItems.clear();
     m_validlyCachedClientsDirty = true;

[pdr., 2015/08/20 22:45:06]

Are we still planning on removing m_validlyCachedClientsDirty and
m_validlyCachedClients?

[Xianzhu, 2015/08/21 00:31:38]

I'm thinking of this, but not sure for now about:
1. non-LayoutObject clients: they still need the set to check for validity of
cache;
2. deleted objects (including LayoutObjects).

For 1, without the set, we can treat them as non-cacheable or to duplicate the
same logic for LayoutObjects. Perhaps we can do the latter for LineBoxes, and
the former for all other clients.

For 2, I'm not sure how deleted objects will be represented in the diff passed
to cc. The diff must be able to convey the information of deleted display items,
as new display items of new objects may use the same ids. Perhaps we can use a
m_detetedClients set for the need.

+    m_subtreeIndicesByClientDirty = true;
     m_currentDisplayItems.swap(updatedList);
     m_numCachedItems = 0;
 }
@@ -391,6 +402,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)