Changeset 116377 in webkit
- Timestamp:
- May 7, 2012 5:11:35 PM (12 years ago)
- Location:
- trunk/Source
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WebCore/ChangeLog
r116376 r116377 1 2012-05-07 Dana Jansens <danakj@chromium.org> 2 3 Region::intersects() and Region::contains() are slow due to copy overhead 4 https://bugs.webkit.org/show_bug.cgi?id=81076 5 6 Reviewed by Anders Carlsson. 7 8 Testing contains() and intersects() requires a copy which ends up 9 invoking a malloc on sufficiently complicated web pages, and slows down 10 the test unnecessarily. These methods can be done by iterating over the 11 Region::Shape values rather than making a copy of the entire region and 12 manipulating it. 13 14 This uses Region::Shape::compareShapes() to walk the query regions and 15 compute the result of the intersects or contains tests without making a 16 copy. 17 18 This change improves the performance of the Region overlap testing for 19 composited layers, and allows for testing contains() before unite() to 20 avoid unnecessary copies of the Region when inserting into complex 21 Regions. With a layout test that has 225 composited layers, and tests 22 Region.intersects() for 1000 layers above them, this change decreases 23 the running time of the test by 1.2% by avoiding a copy of the 225 24 rects each time. 25 26 Unit test: RegionTest.intersectsRegion 27 RegionTest.containsRegion 28 29 * platform/graphics/Region.cpp: 30 (WebCore::Region::contains): 31 (WebCore::Region::intersects): 32 (WebCore): 33 (WebCore::Region::Shape::compareShapes): 34 (Region::Shape::CompareContainsOperation): 35 (WebCore::Region::Shape::CompareContainsOperation::aOutsideB): 36 (WebCore::Region::Shape::CompareContainsOperation::bOutsideA): 37 (WebCore::Region::Shape::CompareContainsOperation::aOverlapsB): 38 (Region::Shape::CompareIntersectsOperation): 39 (WebCore::Region::Shape::CompareIntersectsOperation::aOutsideB): 40 (WebCore::Region::Shape::CompareIntersectsOperation::bOutsideA): 41 (WebCore::Region::Shape::CompareIntersectsOperation::aOverlapsB): 42 * platform/graphics/Region.h: 43 (Shape): 44 1 45 2012-05-07 David Tseng <dtseng@google.com> 2 46 -
trunk/Source/WebCore/platform/graphics/Region.cpp
r115716 r116377 71 71 return false; 72 72 73 return WebCore::intersect(region, *this) == region;73 return Shape::compareShapes<Shape::CompareContainsOperation>(m_shape, region.m_shape); 74 74 } 75 75 … … 107 107 return false; 108 108 109 // FIXME: this could be optimized. 110 Region tempRegion(*this); 111 tempRegion.intersect(region); 112 return !tempRegion.isEmpty(); 109 return Shape::compareShapes<Shape::CompareIntersectsOperation>(m_shape, region.m_shape); 113 110 } 114 111 … … 126 123 return totalArea; 127 124 } 125 126 template<typename CompareOperation> 127 bool Region::Shape::compareShapes(const Shape& aShape, const Shape& bShape) 128 { 129 bool result = CompareOperation::defaultResult; 130 131 Shape::SpanIterator aSpan = aShape.spans_begin(); 132 Shape::SpanIterator aSpanEnd = aShape.spans_end(); 133 Shape::SpanIterator bSpan = bShape.spans_begin(); 134 Shape::SpanIterator bSpanEnd = bShape.spans_end(); 135 136 bool aHadSegmentInPreviousSpan = false; 137 bool bHadSegmentInPreviousSpan = false; 138 while (aSpan != aSpanEnd && bSpan != bSpanEnd) { 139 int aY = aSpan->y; 140 int aMaxY = (aSpan + 1)->y; 141 int bY = bSpan->y; 142 int bMaxY = (bSpan + 1)->y; 143 144 Shape::SegmentIterator aSegment = aShape.segments_begin(aSpan); 145 Shape::SegmentIterator aSegmentEnd = aShape.segments_end(aSpan); 146 Shape::SegmentIterator bSegment = bShape.segments_begin(bSpan); 147 Shape::SegmentIterator bSegmentEnd = bShape.segments_end(bSpan); 148 149 // Look for a non-overlapping part of the spans. If B had a segment in its previous span, then we already tested A against B within that span. 150 bool aHasSegmentInSpan = aSegment != aSegmentEnd; 151 bool bHasSegmentInSpan = bSegment != bSegmentEnd; 152 if (aY < bY && !bHadSegmentInPreviousSpan && aHasSegmentInSpan && CompareOperation::aOutsideB(result)) 153 return result; 154 if (bY < aY && !aHadSegmentInPreviousSpan && bHasSegmentInSpan && CompareOperation::bOutsideA(result)) 155 return result; 156 157 aHadSegmentInPreviousSpan = aHasSegmentInSpan; 158 bHadSegmentInPreviousSpan = bHasSegmentInSpan; 159 160 bool spansOverlap = bMaxY > aY && bY < aMaxY; 161 if (spansOverlap) { 162 while (aSegment != aSegmentEnd && bSegment != bSegmentEnd) { 163 int aX = *aSegment; 164 int aMaxX = *(aSegment + 1); 165 int bX = *bSegment; 166 int bMaxX = *(bSegment + 1); 167 168 bool segmentsOverlap = bMaxX > aX && bX < aMaxX; 169 if (segmentsOverlap && CompareOperation::aOverlapsB(result)) 170 return result; 171 if (aX < bX && CompareOperation::aOutsideB(result)) 172 return result; 173 if (bX < aX && CompareOperation::bOutsideA(result)) 174 return result; 175 176 if (aMaxX < bMaxX) 177 aSegment += 2; 178 else if (bMaxX < aMaxX) 179 bSegment += 2; 180 else { 181 aSegment += 2; 182 bSegment += 2; 183 } 184 } 185 186 if (aSegment != aSegmentEnd && CompareOperation::aOutsideB(result)) 187 return result; 188 if (bSegment != bSegmentEnd && CompareOperation::bOutsideA(result)) 189 return result; 190 } 191 192 if (aMaxY < bMaxY) 193 aSpan += 1; 194 else if (bMaxY < aMaxY) 195 bSpan += 1; 196 else { 197 aSpan += 1; 198 bSpan += 1; 199 } 200 } 201 202 if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutsideB(result)) 203 return result; 204 if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutsideA(result)) 205 return result; 206 207 return result; 208 } 209 210 struct Region::Shape::CompareContainsOperation { 211 const static bool defaultResult = true; 212 inline static bool aOutsideB(bool& /* result */) { return false; } 213 inline static bool bOutsideA(bool& result) { result = false; return true; } 214 inline static bool aOverlapsB(bool& /* result */) { return false; } 215 }; 216 217 struct Region::Shape::CompareIntersectsOperation { 218 const static bool defaultResult = false; 219 inline static bool aOutsideB(bool& /* result */) { return false; } 220 inline static bool bOutsideA(bool& /* result */) { return false; } 221 inline static bool aOverlapsB(bool& result) { result = true; return true; } 222 }; 128 223 129 224 Region::Shape::Shape() -
trunk/Source/WebCore/platform/graphics/Region.h
r109851 r116377 96 96 void swap(Shape&); 97 97 98 struct CompareContainsOperation; 99 struct CompareIntersectsOperation; 100 101 template<typename CompareOperation> 102 static bool compareShapes(const Shape& shape1, const Shape& shape2); 103 98 104 #ifndef NDEBUG 99 105 void dump() const; -
trunk/Source/WebKit/chromium/ChangeLog
r116375 r116377 1 2012-05-07 Dana Jansens <danakj@chromium.org> 2 3 Region::intersects() and Region::contains() are slow due to copy overhead 4 https://bugs.webkit.org/show_bug.cgi?id=81076 5 6 Reviewed by Anders Carlsson. 7 8 * tests/RegionTest.cpp: 9 (WebCore): 10 (WebCore::TEST): 11 1 12 2012-05-07 Tony Chang <tony@chromium.org> 2 13 -
trunk/Source/WebKit/chromium/tests/RegionTest.cpp
r110704 r116377 125 125 } 126 126 127 #define TEST_NO_INTERSECT(a, b) \ 128 { \ 129 Region ar = a; \ 130 Region br = b; \ 131 EXPECT_FALSE(ar.intersects(br)); \ 132 EXPECT_FALSE(br.intersects(ar)); \ 133 } 134 135 #define TEST_INTERSECT(a, b) \ 136 { \ 137 Region ar = a; \ 138 Region br = b; \ 139 EXPECT_TRUE(ar.intersects(br)); \ 140 EXPECT_TRUE(br.intersects(ar)); \ 141 } 142 143 TEST(RegionTest, intersectsRegion) 144 { 145 Region r; 146 147 TEST_NO_INTERSECT(IntRect(), IntRect()); 148 TEST_NO_INTERSECT(IntRect(), IntRect(0, 0, 1, 1)); 149 TEST_NO_INTERSECT(IntRect(), IntRect(1, 1, 1, 1)); 150 151 r.unite(IntRect(0, 0, 1, 1)); 152 TEST_NO_INTERSECT(r, IntRect()); 153 TEST_INTERSECT(r, IntRect(0, 0, 1, 1)); 154 TEST_INTERSECT(r, IntRect(0, 0, 2, 2)); 155 TEST_INTERSECT(r, IntRect(-1, 0, 2, 2)); 156 TEST_INTERSECT(r, IntRect(-1, -1, 2, 2)); 157 TEST_INTERSECT(r, IntRect(0, -1, 2, 2)); 158 TEST_INTERSECT(r, IntRect(-1, -1, 3, 3)); 159 160 r.unite(IntRect(0, 0, 3, 3)); 161 r.unite(IntRect(10, 0, 3, 3)); 162 r.unite(IntRect(0, 10, 13, 3)); 163 TEST_NO_INTERSECT(r, IntRect()); 164 TEST_INTERSECT(r, IntRect(1, 1, 1, 1)); 165 TEST_INTERSECT(r, IntRect(0, 0, 2, 2)); 166 TEST_INTERSECT(r, IntRect(1, 0, 2, 2)); 167 TEST_INTERSECT(r, IntRect(1, 1, 2, 2)); 168 TEST_INTERSECT(r, IntRect(0, 1, 2, 2)); 169 TEST_INTERSECT(r, IntRect(0, 0, 3, 3)); 170 TEST_INTERSECT(r, IntRect(-1, -1, 2, 2)); 171 TEST_INTERSECT(r, IntRect(2, -1, 2, 2)); 172 TEST_INTERSECT(r, IntRect(2, 2, 2, 2)); 173 TEST_INTERSECT(r, IntRect(-1, 2, 2, 2)); 174 175 TEST_INTERSECT(r, IntRect(11, 1, 1, 1)); 176 TEST_INTERSECT(r, IntRect(10, 0, 2, 2)); 177 TEST_INTERSECT(r, IntRect(11, 0, 2, 2)); 178 TEST_INTERSECT(r, IntRect(11, 1, 2, 2)); 179 TEST_INTERSECT(r, IntRect(10, 1, 2, 2)); 180 TEST_INTERSECT(r, IntRect(10, 0, 3, 3)); 181 TEST_INTERSECT(r, IntRect(9, -1, 2, 2)); 182 TEST_INTERSECT(r, IntRect(12, -1, 2, 2)); 183 TEST_INTERSECT(r, IntRect(12, 2, 2, 2)); 184 TEST_INTERSECT(r, IntRect(9, 2, 2, 2)); 185 186 TEST_INTERSECT(r, IntRect(0, -1, 13, 5)); 187 TEST_INTERSECT(r, IntRect(1, -1, 11, 5)); 188 TEST_INTERSECT(r, IntRect(2, -1, 9, 5)); 189 TEST_INTERSECT(r, IntRect(2, -1, 8, 5)); 190 TEST_INTERSECT(r, IntRect(3, -1, 8, 5)); 191 TEST_NO_INTERSECT(r, IntRect(3, -1, 7, 5)); 192 193 TEST_INTERSECT(r, IntRect(0, 1, 13, 1)); 194 TEST_INTERSECT(r, IntRect(1, 1, 11, 1)); 195 TEST_INTERSECT(r, IntRect(2, 1, 9, 1)); 196 TEST_INTERSECT(r, IntRect(2, 1, 8, 1)); 197 TEST_INTERSECT(r, IntRect(3, 1, 8, 1)); 198 TEST_NO_INTERSECT(r, IntRect(3, 1, 7, 1)); 199 200 TEST_INTERSECT(r, IntRect(0, 0, 13, 13)); 201 TEST_INTERSECT(r, IntRect(0, 1, 13, 11)); 202 TEST_INTERSECT(r, IntRect(0, 2, 13, 9)); 203 TEST_INTERSECT(r, IntRect(0, 2, 13, 8)); 204 TEST_INTERSECT(r, IntRect(0, 3, 13, 8)); 205 TEST_NO_INTERSECT(r, IntRect(0, 3, 13, 7)); 206 } 207 208 #define TEST_NO_CONTAINS(a, b) \ 209 { \ 210 Region ar = a; \ 211 Region br = b; \ 212 EXPECT_FALSE(ar.contains(br)); \ 213 } 214 215 #define TEST_CONTAINS(a, b) \ 216 { \ 217 Region ar = a; \ 218 Region br = b; \ 219 EXPECT_TRUE(ar.contains(br)); \ 220 } 221 222 TEST(RegionTest, containsRegion) 223 { 224 TEST_CONTAINS(IntRect(), IntRect()); 225 TEST_NO_CONTAINS(IntRect(), IntRect(0, 0, 1, 1)); 226 TEST_NO_CONTAINS(IntRect(), IntRect(1, 1, 1, 1)); 227 228 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(11, 10, 1, 1)); 229 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 11, 1, 1)); 230 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 1, 1)); 231 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 1, 1)); 232 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 2, 2)); 233 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 9, 2, 2)); 234 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 10, 2, 2)); 235 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(10, 10, 2, 2)); 236 TEST_NO_CONTAINS(IntRect(10, 10, 1, 1), IntRect(9, 9, 3, 3)); 237 238 Region hLines; 239 for (int i = 10; i < 20; i += 2) 240 hLines.unite(IntRect(i, 10, 1, 10)); 241 242 TEST_CONTAINS(IntRect(10, 10, 9, 10), hLines); 243 TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), hLines); 244 TEST_NO_CONTAINS(IntRect(10, 11, 9, 9), hLines); 245 TEST_NO_CONTAINS(IntRect(10, 10, 8, 10), hLines); 246 TEST_NO_CONTAINS(IntRect(11, 10, 8, 10), hLines); 247 248 Region vLines; 249 for (int i = 10; i < 20; i += 2) 250 vLines.unite(IntRect(10, i, 10, 1)); 251 252 TEST_CONTAINS(IntRect(10, 10, 10, 9), vLines); 253 TEST_NO_CONTAINS(IntRect(10, 10, 9, 9), vLines); 254 TEST_NO_CONTAINS(IntRect(11, 10, 9, 9), vLines); 255 TEST_NO_CONTAINS(IntRect(10, 10, 10, 8), vLines); 256 TEST_NO_CONTAINS(IntRect(10, 11, 10, 8), vLines); 257 258 Region grid; 259 for (int i = 10; i < 20; i += 2) 260 for (int j = 10; j < 20; j += 2) 261 grid.unite(IntRect(i, j, 1, 1)); 262 263 TEST_CONTAINS(IntRect(10, 10, 9, 9), grid); 264 TEST_NO_CONTAINS(IntRect(10, 10, 9, 8), grid); 265 TEST_NO_CONTAINS(IntRect(10, 11, 9, 8), grid); 266 TEST_NO_CONTAINS(IntRect(10, 10, 8, 9), grid); 267 TEST_NO_CONTAINS(IntRect(11, 10, 8, 9), grid); 268 269 TEST_CONTAINS(hLines, hLines); 270 TEST_CONTAINS(vLines, vLines); 271 TEST_NO_CONTAINS(vLines, hLines); 272 TEST_NO_CONTAINS(hLines, vLines); 273 TEST_CONTAINS(grid, grid); 274 TEST_CONTAINS(hLines, grid); 275 TEST_CONTAINS(vLines, grid); 276 TEST_NO_CONTAINS(grid, hLines); 277 TEST_NO_CONTAINS(grid, vLines); 278 279 for (int i = 10; i < 20; i += 2) 280 TEST_CONTAINS(hLines, IntRect(i, 10, 1, 10)); 281 282 for (int i = 10; i < 20; i += 2) 283 TEST_CONTAINS(vLines, IntRect(10, i, 10, 1)); 284 285 for (int i = 10; i < 20; i += 2) 286 for (int j = 10; j < 20; j += 2) 287 TEST_CONTAINS(grid, IntRect(i, j, 1, 1)); 288 289 Region container; 290 container.unite(IntRect(0, 0, 40, 20)); 291 container.unite(IntRect(0, 20, 41, 20)); 292 TEST_CONTAINS(container, IntRect(5, 5, 30, 30)); 293 294 container = Region(); 295 container.unite(IntRect(0, 0, 10, 10)); 296 container.unite(IntRect(0, 30, 10, 10)); 297 container.unite(IntRect(30, 30, 10, 10)); 298 container.unite(IntRect(30, 0, 10, 10)); 299 TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30)); 300 301 container = Region(); 302 container.unite(IntRect(0, 0, 10, 10)); 303 container.unite(IntRect(0, 30, 10, 10)); 304 container.unite(IntRect(30, 0, 10, 40)); 305 TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30)); 306 307 container = Region(); 308 container.unite(IntRect(30, 0, 10, 10)); 309 container.unite(IntRect(30, 30, 10, 10)); 310 container.unite(IntRect(0, 0, 10, 40)); 311 TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30)); 312 313 container = Region(); 314 container.unite(IntRect(0, 0, 10, 40)); 315 container.unite(IntRect(30, 0, 10, 40)); 316 TEST_NO_CONTAINS(container, IntRect(5, 5, 30, 30)); 317 318 container = Region(); 319 container.unite(IntRect(0, 0, 40, 40)); 320 TEST_NO_CONTAINS(container, IntRect(10, -1, 20, 10)); 321 322 container = Region(); 323 container.unite(IntRect(0, 0, 40, 40)); 324 TEST_NO_CONTAINS(container, IntRect(10, 31, 20, 10)); 325 326 container = Region(); 327 container.unite(IntRect(0, 0, 40, 20)); 328 container.unite(IntRect(0, 20, 41, 20)); 329 TEST_NO_CONTAINS(container, IntRect(-1, 10, 10, 20)); 330 331 container = Region(); 332 container.unite(IntRect(0, 0, 40, 20)); 333 container.unite(IntRect(0, 20, 41, 20)); 334 TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20)); 335 336 container = Region(); 337 container.unite(IntRect(0, 0, 40, 40)); 338 container.subtract(IntRect(0, 20, 60, 0)); 339 TEST_NO_CONTAINS(container, IntRect(31, 10, 10, 20)); 340 } 341 127 342 } // namespace
Note: See TracChangeset
for help on using the changeset viewer.