New display item caching

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 c2b800adb3cf2a7c2a151624e4769053f4c8d3ff..ef273a5ef765f4da2e9968695048a69f2be74be8 100644
--- a/Source/platform/graphics/paint/DisplayItemList.cpp
+++ b/Source/platform/graphics/paint/DisplayItemList.cpp
@@ -31,7 +31,9 @@ void DisplayItemList::add(WTF::PassOwnPtr<DisplayItem> 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()
@@ -40,34 +42,41 @@ void DisplayItemList::invalidateAll()
     // Can only be called during layout/paintInvalidation, not during painting.
     ASSERT(m_newPaints.isEmpty());
     m_paintList.clear();
-    m_cachedClients.clear();
-}
-
-bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
-{
-    return RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled() && m_cachedClients.contains(client);
+    m_cachedDisplayItemsInfoByClient.clear();
 }
 
-PaintList::iterator DisplayItemList::findNextMatchingCachedItem(PaintList::iterator begin, const DisplayItem& displayItem)
+size_t DisplayItemList::findNextMatchingCachedItem(const 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;
+    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;
     }
-
-    ASSERT_NOT_REACHED();
-    return end;
+    info.updateOffset = offset + 1;
+    return info.displayItemIndexes[offset];
 }
 
-static void appendDisplayItem(PaintList& list, HashSet<DisplayItemClient>& clients, WTF::PassOwnPtr<DisplayItem> displayItem)
+void DisplayItemList::appendDisplayItem(PaintList& list, DisplayItemList::DisplayItemsInfoByClientMap& displayItemsInfoByClient, WTF::PassOwnPtr<DisplayItem> displayItem)
 {
-    clients.add(displayItem->client());
+    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);
+    }
     list.append(displayItem);
 }
 
@@ -78,52 +87,37 @@ static void appendDisplayItem(PaintList& list, HashSet<DisplayItemClient>& clien
 // 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());
-            }
-
-            // 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());
-
+        if (!newDisplayItem->isCached()) {
             // Copy over the new item.
-            appendDisplayItem(updatedList, newCachedClients, newDisplayItem.release());
+            appendDisplayItem(updatedList, newCachedDisplayItemsInfoByClient, newDisplayItem.release());
+            continue;
         }
-    }
 
-    // Copy over any remaining items that are validly cached.
-    for (; paintListIt != paintListEnd; ++paintListIt) {
-        if (clientCacheIsValid((*paintListIt)->client()))
-            appendDisplayItem(updatedList, newCachedClients, paintListIt->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;
+        }
+        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
@@ -131,12 +125,15 @@ void DisplayItemList::updatePaintList()
 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");
@@ -145,13 +142,33 @@ WTF::String DisplayItemList::paintListAsDebugString(const PaintList& list) const
     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)
 {