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))
+        ++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;

[chrishtr, 2015/01/22 22:17:21]

Put this in the constructor instead.

[Xianzhu, 2015/01/22 23:50:59]

Done.

+        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.");
+#ifndef NDEBUG
+            WTF_LOG_ERROR("displayItem=%s", newDisplayItem->asDebugString().utf8().data());
+            // 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());

[chrishtr, 2015/01/22 22:17:21]

How about replacing 94-113 with:

if (newDisplayItem->isCached() {
  size_t index = findNextMatchingCachedItem(*newDisplayItem);
  if (index == kNotFound) {
    log errors
  } else {
    ASSERT(!m_paintList[index]->isCached()); // check for bugs
    newDisplayItem.swap(m_paintList[index]);
  }
}
appendDisplayItem(updatedList, newCachedDisplayItemsInfoByClient,
newDisplayItem.release());

[Xianzhu, 2015/01/22 23:50:59]

Just discussed a related issue with trchen@. We noticed that sometimes some meta
display items (items other than DrawingDisplayItem/CachedDisplayItem) change
without invalidation. For example, when an iframe is scrolled, the transform
display items change, but we don't invalidate the iframe. With the old code,
we'll reuse the old transform display items because we find matches, causing
scrolling not working. Your suggested code basically does the same as the old
code.

In the new code, we use old display items only for CachedDisplayItems. For other
display items, we don't try to match, but use the new display item directly.
This avoids findNextMachingCachedItem() calls for non-CachedDisplayItems.

[Xianzhu, 2015/01/23 23:52:45]

Sorry I was wrong about your suggested code which is actually much better :)

Done.

Didn't add ASSERT(!m_paintList[index]->isCached()) because in debug mode
CachedDisplayItems are added into paint list to visually indicate the errors.

     }
 
     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));

[chrishtr, 2015/01/22 22:17:21]

s/mergeIndex/updateOffset/. Or better yet, just ASSERT(item.value.updateOffset
== 0) since printing during update is not a common debug need.

[Xianzhu, 2015/01/22 23:50:59]

Done.
I found this is useful when debugging updatePaintList() method. In gdb, I can
manually call showDebugData() anytime.

The change in paintListAsDebugString() is also for debugging updatePaintList()
(when we may encounter null entries in the paint list).

+        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