First version of new merge algorithm (not enabled yet)

Source/platform/graphics/paint/DisplayItemList.h

Index: Source/platform/graphics/paint/DisplayItemList.h
diff --git a/Source/platform/graphics/paint/DisplayItemList.h b/Source/platform/graphics/paint/DisplayItemList.h
index c1949ad0a9d3f2bfdb2140a9089bf7e687794d61..de674c59fd576242c25d0e95152aa455722574a0 100644
--- a/Source/platform/graphics/paint/DisplayItemList.h
+++ b/Source/platform/graphics/paint/DisplayItemList.h
@@ -7,6 +7,7 @@
 
 #include "platform/PlatformExport.h"
 #include "platform/graphics/paint/DisplayItem.h"
+#include "wtf/HashMap.h"
 #include "wtf/HashSet.h"
 #include "wtf/PassOwnPtr.h"
 #include "wtf/Vector.h"
@@ -25,7 +26,7 @@ public:
 
     void endNewPaints() { updatePaintList(); }
 
-    const PaintList& paintList();
+    const PaintList& paintList() const;
     void add(WTF::PassOwnPtr<DisplayItem>);
 
     void invalidate(DisplayItemClient);
@@ -43,17 +44,31 @@ protected:
     DisplayItemList() { };
 
 private:
-    PaintList::iterator findNextMatchingCachedItem(PaintList::iterator, const DisplayItem&);
-    bool wasInvalidated(const DisplayItem&) const;
-    void updatePaintList();
+    friend class DrawingRecorderTest;
+    friend class ViewDisplayListTest;
 
 #ifndef NDEBUG
     WTF::String paintListAsDebugString(const PaintList&) const;
 #endif
 
+    void updatePaintList();
+
+    typedef HashSet<DisplayItemClient> DisplayItemClientSet;
+    typedef HashMap<DisplayItem::Id, size_t> DisplayItemIndexMap;
+
+    size_t findDisplayItemById(const DisplayItem::Id&) const;
+    size_t findMatchingCachedItem(const DisplayItem&) const;
+
+    static void appendDisplayItem(WTF::PassOwnPtr<DisplayItem>, PaintList&, DisplayItemClientSet&, DisplayItemIndexMap&);
+    void copyCachedSubtree(const DisplayItem&, PaintList&, DisplayItemClientSet&, DisplayItemIndexMap&);
+
     PaintList m_paintList;
-    HashSet<DisplayItemClient> m_cachedClients;
+    DisplayItemClientSet m_cachedClients;

[pdr., 2015/02/04 05:19:58]

We're adding a lot of complexity (exposing Id, hashing Id, two hash tables, and
keeping the map and set synced) for what may not be a lot of gain. What's the
maximum set of unique ids any given client can have? I wonder if it would be
both faster and simpler to track a HashSet<client, Vector<DisplayItemClient>>?

[Xianzhu, 2015/02/04 20:46:32]

Actually the method was used in an older version of the new merge algorithm
(https://codereview.chromium.org/847783003/#ps200001). It was based on the
implication that the number and order of all new display items of a
non-invalidated client match those of all cached display items of the client.
With this implication, the algorithm can be simpler (and we don't need unique
display item ids). Some drawbacks might be:

- we must keep all empty BeginSubtree/EndSubtree display item pairs (as well as
dummy display items) whose number can be very large. Based on my test more than
50% of the paint list are these empty pairs;

- it prevents us from doing more optimizations (crbug.com/451090), e.g. adding a
child without invalidating the parent if the parent's drawings are not affected.

I think we can use the vector method first at least, and evaluate if it's worth
to avoid the above drawbacks.

+    DisplayItemIndexMap m_displayItemIndexMap;

[pdr., 2015/02/04 05:19:58]

Can you add a comment here saying that this maps from display item to an index
in the paint list?

     PaintList m_newPaints;
+#if ENABLE(ASSERT)
+    HashSet<DisplayItem::Id> m_newPaintIds;
+#endif
 };
 
 } // namespace blink