Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
183663030:
Reduce number of vector buffer reallocs in Regions::unite . (Closed)
|
Created:
6 years, 9 months ago by ostap Modified:
6 years, 6 months ago CC:
blink-reviews, jamesr, krit, dsinclair, jbroman, danakj, Rik, Stephen Chennney, pdr., rwlbuis, Erik Corry, Mikhail, Chris Evans Base URL:
https://chromium.googlesource.com/chromium/blink.git@master Visibility:
Public. |
DescriptionReduce number of vector buffer reallocs in Regions::unite .
When acceleratedCompositingForFixedPositionEnabled is not set
FrameView::scrollContentsFastPath() performs invalidate for every sticky or
fixed layer. Page http://people.mozilla.org/~jorendorff/es6-draft.html#sec-terms-and-definitions-symbol-type
causes Region::unite a lot. Vector buffer reallocations are hot in profiler.
This patch pre-allocates vector buffers in Region::Shape::shapeOperation() and
moves Vector allocation out of inner loop. This significantly reduces number of
vector buffer reallocs.
BUG=335306
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=175822
Patch Set 1 #Patch Set 2 : Increase initial vector buffer size to sum of source buffers size and add buffer trimming. #Patch Set 3 : Rebased patch. #
Total comments: 13
Patch Set 4 : Updated by review comments. #Patch Set 5 : Use new Vector::shrinkToReasonableCapacity() API. #
Total comments: 4
Patch Set 6 : Add assert to check that segments capacity is not zeroed. #Patch Set 7 : Add back shrinkToReasonableCapacity() change. #
Total comments: 2
Patch Set 8 : Simplify vectore pre-allocating Shape() constructor. #Messages
Total messages: 25 (0 generated)
Could you take a look? This should improve performance of desktop chromium for pages that have a lot of layers. Thanks!
1) I'm not the right person to review this CL. We should find someone who is better qualified. 2) Can you quantify the performance improvement? What percent of the time do we save on what workload with this CL?
On 2014/04/05 21:58:39, abarth wrote: > 1) I'm not the right person to review this CL. We should find someone who is > better qualified. I thought that danakj would be a good reviewer for the Regions, because she was fixing it in webkit. But she is not in owners for platform. > 2) Can you quantify the performance improvement? What percent of the time do we > save on what workload with this CL? In a simple benchmark that continuously adds (union) 1000 non-intersecting regions the improvement was about 10 times. In this case spans and segments vectors are continuously growing, so vector storage gets reallocated multiple times in union operation. That's what happens in FrameView::scrollContentsFastPath() when http://people.mozilla.org/~jorendorff/es6-draft.html is scrolled (with sticky positioning enabled). This patch preallocates vector storage at the beginning of operation and drops excessive storage at the end if necessary. With the patch vector storage realloc disappears from profiler top and page scrolls much smoother. Of course es6-draft.html page is an extreme case (it has 3350 headings which are all position:sticky layers), but this patch should help other pages with big number of layers (above 100).
Neat. We can ask danakj to review the CL. @danakj: Thoughts?
I like it overall! yay for reserving memory up front to avoid useless copies. https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:249: void Region::Shape::trimCapacities() Methods in the same order as their declarations in the .h https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:252: m_segments.shrinkToFit(); I feel like this is kinda unfortunate, in that you make it very likely that the next operation on the region is going to require a realloc/memcpy. Also the *2 seems like it's leaking out of the Vector implementation here. It'd be really nice if something like Vector::shrinkCapacity() was public, or maybe a shrinkToReasonableCapacity() or something that would take the *2 into account. Is there a Vector owner who can approve/disapprove of such an idea? https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:436: Vector<int, segmentsDefaultCapacity> segments; would it improve anything further in your benchmark to use the max(shape1.segmentsSize(), shape2.segmentsSize()) here? https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:461: // clear vector without dropping capacity nit: proper sentence (capitalized, with period at the end) https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:462: segments.resize(0); keep this in the same position? (below s1,s2 assignments) https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:506: // Trim excess capacities if necessary. Prefer not to add comments that just repeat the name of the method more or less :) If you feel any part of this comment is adding value beyond the method name, can you just add it to the trimCapacities() method name?
https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:249: void Region::Shape::trimCapacities() On 2014/04/09 18:39:51, danakj wrote: > Methods in the same order as their declarations in the .h It seems that all other methods are not in the same order in Regions.cpp , but I moved trimCapacities() after compareShapes() as it in .h . https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:252: m_segments.shrinkToFit(); On 2014/04/09 18:39:51, danakj wrote: > I feel like this is kinda unfortunate, in that you make it very likely that the > next operation on the region is going to require a realloc/memcpy. Region always allocate new buffers for operation. They never do it in place. I just want to limit number of reallocs if unused buffer tail is reasonably small. Also, *2 is taken from vector, but it used only if there is also other ratio 1.25 (Vector::expandCapacity). Don't know what is better here - do less reallocs or save a bit more RAM. > Also the *2 > seems like it's leaking out of the Vector implementation here. > It'd be really nice if something like Vector::shrinkCapacity() was public, or > maybe a shrinkToReasonableCapacity() or something that would take the *2 into > account. Is there a Vector owner who can approve/disapprove of such an idea? Yes, shrinkToReasonableCapacity() would be great! https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:436: Vector<int, segmentsDefaultCapacity> segments; On 2014/04/09 18:39:51, danakj wrote: > would it improve anything further in your benchmark to use the > max(shape1.segmentsSize(), shape2.segmentsSize()) here? No, no change at all. But this benchmark is very special case that emulates what happens on http://people.mozilla.org/~jorendorff/es6-draft.html with sticky enabled. It just adds non-intersecting rects to the existing shape and this "segments" vector never grows above default capacity. I think it could help for the case when complex shapes get joined. Since it doesn't make things slower in my benchmark, I just added it because it looks reasonable. https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:461: // clear vector without dropping capacity On 2014/04/09 18:39:51, danakj wrote: > nit: proper sentence (capitalized, with period at the end) Done. https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:462: segments.resize(0); On 2014/04/09 18:39:51, danakj wrote: > keep this in the same position? (below s1,s2 assignments) Done. https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:506: // Trim excess capacities if necessary. On 2014/04/09 18:39:51, danakj wrote: > Prefer not to add comments that just repeat the name of the method more or less > :) If you feel any part of this comment is adding value beyond the method name, > can you just add it to the trimCapacities() method name? Done.
https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... Source/platform/geometry/Region.cpp:252: m_segments.shrinkToFit(); On 2014/04/09 22:45:43, ostap wrote: > On 2014/04/09 18:39:51, danakj wrote: > > I feel like this is kinda unfortunate, in that you make it very likely that > the > > next operation on the region is going to require a realloc/memcpy. > > Region always allocate new buffers for operation. They never do it in place. I > just want to limit number of reallocs if unused buffer tail is reasonably small. > Also, *2 is taken from vector, but it used only if there is also other ratio > 1.25 (Vector::expandCapacity). Don't know what is better here - do less reallocs > or save a bit more RAM. > > > Also the *2 > > seems like it's leaking out of the Vector implementation here. > > It'd be really nice if something like Vector::shrinkCapacity() was public, or > > maybe a shrinkToReasonableCapacity() or something that would take the *2 into > > account. Is there a Vector owner who can approve/disapprove of such an idea? > > Yes, shrinkToReasonableCapacity() would be great! Wanna add that to the CL and we'll see what OWNERs have to say?
On 2014/04/15 20:15:43, danakj wrote: > https://codereview.chromium.org/183663030/diff/40001/Source/platform/geometry... > File Source/platform/geometry/Region.cpp (right): > > Yes, shrinkToReasonableCapacity() would be great! > > Wanna add that to the CL and we'll see what OWNERs have to say? Done: https://codereview.chromium.org/239603005/
On 2014/04/06 04:26:21, abarth wrote: > Neat. We can ask danakj to review the CL. > > @danakj: Thoughts? ping shrinkToReasonableCapacity() patch was landed and this CL was updated to use shrinkToReasonableCapacity() . Could you take another look, please?
LGTM https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... Source/platform/geometry/Region.cpp:463: segments.resize(0); Can you assert the capacity after this verify it keeps doing what you intend?
https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... Source/platform/geometry/Region.cpp:463: segments.resize(0); On 2014/05/12 22:57:09, danakj wrote: > Can you assert the capacity after this verify it keeps doing what you intend? Assert that capacity didn't grow and there was now reallocs? I think this assert is not right and there could be reallocs in some cases like joining single line of non-intersecting rects with another single line of rects at the same height. But those cases are extremely rare I don't think it should be taken into account.
https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... Source/platform/geometry/Region.cpp:463: segments.resize(0); On 2014/05/13 19:05:21, ostap wrote: > On 2014/05/12 22:57:09, danakj wrote: > > Can you assert the capacity after this verify it keeps doing what you intend? > > Assert that capacity didn't grow and there was now reallocs? > I think this assert is not right and there could be reallocs in some cases like > joining single line of non-intersecting rects with another single line of rects > at the same height. But those cases are extremely rare I don't think it should > be taken into account. I meant assert that the capacity was not shrunken to 0 as the comment claims it will not be.
https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/80001/Source/platform/geometry... Source/platform/geometry/Region.cpp:463: segments.resize(0); On 2014/05/13 19:09:03, danakj wrote: > On 2014/05/13 19:05:21, ostap wrote: > > On 2014/05/12 22:57:09, danakj wrote: > > > Can you assert the capacity after this verify it keeps doing what you > intend? > > > > Assert that capacity didn't grow and there was now reallocs? > > I think this assert is not right and there could be reallocs in some cases > like > > joining single line of non-intersecting rects with another single line of > rects > > at the same height. But those cases are extremely rare I don't think it should > > be taken into account. > > I meant assert that the capacity was not shrunken to 0 as the comment claims it > will not be. Done.
eseidel@chromium.org: Please review changes since abarth seems not available now.
Region has long been of horrible performance: https://bugs.webkit.org/show_bug.cgi?id=98800 https://bugs.webkit.org/show_bug.cgi?id=79174 (and many more if you search for Region::unite in all bugs in webkit) https://bugs.webkit.org/buglist.cgi?query_format=specific&order=relevance+des...
CCing wtf ninjas.
On 2014/05/28 23:58:23, eseidel wrote: > Region has long been of horrible performance: > https://bugs.webkit.org/show_bug.cgi?id=98800 > https://bugs.webkit.org/show_bug.cgi?id=79174 > (and many more if you search for Region::unite in all bugs in webkit) > https://bugs.webkit.org/buglist.cgi?query_format=specific&order=relevance+des... Seems you already had similar idea here: https://bugs.webkit.org/show_bug.cgi?id=98800#c6 (idea #2). It improves performance of the Region::unite several times when the number of segments/spans grows above 1000 . I'm surprised that it was not done before if this is a known problem.
https://codereview.chromium.org/183663030/diff/120001/Source/platform/geometr... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/120001/Source/platform/geometr... Source/platform/geometry/Region.cpp:245: segmentsCapacity = (segmentsCapacity + segmentsMask) & ~segmentsMask; Why is all this capacity dance needed? Can't we just call reserveCapacity with our desired capacity?
https://codereview.chromium.org/183663030/diff/120001/Source/platform/geometr... File Source/platform/geometry/Region.cpp (right): https://codereview.chromium.org/183663030/diff/120001/Source/platform/geometr... Source/platform/geometry/Region.cpp:245: segmentsCapacity = (segmentsCapacity + segmentsMask) & ~segmentsMask; On 2014/05/29 15:45:16, eseidel wrote: > Why is all this capacity dance needed? Can't we just call reserveCapacity with > our desired capacity? Yes, we can. Tried to reserve some more space because 1st versions were pre-allocating less buffer and it could grow. It appeared to be more effective to pre-allocate bigger buffer and drop excess capacity later, if necessary. Done
lgtm This seems very reasonable to me. We can always iterate further from here. Do we have specific tests we expect to be faster?
On 2014/05/30 00:03:30, eseidel wrote: > lgtm > > This seems very reasonable to me. We can always iterate further from here. Do > we have specific tests we expect to be faster? To test this I have made very simple micro benchmark that just adds 1000 non-intersecting rects to the region and repeats loop 1000 times. That's what basically happens on the http://people.mozilla.org/~jorendorff/es6-draft.html page (it has more than 3000 headings with sticky style). Do you think it is worth checking in this micro benchmark? Also with this patch Region::unite disappears from the top in profiler.
The CQ bit was checked by sl.ostapenko@samsung.com
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/sl.ostapenko@samsung.com/183663030/140001
Message was sent while issue was closed.
Change committed as 175822 |
