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);
+    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 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);
     if (it == displayItemIndicesByClient.end())
         return kNotFound;
 
     const Vector<size_t>& indices = it->value;
     for (size_t index : indices) {
         // TODO(pdr): elementAt is not cheap so this should be refactored (See crbug.com/505965).
         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;
 
+    // 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);
 }
 
 // Find forward for the item and index all skipped indexable items.
 DisplayItems::iterator DisplayItemList::findOutOfOrderCachedItemForward(const DisplayItem::Id& id, OutOfOrderIndexContext& context)
 {
     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 10 matching lines @@
                 ++currentIt;
         }
     }
 
 #if ENABLE(ASSERT)
     if (RuntimeEnabledFeatures::slimmingPaintUnderInvalidationCheckingEnabled())
         checkNoRemainingCachedDisplayItems();
 #endif // ENABLE(ASSERT)
 
     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;
 }
 
 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