New display item caching

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..9d23eb51960dd90fcef3c8415e895401e007383c 100644
--- a/Source/platform/graphics/paint/DisplayItemList.h
+++ b/Source/platform/graphics/paint/DisplayItemList.h
@@ -7,7 +7,7 @@
 
 #include "platform/PlatformExport.h"
 #include "platform/graphics/paint/DisplayItem.h"
-#include "wtf/HashSet.h"
+#include "wtf/HashMap.h"
 #include "wtf/PassOwnPtr.h"
 #include "wtf/Vector.h"
 
@@ -30,7 +30,7 @@ public:
 
     void invalidate(DisplayItemClient);
     void invalidateAll();
-    bool clientCacheIsValid(DisplayItemClient) const;
+    bool clientCacheIsValid(DisplayItemClient client) const { return m_cachedDisplayItemsInfoByClient.contains(client); }
 
     // Plays back the current PaintList() into the given context.
     void replay(GraphicsContext*);
@@ -43,16 +43,32 @@ protected:
     DisplayItemList() { };
 
 private:
-    PaintList::iterator findNextMatchingCachedItem(PaintList::iterator, const DisplayItem&);
-    bool wasInvalidated(const DisplayItem&) const;
+    size_t findNextMatchingCachedItem(const DisplayItem&);
     void updatePaintList();
 
 #ifndef NDEBUG
     WTF::String paintListAsDebugString(const PaintList&) const;
+    WTF::String cachedDisplayItemsInfoByClientAsDebugString() const;
 #endif
 
+    struct DisplayItemsInfo {
+        // A temporary offset of displayItemIndexes during updatePaintList() used as the
+        // starting point to find the next matching cached display item of the client.
+        // This helps reduce the complexity of finding the next matching display item
+        // from O(m*n) to O(m*n).

[chrishtr, 2015/01/22 20:13:07]

From O(m*n) to O(m*n)?

[Xianzhu, 2015/01/22 21:48:12]

Sorry, this should be "From O(m*n) to O(m+n)". The whole statement is also
inaccurate.

Updated.

+        // (m,n = number of existing/new display items of a client, respectively).
+        size_t updateOffset;
+
+        // Indexes into PaintList of all display items of a client.
+        Vector<size_t> displayItemIndexes;
+    };
+
+    typedef HashMap<DisplayItemClient, DisplayItemsInfo> DisplayItemsInfoByClientMap;
+    static void appendDisplayItem(PaintList&, DisplayItemsInfoByClientMap&, WTF::PassOwnPtr<DisplayItem>);
+    static void appendErrorIndicatorDisplayItem(PaintList&, DisplayItemsInfoByClientMap&, WTF::PassOwnPtr<DisplayItem>);
+
     PaintList m_paintList;
-    HashSet<DisplayItemClient> m_cachedClients;
+    DisplayItemsInfoByClientMap m_cachedDisplayItemsInfoByClient;
     PaintList m_newPaints;
 };