First version of new merge algorithm (not enabled yet)

Source/platform/graphics/paint/DisplayItemList.h

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef DisplayItemList_h
 #define DisplayItemList_h
 
 #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"
 
 namespace blink {
 
 class GraphicsContext;
 
 typedef Vector<OwnPtr<DisplayItem>> PaintList;
 
 class PLATFORM_EXPORT DisplayItemList {
     WTF_MAKE_NONCOPYABLE(DisplayItemList);
     WTF_MAKE_FAST_ALLOCATED;
 public:
     static PassOwnPtr<DisplayItemList> create() { return adoptPtr(new DisplayItemList); }
 
     void endNewPaints() { updatePaintList(); }
 
-    const PaintList& paintList();
+    const PaintList& paintList() const;
     void add(WTF::PassOwnPtr<DisplayItem>);
 
     void invalidate(DisplayItemClient);
     void invalidateAll();
     bool clientCacheIsValid(DisplayItemClient) const;
 
     // Plays back the current PaintList() into the given context.
     void replay(GraphicsContext*);
 
 #ifndef NDEBUG
     void showDebugData() const;
 #endif
 
 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
 
 #endif // DisplayItemList_h