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..27cce029205a86745b28db4c0de50ca04460d409 100644
--- a/Source/platform/graphics/paint/DisplayItemList.cpp
+++ b/Source/platform/graphics/paint/DisplayItemList.cpp
@@ -15,7 +15,7 @@
 
 namespace blink {
 
-const PaintList& DisplayItemList::paintList()
+const PaintList& DisplayItemList::paintList() const
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
     ASSERT(m_newPaints.isEmpty());
@@ -25,12 +25,33 @@ const PaintList& DisplayItemList::paintList()
 void DisplayItemList::add(WTF::PassOwnPtr<DisplayItem> displayItem)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
+    if (displayItem->isEnd()) {
+        ASSERT(!m_newPaints.isEmpty());
+        if (m_newPaints.last()->isBegin()) {
+            ASSERT(displayItem->isEndAndPairedWith(*m_newPaints.last()));
+            // Remove empty pairs.

[chrishtr, 2015/02/03 00:39:00]

Why bother to clean these out?

[Xianzhu, 2015/02/03 01:57:12]

Without this, most of the display items in a paint list would be empty
BeginSubtree/EndSubtree pairs.

Tested ViewDisplayListTest.FullDocumentPaintingWithCaret without this, and it
produced 30 display items (originally 2). With this code, we generate 10 display
items (see the patched ViewDisplayListTest.cpp).

+#if ENABLE(ASSERT)
+            m_newPaintIds.remove(m_newPaints.last()->id());
+#endif
+            m_newPaints.removeLast();
+            return;
+        }
+    }
+#if ENABLE(ASSERT)
+    if (RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled()) {
+        ASSERT(!m_newPaintIds.contains(displayItem->id()));
+        if (displayItem->isDrawing() || displayItem->isBeginSubtree())
+            m_newPaintIds.add(displayItem->id());
+    }
+#endif
     m_newPaints.append(displayItem);
 }
 
 void DisplayItemList::invalidate(DisplayItemClient client)
 {
     ASSERT(RuntimeEnabledFeatures::slimmingPaintEnabled());
+    // Can only be called during layout/paintInvalidation, not during painting.
+    ASSERT(m_newPaints.isEmpty());
     m_cachedClients.remove(client);
 }
 
@@ -48,36 +69,56 @@ bool DisplayItemList::clientCacheIsValid(DisplayItemClient client) const
     return RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled() && m_cachedClients.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();
+    ASSERT(displayItem.isCached());
+    ASSERT(clientCacheIsValid(displayItem.client()));
 
-    if (!clientCacheIsValid(displayItem.client()))
-        return end;
+    DisplayItem::Id drawingDisplayItemId(displayItem.client(), DisplayItem::cachedTypeToDrawingType(displayItem.type()));
+    DisplayItemIndexMap::const_iterator it = m_displayItemIndexMap.find(drawingDisplayItemId);
+    return it == m_displayItemIndexMap.end() ? kNotFound : it->value;
+}
 
-    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;
-    }
+void DisplayItemList::appendDisplayItem(PassOwnPtr<DisplayItem> displayItem, PaintList& list, DisplayItemClientSet& cachedClients, DisplayItemIndexMap& displayItemIndexMap)
+{
+    const DisplayItem::Id& id = displayItem->id();
+    list.append(displayItem);
+    cachedClients.add(id.client);
 
-    ASSERT_NOT_REACHED();
-    return end;
+    // For now we only need to map Drawing and BeginSubtree display items.
+    if (!list.last()->isDrawing() && !list.last()->isBeginSubtree())
+        return;
+    ASSERT(!displayItemIndexMap.contains(id));
+    displayItemIndexMap.add(id, list.size() - 1);
 }
 
