Chromium Code Reviews
Help | Chromium Project | Gerrit Changes | Sign in
(4)

Issue 2853333004: Add range insertion for base::flat_tree (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
1 month, 2 weeks ago by jdoerrie
Modified:
1 month ago
Reviewers:
danakj, brettw, dyaroshev, vmpstr
CC:
chromium-reviews, danakj+watch_chromium.org, vmpstr+watch_chromium.org
Target Ref:
refs/heads/master
Project:
chromium
Visibility:
Public.

Description

Add range insertion for base::flat_tree This change implements an efficient algorithm for base::flat_tree::insert(Iter, Iter). BUG=671759, 682249 Review-Url: https://codereview.chromium.org/2853333004 Cr-Commit-Position: refs/heads/master@{#473148} Committed: https://chromium.googlesource.com/chromium/src/+/154dc49655238f0fc9928763bcf47930823a8e02

Patch Set 1 #

Patch Set 2 : Faster Algorithm #

Total comments: 3

Patch Set 3 : Rename prev_end to middle and check for sortedness #

Total comments: 13

Patch Set 4 : Add iterator arguments to sort_and_unique and test for empty range #

Total comments: 4

Patch Set 5 : Reuse Binary Search Result and Dupes #

Total comments: 11

Patch Set 6 : Next Round #

Total comments: 6

Patch Set 7 : Address comments #

Total comments: 2

Patch Set 8 : Next Round #

Total comments: 12

Patch Set 9 : Next Round of Comments #

Total comments: 10

Patch Set 10 : Another round of comments #

Unified diffs Side-by-side diffs Delta from patch set Stats (+280 lines, -14 lines) Patch
M base/containers/flat_map.h View 1 2 3 4 5 1 chunk +2 lines, -0 lines 0 comments Download
M base/containers/flat_set.h View 1 2 3 4 5 1 chunk +2 lines, -0 lines 0 comments Download
M base/containers/flat_tree.h View 1 2 3 4 5 6 7 8 9 11 chunks +157 lines, -12 lines 0 comments Download
M base/containers/flat_tree_unittest.cc View 1 2 3 4 5 3 chunks +119 lines, -2 lines 0 comments Download
Trybot results:  win_chromium_rel_ng   win_chromium_rel_ng   chromium_presubmit   linux_android_rel_ng   ios-simulator   win_clang   win_chromium_x64_rel_ng   mac_chromium_rel_ng   win_chromium_compile_dbg_ng   win_chromium_rel_ng   mac_chromium_compile_dbg_ng   ios-device-xcode-clang   ios-device   ios-simulator   ios-simulator-xcode-clang   linux_chromium_tsan_rel_ng   linux_chromium_asan_rel_ng   linux_chromium_chromeos_rel_ng   linux_chromium_compile_dbg_ng   linux_chromium_chromeos_ozone_rel_ng   linux_chromium_rel_ng   linux_android_rel_ng   chromeos_daisy_chromium_compile_only_ng   chromium_presubmit   cast_shell_linux   chromeos_amd64-generic_chromium_compile_only_ng   cast_shell_android   android_clang_dbg_recipe   android_compile_dbg   android_cronet   android_n5x_swarming_rel   android_arm64_dbg_recipe   win_clang   win_chromium_x64_rel_ng   win_chromium_rel_ng   mac_chromium_rel_ng   win_chromium_compile_dbg_ng   mac_chromium_compile_dbg_ng   ios-simulator-xcode-clang   ios-device-xcode-clang   ios-device   ios-simulator   linux_chromium_tsan_rel_ng   linux_chromium_rel_ng   linux_chromium_compile_dbg_ng   linux_chromium_chromeos_ozone_rel_ng   linux_chromium_chromeos_rel_ng   chromeos_daisy_chromium_compile_only_ng   chromium_presubmit   linux_chromium_asan_rel_ng   chromeos_amd64-generic_chromium_compile_only_ng   cast_shell_linux   linux_android_rel_ng   cast_shell_android   android_cronet   android_n5x_swarming_rel   android_compile_dbg   android_arm64_dbg_recipe   android_clang_dbg_recipe 
Commit queue not available (can’t edit this change).

Messages

Total messages: 83 (53 generated)
jdoerrie
Dear all, please review. This change follows the discussion between dyaroshev@ and me in http://crbug.com/682249. ...
1 month, 2 weeks ago (2017-05-08 14:52:52 UTC) #15
brettw
I didn't look at this yet, but I'm noticing I got a similar code review: ...
1 month, 2 weeks ago (2017-05-08 20:29:01 UTC) #16
jdoerrie
Thanks for the link to the other CL, I wasn't aware of it. It looks ...
1 month, 2 weeks ago (2017-05-08 23:11:43 UTC) #20
dyaroshev
https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h#newcode619 base/containers/flat_tree.h:619: }); You are doing binary search for the first ...
1 month, 2 weeks ago (2017-05-09 01:38:50 UTC) #23
dyaroshev
On 2017/05/08 23:11:43, jdoerrie (slow this week) wrote: > On 2017/05/08 14:52:52, jdoerrie (slow this ...
1 month, 2 weeks ago (2017-05-09 01:52:50 UTC) #24
dyaroshev
https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree_unittest.cc File base/containers/flat_tree_unittest.cc (right): https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree_unittest.cc#newcode772 base/containers/flat_tree_unittest.cc:772: } An empty range check is important. Maybe we ...
1 month, 2 weeks ago (2017-05-09 09:32:47 UTC) #25
dyaroshev
https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h#newcode619 base/containers/flat_tree.h:619: }); On 2017/05/09 01:38:49, dyaroshev wrote: > You are ...
1 month, 2 weeks ago (2017-05-09 11:31:42 UTC) #26
jdoerrie
https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h#newcode619 base/containers/flat_tree.h:619: }); On 2017/05/09 11:31:42, dyaroshev wrote: > On 2017/05/09 ...
1 month, 2 weeks ago (2017-05-09 17:03:30 UTC) #29
brettw
https://codereview.chromium.org/2853333004/diff/60001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/60001/base/containers/flat_tree.h#newcode204 base/containers/flat_tree.h:204: void insert(InputIterator first, InputIterator last); I hate diverging from ...
1 month, 2 weeks ago (2017-05-09 20:25:45 UTC) #30
dyaroshev
https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h#newcode619 base/containers/flat_tree.h:619: }); On 2017/05/09 17:03:30, jdoerrie (slow this week) wrote: ...
1 month, 2 weeks ago (2017-05-09 21:37:20 UTC) #33
dyaroshev
https://codereview.chromium.org/2853333004/diff/60001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/60001/base/containers/flat_tree.h#newcode204 base/containers/flat_tree.h:204: void insert(InputIterator first, InputIterator last); On 2017/05/09 21:37:19, dyaroshev ...
1 month, 2 weeks ago (2017-05-09 22:04:05 UTC) #34
brettw
On 2017/05/09 22:04:05, dyaroshev wrote: > I thought about it a bit more - probably ...
1 month, 2 weeks ago (2017-05-09 22:48:25 UTC) #35
jdoerrie
https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/40001/base/containers/flat_tree.h#newcode619 base/containers/flat_tree.h:619: }); On 2017/05/09 21:37:19, dyaroshev wrote: > On 2017/05/09 ...
1 month, 1 week ago (2017-05-10 15:39:18 UTC) #38
brettw
owners LGTM I didn't look at the logic details, I think dyaroshev was looking at ...
1 month, 1 week ago (2017-05-10 16:52:06 UTC) #39
dyaroshev
https://codereview.chromium.org/2853333004/diff/80001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/80001/base/containers/flat_tree.h#newcode621 base/containers/flat_tree.h:621: difference_type pos_first_new = std::distance(begin(), end()); Nit: Just say size()? ...
1 month, 1 week ago (2017-05-10 17:12:09 UTC) #40
jdoerrie
https://codereview.chromium.org/2853333004/diff/80001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/80001/base/containers/flat_tree.h#newcode204 base/containers/flat_tree.h:204: void insert(InputIterator first, On 2017/05/10 16:52:06, brettw (behind--catching up) ...
1 month, 1 week ago (2017-05-11 06:34:57 UTC) #45
dyaroshev
https://codereview.chromium.org/2853333004/diff/80001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/80001/base/containers/flat_tree.h#newcode624 base/containers/flat_tree.h:624: }; On 2017/05/11 06:34:57, jdoerrie (slow this week) wrote: ...
1 month, 1 week ago (2017-05-11 09:46:43 UTC) #48
jdoerrie
Next round, I tried to de-duplicate the code a bit. Performance for single element insertions ...
1 month, 1 week ago (2017-05-12 10:32:57 UTC) #51
dyaroshev
https://codereview.chromium.org/2853333004/diff/120001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/120001/base/containers/flat_tree.h#newcode663 base/containers/flat_tree.h:663: } Ok, I seem to fail to explain. Check ...
1 month, 1 week ago (2017-05-12 11:23:28 UTC) #52
jdoerrie
https://codereview.chromium.org/2853333004/diff/120001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/120001/base/containers/flat_tree.h#newcode663 base/containers/flat_tree.h:663: } On 2017/05/12 11:23:28, dyaroshev wrote: > Ok, I ...
1 month, 1 week ago (2017-05-12 21:03:17 UTC) #59
dyaroshev
Move only won't work( (std::make_move_iterator allows you to insert ranges of move only elements) Nit: ...
1 month, 1 week ago (2017-05-12 22:10:03 UTC) #60
jdoerrie
https://codereview.chromium.org/2853333004/diff/140001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/140001/base/containers/flat_tree.h#newcode640 base/containers/flat_tree.h:640: if (insert_inplace) { On 2017/05/12 22:10:03, dyaroshev wrote: > ...
1 month, 1 week ago (2017-05-17 06:41:16 UTC) #63
dyaroshev
LGTM with nits. (not going to torture you anymore)) Great work. I think that caching ...
1 month ago (2017-05-17 10:15:19 UTC) #66
jdoerrie
https://codereview.chromium.org/2853333004/diff/140001/base/containers/flat_tree.h File base/containers/flat_tree.h (right): https://codereview.chromium.org/2853333004/diff/140001/base/containers/flat_tree.h#newcode648 base/containers/flat_tree.h:648: std::copy(first, last, std::inserter(*this, end())); On 2017/05/17 10:15:19, dyaroshev wrote: ...
1 month ago (2017-05-17 11:32:05 UTC) #69
jdoerrie
I just saw your LGTM, thanks for the rigorous review and insightful comments :) I'll ...
1 month ago (2017-05-17 11:37:47 UTC) #70
brettw
LGTM, I didn't look at the details.
1 month ago (2017-05-18 22:24:42 UTC) #73
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/2853333004/180001
1 month ago (2017-05-19 06:07:05 UTC) #76
commit-bot: I haz the power
Try jobs failed on following builders: win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_ng/builds/449574)
1 month ago (2017-05-19 07:52:43 UTC) #78
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/2853333004/180001
1 month ago (2017-05-19 07:58:54 UTC) #80
commit-bot: I haz the power
1 month ago (2017-05-19 10:35:47 UTC) #83
Message was sent while issue was closed.
Committed patchset #10 (id:180001) as
https://chromium.googlesource.com/chromium/src/+/154dc49655238f0fc9928763bcf4...
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld cb946e318