Bug 118764 – Optimize RenderLayerCompositor's OverlapMap

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Simon Fraser (smfr)]

OverlapMap::overlapsLayers() can end up doing hundreds of rect intersections on some content. This can be optimized if we keep a bounding rect of the list of rects.

[Simon Fraser (smfr)]

Kinda patch:

diff --git a/Source/WebCore/rendering/RenderLayerCompositor.cpp b/Source/WebCore/rendering/RenderLayerCompositor.cpp
index 26bcdfd087d333112f630ebc93387b1c8f19a6ed..05da81d52cda0b3812c0a4c3cbc0603974b465c4 100644
--- a/Source/WebCore/rendering/RenderLayerCompositor.cpp
+++ b/Source/WebCore/rendering/RenderLayerCompositor.cpp
@@ -99,6 +99,9 @@ static const double throttledLayerFlushDelay = .5;
 
 using namespace HTMLNames;
 
+static size_t totalRectCompares = 0;
+static size_t totalTries = 0;
+
 class RenderLayerCompositor::OverlapMap {
     WTF_MAKE_NONCOPYABLE(OverlapMap);
 public:
@@ -128,12 +131,7 @@ public:
 
     bool overlapsLayers(const IntRect& bounds) const
     {
-        const RectList& layerRects = m_overlapStack.last();
-        for (unsigned i = 0; i < layerRects.size(); i++) {
-            if (layerRects[i].intersects(bounds))
-                return true;
-        }
-        return false;
+        return m_overlapStack.last().intersects(bounds);
     }
 
     bool isEmpty()
@@ -148,14 +146,50 @@ public:
 
     void popCompositingContainer()
     {
-        m_overlapStack[m_overlapStack.size() - 2].appendVector(m_overlapStack.last());
+        m_overlapStack[m_overlapStack.size() - 2].append(m_overlapStack.last());
         m_overlapStack.removeLast();
     }
 
     RenderGeometryMap& geometryMap() { return m_geometryMap; }
 
 private:
-    typedef Vector<IntRect> RectList;
+    struct RectList {
+        Vector<IntRect> rects;
+        IntRect boundingRect;
+        
+        void append(const IntRect& rect)
+        {
+            rects.append(rect);
+            boundingRect.unite(rect);
+        }
+
+        void append(const RectList& rectList)
+        {
+            rects.appendVector(rectList.rects);
+            boundingRect.unite(rectList.boundingRect);
+        }
+        
+        bool intersects(const IntRect& rect) const
+        {
+            if (!rects.size())
+                return false;
+            ++totalTries;
+            if (!boundingRect.intersects(rect)) {
+                WTFLogAlways("bounding rect early return\n");
+                return false;
+            }
+
+            for (unsigned i = 0; i < rects.size(); i++) {
+                if (rects[i].intersects(rect)) {
+                    totalRectCompares += i;
+                    return true;
+                }
+            }
+            totalRectCompares += rects.size();
+            return false;
+        }
+    };
+
     Vector<RectList> m_overlapStack;
     HashSet<const RenderLayer*> m_layers;
     RenderGeometryMap m_geometryMap;
@@ -652,6 +686,10 @@ void RenderLayerCompositor::updateCompositingLayers(CompositingUpdateType update
         // most of the time, geometry is updated via RenderLayer::styleChanged().
         updateLayerTreeGeometry(updateRoot, 0);
     }
+
+
+    WTFLogAlways("Mean rect compares %.2f (%zu tries)\n", (double)totalRectCompares / totalTries, totalTries);
+
     
 #if !LOG_DISABLED
     if (compositingLogEnabled() && isFullUpdate && (needHierarchyUpdate || needGeometryUpdate)) {
@@ -1501,7 +1539,7 @@ void RenderLayerCompositor::updateLayerTreeGeometry(RenderLayer* layer, int dept
     if (RenderLayerBacking* layerBacking = layer->backing()) {
         // The compositing state of all our children has been updated already, so now
         // we can compute and cache the composited bounds for this layer.
-        layerBacking->updateCompositedBounds();
+//        layerBacking->updateCompositedBounds();
 
         if (RenderLayer* reflection = layer->reflectionLayer()) {
             if (reflection->backing())

[Simon Fraser (smfr)]

Created attachment 206891 [details]
Patch

[Simon Fraser (smfr)]

http://trac.webkit.org/changeset/152806