|Summary:||Region::intersects() and Region::contains() are slow due to copy overhead|
|Product:||WebKit||Reporter:||Dana Jansens <danakj>|
|Component:||New Bugs||Assignee:||Dana Jansens <danakj>|
|Severity:||Normal||CC:||andersca, backer, enne, jamesr, piman, simon.fraser, webkit.review.bot|
|Version:||528+ (Nightly build)|
|Bug Depends on:|
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 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.