Title: [132990] trunk/Source/WebCore
- Revision
- 132990
- Author
- [email protected]
- Date
- 2012-10-30 23:48:11 -0700 (Tue, 30 Oct 2012)
Log Message
RoboHornetPro spends ~25% of total test time in WebCore::Region::Shape methods
https://bugs.webkit.org/show_bug.cgi?id=98800
Reviewed by Sam Weinig.
This patch brings our total RoboHornetPro time from 8.2 seconds to 5.3 seconds!
OverlapMap previously used Regions to track Layer bounds rects.
Unfortunately unioning a list of Regions is O(N^2)
where N is the number of Shapes (in this case rects).
This is because Shapes are immutable, so to union two shapes, we copy
both Shapes' segment/span vectors into a single new Shape.
Thus if we union a set of M Regions, each with 1 Shape, we'll end up copying
the segments of the first Shape N times before we have the final Region/Shape
and the second shape N-1 times. The sum of 1 to N is (N*(N-1))/2 aka order N^2.
Fixing the N^2 algorithm covered by https://bugs.webkit.org/show_bug.cgi?id=100814.
For now we just avoid this O(N^2) by moving away from Region, since OverlapMap
doesn't need it. We just collect a vector of the layer rects and hit-test that directly.
Hit-testing the rect list is O(N), just like hit-testing the same information in a Region would be.
Even better for us is that the OverlapMap is never even used in RoboHornetPro.
We just collect these rects to end up doing nothing with them. :)
* rendering/RenderLayerCompositor.cpp:
(WebCore::RenderLayerCompositor::OverlapMap::add):
(WebCore::RenderLayerCompositor::OverlapMap::overlapsLayers):
(WebCore::RenderLayerCompositor::OverlapMap::pushCompositingContainer):
(WebCore::RenderLayerCompositor::OverlapMap::popCompositingContainer):
(RenderLayerCompositor::OverlapMap):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (132989 => 132990)
--- trunk/Source/WebCore/ChangeLog 2012-10-31 06:17:38 UTC (rev 132989)
+++ trunk/Source/WebCore/ChangeLog 2012-10-31 06:48:11 UTC (rev 132990)
@@ -1,3 +1,36 @@
+2012-10-30 Eric Seidel <[email protected]>
+
+ RoboHornetPro spends ~25% of total test time in WebCore::Region::Shape methods
+ https://bugs.webkit.org/show_bug.cgi?id=98800
+
+ Reviewed by Sam Weinig.
+
+ This patch brings our total RoboHornetPro time from 8.2 seconds to 5.3 seconds!
+
+ OverlapMap previously used Regions to track Layer bounds rects.
+ Unfortunately unioning a list of Regions is O(N^2)
+ where N is the number of Shapes (in this case rects).
+ This is because Shapes are immutable, so to union two shapes, we copy
+ both Shapes' segment/span vectors into a single new Shape.
+ Thus if we union a set of M Regions, each with 1 Shape, we'll end up copying
+ the segments of the first Shape N times before we have the final Region/Shape
+ and the second shape N-1 times. The sum of 1 to N is (N*(N-1))/2 aka order N^2.
+ Fixing the N^2 algorithm covered by https://bugs.webkit.org/show_bug.cgi?id=100814.
+
+ For now we just avoid this O(N^2) by moving away from Region, since OverlapMap
+ doesn't need it. We just collect a vector of the layer rects and hit-test that directly.
+ Hit-testing the rect list is O(N), just like hit-testing the same information in a Region would be.
+
+ Even better for us is that the OverlapMap is never even used in RoboHornetPro.
+ We just collect these rects to end up doing nothing with them. :)
+
+ * rendering/RenderLayerCompositor.cpp:
+ (WebCore::RenderLayerCompositor::OverlapMap::add):
+ (WebCore::RenderLayerCompositor::OverlapMap::overlapsLayers):
+ (WebCore::RenderLayerCompositor::OverlapMap::pushCompositingContainer):
+ (WebCore::RenderLayerCompositor::OverlapMap::popCompositingContainer):
+ (RenderLayerCompositor::OverlapMap):
+
2012-10-30 Beth Dakin <[email protected]>
https://bugs.webkit.org/show_bug.cgi?id=100813
Modified: trunk/Source/WebCore/rendering/RenderLayerCompositor.cpp (132989 => 132990)
--- trunk/Source/WebCore/rendering/RenderLayerCompositor.cpp 2012-10-31 06:17:38 UTC (rev 132989)
+++ trunk/Source/WebCore/rendering/RenderLayerCompositor.cpp 2012-10-31 06:48:11 UTC (rev 132990)
@@ -95,7 +95,7 @@
// contribute to overlap as soon as their composited ancestor has been
// recursively processed and popped off the stack.
ASSERT(m_overlapStack.size() >= 2);
- m_overlapStack[m_overlapStack.size() - 2].unite(bounds);
+ m_overlapStack[m_overlapStack.size() - 2].append(bounds);
m_layers.add(layer);
}
@@ -106,7 +106,12 @@
bool overlapsLayers(const IntRect& bounds) const
{
- return m_overlapStack.last().intersects(bounds);
+ const RectList& layerRects = m_overlapStack.last();
+ for (unsigned i = 0; i < layerRects.size(); i++) {
+ if (layerRects[i].intersects(bounds))
+ return true;
+ }
+ return false;
}
bool isEmpty()
@@ -116,19 +121,20 @@
void pushCompositingContainer()
{
- m_overlapStack.append(Region());
+ m_overlapStack.append(RectList());
}
void popCompositingContainer()
{
- m_overlapStack[m_overlapStack.size() - 2].unite(m_overlapStack.last());
+ m_overlapStack[m_overlapStack.size() - 2].append(m_overlapStack.last());
m_overlapStack.removeLast();
}
-
+
RenderGeometryMap& geometryMap() { return m_geometryMap; }
private:
- Vector<Region> m_overlapStack;
+ typedef Vector<IntRect> RectList;
+ Vector<RectList> m_overlapStack;
HashSet<const RenderLayer*> m_layers;
RenderGeometryMap m_geometryMap;
};
_______________________________________________
webkit-changes mailing list
[email protected]
http://lists.webkit.org/mailman/listinfo/webkit-changes
