Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(71)

Issue 2570393002: cc: Change Nodes collection to use base::ContiguousContainer instead of deque. (Closed)

Created:
4 years ago by vmpstr
Modified:
4 years ago
Reviewers:
danakj, DmitrySkiba
CC:
chromium-reviews, cc-bugs_chromium.org
Target Ref:
refs/pending/heads/master
Project:
chromium
Visibility:
Public.

Description

cc: Change Nodes collection to use base::ContiguousContainer instead of deque. This patch changes the the underlying structure to be base::ContiguousContainer. This provides better memory behavior and impacts performance as demonstrated by the results below. This is an acceptable change in performance with the benefit of memory savings. (N7v2) Before: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 91842.1953125 runs/s *RESULT rtree_construct: 1000= 9855.638671875 runs/s *RESULT rtree_construct: 10000= 747.183837890625 runs/s *RESULT rtree_construct: 100000= 63.701416015625 runs/s [ OK ] RTreePerfTest.Construct (8245 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 363610 runs/s *RESULT rtree_search: 1000= 97453.4921875 runs/s *RESULT rtree_search: 10000= 13022.0244140625 runs/s *RESULT rtree_search: 100000= 848.8214111328125 runs/s [ OK ] RTreePerfTest.Search (8093 ms) After: [ RUN ] RTreePerfTest.Construct *RESULT rtree_construct: 100= 74468.8828125 runs/s (-19%) *RESULT rtree_construct: 1000= 12053.529296875 runs/s (+22%) *RESULT rtree_construct: 10000= 716.7188720703125 runs/s (-4%) *RESULT rtree_construct: 100000= 54.01991653442383 runs/s (-16%) [ OK ] RTreePerfTest.Construct (8182 ms) [ RUN ] RTreePerfTest.Search *RESULT rtree_search: 100= 351755 runs/s *RESULT rtree_search: 1000= 96155 runs/s *RESULT rtree_search: 10000= 10232.65625 runs/s *RESULT rtree_search: 100000= 863.5242309570312 runs/s [ OK ] RTreePerfTest.Search (8176 ms) Additionally this changes the union operation to be faster than gfx::Rect::Union, since there are some assumptions that we can make. Also, Union shows up as the hottest function on Linux profiles. BUG=674169 R=danakj@chromium.org,dskiba@chromium.org CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel Committed: https://crrev.com/ba09803911f3a0dc8d8e3b87f3fb8529baf4888d Cr-Commit-Position: refs/heads/master@{#439258}

Patch Set 1 #

Patch Set 2 : update #

Total comments: 2

Patch Set 3 : update #

Patch Set 4 : win compile fix #

Unified diffs Side-by-side diffs Delta from patch set Stats (+22 lines, -6 lines) Patch
M cc/base/rtree.h View 1 2 chunks +2 lines, -2 lines 0 comments Download
M cc/base/rtree.cc View 1 2 3 2 chunks +20 lines, -4 lines 0 comments Download

Messages

Total messages: 31 (13 generated)
vmpstr
Behold, a patch. This does seem to change the performance a little bit, but I ...
4 years ago (2016-12-14 19:36:00 UTC) #2
DmitrySkiba
Looks good! But I wonder what is the perf impact on Android? Can you check ...
4 years ago (2016-12-14 20:01:22 UTC) #3
danakj
I am thoroughly amazed that searching a list can be at all comparable. Confirming on ...
4 years ago (2016-12-14 20:14:43 UTC) #4
vmpstr
On 2016/12/14 20:14:43, danakj_OOO_and_slow wrote: > I am thoroughly amazed that searching a list can ...
4 years ago (2016-12-14 21:02:50 UTC) #5
danakj
On Wed, Dec 14, 2016 at 4:02 PM, <vmpstr@chromium.org> wrote: > On 2016/12/14 20:14:43, danakj_OOO_and_slow ...
4 years ago (2016-12-14 21:27:16 UTC) #6
vmpstr
On 2016/12/14 21:27:16, danakj_OOO_and_slow wrote: > On Wed, Dec 14, 2016 at 4:02 PM, <mailto:vmpstr@chromium.org> ...
4 years ago (2016-12-14 22:03:43 UTC) #7
danakj
Interesting, is it that list's allocator ends up allocating all the nodes together in memory ...
4 years ago (2016-12-15 15:53:31 UTC) #8
vmpstr
On 2016/12/15 15:53:31, danakj_OOO_and_slow wrote: > Interesting, is it that list's allocator ends up allocating ...
4 years ago (2016-12-15 20:03:27 UTC) #9
vmpstr
Out of all permutations of "optimizing union" and using either list or contiguous container, the ...
4 years ago (2016-12-15 22:57:20 UTC) #10
danakj
LGTM, update CL description pls https://codereview.chromium.org/2570393002/diff/20001/cc/base/rtree.cc File cc/base/rtree.cc (right): https://codereview.chromium.org/2570393002/diff/20001/cc/base/rtree.cc#newcode85 cc/base/rtree.cc:85: auto& bounds = (*branches)[current_branch].bounds; ...
4 years ago (2016-12-16 14:36:22 UTC) #11
vmpstr
https://codereview.chromium.org/2570393002/diff/20001/cc/base/rtree.cc File cc/base/rtree.cc (right): https://codereview.chromium.org/2570393002/diff/20001/cc/base/rtree.cc#newcode85 cc/base/rtree.cc:85: auto& bounds = (*branches)[current_branch].bounds; On 2016/12/16 14:36:22, danakj_OOO_and_slow wrote: ...
4 years ago (2016-12-16 18:57:52 UTC) #14
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.org/2570393002/40001
4 years ago (2016-12-16 18:58:29 UTC) #17
commit-bot: I haz the power
Try jobs failed on following builders: win_clang on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_clang/builds/140403)
4 years ago (2016-12-16 19:41:17 UTC) #19
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.org/2570393002/60001
4 years ago (2016-12-16 19:57:36 UTC) #22
commit-bot: I haz the power
Try jobs failed on following builders: linux_chromium_chromeos_rel_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_chromeos_rel_ng/builds/334843)
4 years ago (2016-12-16 22:34:03 UTC) #24
commit-bot: I haz the power
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.org/2570393002/60001
4 years ago (2016-12-16 23:15:01 UTC) #26
commit-bot: I haz the power
Committed patchset #4 (id:60001)
4 years ago (2016-12-17 00:43:32 UTC) #29
commit-bot: I haz the power
4 years ago (2016-12-17 00:46:05 UTC) #31
Message was sent while issue was closed.
Patchset 4 (id:??) landed as
https://crrev.com/ba09803911f3a0dc8d8e3b87f3fb8529baf4888d
Cr-Commit-Position: refs/heads/master@{#439258}

Powered by Google App Engine
This is Rietveld 408576698