Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2807933002:
Removing (dest != prev) check from LastUnique algorithm. (Closed)
DescriptionRemoving (dest != prev) check from LastUnique algorithm.
This check returns false for the first part of the loop and returns true for the second
one. We split this loop in two and remove this check.
Review-Url: https://codereview.chromium.org/2807933002
Cr-Commit-Position: refs/heads/master@{#469016}
Committed: https://chromium.googlesource.com/chromium/src/+/e01cd8a6d0e2addaca41d6e686d566d5050656a0
Patch Set 1 #
Total comments: 12
Patch Set 2 : Minimizing changes. #
Total comments: 7
Patch Set 3 : Comments. #
Total comments: 1
Patch Set 4 : Comments 2. #
Messages
Total messages: 29 (11 generated)
Description was changed from ========== Removing (dest != prev) check from LastUnique algorithm (speeding it up by ~30%) and refactoring. ========== to ========== Removing (dest != prev) check from LastUnique algorithm (speeding it up by ~30%) and refactoring. ==========
dyaroshev@yandex-team.ru changed reviewers: + brettw@chromium.org, danakj@chromium.org
S https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.cc File base/algorithm/benchmarks.cc (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.c... base/algorithm/benchmarks.cc:1: // Copyright 2017 The Chromium Authors. All rights reserved. I will remove these benchmarks before merging. I've included it here to show what was measured and to give the ability to reproduce my results. Benchmarking was done using google benchmark library: https://github.com/google/benchmark Here are my results: https://drive.google.com/file/d/0B5pZ43DhqaQDN2NwaFRvOC1hNkk/view?usp=sharing As you can see, we get ~30% faster with this change. Even though these are still extremely fast operations, I think there is no good reason to keep it slower. https://codereview.chromium.org/2807933002/diff/1/base/containers/flat_tree.h File base/containers/flat_tree.h (left): https://codereview.chromium.org/2807933002/diff/1/base/containers/flat_tree.h... base/containers/flat_tree.h:33: if (dest != prev) I suspect, that the main reason why this way is slower is because of this check. It makes sense only once: when you find first element to remove an we do it on every iteration of the loop. When we split this in two loops: before & after first element to remove - this check goes away. Branches are somewhat expensive (in very hot loops). https://codereview.chromium.org/2807933002/diff/1/base/containers/flat_tree_u... File base/containers/flat_tree_unittest.cc (left): https://codereview.chromium.org/2807933002/diff/1/base/containers/flat_tree_u... base/containers/flat_tree_unittest.cc:173: TEST(FlatTree, LastUnique) { @brettew - I haven't seen these tests. I like my tests somewhat better and I incorporated your cases in ints cases. I can do smth else if you want.
Noticed typos. https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_ranges.h File base/algorithm/sorted_ranges.h (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_range... base/algorithm/sorted_ranges.h:17: // the equal group, they choose last. but they keep the last element in the group of equivalents. https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_range... File base/algorithm/sorted_ranges_unittest.cc (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_range... base/algorithm/sorted_ranges_unittest.cc:19: const std::vector<T>& expected) { Unused
https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.cc File base/algorithm/benchmarks.cc (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.c... base/algorithm/benchmarks.cc:1: // Copyright 2017 The Chromium Authors. All rights reserved. On 2017/04/08 16:48:03, dyaroshev wrote: > Here are my results: > https://drive.google.com/file/d/0B5pZ43DhqaQDN2NwaFRvOC1hNkk/view?usp=sharing > As you can see, we get ~30% faster with this change. > To clarify: one_cycle_and_if - previous version. two_cycles - current version.
Please add a one-line title to the CL description. See https://chris.beams.io/posts/git-commit/
Description was changed from ========== Removing (dest != prev) check from LastUnique algorithm (speeding it up by ~30%) and refactoring. ========== to ========== Removing (dest != prev) check from LastUnique algorithm. This check returns false for the first part of the loop and returns true for the second one. We split this loop in two and remove this check. ==========
On 2017/04/12 15:44:22, danakj (out sick) wrote: > Please add a one-line title to the CL description. See > https://chris.beams.io/posts/git-commit/ Done.
Description was changed from ========== Removing (dest != prev) check from LastUnique algorithm. This check returns false for the first part of the loop and returns true for the second one. We split this loop in two and remove this check. ========== to ========== Removing (dest != prev) check from LastUnique algorithm. This check returns false for the first part of the loop and returns true for the second one. We split this loop in two and remove this check. ==========
https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_ranges.h File base/algorithm/sorted_ranges.h (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_range... base/algorithm/sorted_ranges.h:33: *out++ = *first; Wouldn't this preclude the container from holding move-only types?
https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_ranges.h File base/algorithm/sorted_ranges.h (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/sorted_range... base/algorithm/sorted_ranges.h:33: *out++ = *first; On 2017/04/12 15:54:48, danakj (out sick) wrote: > Wouldn't this preclude the container from holding move-only types? This algorithm should not move elements - it's a copy algorithm (like std::unique_copy). When we call it and we want to move elements, we ought to use move_iterators (like in UniquePickLast). So no, it works. There are tests for move only types (both new and for flat_tree).
At a high level, this is harder for me to understand than the old implementation. My rationale for keeping this in the internal part of flat_tree is that this is very unlikely to be used outside of this one use case. We try to keep the base API as simple as possible rather than a Boost-like collection of everything that anybody might ever want to use. I still think my reasoning for putting the algorithm where it was stands. In light of the above "this is an implementation detail of flat_*", the copy and non-copy variants aren't needed. To me, they make the API more difficult to understand as you have to understand what they all mean. Being like std::unique isn't much benefit here because I've never heard of std::unique_copy, and I think I have more familiarity with this kind of thing than most engineers on the team.
I'm much more interested in having a better deque/queue implementation that uses a vector. This just came up again today when I wondered why FrameTree::NodeIterator::NodeIterator was going through so much memory.
Is there a way we can get your performance advantage while keeping the implementation simple and in the flat_tree header?
On 2017/04/24 05:07:49, brettw (plz ping after 24h) wrote: > Is there a way we can get your performance advantage while keeping the > implementation simple and in the flat_tree header? Sorry, that I didn't respond for a while - I was on vacation. If you think that having a standalone header with algorithms is not benefitial, I can easily move the algorithm in the flat_tree header.
Patchset #2 (id:20001) has been deleted
On 2017/04/17 17:55:08, brettw (plz ping after 24h) wrote: > I've never heard of std::unique_copy, and I > think I have more familiarity with this kind of thing than most engineers on the > team. It's a cool algorithm) I suspect reasonably faster than copy + unique. Anyways, I did my best to minimize the changes. The only thing I left, that's not strictly necessary is defining all operations in containers_test_utils. That's just a good practise, I can reverse it too if you want me too.
Patchset #2 (id:40001) has been deleted
LGTM, just some comment suggestions. I like this approach much better. https://codereview.chromium.org/2807933002/diff/1/base/BUILD.gn File base/BUILD.gn (right): https://codereview.chromium.org/2807933002/diff/1/base/BUILD.gn#newcode119 base/BUILD.gn:119: "algorithm/sorted_ranges.h", Can you think of anything else we might move into this directory? Having a base subdirectory with one file in it seems not that great. If there isn't much more we can move there, maybe just put it in containers? One thing to consider might be to move the code in //base/containers/adapters.h to //base/algorithm/reverse_adapter.h https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.cc File base/algorithm/benchmarks.cc (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.c... base/algorithm/benchmarks.cc:1: // Copyright 2017 The Chromium Authors. All rights reserved. You can add them to the //base:base_perftests target. I don't think that target is run by any bot. But recently I've been using the JSON parser one manually when making changes to it. So it seels suited to what you're doing. https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... base/containers/flat_tree.h:27: return last; Can you append to this line "No duplicate elements found." https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... base/containers/flat_tree.h:34: // adjacent_find will force us to use BidirectionalIterator. This comment is confusing by itself here. I think you mean "...so do the search manually instead." Can you add something like that? Otherwise it seems like the comment might be explaining why you're calling adjacent_find. If this isn't what you mean, can you expand on this comment a bit more (or delete it)? https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... base/containers/flat_tree.h:36: for (Iterator next = std::next(first); next != last; ++next, ++first) This should have {} by our style guide (# lines is > 1). https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... base/containers/flat_tree.h:40: // last element should be copied unconditionally. Minor nit: capital letter @ beginning.
Patchset #3 (id:80001) has been deleted
@brettw I'm a bit confused with your comments - I deleted a few patchsets - maybe we had a little communication problem because of that. Can you please confirm your approve? https://codereview.chromium.org/2807933002/diff/1/base/BUILD.gn File base/BUILD.gn (right): https://codereview.chromium.org/2807933002/diff/1/base/BUILD.gn#newcode119 base/BUILD.gn:119: "algorithm/sorted_ranges.h", On 2017/04/26 21:48:50, brettw (plz ping after 24h) wrote: > Can you think of anything else we might move into this directory? Having a base > subdirectory with one file in it seems not that great. If there isn't much more > we can move there, maybe just put it in containers? > > One thing to consider might be to move the code in //base/containers/adapters.h > to //base/algorithm/reverse_adapter.h After your previous suggestion, I removed this directory. https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.cc File base/algorithm/benchmarks.cc (right): https://codereview.chromium.org/2807933002/diff/1/base/algorithm/benchmarks.c... base/algorithm/benchmarks.cc:1: // Copyright 2017 The Chromium Authors. All rights reserved. On 2017/04/26 21:48:51, brettw (plz ping after 24h) wrote: > You can add them to the //base:base_perftests target. I don't think that target > is run by any bot. But recently I've been using the JSON parser one manually > when making changes to it. So it seels suited to what you're doing. Unfortunately, it would break your builds. Google benchmark library is not in Chromium. I'm thinking about adding it. You think this might be a good idea? https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... base/containers/flat_tree.h:34: // adjacent_find will force us to use BidirectionalIterator. On 2017/04/26 21:48:51, brettw (plz ping after 24h) wrote: > This comment is confusing by itself here. I think you mean "...so do the search > manually instead." Can you add something like that? Otherwise it seems like the > comment might be explaining why you're calling adjacent_find. If this isn't what > you mean, can you expand on this comment a bit more (or delete it)? I've done smth. Looks better? https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... base/containers/flat_tree.h:36: for (Iterator next = std::next(first); next != last; ++next, ++first) On 2017/04/26 21:48:51, brettw (plz ping after 24h) wrote: > This should have {} by our style guide (# lines is > 1). Done. https://codereview.chromium.org/2807933002/diff/60001/base/containers/flat_tr... base/containers/flat_tree.h:40: // last element should be copied unconditionally. On 2017/04/26 21:48:51, brettw (plz ping after 24h) wrote: > Minor nit: capital letter @ beginning. Done.
Ping @dana
LGTM https://codereview.chromium.org/2807933002/diff/100001/base/containers/flat_t... File base/containers/flat_tree.h (right): https://codereview.chromium.org/2807933002/diff/100001/base/containers/flat_t... base/containers/flat_tree.h:26: // No duplicate elements found.. nit: just one period
The CQ bit was checked by dyaroshev@yandex-team.ru
The patchset sent to the CQ was uploaded after l-g-t-m from brettw@chromium.org, danakj@chromium.org Link to the patchset: https://codereview.chromium.org/2807933002/#ps120001 (title: "Comments 2.")
CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 120001, "attempt_start_ts": 1493825023207180,
"parent_rev": "9ca2a9ed3bf95aa2fb4d539f48bee36df2b3dd26", "commit_rev":
"e01cd8a6d0e2addaca41d6e686d566d5050656a0"}
Message was sent while issue was closed.
Description was changed from ========== Removing (dest != prev) check from LastUnique algorithm. This check returns false for the first part of the loop and returns true for the second one. We split this loop in two and remove this check. ========== to ========== Removing (dest != prev) check from LastUnique algorithm. This check returns false for the first part of the loop and returns true for the second one. We split this loop in two and remove this check. Review-Url: https://codereview.chromium.org/2807933002 Cr-Commit-Position: refs/heads/master@{#469016} Committed: https://chromium.googlesource.com/chromium/src/+/e01cd8a6d0e2addaca41d6e686d5... ==========
Message was sent while issue was closed.
Committed patchset #4 (id:120001) as https://chromium.googlesource.com/chromium/src/+/e01cd8a6d0e2addaca41d6e686d5... |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
