Changeset 116538 in webkit

Timestamp:

May 9, 2012 10:01:16 AM (12 years ago)

Author:

danakj@chromium.org

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):

Location:

trunk/Source

Files:

• WebCore/ChangeLog (modified) (1 diff)
• WebCore/platform/graphics/Region.cpp (modified) (6 diffs)
• WebCore/platform/graphics/Region.h (modified) (2 diffs)
• WebKit/chromium/ChangeLog (modified) (1 diff)
• WebKit/chromium/tests/RegionTest.cpp (modified) (1 diff)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2012-05-09  Dana Jansens  <danakj@chromium.org>
+
+        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  <tommyw@google.com>
 

trunk/Source/WebCore/platform/graphics/Region.cpp

@@ -488 +488 @@
         }
         
-        if (shape2.isEmpty()) {
-            result = shape1;
-            return true;
-        }
-
         return false;
     }
@@ -510 +505 @@
 
 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;
     }
@@ -539 +524 @@
 
 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;
     }
@@ -574 +553 @@
 void Region::intersect(const Region& region)
 {
+    if (m_bounds.isEmpty())
+        return;
     if (!m_bounds.intersects(region.m_bounds)) {
         m_shape = Shape();
@@ -590 +571 @@
     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);
@@ -599 +590 @@
 void Region::subtract(const Region& region)
 {
+    if (m_bounds.isEmpty())
+        return;
     if (region.isEmpty())
         return;

trunk/Source/WebCore/platform/graphics/Region.h

@@ -39 +39 @@
     IntRect bounds() const { return m_bounds; }
     bool isEmpty() const { return m_bounds.isEmpty(); }
+    bool isRect() const { return m_shape.isRect(); }
 
     Vector<IntRect> rects() const;
@@ -80 +81 @@
         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;

trunk/Source/WebKit/chromium/ChangeLog

@@ +1 @@
+2012-05-09  Dana Jansens  <danakj@chromium.org>
+
+        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  <tommyw@google.com>
 

trunk/Source/WebKit/chromium/tests/RegionTest.cpp

@@ -363 +363 @@
 }
 
+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