Bug 81076

Summary: Region::intersects() and Region::contains() are slow due to copy overhead
Product: WebKit Reporter: Dana Jansens <danakj>
Component: New BugsAssignee: Dana Jansens <danakj>
Status: RESOLVED FIXED    
Severity: Normal CC: andersca, backer, enne, jamesr, piman, simon.fraser, webkit.review.bot
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on:    
Bug Blocks: 85260    
Attachments:
Description Flags
Patch
none
Patch
none
Patch
none
perf demo layout test
none
Patch for landing none

Description Dana Jansens 2012-03-13 21:26:37 PDT
Region::intersects() and Region::contains() are slow due to copy overhead
Comment 1 Dana Jansens 2012-03-13 21:28:28 PDT
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.
Comment 2 Dana Jansens 2012-03-13 21:33:11 PDT
Created attachment 131782 [details]
Patch
Comment 3 Build Bot 2012-03-14 02:59:53 PDT
Comment on attachment 131782 [details]
Patch

Attachment 131782 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/11951139
Comment 4 Dana Jansens 2012-03-14 07:53:44 PDT
Created attachment 131844 [details]
Patch

Comment out ununsed parameters.
Comment 5 Dana Jansens 2012-04-30 21:59:22 PDT
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().
Comment 6 Dana Jansens 2012-05-03 12:02:00 PDT
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
Comment 7 Dana Jansens 2012-05-07 15:39:56 PDT
Created attachment 140607 [details]
Patch for landing
Comment 8 WebKit Review Bot 2012-05-07 17:10:52 PDT
Comment on attachment 140607 [details]
Patch for landing

Clearing flags on attachment: 140607

Committed r116377: <http://trac.webkit.org/changeset/116377>
Comment 9 WebKit Review Bot 2012-05-07 17:10:57 PDT
All reviewed patches have been landed.  Closing bug.