- Revision
- 116538
- Author
- [email protected]
- Date
- 2012-05-09 10:01:16 -0700 (Wed, 09 May 2012)
Log Message
Early-out and avoid any copying when possible for Region operations
https://bugs.webkit.org/show_bug.cgi?id=85260
Reviewed by Anders Carlsson.
Source/WebCore:
For an empty region, any intersection or subtraction will not modify
the region, so we can simply return instead of creating a new Shape
and replacing the current empty Shape.
When a region is united with a region it contains, the orignal
containing region is the result. So, if A.unite(B) and A.contains(B)
then A does not need to change at all and we can return without making
a copy of A's shape. When A is a rect, we can do this test even more
simply.
We also remove redundant checks from trySimpleOperation() methods, where
the test is already done in the Region calling site.
This change improves the performance of the Region overlap testing for
composited layers, and allows us to avoid unnecessary copies of the
Region during unite. With a layout test (attached to bug #81087), that
creates a Region from the union of 225 composited layers, as well as
600 overlapping layers above them, this change decreases the running
time of the test by 3.2% by avoiding a copy of the entire Region for
each insertion that does not change the resulting Region.
Unit tests: RegionTest.unite
* platform/graphics/Region.cpp:
(WebCore::Region::Shape::UnionOperation::trySimpleOperation):
(WebCore::Region::Shape::IntersectOperation::trySimpleOperation):
(WebCore::Region::Shape::SubtractOperation::trySimpleOperation):
(WebCore::Region::intersect):
(WebCore::Region::unite):
(WebCore::Region::subtract):
* platform/graphics/Region.h:
(WebCore::Region::isRect):
(WebCore::Region::Shape::isRect):
Source/WebKit/chromium:
* tests/RegionTest.cpp:
(WebCore::TEST):
(WebCore):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (116537 => 116538)
--- trunk/Source/WebCore/ChangeLog 2012-05-09 16:32:57 UTC (rev 116537)
+++ trunk/Source/WebCore/ChangeLog 2012-05-09 17:01:16 UTC (rev 116538)
@@ -1,3 +1,44 @@
+2012-05-09 Dana Jansens <[email protected]>
+
+ Early-out and avoid any copying when possible for Region operations
+ https://bugs.webkit.org/show_bug.cgi?id=85260
+
+ Reviewed by Anders Carlsson.
+
+ For an empty region, any intersection or subtraction will not modify
+ the region, so we can simply return instead of creating a new Shape
+ and replacing the current empty Shape.
+
+ When a region is united with a region it contains, the orignal
+ containing region is the result. So, if A.unite(B) and A.contains(B)
+ then A does not need to change at all and we can return without making
+ a copy of A's shape. When A is a rect, we can do this test even more
+ simply.
+
+ We also remove redundant checks from trySimpleOperation() methods, where
+ the test is already done in the Region calling site.
+
+ This change improves the performance of the Region overlap testing for
+ composited layers, and allows us to avoid unnecessary copies of the
+ Region during unite. With a layout test (attached to bug #81087), that
+ creates a Region from the union of 225 composited layers, as well as
+ 600 overlapping layers above them, this change decreases the running
+ time of the test by 3.2% by avoiding a copy of the entire Region for
+ each insertion that does not change the resulting Region.
+
+ Unit tests: RegionTest.unite
+
+ * platform/graphics/Region.cpp:
+ (WebCore::Region::Shape::UnionOperation::trySimpleOperation):
+ (WebCore::Region::Shape::IntersectOperation::trySimpleOperation):
+ (WebCore::Region::Shape::SubtractOperation::trySimpleOperation):
+ (WebCore::Region::intersect):
+ (WebCore::Region::unite):
+ (WebCore::Region::subtract):
+ * platform/graphics/Region.h:
+ (WebCore::Region::isRect):
+ (WebCore::Region::Shape::isRect):
+
2012-05-09 Tommy Widenflycht <[email protected]>
MediaStream API: SessionDescription::addCandidate should not crash for malformed input
Modified: trunk/Source/WebCore/platform/graphics/Region.cpp (116537 => 116538)
--- trunk/Source/WebCore/platform/graphics/Region.cpp 2012-05-09 16:32:57 UTC (rev 116537)
+++ trunk/Source/WebCore/platform/graphics/Region.cpp 2012-05-09 17:01:16 UTC (rev 116538)
@@ -487,11 +487,6 @@
return true;
}
- if (shape2.isEmpty()) {
- result = shape1;
- return true;
- }
-
return false;
}
@@ -509,18 +504,8 @@
}
struct Region::Shape::IntersectOperation {
- static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Shape& result)
+ static bool trySimpleOperation(const Shape&, const Shape&, Shape&)
{
- if (shape1.isEmpty()) {
- result = Shape();
- return true;
- }
-
- if (shape2.isEmpty()) {
- result = shape1;
- return true;
- }
-
return false;
}
@@ -538,14 +523,8 @@
}
struct Region::Shape::SubtractOperation {
- static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Region::Shape& result)
+ static bool trySimpleOperation(const Shape&, const Shape&, Region::Shape&)
{
-
- if (shape1.isEmpty() || shape2.isEmpty()) {
- result = Shape();
- return true;
- }
-
return false;
}
@@ -573,6 +552,8 @@
void Region::intersect(const Region& region)
{
+ if (m_bounds.isEmpty())
+ return;
if (!m_bounds.intersects(region.m_bounds)) {
m_shape = Shape();
m_bounds = IntRect();
@@ -589,6 +570,16 @@
{
if (region.isEmpty())
return;
+ if (isRect() && m_bounds.contains(region.m_bounds))
+ return;
+ if (region.isRect() && region.m_bounds.contains(m_bounds)) {
+ m_shape = region.m_shape;
+ m_bounds = region.m_bounds;
+ return;
+ }
+ // FIXME: We may want another way to construct a Region without doing this test when we expect it to be false.
+ if (!isRect() && contains(region))
+ return;
Shape unitedShape = Shape::unionShapes(m_shape, region.m_shape);
@@ -598,6 +589,8 @@
void Region::subtract(const Region& region)
{
+ if (m_bounds.isEmpty())
+ return;
if (region.isEmpty())
return;
if (!m_bounds.intersects(region.m_bounds))
Modified: trunk/Source/WebCore/platform/graphics/Region.h (116537 => 116538)
--- trunk/Source/WebCore/platform/graphics/Region.h 2012-05-09 16:32:57 UTC (rev 116537)
+++ trunk/Source/WebCore/platform/graphics/Region.h 2012-05-09 17:01:16 UTC (rev 116538)
@@ -38,6 +38,7 @@
IntRect bounds() const { return m_bounds; }
bool isEmpty() const { return m_bounds.isEmpty(); }
+ bool isRect() const { return m_shape.isRect(); }
Vector<IntRect> rects() const;
@@ -79,6 +80,7 @@
IntRect bounds() const;
bool isEmpty() const { return m_spans.isEmpty(); }
+ bool isRect() const { return m_spans.size() <= 2 && m_segments.size() <= 2; }
typedef const Span* SpanIterator;
SpanIterator spans_begin() const;
Modified: trunk/Source/WebKit/chromium/ChangeLog (116537 => 116538)
--- trunk/Source/WebKit/chromium/ChangeLog 2012-05-09 16:32:57 UTC (rev 116537)
+++ trunk/Source/WebKit/chromium/ChangeLog 2012-05-09 17:01:16 UTC (rev 116538)
@@ -1,3 +1,14 @@
+2012-05-09 Dana Jansens <[email protected]>
+
+ Early-out and avoid any copying when possible for Region operations
+ https://bugs.webkit.org/show_bug.cgi?id=85260
+
+ Reviewed by Anders Carlsson.
+
+ * tests/RegionTest.cpp:
+ (WebCore::TEST):
+ (WebCore):
+
2012-05-09 Tommy Widenflycht <[email protected]>
[chromium] MediaStream API: Fixing a memory leak in WebUserMediaRequest
Modified: trunk/Source/WebKit/chromium/tests/RegionTest.cpp (116537 => 116538)
--- trunk/Source/WebKit/chromium/tests/RegionTest.cpp 2012-05-09 16:32:57 UTC (rev 116537)
+++ trunk/Source/WebKit/chromium/tests/RegionTest.cpp 2012-05-09 17:01:16 UTC (rev 116538)
@@ -362,4 +362,33 @@
TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20));
}
+TEST(RegionTest, unite)
+{
+ Region r;
+ Region r2;
+
+ // A rect uniting a contained rect does not change the region.
+ r2 = r = IntRect(0, 0, 50, 50);
+ r2.unite(IntRect(20, 20, 10, 10));
+ EXPECT_EQ(r, r2);
+
+ // A rect uniting a containing rect gives back the containing rect.
+ r = IntRect(0, 0, 50, 50);
+ r.unite(IntRect(0, 0, 100, 100));
+ EXPECT_EQ(Region(IntRect(0, 0, 100, 100)), r);
+
+ // A complex region uniting a contained rect does not change the region.
+ r = IntRect(0, 0, 50, 50);
+ r.unite(IntRect(100, 0, 50, 50));
+ r2 = r;
+ r2.unite(IntRect(20, 20, 10, 10));
+ EXPECT_EQ(r, r2);
+
+ // A complex region uniting a containing rect gives back the containing rect.
+ r = IntRect(0, 0, 50, 50);
+ r.unite(IntRect(100, 0, 50, 50));
+ r. unite(IntRect(0, 0, 500, 500));
+ EXPECT_EQ(Region(IntRect(0, 0, 500, 500)), r);
+}
+
} // namespace