-static void appendDisplayItem(PaintList& list, HashSet<DisplayItemClient>& clients, WTF::PassOwnPtr<DisplayItem> displayItem)
+void DisplayItemList::copyCachedSubtree(const DisplayItem& displayItem, PaintList& list, DisplayItemClientSet& cachedClients, DisplayItemIndexMap& displayItemIndexMap)
 {
-    clients.add(displayItem->client());
-    list.append(displayItem);
+    ASSERT(displayItem.isSubtreeCached());
+    ASSERT(clientCacheIsValid(displayItem.client()));
+
+    DisplayItem::Id beginSubtreeDisplayItemId(displayItem.client(), DisplayItem::subtreeCachedTypeToBeginSubtreeType(displayItem.type()));
+    DisplayItemIndexMap::const_iterator it = m_displayItemIndexMap.find(beginSubtreeDisplayItemId);
+    if (it == m_displayItemIndexMap.end())
+        return;

[chrishtr, 2015/02/03 00:39:00]

Don't you want to insert the CachedSubtreeDisplayItem in this case?

[Xianzhu, 2015/02/03 01:57:12]

No. This is a valid case that the subtree previously produced nothing. We don't
store empty BeginSubtree/EndSubtree pairs otherwise there would be too many of
them.

Added comments about the case.

+
+    DisplayItem::Id endSubtreeId(displayItem.client(), DisplayItem::subtreeCachedTypeToEndSubtreeType(displayItem.type()));
+    for (size_t i = it->value; ; ++i) {
+        if (clientCacheIsValid(m_paintList[i]->client()))
+            appendDisplayItem(m_paintList[i].release(), list, cachedClients, displayItemIndexMap);
+        if (list.last()->id() == endSubtreeId)
+            break;
+    }

[chrishtr, 2015/02/03 00:39:00]

Add an assert that it found the endSubtreeId. Better yet, why not look up the
index of the first and last in the displayItemIndexMap, and do a simple for loop
count between them?

[Xianzhu, 2015/02/03 01:57:12]

Looping between first/last looks clearer. Done.

In this patch only Drawing and BeginSubtree display items are mapped. The
limitation seems not necessary. Removed it.

 }
 
 // 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.
+// The algorithm is O(|existing paint list| + |newly painted list|):
+// - For CachedDisplayItem, copy the corresponding cached DrawingDisplayItem;
+// - For SubtreeCachedDisplayItem, copy the cached display items from the
+//   corresponding BeginSubtreeDisplayItem and EndSubtreeDisplayItem;
+// - Otherwise, copy the new display item.
 void DisplayItemList::updatePaintList()
 {
     if (!RuntimeEnabledFeatures::slimmingPaintDisplayItemCacheEnabled()) {
@@ -88,44 +129,36 @@ void DisplayItemList::updatePaintList()
     }
 
     PaintList updatedList;
+    DisplayItemIndexMap newDisplayItemIndexMap;
     HashSet<DisplayItemClient> newCachedClients;
 
-    PaintList::iterator paintListIt = m_paintList.begin();
-    PaintList::iterator paintListEnd = m_paintList.end();
-
     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()) {

[chrishtr, 2015/02/03 00:39:00]

Subtree cached can be thought of as a type of cached, right? Then you can use
the same helper method to map from cached display item to non-cached.
Then if you add a fallback to the existing cached item if the non-cached is not
present, you can also avoid the 'continue' jumps.

[Xianzhu, 2015/02/03 01:57:12]

There seems little code to share by SubtreeCached and normal Cached (extracted
findDisplayItemById though in the new patch set).

The 'continue' jumps is to skip the display item which previously generated
nothing (empty subtree or empty picture), so seems unavoidable. (I could use a
bool variable to avoid the 'continue's but this seems no better).

The patch in https://codereview.chromium.org/847783003/ used the 'not-found'
result as an indicator of under-invalidation and appended the cached display
items into paint list to draw visual indications. However, the method is far
from complete to detect under-invalidations, and requires us to keep empty
display items (which was also a must when we used linear storage, but not
necessary when we use the map).

+            copyCachedSubtree(*newDisplayItem, updatedList, newCachedClients, newDisplayItemIndexMap);
+            continue;
+        }
+
+        if (newDisplayItem->isCached()) {
+            size_t index = findMatchingCachedItem(*newDisplayItem);
+            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(newDisplayItem.release(), updatedList, newCachedClients, newDisplayItemIndexMap);
     }
 
     m_newPaints.clear();
     m_paintList.clear();
     m_paintList.swap(updatedList);
+    m_displayItemIndexMap.clear();
+    m_displayItemIndexMap.swap(newDisplayItemIndexMap);
     m_cachedClients.clear();
     m_cachedClients.swap(newCachedClients);
+#if ENABLE(ASSERT)
+    m_newPaintIds.clear();
+#endif
 }
 
 #ifndef NDEBUG
@@ -133,12 +166,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 +189,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)
 {