Bug 81076 – Region::intersects() and Region::contains() are slow due to copy overhead

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Dana Jansens]

Region::intersects() and Region::contains() are slow due to copy overhead

[Dana Jansens]

Testing contains() and intersects() requires a copy which ends up invoking a malloc on sufficiently complicated web pages, and slows down the test unnecessarily. These methods can be done by iterating over the Region::Shape values rather than making a copy of the entire region and manipulating it.

[Dana Jansens]

Created attachment 131782 [details]
Patch

[Build Bot]

Comment on attachment 131782 [details]
Patch

Attachment 131782 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/11951139

[Dana Jansens]

Created attachment 131844 [details]
Patch

Comment out ununsed parameters.

[Dana Jansens]

Created attachment 139579 [details]
Patch

Rebased, and moved the Region::compareRegions function to Region::Shape::compareShapes, so that ShapeOpertions' trySimpleOperation can make use of it - specifically, union can make a simple case when shape2.contains(shape1) by setting result to shape2.

Some motivation:

We have a test case with 500 composited divs that are constantly moved. The Region class becomes the most expensive thing in the stack in this case.

The test case: http://chromium.googlecode.com/issues/attachment?aid=1246870000000&name=absolute-divs.html&token=KOhmGHsHqUSprb_Hk0wlH3M9UJc%3A1335840366548
Comes from bug: http://code.google.com/p/chromium/issues/detail?id=124687

The Region::intersects() test becomes a hotspot in the code to compute the overlap map for composited layers, due to copying Region overhead.

The Region::unite() method becomes the most expensive piece, but we make it much faster by testing Region::contains() with an early-out, avoiding a copy.

I see an improvement of this test case in chromium from 28fps to 37fps (32% improvement) by using this CL along with the early-out in Region::unite().

[Dana Jansens]

Created attachment 140060 [details]
perf demo layout test

I'm not sure if this is the best way to demonstrate perf impact, as the majority of time in a layout test is in setup/teardown, but here's some more data. This test is not as pathological as the rects moving randomly every frame test mentioned in the crbug, but it still demonstrates the change.

There's 3 numbers here, one on ToT, one with this CL to speed up intersects(), and the third with the followup cl #85260 to make unite() check contains().

This test tries to stress the composited layer overlap code, as it makes use of a Region to decide if a layer overlaps composited layers. I ran the test with --repeat-each=100.

ToT: 57.47s
#81076: 56.79s = 1.2% improvement
#85260: 54.97s = 4.4% improvement

Actual numbers:

% time drt --no-new-test-results compositing/layer-creation/overlap-many-children.html --repeat-each=100
All 100 tests ran as expected.                      
real	0m47.069s
user	0m57.470s
sys	0m1.640s
% time drt --no-new-test-results compositing/layer-creation/overlap-many-children.html --repeat-each=100
All 100 tests ran as expected.                      
real	0m46.332s
user	0m56.790s
sys	0m1.620s
% time drt --no-new-test-results compositing/layer-creation/overlap-many-children.html --repeat-each=100
All 100 tests ran as expected.                      
real	0m44.203s
user	0m54.970s
sys	0m1.680s

[Dana Jansens]

Created attachment 140607 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 140607 [details]
Patch for landing

Clearing flags on attachment: 140607

Committed r116377: <http://trac.webkit.org/changeset/116377>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.