Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
78883002:
Cluster invalidation rectangles into coherent regions to lessen SkPicture re-recording (Closed)
|
Created:
7 years, 1 month ago by humper Modified:
7 years, 1 month ago CC:
chromium-reviews, cc-bugs_chromium.org Base URL:
https://chromium.googlesource.com/chromium/src.git@master Visibility:
Public. |
DescriptionCluster invalidation rectangles into coherent regions to lessen SkPicture re-recording
Apply a simple linear greedy clustering approach to all invalidated tiles in a layer to try to reduce the amount of clean layer area that gets re-recorded in response to a multi-rectangle invalidation event.
BUG=312861
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=236806
Patch Set 1 #Patch Set 2 : Decrease the density threshold from very high testing value #
Total comments: 19
Patch Set 3 : Address vlad's nits; rewrite single-function class as a function. Better sorting. #
Total comments: 17
Patch Set 4 : Vlad is promoted to Vice President In Charge Of Nits #Patch Set 5 : A few more nits that I missed in the last upload #
Total comments: 4
Patch Set 6 : move functions into anon namespace #
Total comments: 12
Patch Set 7 : fix up latest round of nits #
Total comments: 1
Patch Set 8 : Final round of nits #
Messages
Total messages: 16 (0 generated)
Rework the creation of PicturePile to attempt to cluster groups of nearby updates together into a single record rect. Should take some of the pressure off websites that have simultaneous updates that are far apart.
Driveby happiness.
Looking good, but a couple of questions and a couple of nits below. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile.cc File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:38: class TileClustering { Why is this a separate class? Since all of the interesting work is done in the constructor, I think it would be slightly more efficient to have a function that takes the resulting rects as a pointer and returns the final density https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:40: TileClustering(const std::vector<gfx::Rect> &tiles, float thresh) nit: spacing (vector<...>& tiles) and don't abbreviate threshold https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:65: if (proposed_density >= clustering_threshold) { What happens in the case where we have a full row followed by an empty row followed by a full row (full = invalidated, empty = not invalidated). If I understand this correct, both rows would end up in a separate cluster after we add the first tile of the last row, although if we added the full row then the density would still be > 0.5. Is this expected? Ie we just have to live with it? :P https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:102: std::vector<gfx::Rect> record_rects; nit: we typically name private members with a trailing udnerscore https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:144: nit: remove this line (and most trailing blank lines after comments) https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:159: if (invalid_tiles.size() == 1) { Maybe make this a helper function, something along the lines of the following: ClusterRects(invalid_tiles, &record_rects); just to keep the Update function cleaner https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:166: std::sort(invalid_tiles_vertical.begin(), Assuming that the sort totally ignores the other coordinate, can't you end up in situations like having one row of tiles (say 5 tiles 256x256) and having the first two tiles being at 0,0 and at 1024,0 (sort by y here), so then adding the second tile would immediately break the threshold? I think this might be solved by a more involved sort function though like a.y < b.y || (a.y == b.y && a.x < b.x) or something https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:172: TileClustering vertical_clustering(invalid_tiles_vertical, 0.5); nit: Make density a constant at the top please, and you can move the comment there as well.
https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile.cc File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:178: TileClustering horizontal_clustering(invalid_tiles_vertical, 0.5); Is it expensive to sort and walk through all the invalidated tiles twice in different directions? Did you abandon your original approach (at least that I had heard described) about merging everything on horizontal rows and then clustering those rows vertically? Was it not performant?
https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile.cc File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:38: class TileClustering { On 2013/11/20 18:02:32, vmpstr wrote: > Why is this a separate class? Since all of the interesting work is done in the > constructor, I think it would be slightly more efficient to have a function that > takes the resulting rects as a pointer and returns the final density No particular reason; I had initially imagined it as something more complex, and it turned out to just be a function. I'll redo it as a function, that will be better. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:40: TileClustering(const std::vector<gfx::Rect> &tiles, float thresh) On 2013/11/20 18:02:32, vmpstr wrote: > nit: spacing (vector<...>& tiles) and don't abbreviate threshold Done. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:65: if (proposed_density >= clustering_threshold) { On 2013/11/20 18:02:32, vmpstr wrote: > What happens in the case where we have a full row followed by an empty row > followed by a full row (full = invalidated, empty = not invalidated). If I > understand this correct, both rows would end up in a separate cluster after we > add the first tile of the last row, although if we added the full row then the > density would still be > 0.5. Is this expected? Ie we just have to live with it? > :P This is partially an artifact of the greedy clustering algorithm, and partly a consequence of the fact that I don't pre-group adjacent tiles together (see comment by enne below). The greediness can't be helped, but certainly we can cluster things by line instead of by tile, which would help with this concern (if it is indeed a concern). https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:102: std::vector<gfx::Rect> record_rects; On 2013/11/20 18:02:32, vmpstr wrote: > nit: we typically name private members with a trailing udnerscore Done. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:144: On 2013/11/20 18:02:32, vmpstr wrote: > nit: remove this line (and most trailing blank lines after comments) Done. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:159: if (invalid_tiles.size() == 1) { On 2013/11/20 18:02:32, vmpstr wrote: > Maybe make this a helper function, something along the lines of the following: > > ClusterRects(invalid_tiles, &record_rects); > > just to keep the Update function cleaner will do. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:166: std::sort(invalid_tiles_vertical.begin(), On 2013/11/20 18:02:32, vmpstr wrote: > Assuming that the sort totally ignores the other coordinate, can't you end up in > situations like having one row of tiles (say 5 tiles 256x256) and having the > first two tiles being at 0,0 and at 1024,0 (sort by y here), so then adding the > second tile would immediately break the threshold? > > I think this might be solved by a more involved sort function though > like a.y < b.y || (a.y == b.y && a.x < b.x) or something better sort would help with this, although grouping adjacent tiles and clustering by line will help also; since the clustering is really meant to work in 1D I think we should do that before this lands. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:172: TileClustering vertical_clustering(invalid_tiles_vertical, 0.5); On 2013/11/20 18:02:32, vmpstr wrote: > nit: Make density a constant at the top please, and you can move the comment > there as well. Yeah, absolutely -- wasn't sure the best way to make it controllable so it ended up as a magic number :) https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:178: TileClustering horizontal_clustering(invalid_tiles_vertical, 0.5); On 2013/11/20 19:15:33, enne wrote: > Is it expensive to sort and walk through all the invalidated tiles twice in > different directions? > > Did you abandon your original approach (at least that I had heard described) > about merging everything on horizontal rows and then clustering those rows > vertically? Was it not performant? Not abandoned, just not done yet. There are a couple of ways to handle that; if I use a more clever sort like vlad describes above, I can add all horizontally (or vertically, depending on the direction) adjacent tiles at once, since adding more adjacent tiles should typically (but not always) improve the density. We could also only do the horizontal version if the vertical version results in multiple clusters, or with a separate density control (if the best we could do was something close to the threshold, say).
new version as a function, better sorting, nits addressed. https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile.cc File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/40001/cc/resources/picture_pile... cc/resources/picture_pile.cc:47: for (std::vector<gfx::Rect>::iterator it = tiles.begin(); Heh, that's what I get for not testing before doing the CL upload because I thought I was just doing "nits" -- this has to be const_iterator.
A few more comments, mostly style. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:30: static bool rect_sort_y(const gfx::Rect &r1, const gfx::Rect &r2) { Can you please put constants and these functions into the anonymous namespace above (and you don't need to qualify them as static in that case) https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:41: #define DENSITY_THRESHOLD 0.5 This should just be a const float kDensityThreshold = 0.5; https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:43: std::vector<gfx::Rect> nit: spacing looks a bit weird... I think clang-format would typically break on the opening paren if it can https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:44: do_clustering(const std::vector<gfx::Rect>& tiles, float *density) { In order to avoid a (possible) copy of a vector, I think you should take the output vector with a pointer and return the density instead https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:63: // consider adding the invalid tile to the current record nit: Comments should be proper sentences (ie, start with a capital) https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:94: if (!cur_record_rect.IsEmpty()) { I think you should early out if given tiles vector is empty, and then this if should never fail (and thus no need for it, just do the push_back) https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:115: if (invalid_tiles.size() == 1) { Also handle invalid_tiles.size() == 0, since that's trivial https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:119: } else { No need for this else (since you early out in the if) https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:128: do_clustering(invalid_tiles_vertical, &vertical_density); nit: indent 4 spaces when breaking a line or in general whatever clang-format wants to do
https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:30: static bool rect_sort_y(const gfx::Rect &r1, const gfx::Rect &r2) { On 2013/11/21 19:05:58, vmpstr wrote: > Can you please put constants and these functions into the anonymous namespace > above (and you don't need to qualify them as static in that case) Done. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:41: #define DENSITY_THRESHOLD 0.5 On 2013/11/21 19:05:58, vmpstr wrote: > This should just be a const float kDensityThreshold = 0.5; Done. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:43: std::vector<gfx::Rect> On 2013/11/21 19:05:58, vmpstr wrote: > nit: spacing looks a bit weird... I think clang-format would typically break on > the opening paren if it can Done. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:44: do_clustering(const std::vector<gfx::Rect>& tiles, float *density) { On 2013/11/21 19:05:58, vmpstr wrote: > In order to avoid a (possible) copy of a vector, I think you should take the > output vector with a pointer and return the density instead Done. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:63: // consider adding the invalid tile to the current record On 2013/11/21 19:05:58, vmpstr wrote: > nit: Comments should be proper sentences (ie, start with a capital) Done. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:94: if (!cur_record_rect.IsEmpty()) { On 2013/11/21 19:05:58, vmpstr wrote: > I think you should early out if given tiles vector is empty, and then this if > should never fail (and thus no need for it, just do the push_back) Done by handling outside this function. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:115: if (invalid_tiles.size() == 1) { On 2013/11/21 19:05:58, vmpstr wrote: > Also handle invalid_tiles.size() == 0, since that's trivial Done. https://codereview.chromium.org/78883002/diff/110001/cc/resources/picture_pil... cc/resources/picture_pile.cc:119: } else { On 2013/11/21 19:05:58, vmpstr wrote: > No need for this else (since you early out in the if) Done.
This looks good if that's the approach we want to take. See my comment below about my concern https://codereview.chromium.org/78883002/diff/190001/cc/resources/picture_pil... File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/190001/cc/resources/picture_pil... cc/resources/picture_pile.cc:44: float do_clustering(const std::vector<gfx::Rect>& tiles, You can move all of the non member functions to the anonymous namespace https://codereview.chromium.org/78883002/diff/190001/cc/resources/picture_pil... cc/resources/picture_pile.cc:133: // TODO(humper): Heuristics for skipping this step? I think we should either just skip the horizontal cluster or do it if vertical_density < something. I'm concerned that we might spend more time trying to be the best we can, rather than just recording the good enough clustering. That is, the savings on the recording cost from having a possibly better clustering are offset by two things: 1. The time we spend to determine the better clustering 2. Possibly more calls to picture raster calls down the road (it's not that bad that we have _some_ empty space in the cluster). It would be nice if we had some sort of a measure of the performance. Maybe rasterize and record can help? I'm not sure it would exercise all of the use cases though.
https://codereview.chromium.org/78883002/diff/190001/cc/resources/picture_pil... File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/190001/cc/resources/picture_pil... cc/resources/picture_pile.cc:44: float do_clustering(const std::vector<gfx::Rect>& tiles, On 2013/11/21 19:47:59, vmpstr wrote: > You can move all of the non member functions to the anonymous namespace Done. https://codereview.chromium.org/78883002/diff/190001/cc/resources/picture_pil... cc/resources/picture_pile.cc:133: // TODO(humper): Heuristics for skipping this step? On 2013/11/21 19:47:59, vmpstr wrote: > I think we should either just skip the horizontal cluster or do it if > vertical_density < something. I'm concerned that we might spend more time trying > to be the best we can, rather than just recording the good enough clustering. > > That is, the savings on the recording cost from having a possibly better > clustering are offset by two things: > 1. The time we spend to determine the better clustering > 2. Possibly more calls to picture raster calls down the road (it's not that bad > that we have _some_ empty space in the cluster). > > It would be nice if we had some sort of a measure of the performance. Maybe > rasterize and record can help? I'm not sure it would exercise all of the use > cases though. I'm concerned about sites that have two long vertical strips of updates on either side of the page (e.g. two sidebars with content in the middle). For those sites, the horizontal clustering should do much better.
lgtm with a few nits. I'd also like enne to take a look for a final approval. Also, you might as well fix the patch title and description, since I think we want this to go in fairly soon. https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:84: if (!cur_record_rect.IsEmpty()) { Can this condition ever be false? https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:91: } else { nit: no need for else if (...) return 1; return ...; Can total_record_area even be zero with all the early outs in ClusterTiles? https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:137: } else { Also technically no need for the else, but it kinda looks more symmetrical
lgtm in general. Sorry to continue the nit train. I ran this on an N4 and for like ~35 rects it's 0.03ms of work. 35 rects is probably not going to be too far off from average since that's like 1000x8000ish and probably about the size of the interest rect on most pages. https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:24: const float kDensityTreshold = 0.5f; Typo https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:36: TRACE_EVENT0("cc.debug", "do_clustering"); No need for two traces. You already have one in ClusterTiles. https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:46: int total_area = 0, invalid_area = 0; total_area vs. total_record_area are a little hard to differentiate. What about total_record_area, total_invalid_area, cluster_record_area, and cluster_invalid_area? https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:90: return 1; 1 => 1.f https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:91: } else { On 2013/11/21 20:57:36, vmpstr wrote: > nit: no need for else > > if (...) > return 1; > return ...; > > Can total_record_area even be zero with all the early outs in ClusterTiles? It doesn't look like it can. Maybe that can just get DCHECK'd? https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:99: TRACE_EVENT1("cc.debug", "ClusterTiles", cc.debug => cc, I think. cc.debug is usually more for expensive things like all of the quad state. This seems like a reasonable thing to have in most traces. https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:100: "number of tiles", Also, I don't think any trace events use spaces in their names. Maybe just make this "count" for simplicity? https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:137: } else { On 2013/11/21 20:57:36, vmpstr wrote: > Also technically no need for the else, but it kinda looks more symmetrical It's against the Chromium style guide. "Don't use else after return" https://codereview.chromium.org/78883002/diff/220001/cc/resources/picture_pil... cc/resources/picture_pile.cc:214: record_rect.Inset(-buffer_pixels(), -buffer_pixels(), Can you add a PaddedRect(gfx::Rect) function, call it here, and call it from PaddedRect(const PictureMapKey&) so that all the insetting is done in one place?
all new nits addressed, I think.
Thanks! Looks great! Before you land, can you also update the description (which ends up being the commit message) to include your snazzy new subject line, link to the right bug, and maybe a short description? https://codereview.chromium.org/78883002/diff/290001/cc/resources/picture_pil... File cc/resources/picture_pile.cc (right): https://codereview.chromium.org/78883002/diff/290001/cc/resources/picture_pil... cc/resources/picture_pile.cc:86: DCHECK_NE(total_record_area,0); Space between comma and zero.
CQ is trying da patch. Follow status at https://chromium-status.appspot.com/cq/humper@google.com/78883002/330001
Message was sent while issue was closed.
Change committed as 236806 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
