New display item caching

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"
 #ifndef NDEBUG
@@ skipping 13 matching lines @@
 
 void DisplayItemList::add(WTF::PassOwnPtr<DisplayItem> displayItem)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     m_newPaints.append(displayItem);
 }
 
 void DisplayItemList::invalidate(DisplayItemClient client)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
-    m_cachedClients.remove(client);
+    // Can only be called during layout/paintInvalidation, not during painting.
+    ASSERT(m_newPaints.isEmpty());
+    m_cachedDisplayItemsInfoByClient.remove(client);
 }
 
 void DisplayItemList::invalidateAll()
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     // Can only be called during layout/paintInvalidation, not during painting.
     ASSERT(m_newPaints.isEmpty());
     m_paintList.clear();
-    m_cachedClients.clear();
+    m_cachedDisplayItemsInfoByClient.clear();
 }
 
-bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
+size_t DisplayItemList::findNextMatchingCachedItem(const DisplayItem& displayItem)
 {
-    return RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled() && m_cachedClients.contains(client);
+    ASSERT(displayItem.isCached());
+    ASSERT(clientCacheIsValid(displayItem.client()));
+
+    DisplayItemsInfo& info = m_cachedDisplayItemsInfoByClient.find(displayItem.client())->value;
+    size_t offset = info.updateOffset;
+    while (offset < info.displayItemIndexes.size() && !m_paintList[info.displayItemIndexes[offset]]->idsEqual(displayItem))

[chrishtr, 2015/01/22 20:13:07]

The optimization using offset implies that cached display items within an
uninvalidated DisplayItemClient never change order...not obvious anymore that
that holds.

Why not just use a nested hash map for now? Or a sorted array.

[Xianzhu, 2015/01/22 21:48:12]

There might be two reasons of using a vector containing items in the original
order:

- I'm afraid that removing the implication of display item order of an
uninvalidated DisplayItemClient will hide more under-invalidation bugs
(crbug.com/450725). However, I think allowing reordering without invalidation
could be a useful optimization in the future and added the case in
crbug.com/451090).

- We still have duplicate ids (mostly for EndClip, but maybe also others) which
prevent us from using a map or ignoring the original order. Duplicate ids seem
not to harm so far. Do we actually want to fix it?

+        ++offset;
+    // FIXME: We should assert index < info.displayItemIndexes.size(), but currently
+    // our paint invalidation doesn't always invalidate all objects needing repaint.
+    // We should fix them before enabling the assert. crbug.com/450725.
+    if (offset >= info.displayItemIndexes.size()) {
+        // The object needed repaint but wasn't invalidated. Should remove this condition
+        // after we fix all invalidation issues.
+        return kNotFound;
+    }
+    info.updateOffset = offset + 1;
+    return info.displayItemIndexes[offset];
 }
 
