Raster display item lists via a visual rect RTree.

third_party/WebKit/Source/platform/graphics/paint/PaintController.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 PaintController_h
 #define PaintController_h
 
 #include "platform/PlatformExport.h"
 #include "platform/RuntimeEnabledFeatures.h"
 #include "platform/geometry/IntRect.h"
@@ skipping 105 matching lines @@
     // Returns the approximate memory usage, excluding memory likely to be
     // shared with the embedder after copying to WebPaintController.
     // Should only be called right after commitNewDisplayItems.
     size_t approximateUnsharedMemoryUsage() const;
 
     // Get the artifact generated after the last commit.
     const PaintArtifact& paintArtifact() const;
     const DisplayItemList& displayItemList() const { return paintArtifact().displayItemList(); }
     const Vector<PaintChunk>& paintChunks() const { return paintArtifact().paintChunks(); }
 
+    typedef WTF::HashMap<DisplayItemClient, IntRect> DisplayItemRectMap;

[esprehn, 2015/12/08 19:58:31]

Doesn't this approach the size of the layout tree if you invalidate paint on
many things? Every layout object is a client, so this map contains the entire
layout tree?

[wkorman, 2015/12/08 20:55:10]

I believe you are correct. We obviously won't enable this code path until/unless
we gain comfort with the memory/performance ramifications. When we submit it
will be behind a flag.

We know that we may need to explore alternate data structure/approach for better
memory efficiency, but expectation is that there is a worthwhile performance
gain for memory increase.

What is your level of concern re: the degenerate case where we store the entire
layout tree, in the big picture of overall Blink/Chrome memory usage and
haraken@'s analysis?

https://docs.google.com/presentation/d/1_LRxXp30j60npShHSRVit0B5tLOS4TLiZ68gQ...

[Xianzhu, 2015/12/09 17:09:27]

FYI I have converted DisplayItemClient to an interface, making it possible to
let PaintController access client data. We can add a method
DisplayItemClient::previousPaintBounds() and LayoutObject can just return its
m_previousPaintInvalidaitonRect.

+    const DisplayItemRectMap& displayItemVisualRects() const { return m_displayItemInvalidationRects; }
+
     bool clientCacheIsValid(DisplayItemClient) const;
     bool cacheIsEmpty() const { return m_currentPaintArtifact.isEmpty(); }
 
     bool displayItemConstructionIsDisabled() const { return m_constructionDisabled; }
     void setDisplayItemConstructionIsDisabled(const bool disable) { m_constructionDisabled = disable; }
 
     bool textPainted() const { return m_textPainted; }
     void setTextPainted() { m_textPainted = true; }
     bool imagePainted() const { return m_imagePainted; }
     void setImagePainted() { m_imagePainted = true; }
@@ skipping 95 matching lines @@
     // are known to be valid.
     // TODO(wangxianzhu): Use client side flag to avoid const of hash table.
     HashSet<DisplayItemClient> m_clientsCheckedPaintInvalidation;
 
 #if ENABLE(ASSERT)
     // Set of clients which had paint offset changes since the last commit. This is used for
     // ensuring paint offsets are only updated once and are the same in all phases.
     HashSet<DisplayItemClient> m_clientsWithPaintOffsetInvalidations;
 #endif
 
+    DisplayItemRectMap m_displayItemInvalidationRects;
+
     // Allow display item construction to be disabled to isolate the costs of construction
     // in performance metrics.
     bool m_constructionDisabled;
 
     // Indicates this PaintController has ever had text. It is never reset to false.
     bool m_textPainted;
     bool m_imagePainted;
 
     int m_skippingCacheCount;
 
@@ skipping 11 matching lines @@
     // easily find where the duplicated ids are from.
     DisplayItemIndicesByClientMap m_newDisplayItemIndicesByClient;
 #endif
 
     OwnPtr<Vector<String>> m_trackedPaintInvalidationObjects;
 };
 
 } // namespace blink
 
 #endif // PaintController_h