Subtree caching implementation in blink-core

Source/platform/graphics/paint/DisplayItemList.cpp

 // 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.
 
 #include "config.h"
 #include "platform/graphics/paint/DisplayItemList.h"
 
 #include "platform/NotImplemented.h"
 #include "platform/RuntimeEnabledFeatures.h"
 #include "platform/TraceEvent.h"
@@ skipping 73 matching lines @@
 #if ENABLE(ASSERT)
     size_t index = findMatchingItemFromIndex(displayItem->nonCachedId(), m_newDisplayItemIndicesByClient, m_newDisplayItems);
     if (index != kNotFound) {
 #ifndef NDEBUG
         showDebugData();
         WTFLogAlways("DisplayItem %s has duplicated id with previous %s (index=%d)\n",
             displayItem->asDebugString().utf8().data(), m_newDisplayItems[index].asDebugString().utf8().data(), static_cast<int>(index));
 #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.
     if (skippingCache())
         displayItem->setSkippedCache();
 }
 
 void DisplayItemList::beginScope()
 {
     ASSERT_WITH_SECURITY_IMPLICATION(m_nextScope < UINT_MAX);
     m_scopeStack.append(m_nextScope++);
     beginSkippingCache();
 }
 
 void DisplayItemList::endScope()
 {
     m_scopeStack.removeLast();
     endSkippingCache();
 }
 
 void DisplayItemList::invalidate(DisplayItemClient client)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     // Can only be called during layout/paintInvalidation, not during painting.
     ASSERT(m_newDisplayItems.isEmpty());
     updateValidlyCachedClientsIfNeeded();
     m_validlyCachedClients.remove(client);
+    updateSubtreeIndicesByClientIfNeeded();
+    m_subtreeIndicesByClient.remove(client);
 }
 
 void DisplayItemList::invalidateAll()
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     // Can only be called during layout/paintInvalidation, not during painting.
     ASSERT(m_newDisplayItems.isEmpty());
     m_currentDisplayItems.clear();
     m_validlyCachedClients.clear();
     m_validlyCachedClientsDirty = false;
+    m_subtreeIndicesByClient.clear();
+    m_subtreeIndicesByClientDirty = false;
 }
 
 bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
 {
     if (skippingCache())
         return false;
     updateValidlyCachedClientsIfNeeded();
     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);
     if (it == displayItemIndicesByClient.end())
         return kNotFound;
 
     const Vector<size_t>& indices = it->value;
     for (size_t index : indices) {
         const DisplayItem& existingItem = list[index];
         ASSERT(!existingItem.isValid() || existingItem.client() == id.client);
         if (existingItem.isValid() && id.matches(existingItem))
             return index;
     }
 
     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 {
     OutOfOrderIndexContext(DisplayItems::iterator begin) : nextItemToIndex(begin) { }
 
     DisplayItems::iterator nextItemToIndex;
     DisplayItemIndicesByClientMap displayItemIndicesByClient;
 };
 
 DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItem(DisplayItems::iterator currentIt, const DisplayItem::Id& id, OutOfOrderIndexContext& context)
 {
     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;
         ASSERT(item.isValid());
         if (item.isCacheable() && clientCacheIsValid(item.client())) {
             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;
 }
 
 void DisplayItemList::copyCachedSubtree(DisplayItems::iterator& currentIt, DisplayItems& updatedList)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintV2Enabled());
     ASSERT(currentIt->isBeginSubtree());
     ASSERT(!currentIt->scope());
@@ skipping 32 matching lines @@
     m_newDisplayItemIndicesByClient.clear();
 #endif
 
     if (m_currentDisplayItems.isEmpty()) {
 #if ENABLE(ASSERT)
         for (const auto& item : m_newDisplayItems)
             ASSERT(!item.isCached());
 #endif
         m_currentDisplayItems.swap(m_newDisplayItems);
         m_validlyCachedClientsDirty = true;
+        m_subtreeIndicesByClientDirty = true;
         m_numCachedItems = 0;
         return;
     }
 
     updateValidlyCachedClientsIfNeeded();
 
     // Stores indices to valid DrawingDisplayItems in m_currentDisplayItems that have not been matched
     // by CachedDisplayItems during synchronized matching. The indexed items will be matched
     // by later out-of-order CachedDisplayItems in m_newDisplayItems. This ensures that when
     // 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;
         }
     }
 #endif // ENABLE(ASSERT)
 
     // TODO(jbroman): Consider revisiting this heuristic.
     DisplayItems updatedList(
         kMaximumDisplayItemSize,
         std::max(m_currentDisplayItems.usedCapacityInBytes(), m_newDisplayItems.usedCapacityInBytes()));
     DisplayItems::iterator currentIt = m_currentDisplayItems.begin();
     DisplayItems::iterator currentEnd = m_currentDisplayItems.end();
     for (DisplayItems::iterator newIt = m_newDisplayItems.begin(); newIt != m_newDisplayItems.end(); ++newIt) {
         const DisplayItem& newDisplayItem = *newIt;
         const DisplayItem::Id newDisplayItemId = newDisplayItem.nonCachedId();
         bool newDisplayItemHasCachedType = newDisplayItem.type() != newDisplayItemId.type;
 
         bool isSynchronized = currentIt != currentEnd && newDisplayItemId.matches(*currentIt);
 
         if (newDisplayItemHasCachedType) {
             ASSERT(!RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled());
             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()) {
                 updatedList.appendByMoving(*currentIt, currentIt->derivedSize());
                 ++currentIt;
             } else {
                 ASSERT(newDisplayItem.isCachedSubtree());
                 copyCachedSubtree(currentIt, updatedList);
                 ASSERT(updatedList.last().isEndSubtree());
             }
@@ skipping 11 matching lines @@
         }
     }
 
 #if ENABLE(ASSERT)
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled())
         checkNoRemainingCachedDisplayItems();
 #endif // ENABLE(ASSERT)
 
     m_newDisplayItems.clear();
     m_validlyCachedClientsDirty = true;
+    m_subtreeIndicesByClientDirty = true;
     m_currentDisplayItems.swap(updatedList);
     m_numCachedItems = 0;
 }
 
 size_t DisplayItemList::approximateUnsharedMemoryUsage() const
 {
     size_t memoryUsage = sizeof(*this);
 
     // Memory outside this class due to m_currentDisplayItems.
     memoryUsage += m_currentDisplayItems.memoryUsageInBytes();
@@ skipping 27 matching lines @@
     DisplayItemClient lastClient = nullptr;
     for (const DisplayItem& displayItem : m_currentDisplayItems) {
         if (displayItem.client() == lastClient)
             continue;
         lastClient = displayItem.client();
         if (!displayItem.skippedCache())
             m_validlyCachedClients.add(lastClient);
     }
 }
 
+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)
         item.appendToWebDisplayItemList(list);
 }
 
 void DisplayItemList::commitNewDisplayItemsAndAppendToWebDisplayItemList(WebDisplayItemList* list)
 {
     commitNewDisplayItems();
     appendToWebDisplayItemList(list);
@@ skipping 142 matching lines @@
 
 void DisplayItemList::replay(GraphicsContext& context)
 {
     TRACE_EVENT0("blink,benchmark", "DisplayItemList::replay");
     ASSERT(m_newDisplayItems.isEmpty());
     for (DisplayItem& displayItem : m_currentDisplayItems)
         displayItem.replay(context);
 }
 
 } // namespace blink