-PaintList::iterator DisplayItemList::findNextMatchingCachedItem(PaintList::iterator begin, const DisplayItem& displayItem)
+void DisplayItemList::appendDisplayItem(PaintList& list, DisplayItemList::DisplayItemsInfoByClientMap& displayItemsInfoByClient, WTF::PassOwnPtr<DisplayItem> displayItem)
 {
-    PaintList::iterator end = m_paintList.end();
-
-    if (!clientCacheIsValid(displayItem.client()))
-        return end;
-
-    for (PaintList::iterator it = begin; it != end; ++it) {
-        DisplayItem& existing = **it;
-        if (existing.idsEqual(displayItem))
-            return it;
+    DisplayItemsInfoByClientMap::iterator it = displayItemsInfoByClient.find(displayItem->client());
+    if (it != displayItemsInfoByClient.end()) {
+        it->value.displayItemIndexes.append(list.size());
+    } else {
+        DisplayItemsInfo info;
+        info.updateOffset = 0;
+        info.displayItemIndexes.append(list.size());
+        displayItemsInfoByClient.add(displayItem->client(), info);
     }
-
-    ASSERT_NOT_REACHED();
-    return end;
-}
-
-static void appendDisplayItem(PaintList& list, HashSet<DisplayItemClient>& clients, WTF::PassOwnPtr<DisplayItem> displayItem)
-{
-    clients.add(displayItem->client());
     list.append(displayItem);
 }
 
 // Update the existing paintList by removing invalidated entries, updating
 // repainted ones, and appending new items.
 //
 // The algorithm is O(|existing paint list| + |newly painted list|): by using
 // the ordering implied by the existing paint list, extra treewalks are avoided.
 void DisplayItemList::updatePaintList()
 {
-    if (!RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled()) {
-        m_paintList.clear();
-        m_paintList.swap(m_newPaints);
-        m_cachedClients.clear();
-        return;
-    }
-
     PaintList updatedList;
-    HashSet<DisplayItemClient> newCachedClients;
-
-    PaintList::iterator paintListIt = m_paintList.begin();
-    PaintList::iterator paintListEnd = m_paintList.end();
+    DisplayItemsInfoByClientMap newCachedDisplayItemsInfoByClient;
 
     for (OwnPtr<DisplayItem>& newDisplayItem : m_newPaints) {
-        PaintList::iterator cachedItemIt = findNextMatchingCachedItem(paintListIt, *newDisplayItem);
-        if (cachedItemIt != paintListEnd) {
-            // Copy all of the existing items over until we hit the matching cached item.
-            for (; paintListIt != cachedItemIt; ++paintListIt) {
-                if (clientCacheIsValid((*paintListIt)->client()))
-                    appendDisplayItem(updatedList, newCachedClients, paintListIt->release());
-            }
+        if (!newDisplayItem->isCached()) {
+            // Copy over the new item.
+            appendDisplayItem(updatedList, newCachedDisplayItemsInfoByClient, newDisplayItem.release());
+            continue;
+        }
 
-            // Use the cached item for the new display item.
-            appendDisplayItem(updatedList, newCachedClients, cachedItemIt->release());
-            ++paintListIt;
-        } else {
-            // If the new display item is a cached placeholder, we should have found
-            // the cached display item.
-            ASSERT(!newDisplayItem->isCached());
-
-            // Copy over the new item.
-            appendDisplayItem(updatedList, newCachedClients, newDisplayItem.release());
+        // Use the cached item for the new display item.
+        size_t index = findNextMatchingCachedItem(*newDisplayItem);
+        if (index == kNotFound) {
+            // FIXME: The object needed repaint but wasn't invalidated. Should remove this condition
+            // after we fix all invalidation issues. crbug.com/450725.
+            WTF_LOG_ERROR("Object needed repaint but wasn't invalidated. displayItem=%s", newDisplayItem->asDebugString().utf8().data());
+#ifndef NDEBUG
+            // Append the CachedDisplayItem which will visually show error indicator.
+            appendDisplayItem(updatedList, newCachedDisplayItemsInfoByClient, newDisplayItem.release());
+#endif
+            continue;
         }
-    }
-
-    // Copy over any remaining items that are validly cached.
-    for (; paintListIt != paintListEnd; ++paintListIt) {
-        if (clientCacheIsValid((*paintListIt)->client()))
-            appendDisplayItem(updatedList, newCachedClients, paintListIt->release());
+        appendDisplayItem(updatedList, newCachedDisplayItemsInfoByClient, m_paintList[index].release());
     }
 
     m_newPaints.clear();
     m_paintList.clear();
     m_paintList.swap(updatedList);
-    m_cachedClients.clear();
-    m_cachedClients.swap(newCachedClients);
+    m_cachedDisplayItemsInfoByClient.clear();
+    m_cachedDisplayItemsInfoByClient.swap(newCachedDisplayItemsInfoByClient);
 }
 
 #ifndef NDEBUG
 
 WTF::String DisplayItemList::paintListAsDebugString(const PaintList& list) const
 {
     StringBuilder stringBuilder;
-    bool isFirst = true;
-    for (auto& displayItem : list) {
-        if (!isFirst)
+    for (size_t i = 0; i < list.size(); ++i) {
+        const OwnPtr<DisplayItem>& displayItem = list[i];
+        if (i)
             stringBuilder.append(",\n");
-        isFirst = false;
-        stringBuilder.append('{');
+        if (!displayItem) {
+            stringBuilder.append("null");
+            continue;
+        }
+        stringBuilder.append(String::format("{index: %d, ", (int)i));
         displayItem->dumpPropertiesAsDebugString(stringBuilder);
         stringBuilder.append(", cacheIsValid: ");
         stringBuilder.append(clientCacheIsValid(displayItem->client()) ? "true" : "false");
         stringBuilder.append('}');
     }
     return stringBuilder.toString();
 }
 
+WTF::String DisplayItemList::cachedDisplayItemsInfoByClientAsDebugString() const
+{
+    StringBuilder stringBuilder;
+    bool isFirst = true;
+    for (auto& item : m_cachedDisplayItemsInfoByClient) {
+        if (!isFirst)
+            stringBuilder.append(",\n");
+        isFirst = false;
+        stringBuilder.append(String::format("{client:%p, mergeIndex:%d, displayItemIndexes:[", item.key, (int)item.value.updateOffset));
+        for (size_t i = 0; i < item.value.displayItemIndexes.size(); ++i) {
+            if (i)
+                stringBuilder.append(',');
+            stringBuilder.append(String::format("%d", (int)item.value.displayItemIndexes[i]));
+        }
+        stringBuilder.append("]}");
+    }
+    return stringBuilder.toString();
+}
+
 void DisplayItemList::showDebugData() const
 {
     fprintf(stderr, "paint list: [%s]\n", paintListAsDebugString(m_paintList).utf8().data());
     fprintf(stderr, "new paints: [%s]\n", paintListAsDebugString(m_newPaints).utf8().data());
+    fprintf(stderr, "cachedDisplayItemsInfo: [%s]\n", cachedDisplayItemsInfoByClientAsDebugString().utf8().data());
 }
 
-#endif
+#endif // ifndef NDEBUG
 
 void DisplayItemList::replay(GraphicsContext* context)
 {
     updatePaintList();
     for (auto& displayItem : m_paintList)
         displayItem->replay(context);
 }
 
 } // namespace blink