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 654b7f0f91cdd8b22e890f7a4ffc863255fe0217..25d4ef010d203b9029d809ba77270e20e4129ba1 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_cachedDisplayItemIndicesByClient.remove(client);
 }
 
 void DisplayItemList::invalidateAll()
@@ -40,92 +42,115 @@ 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()));
+
+    DisplayItemIndices& indicesStruct = m_cachedDisplayItemIndicesByClient.find(displayItem.client())->value;
+    Vector<size_t>& indices = displayItem.isCached()
+        ? indicesStruct.drawingDisplayItemIndices
+        : indicesStruct.beginSubtreeDisplayItemIndices;
+    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 display item 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());
+    DisplayItemIndices& indicesStruct = it == displayItemIndicesByClient.end() ?
+        displayItemIndicesByClient.add(displayItem->client(), DisplayItemIndices()).storedValue->value : it->value;
+
+    if (displayItem->isDrawing())
+        indicesStruct.drawingDisplayItemIndices.append(list.size());
+    else if (displayItem->isBeginSubtree())
+        indicesStruct.beginSubtreeDisplayItemIndices.append(list.size());
+
     list.append(displayItem);
 }
 
+void DisplayItemList::copyCachedSubtree(const DisplayItem& subtreeCachedDisplayItem, PaintList& list, DisplayItemIndicesByClientMap& displayItemIndicesByClient)
+{
+    size_t index = findMatchingCachedItem(subtreeCachedDisplayItem);
+    // Previously the client generated an empty subtree for the phase.
+    if (index == kNotFound)
+        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());
-            }
+        if (newDisplayItem->isSubtreeCached()) {

[pdr., 2015/02/05 03:35:57]

It looks like we may be able to combine this with the isCached branch below into
a single function: copyCachedItems(), and then have the subtree logic in that
function.

[Xianzhu, 2015/02/05 17:57:03]

Done.

+            copyCachedSubtree(*newDisplayItem, updatedList, newCachedDisplayItemIndicesByClient);
+            continue;
+        }
+
+        if (newDisplayItem->isCached()) {
+            size_t index = findMatchingCachedItem(*newDisplayItem);
+            // The client previously produced an empty display item for the type.
+            if (index == kNotFound)
+                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());
+            newDisplayItem = m_paintList[index].release();
         }
-    }
-
-    // Copy over any remaining items that are validly cached.
-    for (; paintListIt != paintListEnd; ++paintListIt) {
-        if (clientCacheIsValid((*paintListIt)->client()))
-            appendDisplayItem(updatedList, newCachedClients, paintListIt->release());
+        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
@@ -133,12 +158,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");
@@ -153,7 +181,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)
 {