First version of new merge algorithm (not enabled yet)

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 783e1589c55b89f870bc610c822d9b4de3811b56..ecc44cf81a92798acf4f7cac28e661b7bfdee403 100644
--- a/Source/platform/graphics/paint/DisplayItemList.cpp
+++ b/Source/platform/graphics/paint/DisplayItemList.cpp
@@ -41,7 +41,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_cachedDisplayItemIndicesByClient.remove(client);
 }
 
 void DisplayItemList::invalidateAll()
@@ -50,92 +52,101 @@ void DisplayItemList::invalidateAll()
     // Can only be called during layout/paintInvalidation, not during painting.
     ASSERT(m_newPaints.isEmpty());
     m_paintList.clear();
-    m_cachedClients.clear();
+    m_cachedDisplayItemIndicesByClient.clear();
 }
 
 bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
 {
-    return RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled() && m_cachedClients.contains(client);
+    return RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled() && m_cachedDisplayItemIndicesByClient.contains(client);
 }
 
-PaintList::iterator DisplayItemList::findNextMatchingCachedItem(PaintList::iterator begin, const DisplayItem& displayItem)
+size_t DisplayItemList::findMatchingCachedItem(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.isDrawing()
-            && existing.client() == displayItem.client()
-            && existing.type() == DisplayItem::cachedTypeToDrawingType(displayItem.type()))
-            return it;
+    ASSERT(displayItem.isCached() || displayItem.isSubtreeCached());
+    ASSERT(clientCacheIsValid(displayItem.client()));
+
+    Vector<size_t>& indices = m_cachedDisplayItemIndicesByClient.find(displayItem.client())->value;
+    DisplayItem::Type matchingType = displayItem.isCached()
+        ? DisplayItem::cachedTypeToDrawingType(displayItem.type())
+        : DisplayItem::subtreeCachedTypeToBeginSubtreeType(displayItem.type());
+
+    for (size_t index : indices) {
+        OwnPtr<DisplayItem>& existingItem = m_paintList[index];
+        ASSERT(!existingItem || existingItem->client() == displayItem.client());
+        if (existingItem && existingItem->type() == matchingType)
+            return index;
     }
 
-    ASSERT_NOT_REACHED();
-    return end;
+    // Previously the client generated a empty picture or an empty subtree
+    // which is not stored in the cache.
+    return kNotFound;
 }
 
-static void appendDisplayItem(PaintList& list, HashSet<DisplayItemClient>& clients, WTF::PassOwnPtr<DisplayItem> displayItem)
+void DisplayItemList::appendDisplayItem(PaintList& list, DisplayItemIndicesByClientMap& displayItemIndicesByClient, WTF::PassOwnPtr<DisplayItem> displayItem)
 {
-    clients.add(displayItem->client());
+    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(list.size());
+
     list.append(displayItem);
 }
 
+void DisplayItemList::copyCachedItems(const DisplayItem& displayItem, PaintList& list, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
+{
+    size_t index = findMatchingCachedItem(displayItem);
+    if (index == kNotFound)
+        return;
+
+    if (displayItem.isCached()) {
+        appendDisplayItem(list, displayItemIndicesByClient, m_paintList[index].release());
+        return;
+    }
+
+    ASSERT(m_paintList[index]->isBeginSubtree());
+    DisplayItem* beginSubtree = m_paintList[index].get();
+    DisplayItem::Type endSubtreeType = DisplayItem::beginSubtreeTypeToEndSubtreeType(beginSubtree->type());
+    do {
+        if (clientCacheIsValid(m_paintList[index]->client()))
+            appendDisplayItem(list, displayItemIndicesByClient, m_paintList[index].release());
+        ++index;
+    } while (list.last()->client() != beginSubtree->client() || list.last()->type() != endSubtreeType);
+}
+
 // Update the existing paintList by removing invalidated entries, updating
 // repainted ones, and appending new items.
+// - For CachedDisplayItem, copy the corresponding cached DrawingDisplayItem;
+// - For SubtreeCachedDisplayItem, copy the cached display items between the
+//   corresponding BeginSubtreeDisplayItem and EndSubtreeDisplayItem (incl.);
+// - Otherwise, copy the new display item.
 //
-// The algorithm is O(|existing paint list| + |newly painted list|): by using
-// the ordering implied by the existing paint list, extra treewalks are avoided.
+// The algorithm is O(|existing paint list| + |newly painted list|).
+// Coefficients are related to the ratio of [Subtree]CachedDisplayItems
+// and the average number of (Drawing|BeginSubtree)DisplayItems per client.
 void DisplayItemList::updatePaintList()
 {
     if (!RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled()) {
         m_paintList.clear();
         m_paintList.swap(m_newPaints);
-        m_cachedClients.clear();
+        m_cachedDisplayItemIndicesByClient.clear();
         return;
     }
 
     PaintList updatedList;
-    HashSet<DisplayItemClient> newCachedClients;
-
-    PaintList::iterator paintListIt = m_paintList.begin();
-    PaintList::iterator paintListEnd = m_paintList.end();
+    DisplayItemIndicesByClientMap newCachedDisplayItemIndicesByClient;
 
     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());
-
-            // Copy over the new item.
-            appendDisplayItem(updatedList, newCachedClients, newDisplayItem.release());
-        }
-    }
-
-    // Copy over any remaining items that are validly cached.
-    for (; paintListIt != paintListEnd; ++paintListIt) {
-        if (clientCacheIsValid((*paintListIt)->client()))
-            appendDisplayItem(updatedList, newCachedClients, paintListIt->release());
+        if (newDisplayItem->isCached() || newDisplayItem->isSubtreeCached())
+            copyCachedItems(*newDisplayItem, updatedList, newCachedDisplayItemIndicesByClient);
+        else
+            appendDisplayItem(updatedList, newCachedDisplayItemIndicesByClient, newDisplayItem.release());
     }
 
     m_newPaints.clear();
     m_paintList.clear();
     m_paintList.swap(updatedList);
-    m_cachedClients.clear();
-    m_cachedClients.swap(newCachedClients);
+    m_cachedDisplayItemIndicesByClient.clear();
+    m_cachedDisplayItemIndicesByClient.swap(newCachedDisplayItemIndicesByClient);
 }
 
 #ifndef NDEBUG
@@ -143,12 +154,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");
@@ -163,7 +177,7 @@ void DisplayItemList::showDebugData() const
     fprintf(stderr, "new paints: [%s]\n", paintListAsDebugString(m_newPaints).utf8().data());
 }
 
-#endif
+#endif // ifndef NDEBUG
 
 void DisplayItemList::replay(GraphicsContext* context)
 {