Issue 2552343003: First implementation of flat sets

dyaroshev

Description was changed from ========== First implementation of flat sets This patch introduces flat_set in ...

4 years ago (2016-12-06 20:24:04 UTC) #1

dyaroshev

dyaroshev@yandex-team.ru changed reviewers: + danakj@chromium.org, pkasting@chromium.org

4 years ago (2016-12-06 20:24:04 UTC) #2

dyaroshev

Description was changed from ========== First implementation of flat sets This patch introduces flat_set in ...

4 years ago (2016-12-06 20:24:54 UTC) #3

dyaroshev

Description was changed from ========== First implementation of flat sets (TODO: improve the description) This ...

4 years ago (2016-12-07 11:15:37 UTC) #4

Description was changed from

==========
First implementation of flat sets

(TODO: improve the description)

This patch introduces flat_set in chromium.
Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

List of unclear (so far) issues:
 - Do we want an interface that specialize allocators?
   (if we want the ability to specialize underlying containers,
    I think it should be a separate cl).
 - Can we use libcpp tests? They seem to have permissive license,
   but this is not my area of expertise

BUG=671759
==========

to

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.
None of analysed flat_set implementations (boost, eastl, folly) do this. Making
them
const forbids erase(remove_if) idiom, which is widely believed to be the fastest
way to
erase elements from a vector - therefore from a flat_set. I've contacted Sean 
Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator, Sentinel}
pair.
{Iterator/Sentinel} is an interface that is proposed for ranges from Ranges TS:
(talk at CppCon: https://youtu.be/mFUXNMfaciE)
Currently nowhere in chromium we do not use this type of ranges, and introducing
it 
without enable_if tricks make certain scenarios ambiguous.
Example:
   base::flat_set<int> s;
   s.insert(s.begin(), 3); // tries to insert with two template parameters
instead of
                                       // casting iterator to const_iterator.
We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    places in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked). However, we
typically
    do not use allocators in chromium, do we want to keep the possibility of 
    customising them in the interface, or do we want to rip it out?

- Do we want to leave the possibility of a small buffer optimisation for default
flat_set?
   std::vector does not invalidate iterators on move and swap, which forbids
small 
   buffer optimisation. This optimisation sometimes proves to be very
beneficial.
   If we are willing not to give the same guarantee as std::vector, we can
introduce it by
   default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...
==========

dyaroshev

Description was changed from ========== This patch introduces base::flat_set class in chromium. The interface is ...

4 years ago (2016-12-07 11:18:34 UTC) #5

Description was changed from

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.
None of analysed flat_set implementations (boost, eastl, folly) do this. Making
them
const forbids erase(remove_if) idiom, which is widely believed to be the fastest
way to
erase elements from a vector - therefore from a flat_set. I've contacted Sean 
Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator, Sentinel}
pair.
{Iterator/Sentinel} is an interface that is proposed for ranges from Ranges TS:
(talk at CppCon: https://youtu.be/mFUXNMfaciE)
Currently nowhere in chromium we do not use this type of ranges, and introducing
it 
without enable_if tricks make certain scenarios ambiguous.
Example:
   base::flat_set<int> s;
   s.insert(s.begin(), 3); // tries to insert with two template parameters
instead of
                                       // casting iterator to const_iterator.
We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    places in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked). However, we
typically
    do not use allocators in chromium, do we want to keep the possibility of 
    customising them in the interface, or do we want to rip it out?

- Do we want to leave the possibility of a small buffer optimisation for default
flat_set?
   std::vector does not invalidate iterators on move and swap, which forbids
small 
   buffer optimisation. This optimisation sometimes proves to be very
beneficial.
   If we are willing not to give the same guarantee as std::vector, we can
introduce it by
   default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...
==========

to

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator, Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently nowhere in chromium we do
not 
   use this type of ranges, and introducing it without enable_if tricks make
certain  
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // tries to insert with two template parameters
instead of
                                         // casting iterator to const_iterator.
  We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    places in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked). However, we
typically
    do not use allocators in chromium, do we want to keep the possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...
==========

dyaroshev

Description was changed from ========== This patch introduces base::flat_set class in chromium. The interface is ...

4 years ago (2016-12-08 11:18:07 UTC) #6

Description was changed from

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator, Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently nowhere in chromium we do
not 
   use this type of ranges, and introducing it without enable_if tricks make
certain  
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // tries to insert with two template parameters
instead of
                                         // casting iterator to const_iterator.
  We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    places in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked). However, we
typically
    do not use allocators in chromium, do we want to keep the possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...
==========

to

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // tries to insert with two template parameters
instead of
                              // casting iterator to const_iterator.
  We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

dyaroshev

Ping reviewers. Hi. I would like to continue working on this. I suspect that we ...

4 years ago (2016-12-09 17:13:08 UTC) #7

Peter Kasting

I'm not a base/ OWNER, so I'm not sure what sort of feedback you're looking ...

4 years ago (2016-12-12 20:34:30 UTC) #8

I'm not a base/ OWNER, so I'm not sure what sort of feedback you're looking for
from me.

I'd suggest taking the stuff in the libcpp_unittest file that isn't already in
the other unittest and copying those pieces there, then deleting the
libcpp_unittest file, so we just have one unittest file, and it's ours.

A few general comments:
* Spelling ("contiguous" as "contigious", "capacity" as "capasity", "weird" as
"weirid", "successful" as "successfull", etc.)/grammar issues in comments. 
Check these carefully.  (If English is not your strongest language feel free to
rope in someone else to help)
* Try to avoid "clang-format off" (in the places I saw, I don't think it's more
readable than using the normal clang-formatting)
* Prefer EXPECT_ to ASSERT_ if the test would not crash due to the condition
failing
* Prefer EXPECT_EQ(expected, actual) to EXPECT_TRUE(actual == expected)
* I'd probably omit most of the function comments in flat_set.h, except where
there's something of specific note to this container/implementation.  For
example, things like begin() and end() don't need comments; we can assume that
readers will be basically familiar with things common to STL container
interfaces.  To me, the comments just obscure the interface.
* Consider converting "if (x) return a; return b;" into "return x ? a : b;" for
brevity and to make clear this is really about data flow rather than control
flow.

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:552: if (position != end() && !value_comp()(x,
*position))
This condition is basically the negation of the one in equal_range().  Is there
a reason for this inconsistency?  Do we expect one result or the other of the
condition to be more likely?

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:574: if (position == begin() ||
value_comp()(*(position - 1), x))
Nit: Either add braces to outer conditional (body is more than one physical
line), or combine conditionals into one.  (2 places)

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:670: auto res = as_const().lower_bound(x);
Nit: Inline into next statement?

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:683: auto res = as_const().upper_bound(x);
Nit: Inline into next statement?

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:705: if (lower == end() || key_comp()(x, *lower)) {
Nit: No {} (you generally don't use them for one-line bodies in this file, so be
consistent)

dyaroshev

On @pkasting said: I'm not a base/ OWNER, so I'm not sure what sort of ...

4 years ago (2016-12-15 14:28:00 UTC) #10

On @pkasting said:

I'm not a base/ OWNER, so I'm not sure what sort of feedback you're looking for
from me.

- I'm open to suggestions.

I'd suggest taking the stuff in the libcpp_unittest file that isn't already in
the other unittest and copying those pieces there, then deleting the
libcpp_unittest file, so we just have one unittest file, and it's ours.

- Done.

A few general comments:
* Spelling ("contiguous" as "contigious", "capacity" as "capasity", "weird" as
"weirid", "successful" as "successfull", etc.)/grammar issues in comments. 
Check these carefully.  (If English is not your strongest language feel free to
rope in someone else to help)

- Hooray, spell checking in sublime now understands CamelCase and similar
styles. I hope this'll help me to avoid most of mistakes. Unfortunately my
spelling leaves significant space for improvement.

* Try to avoid "clang-format off" (in the places I saw, I don't think it's more
readable than using the normal clang-formatting)
* Prefer EXPECT_ to ASSERT_ if the test would not crash due to the condition
failing
* Prefer EXPECT_EQ(expected, actual) to EXPECT_TRUE(actual == expected)

I was trying to minimise diff with libc++ tests. Not so sure that it was a good
idea, so done.

* I'd probably omit most of the function comments in flat_set.h, except where
there's something of specific note to this container/implementation.  For
example, things like begin() and end() don't need comments; we can assume that
readers will be basically familiar with things common to STL container
interfaces.  To me, the comments just obscure the interface.

- Done.

* Consider converting "if (x) return a; return b;" into "return x ? a : b;" for
brevity and to make clear this is really about data flow rather than control
flow.

- One place, where that was possible (otherwise I would have to use make_pair
instead of brace initialisation, and I think that braces are much nicer). Done.

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:552: if (position != end() && !value_comp()(x,
*position))
On 2016/12/12 20:34:30, Peter Kasting wrote:
> This condition is basically the negation of the one in equal_range().  Is
there
> a reason for this inconsistency?  Do we expect one result or the other of the
> condition to be more likely?

Done.

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:574: if (position == begin() ||
value_comp()(*(position - 1), x))
On 2016/12/12 20:34:30, Peter Kasting wrote:
> Nit: Either add braces to outer conditional (body is more than one physical
> line), or combine conditionals into one.  (2 places)

Done.

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:670: auto res = as_const().lower_bound(x);
On 2016/12/12 20:34:30, Peter Kasting wrote:
> Nit: Inline into next statement?

Done.

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:683: auto res = as_const().upper_bound(x);
On 2016/12/12 20:34:30, Peter Kasting wrote:
> Nit: Inline into next statement?

Done.

https://codereview.chromium.org/2552343003/diff/1/base/containers/flat_set.h#...
base/containers/flat_set.h:705: if (lower == end() || key_comp()(x, *lower)) {
On 2016/12/12 20:34:30, Peter Kasting wrote:
> Nit: No {} (you generally don't use them for one-line bodies in this file, so
be
> consistent)

Done.

dyaroshev

dyaroshev@yandex-team.ru changed reviewers: + cpu@chromium.org, mark@chromium.org

4 years ago (2016-12-15 14:29:25 UTC) #11

dyaroshev

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h#newcode43 base/containers/flat_set.h:43: // Tests: This section does not make sense, since ...

4 years ago (2016-12-15 16:11:00 UTC) #14

Peter Kasting

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h#newcode72 base/containers/flat_set.h:72: // private types much easier to declare before everything ...

4 years ago (2016-12-16 08:09:08 UTC) #15

dyaroshev

Make more libc++ tests more Chromium like. Originally didn't want to do it, so that ...

4 years ago (2016-12-18 22:27:25 UTC) #16

Make more libc++ tests more Chromium like. Originally didn't want to do it, so
that we can check compare against them easier and merge new tests fast, but it's
not going to be much more complicated now.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:43: // Tests:
On 2016/12/15 16:10:59, dyaroshev wrote:
> This section does not make sense, since we have one test file. Remove with
next
> patch.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:72: // private types much easier to declare before
everything else in templates.
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Give an explicit "private:" header.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:77: // Types:
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Some of the section headers use a trailing colon, some a trailing period,
> some nothing.  Be consistent.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:150: // reserve, capacity and shrink_to_fit
invalidate iterators and references.
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Why would capacity() invalidate anything?
> 
> Nit: You use () on function names in the size management section below, but
not
> here.  Be consistent filewide on how you indicate this sort of thing.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:194: // Prefer erase(remove) idiom for deleting
multiple elements.
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: I might separate the future plans into a TODO, and be clearer about
> erase():
> 
> Assume that every operation invalidates iterators and references.  Insertion
or
> removal of one element can take O(size).  Prefer the erase(std::remove(),
end())
> idiom for deleting multiple elements.
> TODO(dyaroshev): Optimize range insertion, which currently just uses repeated
> single insertion.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:195: //
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Remove

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:252: // equivalent elements in sets or maps.
On 2016/12/16 08:09:07, Peter Kasting wrote:
> I don't really understand this comment, sorry :(  (Couldn't find documentation
> of the detail you refer to about std::set(), and don't understand the last
> sentence)

I've tried to make it cleaner.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:256: friend bool operator==(const flat_set& x, const
flat_set& y) {
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Wow, I never even knew you could define non-member friends inside a class
> declaration.

Because I'm writing stl like container, I've tried to match Alexandr Stepanov's
style where it seemed reasonable. He declares operators like this).
However this doesn't allow me to predeclare them and define later, but if I
declare them outside of class I can't keep full interface in one place. I
thought this way is preferable.

Same goes to using x, y vs Scott Meyer's lhs, rhs - Stepanov claims that this is
more mathematic approach.

Here are some of Stepanov's courses, if you are interested:
https://www.youtube.com/user/A9Videos/playlists
(They are unbelievably slow and the sound is bad but material is interesting
and, for my money, considerably more approachable than Elements of Programming
or From Mathematics to Generic Programming).

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:288: struct Impl : Compare {  // empty base class
optimization
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: I suggest being less opaque here, e.g.:
> 
> So that key_comp() and value_comp() don't need to construct a new instance
each
> time, we store an instance of Compare.  This is likely an empty class, so by
> wrapping the underlying_type instance in a struct inheriting from Compare, we
> can make use of the empty base class optimization to save space, compared to
> just keeping a Compare instance as a direct member.

Motivation is not 100% correct, made comment more explicit.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:642: if (lower == end() || key_comp()(x, *lower))
On 2016/12/16 08:09:07, Peter Kasting wrote:
> When would lower != end(), but key_comp() succeed?  Shouldn't
std::lower_bound()
> guarantee that's not the case?

Lower bound returns the smallest position, where you can insert the element.
[1, 3] -> looking for 2, lower_bound - returns [1, -> 3], 2 < 3, we should
return [1, -><- 3] as the result.

I've rechecked against eastl, they do the same thing:
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
File base/containers/flat_set_unittest.cc (right):

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:7: // Following tests are modified and
extended tests from libcpp for std::set.
On 2016/12/16 08:09:08, Peter Kasting wrote:
> You say "extended" here, but below you document only removals, not extensions.
> 
> I kinda feel like either we should document the extensions too, or we should
> just remove all this?  I lean towards the latter, because honestly, these are
> our tests, and we're going to change the syntax, style, etc., so trying to
> document all the exact differences doesn't make a ton of sense to me.

Changed the description a bit. I think removed tests can be useful because they
expose different subtle issues that I think are useful to support in the future.
And when we support them we should port those tests too.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:35: // * No tests, counting allocations.
Flat sets have different allocation
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: No comma

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:44: MoveOnly(const MoveOnly&);
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: As much as possible, declare private section after public.  (multiple
> places)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:45: MoveOnly& operator=(const MoveOnly&);
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Use DISALLOW_COPY_AND_ASSIGN to remove these.  (2 places)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:51: MoveOnly(MoveOnly&& x) : data_(x.data_)
{ x.data_ = 0; }
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: |rhs| may be a more idiomatic name than |x|.  (multiple places)

Replied in other comment

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:54: x.data_ = 0;
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Why set x.data_ at all?  So behavior failures will be more obvious?  (multiple
> places)

We check that we don't leave moved out elements.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:58: int get() const { return data_; }
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Accessors should be named like the underlying member.  (2 places)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:107: void operator,(T const&) = delete;
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Why?

Copied from libc++. I think this is to avoid some scary typos. Removed.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:169: // Check that base::flat_set and it's
iterators can be instantiated with an
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: its

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:182: // unused
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: Not a complete sentence, too vague to be useful/actionable (if you really
> need to describe this difference put it in the section atop the file?)

It's just strange to declare a set of type without comparison. So I wanted to
point that out.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:190: // class flat_set
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: No need to "// class flat_set" above all these tests.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:206: {
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Avoid these {} blocks in tests except where you actually have multiple
such
> blocks.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:207: typedef base::flat_set<int> C;
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: "using" type aliases seem slightly more readable than typedefs to me.
> 
> Avoid cryptic type names like "C".  "Set" here would be fine.  (multiple
tests)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:214:
static_assert((std::is_same<C::reference, int&>::value), "");
On 2016/12/15 16:10:59, dyaroshev wrote:
> Tests for reference/pointer etc are libc++ specific. Fix with the next patch.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:218:
static_assert((std::is_same<C::size_type, std::size_t>::value), "");
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: For better or worse, Chromium code does not qualify size_t with std::.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:238: EXPECT_EQ(m.size(),
static_cast<M::size_type>(0));
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Say 0U instead of casting to size_type.  (The static_assert above ensures
> this is always size_t.)  Also, for EXPECT_EQ/NE, use (expected, actual) order.

> (many places)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:268: EXPECT_EQ(*next(m.begin()), 2);
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: Shouldn't this be std::next()?  (many places)

Worked because of ADL lookup. Copied from libc++ this way. Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:305: EXPECT_EQ(m2.count(4),
static_cast<M::size_type>(1));
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: Here and a lot of places below it seems like a lot of lines are spent
just
> checking all the elements of the set.  Worse, we use various different methods
> (repeatedly calling count(), dereferencing all the iterators, etc.)
> 
> I suggest defining a helper to check equality with some array/initializer_list
> or something, so you can condense these to something more readable like
> EXPECT_TRUE(SetIs(m2, {1, 2, 3, 4}));
> 
> (That's assuming you can't get something like EXPECT_EQ(m2, {1, 2, 3, 4}) to
> work, which would be even better.)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:341: typedef M::value_type V;
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Just use int directly, and don't bother with the explicit constructions
> below.  (many places)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:345: EXPECT_EQ(distance(m.begin(),
m.end()),
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: Shouldn't this be std::distance?  (3 places)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:346:
static_cast<M::difference_type>(m.size()));
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Use ptrdiff_t directly (many places)

I don't think that the standard guaranties this. Anyways I think this way
clearer shows the intention.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:391: M m(ar, ar + sizeof(ar) /
sizeof(ar[0]));
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: use arraysize().  (Multiple places)

Changed to using initiailizer lists and begin/end

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:492: EXPECT_GE(capacity_before,
m.capacity());
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Maybe a stronger test would be to reserve() more space first, then EXPECT_GT
> here?  Otherwise, shrink_to_fit() could do nothing and this test would pass.

I've checked against the spec: shrink_to_fit can do nothing and still be a
conforming shrink_to_fit.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:589: for (int j = 1;
static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: What about:
> 
>   for (int j = 1; i != m.end(); ++i, ++j)
> 
> This avoids the need to cast.  (2 places)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:760: TEST(FlatSet, InsertRange) {
On 2016/12/15 16:10:59, dyaroshev wrote:
> Add tests for stability.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:823: EXPECT_TRUE(!r.second);
On 2016/12/16 08:09:08, Peter Kasting wrote:
> Nit: EXPECT_FALSE(r.second)

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:1097: // Comparators.
On 2016/12/15 16:10:59, dyaroshev wrote:
> Add test that flat_set is sorted with provided comparator.

Done.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:1115: R r = m.count(5);
On 2016/12/16 08:09:07, Peter Kasting wrote:
> Nit: Avoid unneeded temps, e.g.
> 
>   EXPECT_EQ(1U, m.count(5));
>   EXPECT_EQ(1U, m.count(6));
>   ...

Done, where seemed appropriate.

Peter Kasting

Have not re-reviewed https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h#newcode256 base/containers/flat_set.h:256: friend bool operator==(const flat_set& x, const ...

4 years ago (2016-12-18 22:47:43 UTC) #17

Have not re-reviewed

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:256: friend bool operator==(const flat_set& x, const
flat_set& y) {
On 2016/12/18 22:27:23, dyaroshev wrote:
> On 2016/12/16 08:09:07, Peter Kasting wrote:
> > Wow, I never even knew you could define non-member friends inside a class
> > declaration.
> 
> Because I'm writing stl like container, I've tried to match Alexandr
Stepanov's
> style where it seemed reasonable. He declares operators like this).
> However this doesn't allow me to predeclare them and define later, but if I
> declare them outside of class I can't keep full interface in one place. I
> thought this way is preferable.

Yeah, I'm fine with it, it was just new to me.

> Same goes to using x, y vs Scott Meyer's lhs, rhs - Stepanov claims that this
is
> more mathematic approach.

Well, honestly, neither name is really compliant with Google's style guide about
"avoid abbreviations" -- maybe it'd be better to use a name like |other|, which
has more parallel structure with |this|.  I don't feel violently.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set.h:642: if (lower == end() || key_comp()(x, *lower))
On 2016/12/18 22:27:23, dyaroshev wrote:
> On 2016/12/16 08:09:07, Peter Kasting wrote:
> > When would lower != end(), but key_comp() succeed?  Shouldn't
> std::lower_bound()
> > guarantee that's not the case?
> 
> Lower bound returns the smallest position, where you can insert the element.
> [1, 3] -> looking for 2, lower_bound - returns [1, -> 3], 2 < 3, we should
> return [1, -><- 3] as the result.
> 
> I've rechecked against eastl, they do the same thing:
>
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....

Oh, key_comp() is basically equivalent to "<"?  I was thinking it was equivalent
to ">".  This makes more sense now :)

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
File base/containers/flat_set_unittest.cc (right):

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:346:
static_cast<M::difference_type>(m.size()));
On 2016/12/18 22:27:24, dyaroshev wrote:
> On 2016/12/16 08:09:07, Peter Kasting wrote:
> > Nit: Use ptrdiff_t directly (many places)
> 
> I don't think that the standard guaranties this. Anyways I think this way
> clearer shows the intention.

The standard doesn't, but your static_assertions at the top of this file do.  If
this wasn't correct, the file couldn't compile.

This is related to why we explicitly direct people in the codebase to use size_t
instead of e.g. string::size_type.

It's a tradeoff, intent-wise.  You're right that this way makes clear that the
key is to match the result of calling distance().  The other route makes more
clear that in fact, you're guaranteed that that result is a ptrdiff_t.

The main reason I prefer one is just that it's shorter and has fewer symbols
than the other, and since the cast is mostly noise to get the test to compile
without complaint, and not "an important piece of functionality programmers
should read", I figure, just minimize that noise.

Again, I could be convinced to do otherwise.

https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:492: EXPECT_GE(capacity_before,
m.capacity());
On 2016/12/18 22:27:23, dyaroshev wrote:
> On 2016/12/16 08:09:08, Peter Kasting wrote:
> > Maybe a stronger test would be to reserve() more space first, then EXPECT_GT
> > here?  Otherwise, shrink_to_fit() could do nothing and this test would pass.
> 
> I've checked against the spec: shrink_to_fit can do nothing and still be a
> conforming shrink_to_fit.

Wow.  That seems unfortunate.

I would add an explicit comment here noting that this test intentionally doesn't
verify that shrink_to_fit() shrinks anything, due to the reason you just gave :(

dyaroshev

On 2016/12/18 22:47:43, Peter Kasting wrote: > Have not re-reviewed > > https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h > File ...

4 years ago (2016-12-18 23:07:14 UTC) #18

On 2016/12/18 22:47:43, Peter Kasting wrote:
> Have not re-reviewed
> 
>
https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_set.h
> File base/containers/flat_set.h (right):
> 
>
https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
> base/containers/flat_set.h:642: if (lower == end() || key_comp()(x, *lower))
> On 2016/12/18 22:27:23, dyaroshev wrote:
> > On 2016/12/16 08:09:07, Peter Kasting wrote:
> > > When would lower != end(), but key_comp() succeed?  Shouldn't
> > std::lower_bound()
> > > guarantee that's not the case?
> > 
> > Lower bound returns the smallest position, where you can insert the element.
> > [1, 3] -> looking for 2, lower_bound - returns [1, -> 3], 2 < 3, we should
> > return [1, -><- 3] as the result.
> > 
> > I've rechecked against eastl, they do the same thing:
> >
>
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....
> 
> Oh, key_comp() is basically equivalent to "<"?  I was thinking it was
equivalent
> to ">".  This makes more sense now :)
> 

Yes, standard library uses <-like comparators everywhere.

>
https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
> File base/containers/flat_set_unittest.cc (right):
> 
>
https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
> base/containers/flat_set_unittest.cc:346:
> static_cast<M::difference_type>(m.size()));
> On 2016/12/18 22:27:24, dyaroshev wrote:
> > On 2016/12/16 08:09:07, Peter Kasting wrote:
> > > Nit: Use ptrdiff_t directly (many places)
> > 
> > I don't think that the standard guaranties this. Anyways I think this way
> > clearer shows the intention.
> 
> The standard doesn't, but your static_assertions at the top of this file do. 
If
> this wasn't correct, the file couldn't compile.
> 
> This is related to why we explicitly direct people in the codebase to use
size_t
> instead of e.g. string::size_type.
> 
> It's a tradeoff, intent-wise.  You're right that this way makes clear that the
> key is to match the result of calling distance().  The other route makes more
> clear that in fact, you're guaranteed that that result is a ptrdiff_t.
> 
> The main reason I prefer one is just that it's shorter and has fewer symbols
> than the other, and since the cast is mostly noise to get the test to compile
> without complaint, and not "an important piece of functionality programmers
> should read", I figure, just minimize that noise.
> 
> Again, I could be convinced to do otherwise.

static_asserts were copied from libcpp, I'm not sure that they will compile on
MSVC and I've removed them.
I think It adds more precise api check, migration to a newer standard library
version might go easier etc.

How about we wait on third voice on this and similar issues (naming, etc) (we
seem to need it anyway, since you are not a base-owner)?

> 
>
https://codereview.chromium.org/2552343003/diff/40001/base/containers/flat_se...
> base/containers/flat_set_unittest.cc:492: EXPECT_GE(capacity_before,
> m.capacity());
> On 2016/12/18 22:27:23, dyaroshev wrote:
> > On 2016/12/16 08:09:08, Peter Kasting wrote:
> > > Maybe a stronger test would be to reserve() more space first, then
EXPECT_GT
> > > here?  Otherwise, shrink_to_fit() could do nothing and this test would
pass.
> > 
> > I've checked against the spec: shrink_to_fit can do nothing and still be a
> > conforming shrink_to_fit.
> 
> Wow.  That seems unfortunate.
> 
> I would add an explicit comment here noting that this test intentionally
doesn't
> verify that shrink_to_fit() shrinks anything, due to the reason you just gave
:(

Ok. I'll add with the next patch.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set.h:149: void shrink_to_fit();
Add a comment that shrink_to_fit can be a no-op.

Peter Kasting

I think this is about as good as I can get things. One of the ...

4 years ago (2016-12-20 02:33:51 UTC) #19

dyaroshev

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h#newcode47 base/containers/flat_set.h:47: // Current implementation is not particularly tweaked and based ...

3 years, 12 months ago (2016-12-20 21:59:56 UTC) #20

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set.h:47: // Current implementation is not particularly
tweaked and based on
On 2016/12/20 02:33:50, Peter Kasting wrote:
> Nit: Is this referring to the current implementation of the whole class not
> being tweaked, or the current implementation of range insertion?  It sounds
like
> the former, but then talks only about the latter, and it's not clear to me
that
> the former is a big issue aside from the latter.

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set.h:149: void shrink_to_fit();
On 2016/12/18 23:07:14, dyaroshev wrote:
> Add a comment that shrink_to_fit can be a no-op.

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set.h:186: // range insertion before class declaration.
On 2016/12/20 02:33:50, Peter Kasting wrote:
> Nit: "before class declaration" here appears to be referring to "insertion"
> rather than "notes section".  Maybe "See the Notes section in the class
comments
> for more on range insertion."

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set.h:248: // Flat sets are compared using operators
defined for key type and not
On 2016/12/20 02:33:50, Peter Kasting wrote:
> Shouldn't "key type" here be |underlying_type|?  That's what it seems like
> operator==()/operator<() actually invoke.

I think it should work like this regardless of the |underlying type|. Maybe for
general |underlying_type| it's better to write operator<() explicitly by hand,
so we do not rely on it's implementation not being weird this way. I haven't
done it for vectors, since they might have done some tricks to do it faster that
are not available in std::lexicographical_compare. Having said that, I hope that
Chromium's containers do the right thing.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set.h:288: // of an empty base class optimization.
On 2016/12/20 02:33:50, Peter Kasting wrote:
> Nit: OK, how about this.  This is basically your comment, but I tried to make
it
> flow a little better and have a little more detail.
> 
> To support comparators that may not be cheap (or possible!) to
> default-construct, we have to store an instance of Compare.  Using inheritance
> here lets us take advantage of the empty base class optimization to avoid
extra
> space in the common case when Compare has no state.

Done, except I removed not cheap part. If we would care for comparisons that are
not cheep to construct, we would have to expose a way to get a reference to our
compare and we would not use key_comp(), value_comp() in the implementation.
Standard library relies on the comparisons being small cheep objects, I think we
should do the same thing.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
File base/containers/flat_set_unittest.cc (right):

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:57: friend bool operator==(const MoveOnly&
x, const MoveOnly& y) {
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Any particular reason to prefer member vs. non-member for these relational
> operators?

1. This type is implicitly convertible from int (to make tests more readable)
and this allows me to do 1 == MoveOnly(1) as well as MoveOnly(1) == 1. So for
example EXPECT_EQ(1, MoveOnly(1)); will work.
2. This is generally considered to be the preferable way, because there is no
semantic difference between left and right operand, while member form implies
one.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:142: double double_ = 0.0;
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Nit: I dunno that I'm as big a fan of these initializers when we don't
actually
> use them except in one constructor.
> 
> Might be better to instead remove these and declare the first constructor as:
> 
>   Emplaceable() : Emplaceable(0, 0.0) {}

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:176: return std::equal(x_range.begin(),
x_range.end(), y_range.begin());
On 2016/12/20 02:33:50, Peter Kasting wrote:
> Nit: Or just:
> 
>   return (std::distance(x_range.begin(), x_range.end()) ==
>           std::distance(y_range.begin(), y_range.end())) &&
>          std::equal(x_range.begin(), x_range.end(), y_range.begin());

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:185: for (const auto& val : range) {
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Nit: {} unnecessary

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:202: << " Actual: " <<
RangeToString(tested_range);
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Nit: Maybe put a comma at the beginning of this second string constant

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:273: // These are guarantied to be
portable.
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Nit: guaranteed

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:293: using Set = base::flat_set<int>;
On 2016/12/20 02:33:50, Peter Kasting wrote:
> This alias appears in basically every test.  Maybe define it at file scope and
> only override it locally where needed.

Moved all common typedefs in anonymous namespace. Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:302: Set
cont{NonDefaultConstructibleCompare(0)};
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Do you really need to use {} here?  (Maybe it avoids Most Vexing Parse?)

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:421:
EXPECT_EQ(static_cast<Set::size_type>(0), cont.count(0));
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Nit: I still suggest using "0U" and similar for cases like this, as we do in
all
> our other tests.

Done.

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:564: int value = 2;
On 2016/12/20 02:33:51, Peter Kasting wrote:
> Does this test not test the same thing if you inline these values into the
> insert() calls instead of storing in a temp?

I was trying to make emphasise that it calls insert(const value_type&) not
insert(value_type&&).

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_se...
base/containers/flat_set_unittest.cc:621:
EXPECT_EQ(static_cast<Set::size_type>(3), *result.first);
On 2016/12/20 02:33:51, Peter Kasting wrote:
> This cast seems incorrect.

Done.

Peter Kasting

https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h#newcode248 base/containers/flat_set.h:248: // Flat sets are compared using operators defined for ...

3 years, 12 months ago (2016-12-20 22:06:39 UTC) #21

dyaroshev

On 2016/12/20 22:06:39, Peter Kasting wrote: > https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h > File base/containers/flat_set.h (right): > > https://codereview.chromium.org/2552343003/diff/60001/base/containers/flat_set.h#newcode248 ...

3 years, 12 months ago (2016-12-20 22:15:01 UTC) #22

Peter Kasting

Reminder: Try and reply inline in the codereview tool if you can On 2016/12/20 22:15:01, ...

3 years, 12 months ago (2016-12-20 22:53:51 UTC) #23

dyaroshev

On 2016/12/20 22:53:51, Peter Kasting wrote: > Reminder: Try and reply inline in the codereview ...

3 years, 12 months ago (2016-12-20 23:46:29 UTC) #24

Peter Kasting

On 2016/12/20 23:46:29, dyaroshev wrote: > On 2016/12/20 22:53:51, Peter Kasting wrote: > > Reminder: ...

3 years, 12 months ago (2016-12-20 23:57:23 UTC) #25

On 2016/12/20 23:46:29, dyaroshev wrote:
> On 2016/12/20 22:53:51, Peter Kasting wrote:
> > Reminder: Try and reply inline in the codereview tool if you can
> > 
> > On 2016/12/20 22:15:01, dyaroshev wrote:
> > > Defining it in terms of
> > > underlying_type is a very subtle difference from std::set.
> > 
> > I'm not sure I understand what you're saying here.
> > 
> > Are you saying this?  "Technically, set is defined as implementing
operator<()
> > in terms of something equivalent to lexicographical_compare() for the key
> types.
> >  Because underlying_type is a vector, and vector::operator<() is defined
with
> > the same guarantee, we can use that to implement this and be compliant.  But
> if
> > we were to change underlying_type to something without this guarantee, we
> would
> > no longer match std::set.  We could eliminate the possibility of future
> > noncompliance by using lexicographical_compare() directly now."
> > 
> > If yes, then I think it's fine to implement as you've done for now, I would
> just
> > say something like what I've said above in the comment.  My goal was not to
> make
> > you change the implementation, it was to make the comment clearer.
> 
> I think that the comments on the interface should fist of all express the
> semantics of an operation and define a contract on it. The question is - who
has
> the bug: user or container?
> I think that lexicographical_compare is a correct behaviour. But if we define
it
> as comparing on |underlying_type| and then change |underlying_type| to other
> container - we would have to fix users that don't work with new behavior,
which
> does not seem right.
> In a similar situation, the class comments state that iterators invalidate on
> move. In current implementation they don't. But if the user relies on it, he
or
> she breaks the contract, and fixing the user would be a correct thing to do.

Comments need to both express the contract and explain the implementation.  Just
expressing the contract is insufficient, especially in cases where e.g. the
contract is that X may happen but the implementation is that it doesn't.

My suggested comment was an explicit attempt to do both.  I read your response
as saying you're reluctant to talk about underlying_type at all because it's not
part of the contract.  But it's an important part of the implementation, so it
deserves explanation somewhere.

Perhaps this could be resolved by splitting the comment into "contract" and
"implementation" pieces and placing the latter within function definition(s), a
la:

// As with std::set, inequality operators for the whole flat_set are equivalent
// to using lexicographical_compare() on the key types, rather than using
// elementwise key_comp() as e.g. lower_bound() does.

...

friend bool operator<(const flat_set& x, const flat_set& y) {
  // vector::operator<() has the same contract we need here, so we use it
  // directly for brevity and in case it is more optimal than calling
  // lexicograhpical_compare().  If the underlying container type is changed,
  // this code may need to be modified.
  return x.impl_.body_ < y.impl_.body_;
}

dyaroshev

On 2016/12/20 23:57:23, Peter Kasting wrote: > On 2016/12/20 23:46:29, dyaroshev wrote: > > On ...

3 years, 12 months ago (2016-12-21 00:05:14 UTC) #26

On 2016/12/20 23:57:23, Peter Kasting wrote:
> On 2016/12/20 23:46:29, dyaroshev wrote:
> > On 2016/12/20 22:53:51, Peter Kasting wrote:
> > > Reminder: Try and reply inline in the codereview tool if you can
> > > 
> > > On 2016/12/20 22:15:01, dyaroshev wrote:
> > > > Defining it in terms of
> > > > underlying_type is a very subtle difference from std::set.
> > > 
> > > I'm not sure I understand what you're saying here.
> > > 
> > > Are you saying this?  "Technically, set is defined as implementing
> operator<()
> > > in terms of something equivalent to lexicographical_compare() for the key
> > types.
> > >  Because underlying_type is a vector, and vector::operator<() is defined
> with
> > > the same guarantee, we can use that to implement this and be compliant. 
But
> > if
> > > we were to change underlying_type to something without this guarantee, we
> > would
> > > no longer match std::set.  We could eliminate the possibility of future
> > > noncompliance by using lexicographical_compare() directly now."
> > > 
> > > If yes, then I think it's fine to implement as you've done for now, I
would
> > just
> > > say something like what I've said above in the comment.  My goal was not
to
> > make
> > > you change the implementation, it was to make the comment clearer.
> > 
> > I think that the comments on the interface should fist of all express the
> > semantics of an operation and define a contract on it. The question is - who
> has
> > the bug: user or container?
> > I think that lexicographical_compare is a correct behaviour. But if we
define
> it
> > as comparing on |underlying_type| and then change |underlying_type| to other
> > container - we would have to fix users that don't work with new behavior,
> which
> > does not seem right.
> > In a similar situation, the class comments state that iterators invalidate
on
> > move. In current implementation they don't. But if the user relies on it, he
> or
> > she breaks the contract, and fixing the user would be a correct thing to do.
> 
> Comments need to both express the contract and explain the implementation. 
Just
> expressing the contract is insufficient, especially in cases where e.g. the
> contract is that X may happen but the implementation is that it doesn't.
> 
> My suggested comment was an explicit attempt to do both.  I read your response
> as saying you're reluctant to talk about underlying_type at all because it's
not
> part of the contract.  But it's an important part of the implementation, so it
> deserves explanation somewhere.
> 
> Perhaps this could be resolved by splitting the comment into "contract" and
> "implementation" pieces and placing the latter within function definition(s),
a
> la:
> 
> // As with std::set, inequality operators for the whole flat_set are
equivalent
> // to using lexicographical_compare() on the key types, rather than using
> // elementwise key_comp() as e.g. lower_bound() does.
> 
> ...
> 
> friend bool operator<(const flat_set& x, const flat_set& y) {
>   // vector::operator<() has the same contract we need here, so we use it
>   // directly for brevity and in case it is more optimal than calling
>   // lexicograhpical_compare().  If the underlying container type is changed,
>   // this code may need to be modified.
>   return x.impl_.body_ < y.impl_.body_;
> }

Works for me.

dyaroshev

On 2016/12/20 23:57:23, Peter Kasting wrote: > Perhaps this could be resolved by splitting the ...

3 years, 12 months ago (2016-12-21 18:11:27 UTC) #27

Peter Kasting

On 2016/12/21 18:11:27, dyaroshev wrote: > On 2016/12/20 23:57:23, Peter Kasting wrote: > > > ...

3 years, 12 months ago (2016-12-21 20:08:34 UTC) #28

dyaroshev

On 2016/12/20 02:33:51, Peter Kasting wrote: > I think this is about as good as ...

3 years, 12 months ago (2016-12-23 21:49:14 UTC) #29

vmpstr

A lot of this functionality is what an std::set would provide. I feel like this ...

3 years, 11 months ago (2017-01-11 21:01:42 UTC) #31

Peter Kasting

On 2017/01/11 21:01:42, vmpstr wrote: > A lot of this functionality is what an std::set ...

3 years, 11 months ago (2017-01-11 21:32:05 UTC) #32

vmpstr

On 2017/01/11 21:32:05, Peter Kasting wrote: > On 2017/01/11 21:01:42, vmpstr wrote: > > A ...

3 years, 11 months ago (2017-01-11 21:51:51 UTC) #33

dyaroshev

On 2017/01/11 21:01:42, vmpstr wrote: > (I'm also not a base/ owner btw :) ) ...

3 years, 11 months ago (2017-01-16 06:58:02 UTC) #34

On 2017/01/11 21:01:42, vmpstr wrote:
> (I'm also not a base/ owner btw :) )

Thanks for your input anyways)

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:39: //       TODO(dyaroshev): Research the
possibility of using a small buffer.
On 2017/01/11 21:01:42, vmpstr wrote:
> File a bug and reference it here please.

I would like to wait for a reply from a base/Owner. He/She might disagree
whether small buffer optimisation is a good idea. And if we decide to expose
underlying container in the api, small buffer should be it's property rather
than flat_set's. In this case it should be a different bug.

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:43: // TODO(dyaroshev): Add list of benchmarks
heavily affected by performance
On 2017/01/11 21:01:42, vmpstr wrote:
> File a bug and reference it here please.

I don't think this one can be done in a bug. The idea is: when flat_set is used
and we have a benchmark, heavily affected by it, it should be listed here.
Considering how long it takes to commit to base, such list should probably be
somewhere else)

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:53: // TODO(dyaroshev): research better algorithm for
range insertion.
On 2017/01/11 21:01:41, vmpstr wrote:
> File a bug and reference it here please.

I'd postpone this to after review from base/Owners.

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:56: class Compare = std::less<Key>,  // instead of
std::default_order_t
On 2017/01/11 21:01:42, vmpstr wrote:
> I don't think std::default_order_t is in the standard, do you need this
comment?

Thanks, it looks like default_order_t is going to be removed from c++17::
http://en.cppreference.com/w/cpp/utility/functional/default_order

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:157: // clear() leaves the capacity() of the flat_set
unchanged.
On 2017/01/11 21:01:42, vmpstr wrote:
> doesn't this depend on the underlying_type (it's true of std::vector, i
guess)?
> Do you need this comment?

I am a bit on edge here: we currently don't expose underlying container in the
interface and I would like to commit to this property. But, unlike comparisons,
it might not be easy without underlying_type support. I would like to wait for a
base/Owner on this one.

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:298: struct Impl : Compare {
On 2017/01/11 21:01:42, vmpstr wrote:
> According to https://google.github.io/styleguide/cppguide.html#Inheritance
this
> should be composition instead. I don't think the memory savings you might get
> from this are worth the complexity.

I would say that Google's style guide is trying to avoid unnecessary
complications in common code. This is a highly reusable component in base, we
might have a bit of premature optimisations. Let's wait for a base/Owner.

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:542: // crbug.com/677044
On 2017/01/11 21:01:42, vmpstr wrote:
> Leave a more verbose comment please.

Done.

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_s...
base/containers/flat_set.h:553: // crbug.com/677044
On 2017/01/11 21:01:42, vmpstr wrote:
> Leave a more verbose comment please.

Done.

danakj

https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_set.h#newcode53 base/containers/flat_set.h:53: // TODO(dyaroshev): research better algorithm for range insertion. On ...

3 years, 11 months ago (2017-01-16 15:21:44 UTC) #35

dyaroshev

On 2017/01/16 15:21:44, danakj (slow) wrote: > https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_set.h > File base/containers/flat_set.h (right): > > https://codereview.chromium.org/2552343003/diff/140001/base/containers/flat_set.h#newcode53 ...

3 years, 11 months ago (2017-01-17 10:25:14 UTC) #36

Peter Kasting

On 2017/01/17 10:25:14, dyaroshev wrote: > I respond to his reviews fully, I'm sorry if ...

3 years, 11 months ago (2017-01-17 18:06:12 UTC) #37

vmpstr

On 2017/01/17 18:06:12, Peter Kasting wrote: > On 2017/01/17 10:25:14, dyaroshev wrote: > > I ...

3 years, 11 months ago (2017-01-17 19:29:44 UTC) #38

On 2017/01/17 18:06:12, Peter Kasting wrote:
> On 2017/01/17 10:25:14, dyaroshev wrote:
> > I respond to his reviews fully, I'm sorry if it wasn't clear.
> > I asked to wait on a few things:
> >  - creating bugs. I got that I need to create bugs on all todos and I will
do
> > that before merging. I just don't know which todos it's going to be, because
> we
> > haven't settle on the interface yet and there is a possibility that some of
> the
> > things that I've listed as TODOs will be removed.
> >  - removing empty base class optimisation. I'm against it for a highly
> reusable
> > component as flat_set. It's my understanding that we can do slightly more
> > complex things in base against regular code if it makes sense. Removing it
is
> > reasonable amount of work. I would like to have an informed opinion on
writing
> > base on this one.
> >  - clear does not change capacity. We don't expose underlying_type to the
> > outside world right now. If we are going to do that - we can refer to the
> > underlying_type. If we are not - we can commit to the property of a vector.
> It's
> > a useful property of clear() that's good to have a comment about. Anyways,
> > without knowing the interface we are going to expose, I don't think it's a
> good
> > idea to just remove the comment.
> 
> I think the implication was to treat vmpstr's review as if he were an OWNER. 
If
> he doesn't suggest changing various things about the interface, assume we can
> use things as-is.  So I would go ahead and file bugs for all the TODOs that
make
> sense to do given the current interface, and assume we're not going to expose
> the underlying_type.  I think your push-back on the empty base class
> optimization thing might be OK, let's see what vmpstr says in reply.

On TODOs
========
My main concern about TODOs without bugs is that these tend to be forgotten.
Tracking bugs is at least a little bit easier. Also, if someone else decides to
take on a task listed as a TODO, it's easier to reassign bugs instead of
changing the user listed in the TODO.

If we decide not to go ahead with some of the TODOs, closing bugs as WontFix
isn't a big issue (and can be a reminder to cleanup the TODOs in the code)

On empty base optimization
==========================
I'm OK with leaving the empty base optimization. My comment was that it's
introducing complexity that isn't very obvious. For example, returning
key_compare in key_comp returns impl_, which is an instance of the derived
class. However, since the compiler knows that it only needs the key_compare, it
only copies the base class.

If in the future (after say C++14, which adds auto return types), someone
decides to add a function like

friend auto out_of_class_key_comp(const flat_set& set) {
  return set.impl_;
} 

with intent of using it as flat_set::key_compare comp =
out_of_class_key_comp(s);, then the compiler wouldn't know that it only needs
the base, so it would end up copying the entire impl_ which includes all of the
data stored in the container.

Sure, this is a contrived example, but this performance bug is made easier by
the fact that we're complicating the implementation to save a few bytes per
instance of flat_set. 

On comment on clear
===================

Feel free to leave the comment. It's good to know the memory implications of
various functions. That being said, I would also prefer a comment on the insert
functionality to inform the user that we will be doubling the memory when we run
out of capacity (or whatever underlying container decides to do), which is also
a pretty major difference from std::set.

dyaroshev

On 2017/01/17 19:29:44, vmpstr wrote: > On TODOs > ======== > My main concern about ...

3 years, 11 months ago (2017-01-18 16:16:04 UTC) #39

On 2017/01/17 19:29:44, vmpstr wrote:
> On TODOs
> ========
> My main concern about TODOs without bugs is that these tend to be forgotten.
> Tracking bugs is at least a little bit easier. Also, if someone else decides
to
> take on a task listed as a TODO, it's easier to reassign bugs instead of
> changing the user listed in the TODO.
> 
> If we decide not to go ahead with some of the TODOs, closing bugs as WontFix
> isn't a big issue (and can be a reminder to cleanup the TODOs in the code)
> 

All created bugs:

Benchmarks: crbug.com/682215
Interface: crbug.com/682254
Range insertion: crbug.com/682249
Small buffer: crbug.com/682240


> On empty base optimization
> ==========================
> I'm OK with leaving the empty base optimization. My comment was that it's
> introducing complexity that isn't very obvious. For example, returning
> key_compare in key_comp returns impl_, which is an instance of the derived
> class. However, since the compiler knows that it only needs the key_compare,
it
> only copies the base class.
> 
> If in the future (after say C++14, which adds auto return types), someone
> decides to add a function like
> 
> friend auto out_of_class_key_comp(const flat_set& set) {
>   return set.impl_;
> } 
> 
> with intent of using it as flat_set::key_compare comp =
> out_of_class_key_comp(s);, then the compiler wouldn't know that it only needs
> the base, so it would end up copying the entire impl_ which includes all of
the
> data stored in the container.
> 
> Sure, this is a contrived example, but this performance bug is made easier by
> the fact that we're complicating the implementation to save a few bytes per
> instance of flat_set. 
> 

This bug doesn't seem very possible, does it? I've added explicit conversions in
key_comp(), value_comp(), so changing type to auto in them won't break anything.

> On comment on clear
> ===================
> 
> Feel free to leave the comment. It's good to know the memory implications of
> various functions. That being said, I would also prefer a comment on the
insert
> functionality to inform the user that we will be doubling the memory when we
run
> out of capacity (or whatever underlying container decides to do), which is
also
> a pretty major difference from std::set.

I did something - I'm all open to ideas.

dyaroshev

On 2017/01/18 16:16:04, dyaroshev wrote: > On 2017/01/17 19:29:44, vmpstr wrote: > > On TODOs ...

3 years, 11 months ago (2017-01-18 16:29:40 UTC) #40

On 2017/01/18 16:16:04, dyaroshev wrote:
> On 2017/01/17 19:29:44, vmpstr wrote:
> > On TODOs
> > ========
> > My main concern about TODOs without bugs is that these tend to be forgotten.
> > Tracking bugs is at least a little bit easier. Also, if someone else decides
> to
> > take on a task listed as a TODO, it's easier to reassign bugs instead of
> > changing the user listed in the TODO.
> > 
> > If we decide not to go ahead with some of the TODOs, closing bugs as WontFix
> > isn't a big issue (and can be a reminder to cleanup the TODOs in the code)
> > 
> 
> All created bugs:
> 
> Benchmarks: crbug.com/682215
> Interface: crbug.com/682254
> Range insertion: crbug.com/682249
> Small buffer: crbug.com/682240
> 
> 
> > On empty base optimization
> > ==========================
> > I'm OK with leaving the empty base optimization. My comment was that it's
> > introducing complexity that isn't very obvious. For example, returning
> > key_compare in key_comp returns impl_, which is an instance of the derived
> > class. However, since the compiler knows that it only needs the key_compare,
> it
> > only copies the base class.
> > 
> > If in the future (after say C++14, which adds auto return types), someone
> > decides to add a function like
> > 
> > friend auto out_of_class_key_comp(const flat_set& set) {
> >   return set.impl_;
> > } 
> > 
> > with intent of using it as flat_set::key_compare comp =
> > out_of_class_key_comp(s);, then the compiler wouldn't know that it only
needs
> > the base, so it would end up copying the entire impl_ which includes all of
> the
> > data stored in the container.
> > 
> > Sure, this is a contrived example, but this performance bug is made easier
by
> > the fact that we're complicating the implementation to save a few bytes per
> > instance of flat_set. 
> > 
> 
> This bug doesn't seem very possible, does it? I've added explicit conversions
in
> key_comp(), value_comp(), so changing type to auto in them won't break
anything.
> 

I mean, this is private to flat_set implementation. In order to do that or
similar bug a person would have to hack into a class in base. If you really
consider this to be a problem, something can probably be done with private
inheritance but it would make code more complicated then it should be, in my
opinion.

vmpstr

On 2017/01/18 16:29:40, dyaroshev wrote: > On 2017/01/18 16:16:04, dyaroshev wrote: > > On 2017/01/17 ...

3 years, 11 months ago (2017-01-19 20:40:58 UTC) #41

On 2017/01/18 16:29:40, dyaroshev wrote:
> On 2017/01/18 16:16:04, dyaroshev wrote:
> > On 2017/01/17 19:29:44, vmpstr wrote:
> > > On TODOs
> > > ========
> > > My main concern about TODOs without bugs is that these tend to be
forgotten.
> > > Tracking bugs is at least a little bit easier. Also, if someone else
decides
> > to
> > > take on a task listed as a TODO, it's easier to reassign bugs instead of
> > > changing the user listed in the TODO.
> > > 
> > > If we decide not to go ahead with some of the TODOs, closing bugs as
WontFix
> > > isn't a big issue (and can be a reminder to cleanup the TODOs in the code)
> > > 
> > 
> > All created bugs:
> > 
> > Benchmarks: crbug.com/682215
> > Interface: crbug.com/682254
> > Range insertion: crbug.com/682249
> > Small buffer: crbug.com/682240
> > 
> > 
> > > On empty base optimization
> > > ==========================
> > > I'm OK with leaving the empty base optimization. My comment was that it's
> > > introducing complexity that isn't very obvious. For example, returning
> > > key_compare in key_comp returns impl_, which is an instance of the derived
> > > class. However, since the compiler knows that it only needs the
key_compare,
> > it
> > > only copies the base class.
> > > 
> > > If in the future (after say C++14, which adds auto return types), someone
> > > decides to add a function like
> > > 
> > > friend auto out_of_class_key_comp(const flat_set& set) {
> > >   return set.impl_;
> > > } 
> > > 
> > > with intent of using it as flat_set::key_compare comp =
> > > out_of_class_key_comp(s);, then the compiler wouldn't know that it only
> needs
> > > the base, so it would end up copying the entire impl_ which includes all
of
> > the
> > > data stored in the container.
> > > 
> > > Sure, this is a contrived example, but this performance bug is made easier
> by
> > > the fact that we're complicating the implementation to save a few bytes
per
> > > instance of flat_set. 
> > > 
> > 
> > This bug doesn't seem very possible, does it? I've added explicit
conversions
> in
> > key_comp(), value_comp(), so changing type to auto in them won't break
> anything.
> > 
> 
> I mean, this is private to flat_set implementation. In order to do that or
> similar bug a person would have to hack into a class in base. If you really
> consider this to be a problem, something can probably be done with private
> inheritance but it would make code more complicated then it should be, in my
> opinion.

I don't think this is currently a problem, I'm just highlighting why this could
be.. Thanks for updating the comments and doing the rest of the changes. This CL
looks good to me.

dyaroshev

message: On 2017/01/19 20:40:58, vmpstr wrote: > ... This CL looks good to me. Ping ...

3 years, 10 months ago (2017-01-24 14:22:11 UTC) #42

danakj

Description was changed from ========== This patch introduces base::flat_set class in chromium. The interface is ...

3 years, 10 months ago (2017-01-26 16:57:15 UTC) #43

Description was changed from

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // tries to insert with two template parameters
instead of
                              // casting iterator to const_iterator.
  We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

to

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters
instead of
                             // casting iterator to const_iterator.
  We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

danakj

Description was changed from ========== This patch introduces base::flat_set class in chromium. The interface is ...

3 years, 10 months ago (2017-01-26 16:57:30 UTC) #44

Description was changed from

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters
instead of
                             // casting iterator to const_iterator.
  We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

to

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters
instead of
                             // casting iterator to const_iterator.
   We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

danakj

Description was changed from ========== This patch introduces base::flat_set class in chromium. The interface is ...

3 years, 10 months ago (2017-01-26 16:57:41 UTC) #45

Description was changed from

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters
instead of
                             // casting iterator to const_iterator.
   We can probably fix this, but it should be done later.

- no templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

to

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters
instead of
                             // casting iterator to const_iterator.
   We can probably fix this, but it should be done later.

- No templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

dcheng

dcheng@chromium.org changed reviewers: + vmpstr@chromium.org

3 years, 10 months ago (2017-01-26 19:36:47 UTC) #46

dcheng

+vmpstr who fell off the review thread somehow Sorry for the delay! I think danakj@ ...

3 years, 10 months ago (2017-01-26 19:36:48 UTC) #47

dcheng

On 2017/01/26 19:36:48, dcheng wrote: > +vmpstr who fell off the review thread somehow > ...

3 years, 10 months ago (2017-01-26 19:37:18 UTC) #48

vmpstr

This lgtm (as a non owner), I think the patch here is very straight forward. ...

3 years, 10 months ago (2017-01-26 19:42:19 UTC) #49

dcheng

Incidentally... can we provide a usage guide for when to use flat_set in this CL? ...

3 years, 10 months ago (2017-01-26 19:54:24 UTC) #50

dyaroshev

On 2017/01/26 19:54:24, dcheng wrote: > Incidentally... can we provide a usage guide for when ...

3 years, 10 months ago (2017-01-26 20:20:01 UTC) #51

danakj

> - Can we use libcpp tests? I believe we can. There is MIT licenced ...

3 years, 10 months ago (2017-01-26 23:18:05 UTC) #52

dyaroshev

@danakj - thank's for your review, I'll work on fixing your comments in a few ...

3 years, 10 months ago (2017-01-27 00:46:37 UTC) #53

@danakj - thank's for your review, I'll work on fixing your comments in a few
days.

The only real point of dissagreement that I have with your comments - is
typedefs. I think it's good to match stl's concepts when we don't loose
anything.

I replied to most of your comments where I would like some clarification, if
this is ok.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:29: // benchmarks and tests for your code: beware of
bugs and potential performance
On 2017/01/26 23:18:07, danakj (slow) wrote:
> I would like to provide some guidance on when this is faster than set. What
> sizes of elements*capacity is needed to make this slower? Under what sort of
use
> patterns? Assuming build once read once/many, when do we recommend it? I think
> the thread has a good start at data for this.
> 
> Thank you for filing a bug about doing this, but I think we need *some*
guidance
> here before it reasonably belongs in base/. We can expand on that guidance by
> collecting data.
> 
> For instance, if you have a set with under 800 bytes of data, this seems like
a
> easy choice over std::set, to make an obvious claim. Can we start with some
> guidance like that? This should be preferred for sets of small numbers of
small
> items, such as less than 800 bytes or 400 items of 8 bytes each. What do you
> think is an obviously reasonable claim from the data in the thread?
> 

I have an old pc laptop, on weekend I can try to insert decreasing data of
different sizes on it and have some rough results. This would give an ok
upperbound I think. Does it work for you?

> I wanted to say that if you build your set once and and then read from it many
> times this would be good, but the bulk insert implementation seems unfriendly
> actually (and, spoilers, I actually asked it to be removed for now later in
the
> CL).

I think this is a great idea. This way we will insure to not introduce any
unwanted performance failures -> all performance will be obvious to the user.
And constructor implementation with stable_sort + unique instead of insert would
be ok.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:76: using key_type = Key;
On 2017/01/26 23:18:07, danakj (slow) wrote:
> How many of these typedefs do we need? Things like ::iterator and ::key_type
> will be potentially used by chromium code, tho that's almost questionable with
> auto tbh. But what would break if we removed key_compare for instance? or
> size_type, we can just use size_t throughout.
> 
> I agree with vmpstr@ generally that we should keep this small as possible. I
> understand that we want to make it useful in places std::set would be. And to
> that end I would like us to try keep things that we need to use std::set with
> STL such as in <algorithms>, but how many of these are needed for that? I
expect
> few maybe zero thanks to auto. So then we should keep what would reasonably
> expect to need when using the class. And otherwise, if they are helpful to the
> implementation then make them private.

This has to do with C++ container concept
http://en.cppreference.com/w/cpp/concept/Container
I think if we write a container it should be a C++ container as much as
possible, so that as much of generic code that works with containers would work
with this.

key_compare/value_compare - they are from std::set, they are here because this
models an associative container, which requires certain typedefs. I think that
differentiate from std::set where it's not necessary only introduces unnecessary
confusion.

I'm not sure that auto would cut it, because of vector<bool> for example.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:115: flat_set(const flat_set& x);
On 2017/01/26 23:18:06, danakj (slow) wrote:
> use a name better than "x" please throughout

This is stl's original naming convention, used by Alexandr Stepanov, seemed
apropriate for stl like container. What naming convention do you prefer?

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:121: flat_set(std::initializer_list<value_type> il,
On 2017/01/26 23:18:06, danakj (slow) wrote:
> https://google.github.io/styleguide/cppguide.html#General_Naming_Rules starts
> with "Names should be descriptive; avoid abbreviation." Rather than |il| how
> about |list| even? Same throughout.

C++ standard calls this il:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf (look at page
826 for example). What naming convention do you prefer?

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:141: // insert more efficient if we insert into new
memory. We do not take
On 2017/01/26 23:18:06, danakj (slow) wrote:
> I'm not sure what this comment means TBH. When you say be cautious about using
> reserve, how does a user decide to use it or to not? What are the criteria?

If we remove insert(first, last) this comment won't be necessary.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:277: friend bool operator>(const flat_set& x, const
flat_set& y) { return y < x; }
On 2017/01/26 23:18:06, danakj (slow) wrote:
> nit: it would be nice if the operator was the same as the operator its
> implementing, ie x > y.

Ok. This is original stl's style again.
Here is an example https://www.sgi.com/tech/stl/stl_deque.h

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:511: // Currently we use hint the same way as eastl
or boost:
On 2017/01/26 23:18:07, danakj (slow) wrote:
> I'm not sure what "we use hint" here is referring to. What hint? The line
number
> there may become stale, or may already be, it's hard to tell, can you refer to
> what you are linking to conceptually along with the line or drop the line?

hint refers to insert(position, value_type) - this position is a hint. Maybe it
should be renamed to hint.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:579: return
insert(value_type(std::forward<Args>(args)...));
On 2017/01/26 23:18:06, danakj (slow) wrote:
> why does this not use the underlying type's emplace?

Because I have to do binary search on it.
I can't find the position to insert an element without constructing an element.

I looked up to eastl's implementation of this functions:
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:635: auto eq_range = equal_range(x);
On 2017/01/26 23:18:06, danakj (slow) wrote:
> Why is this written like this is a multiset? Is this more efficient than
> lower_bound and compare?

It's a call to our member function equal_range, not std::equal_range.
It does lower_bound + compare.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:672: return const_cast_it(as_const().lower_bound(x));
On 2017/01/26 23:18:06, danakj (slow) wrote:
> why not just call std::lower_bound here? const_cast_it isn't free

Can do that, but it's code duplication.
const_cast_it is free at -O2
clang:
https://godbolt.org/g/HRDAke
gcc:
https://godbolt.org/g/PJuCFm

danakj

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_set.h#newcode76 base/containers/flat_set.h:76: using key_type = Key; On 2017/01/27 00:46:36, dyaroshev wrote: ...

3 years, 10 months ago (2017-01-27 22:10:11 UTC) #54

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:76: using key_type = Key;
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:07, danakj (slow) wrote:
> > How many of these typedefs do we need? Things like ::iterator and ::key_type
> > will be potentially used by chromium code, tho that's almost questionable
with
> > auto tbh. But what would break if we removed key_compare for instance? or
> > size_type, we can just use size_t throughout.
> > 
> > I agree with vmpstr@ generally that we should keep this small as possible. I
> > understand that we want to make it useful in places std::set would be. And
to
> > that end I would like us to try keep things that we need to use std::set
with
> > STL such as in <algorithms>, but how many of these are needed for that? I
> expect
> > few maybe zero thanks to auto. So then we should keep what would reasonably
> > expect to need when using the class. And otherwise, if they are helpful to
the
> > implementation then make them private.
> 
> This has to do with C++ container concept
> http://en.cppreference.com/w/cpp/concept/Container
> I think if we write a container it should be a C++ container as much as
> possible, so that as much of generic code that works with containers would
work
> with this.
> 
> key_compare/value_compare - they are from std::set, they are here because this
> models an associative container, which requires certain typedefs. I think that
> differentiate from std::set where it's not necessary only introduces
unnecessary
> confusion.
> 
> I'm not sure that auto would cut it, because of vector<bool> for example.n the
code.

That's a good point you bring up. We should forbid flat_set<bool> with a
static_assert so we don't end up with vector<bool>s in the code.

I understand that these are for standard defined types but this is really for
specific use in chromium. If they are needed for use with standard algorithms
then great, but majority of these are not and a chromium developer will not need
to use them, right?

I don't want our approach to be that we're building something for boost or for
the STL. I want it to be that we're building it for chromium, if that makes
sense. And we try to minimize our lines of code and don't add dead things. This
whole class is already somewhat exceptional, but I want to try to limit its
scope and let it grow later. Shrinking code is always harder.

If you look in chromium code today there are no uses of key_compare() or
value_compare() for instance. I don't expect that to change.

https://cs.chromium.org/search/?q=key_compare+-f:src/v8+-f:src/third_party+-f...

https://cs.chromium.org/search/?q=value_compare+-f:src/v8+-f:src/third_party+...

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:115: flat_set(const flat_set& x);
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:06, danakj (slow) wrote:
> > use a name better than "x" please throughout
> 
> This is stl's original naming convention, used by Alexandr Stepanov, seemed
> apropriate for stl like container. What naming convention do you prefer?

Give it a name that is meaningful for what it is in the context. Here "other" is
a common choice. For different methods a name that has meaning will be
different.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:121: flat_set(std::initializer_list<value_type> il,
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:06, danakj (slow) wrote:
> > https://google.github.io/styleguide/cppguide.html#General_Naming_Rules
starts
> > with "Names should be descriptive; avoid abbreviation." Rather than |il| how
> > about |list| even? Same throughout.
> 
> C++ standard calls this il:
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf (look at
page
> 826 for example). What naming convention do you prefer?

"list" would better follow chromium/google naming practices. while the methods
in here are named after the STL we are not writing the STL so we should not try
to follow their style choices.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:277: friend bool operator>(const flat_set& x, const
flat_set& y) { return y < x; }
On 2017/01/27 00:46:37, dyaroshev wrote:
> On 2017/01/26 23:18:06, danakj (slow) wrote:
> > nit: it would be nice if the operator was the same as the operator its
> > implementing, ie x > y.
> 
> Ok. This is original stl's style again.
> Here is an example https://www.sgi.com/tech/stl/stl_deque.h

That's ok I still prefer the other

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:292: iterator const_cast_it(const_iterator c_it) {
On 2017/01/26 23:18:08, danakj (slow) wrote:
> Would it work to define this this way for old GCC but otherwise define it as 
> 
> const_iterator const_cast_it(const_iterator c_it) { return c_it; }
> 
> ?

I see that we're using this in places that aren't working around the compiler so
ignore this comment.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:511: // Currently we use hint the same way as eastl
or boost:
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:07, danakj (slow) wrote:
> > I'm not sure what "we use hint" here is referring to. What hint? The line
> number
> > there may become stale, or may already be, it's hard to tell, can you refer
to
> > what you are linking to conceptually along with the line or drop the line?
> 
> hint refers to insert(position, value_type) - this position is a hint. Maybe
it
> should be renamed to hint.

I would say "we use the position hint" here, and name it position_hint in the
code.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:579: return
insert(value_type(std::forward<Args>(args)...));
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:06, danakj (slow) wrote:
> > why does this not use the underlying type's emplace?
> 
> Because I have to do binary search on it.
> I can't find the position to insert an element without constructing an
element.
> 
> I looked up to eastl's implementation of this functions:
>
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....

Ah I see that makes sense. I guess this API will be more useful for a map where
the key is diff from the value being emplaced.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:635: auto eq_range = equal_range(x);
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:06, danakj (slow) wrote:
> > Why is this written like this is a multiset? Is this more efficient than
> > lower_bound and compare?
> 
> It's a call to our member function equal_range, not std::equal_range.
> It does lower_bound + compare.

Ohh, right thanks. I probably woulda done this thru find() but seems okay.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:672: return const_cast_it(as_const().lower_bound(x));
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:06, danakj (slow) wrote:
> > why not just call std::lower_bound here? const_cast_it isn't free
> 
> Can do that, but it's code duplication.
> const_cast_it is free at -O2
> clang:
> https://godbolt.org/g/HRDAke
> gcc:
> https://godbolt.org/g/PJuCFm

That tool is very cool. Ok this seems fine then, thanks.

dyaroshev

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_set.h#newcode1 base/containers/flat_set.h:1: // Copyright 2016 The Chromium Authors. All rights reserved. ...

3 years, 10 months ago (2017-01-30 00:07:13 UTC) #55

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:1: // Copyright 2016 The Chromium Authors. All rights
reserved.
On 2017/01/26 23:18:07, danakj (slow) wrote:
> 2017

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:27: // Waring:
On 2017/01/26 23:18:07, danakj (slow) wrote:
> Do you mean Warning?

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:29: // benchmarks and tests for your code: beware of
bugs and potential performance
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:07, danakj (slow) wrote:
> > I would like to provide some guidance on when this is faster than set. What
> > sizes of elements*capacity is needed to make this slower? Under what sort of
> use
> > patterns? Assuming build once read once/many, when do we recommend it? I
think
> > the thread has a good start at data for this.
> > 
> > Thank you for filing a bug about doing this, but I think we need *some*
> guidance
> > here before it reasonably belongs in base/. We can expand on that guidance
by
> > collecting data.
> > 
> > For instance, if you have a set with under 800 bytes of data, this seems
like
> a
> > easy choice over std::set, to make an obvious claim. Can we start with some
> > guidance like that? This should be preferred for sets of small numbers of
> small
> > items, such as less than 800 bytes or 400 items of 8 bytes each. What do you
> > think is an obviously reasonable claim from the data in the thread?
> > 
> 
> I have an old pc laptop, on weekend I can try to insert decreasing data of
> different sizes on it and have some rough results. This would give an ok
> upperbound I think. Does it work for you?
> 

Writing a good microbenchmark turned out to be harder that I expected, I don't
have much confidence in the results that I've got so far.
I think we good for case when set doesn't mutate much -> stable_sort + unique
should be better that set, so I wrote that as a guidance with the intent to
update it in crbug.com/682215.
Is this ok?

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:41: //   * allocator support was not tested and we
might to decide to use underlying
On 2017/01/26 23:18:06, danakj (slow) wrote:
> "we might decide". Although I think we should drop the Allocator from the
> template. It's not tested as you say and it's not clear how we want to do it
> yet.
> 
> This also means dropping all the Allocator method overloads, which
siginifically
> reduces the API surface which is kinda nice at this stage.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:60: // Meets the requirements of  Container,
AllocatorAwareContainer,
On 2017/01/26 23:18:07, danakj (slow) wrote:
> extra space in there.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:67: // Private typedefs have to be declared higher
than used.
On 2017/01/26 23:18:08, danakj (slow) wrote:
> remove this comment. everything needs to be declared before used

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:74: // Some of these typedefs in the proposal are
defined based on allocator but
On 2017/01/26 23:18:08, danakj (slow) wrote:
> which proposal is this speaking of? it's the first time it's mentioned in this
> file. i think this comment can go away tbh

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:76: using key_type = Key;
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/27 00:46:36, dyaroshev wrote:
> > On 2017/01/26 23:18:07, danakj (slow) wrote:
> > > How many of these typedefs do we need? Things like ::iterator and
::key_type
> > > will be potentially used by chromium code, tho that's almost questionable
> with
> > > auto tbh. But what would break if we removed key_compare for instance? or
> > > size_type, we can just use size_t throughout.
> > > 
> > > I agree with vmpstr@ generally that we should keep this small as possible.
I
> > > understand that we want to make it useful in places std::set would be. And
> to
> > > that end I would like us to try keep things that we need to use std::set
> with
> > > STL such as in <algorithms>, but how many of these are needed for that? I
> > expect
> > > few maybe zero thanks to auto. So then we should keep what would
reasonably
> > > expect to need when using the class. And otherwise, if they are helpful to
> the
> > > implementation then make them private.
> > 
> > This has to do with C++ container concept
> > http://en.cppreference.com/w/cpp/concept/Container
> > I think if we write a container it should be a C++ container as much as
> > possible, so that as much of generic code that works with containers would
> work
> > with this.
> > 
> > key_compare/value_compare - they are from std::set, they are here because
this
> > models an associative container, which requires certain typedefs. I think
that
> > differentiate from std::set where it's not necessary only introduces
> unnecessary
> > confusion.
> > 
> > I'm not sure that auto would cut it, because of vector<bool> for example.n
the
> code.
> 
> That's a good point you bring up. We should forbid flat_set<bool> with a
> static_assert so we don't end up with vector<bool>s in the code.
> 
> I understand that these are for standard defined types but this is really for
> specific use in chromium. If they are needed for use with standard algorithms
> then great, but majority of these are not and a chromium developer will not
need
> to use them, right?
> 
> I don't want our approach to be that we're building something for boost or for
> the STL. I want it to be that we're building it for chromium, if that makes
> sense. And we try to minimize our lines of code and don't add dead things.
This
> whole class is already somewhat exceptional, but I want to try to limit its
> scope and let it grow later. Shrinking code is always harder.
> 
> If you look in chromium code today there are no uses of key_compare() or
> value_compare() for instance. I don't expect that to change.
> 
>
https://cs.chromium.org/search/?q=key_compare+-f:src/v8+-f:src/third_party+-f...
> 
>
https://cs.chromium.org/search/?q=value_compare+-f:src/v8+-f:src/third_party+...

Ok, last attempt after which I give up.

a) I think these stl utils should utilise key/value compare, if it's available,
otherwise hard to find bugs might occur.
https://cs.chromium.org/chromium/src/base/stl_util.h?q=SetIntersect&sq=packag...

b) I was for some time trying to do some decent merge function for many sets (so
far - sort + unique beats me). Such function should utilise
key_compare/value_compare.

c) flat_set are useful in cases where using std::set is wasteful - you can
replace your vector with custom sorting with flat_set / flat_multiset fairly
easy (especially after crbug.com/682254 where I suggest we either add some
conversion from underlying_type and/or deffered_insert of some sort). std::sort
and std::sort + std::unique are quite common. If you do this - key_comp(),
value_comp() might come in handy.

Considering how much time and effort it is to modify base and how small
key_comp() and value_comp() are, I really think they should stay as a part of a
public interface.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:121: flat_set(std::initializer_list<value_type> il,
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/27 00:46:36, dyaroshev wrote:
> > On 2017/01/26 23:18:06, danakj (slow) wrote:
> > > https://google.github.io/styleguide/cppguide.html#General_Naming_Rules
> starts
> > > with "Names should be descriptive; avoid abbreviation." Rather than |il|
how
> > > about |list| even? Same throughout.
> > 
> > C++ standard calls this il:
> > http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf (look at
> page
> > 826 for example). What naming convention do you prefer?
> 
> "list" would better follow chromium/google naming practices. while the methods
> in here are named after the STL we are not writing the STL so we should not
try
> to follow their style choices.

I changed to ilist, like on cppreference. I think list is associated with the
data-structure more than with initilizer_list.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:141: // insert more efficient if we insert into new
memory. We do not take
On 2017/01/27 00:46:36, dyaroshev wrote:
> On 2017/01/26 23:18:06, danakj (slow) wrote:
> > I'm not sure what this comment means TBH. When you say be cautious about
using
> > reserve, how does a user decide to use it or to not? What are the criteria?
> 
> If we remove insert(first, last) this comment won't be necessary.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:145: // Beware that shrink_to_fit() simply forward to
the underlying_type and
On 2017/01/26 23:18:08, danakj (slow) wrote:
> forwards the request to

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:146: // according to c++ standard shrink_to_fit() is
non-binding.
On 2017/01/26 23:18:07, danakj (slow) wrote:
> "is non-binding" could be written more clearly as "is a non-binding request".
> 
> and maybe you want to say that std::vector's is this, just citing the c++
> standard is vague, as this is not an implementation of the c++ standard.
> 
> instead of forwarding to other documentation can you just instead explain the
> behaviour of shrink_to_fit as it is written the same way that vector would?

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:192: // an implementation defined manner.
On 2017/01/26 23:18:07, danakj (slow) wrote:
> implementation-defined

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:219: 
On 2017/01/26 23:18:08, danakj (slow) wrote:
> nit: drop whitespace between overloads here

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:222: size_type erase(const key_type& x);
On 2017/01/26 23:18:07, danakj (slow) wrote:
> This is O(size) + O(log(size)) right? Mention that?

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:232: // Binary search operations.
On 2017/01/26 23:18:06, danakj (slow) wrote:
> I would say Search operations. And mention that they have O(log(size))
> complexity?

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:277: friend bool operator>(const flat_set& x, const
flat_set& y) { return y < x; }
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/27 00:46:37, dyaroshev wrote:
> > On 2017/01/26 23:18:06, danakj (slow) wrote:
> > > nit: it would be nice if the operator was the same as the operator its
> > > implementing, ie x > y.
> > 
> > Ok. This is original stl's style again.
> > Here is an example https://www.sgi.com/tech/stl/stl_deque.h
> 
> That's ok I still prefer the other

If I were to implement it in terms of >, I would have to rewrite forwarding to
the underling type. This is a place for a potential bug and annoying code
duplication. Because you don't seem to mind very much I left it as is.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:284: return !(y < x);
On 2017/01/26 23:18:08, danakj (slow) wrote:
> nit: can you write this !(x>y) so its relationship to the operator its
> implementing is more obvious

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:292: iterator const_cast_it(const_iterator c_it) {
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/26 23:18:08, danakj (slow) wrote:
> > Would it work to define this this way for old GCC but otherwise define it as

> > 
> > const_iterator const_cast_it(const_iterator c_it) { return c_it; }
> > 
> > ?
> 
> I see that we're using this in places that aren't working around the compiler
so
> ignore this comment.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:297: // To support comparators that may not be
possible to default-construct, we
On 2017/01/26 23:18:07, danakj (slow) wrote:
> Can you mention this is the storage for the underlying data of the container.
> Then mention the fact that its inheriting Compare and why. It reads like this
> Impl is only for Compare.

Done?

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:302: // forwarding constructor.
On 2017/01/26 23:18:06, danakj (slow) wrote:
> "Forwarding". Tho, comments should say why, not what. I think this one can go
> away, it only says what the code says.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:511: // Currently we use hint the same way as eastl
or boost:
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/27 00:46:36, dyaroshev wrote:
> > On 2017/01/26 23:18:07, danakj (slow) wrote:
> > > I'm not sure what "we use hint" here is referring to. What hint? The line
> > number
> > > there may become stale, or may already be, it's hard to tell, can you
refer
> to
> > > what you are linking to conceptually along with the line or drop the line?
> > 
> > hint refers to insert(position, value_type) - this position is a hint. Maybe
> it
> > should be renamed to hint.
> 
> I would say "we use the position hint" here, and name it position_hint in the
> code.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:566: std::copy(first, last, std::inserter(*this,
end()));
On 2017/01/26 23:18:06, danakj (slow) wrote:
> This function is O(size * (last-first)).
> 
> We should make it better or remove the function for now. I think we should
> remove it until we need something. This seems in the area of where flat_set
> should likely differentiate from set.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:572: insert(il.begin(), il.end());
On 2017/01/26 23:18:07, danakj (slow) wrote:
> Same here.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:579: return
insert(value_type(std::forward<Args>(args)...));
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/27 00:46:36, dyaroshev wrote:
> > On 2017/01/26 23:18:06, danakj (slow) wrote:
> > > why does this not use the underlying type's emplace?
> > 
> > Because I have to do binary search on it.
> > I can't find the position to insert an element without constructing an
> element.
> > 
> > I looked up to eastl's implementation of this functions:
> >
>
https://github.com/electronicarts/EASTL/blob/master/include/EASTL/vector_set....
> 
> Ah I see that makes sense. I guess this API will be more useful for a map
where
> the key is diff from the value being emplaced.

It would still be implemented in the same way - you can't get to the key out of
Args...
I don't believe there is a good way to avoid constructing a temporary object for
flat_set. Still - it's a useful api to have (for consistency).

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:630: // Binary search operations.
On 2017/01/26 23:18:07, danakj (slow) wrote:
> Search operations. ?

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:635: auto eq_range = equal_range(x);
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/27 00:46:36, dyaroshev wrote:
> > On 2017/01/26 23:18:06, danakj (slow) wrote:
> > > Why is this written like this is a multiset? Is this more efficient than
> > > lower_bound and compare?
> > 
> > It's a call to our member function equal_range, not std::equal_range.
> > It does lower_bound + compare.
> 
> Ohh, right thanks. I probably woulda done this thru find() but seems okay.

Done.

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:672: return const_cast_it(as_const().lower_bound(x));
On 2017/01/27 22:10:11, danakj (slow) wrote:
> On 2017/01/27 00:46:36, dyaroshev wrote:
> > On 2017/01/26 23:18:06, danakj (slow) wrote:
> > > why not just call std::lower_bound here? const_cast_it isn't free
> > 
> > Can do that, but it's code duplication.
> > const_cast_it is free at -O2
> > clang:
> > https://godbolt.org/g/HRDAke
> > gcc:
> > https://godbolt.org/g/PJuCFm
> 
> That tool is very cool. Ok this seems fine then, thanks.

It is! If you are interested - an awesome talk from last cppcon, where they show
a bunch of compilers optimisations with it: https://youtu.be/zBkNBP00wJE

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:684: return const_cast_it(as_const().upper_bound(x));
On 2017/01/26 23:18:06, danakj (slow) wrote:
> why not just call std::lower_bound here? const_cast_it isn't free

Done.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:276: std::stable_sort(begin(), end(), value_comp());
Stability bugs me, I would like your opinion on this.
On one hand - changing from stable sort of a set to unstable has some potential
bugs to it.
On the other hand - stability is rearly a requirement, it's about 10-15% slower
(I've seen some data in a course) and I would like not to have any overhead
compared to a plain vector.

What do you think? Are we ok with switching stability off?

dyaroshev

Fix typo with next commit https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h#newcode31 base/containers/flat_set.h:31: // for different types ...

3 years, 10 months ago (2017-01-30 14:10:58 UTC) #56

danakj

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_set.h#newcode29 base/containers/flat_set.h:29: // benchmarks and tests for your code: beware of ...

3 years, 10 months ago (2017-01-30 20:24:31 UTC) #57

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:29: // benchmarks and tests for your code: beware of
bugs and potential performance
On 2017/01/30 00:07:12, dyaroshev wrote:
> On 2017/01/27 00:46:36, dyaroshev wrote:
> > On 2017/01/26 23:18:07, danakj (slow) wrote:
> > > I would like to provide some guidance on when this is faster than set.
What
> > > sizes of elements*capacity is needed to make this slower? Under what sort
of
> > use
> > > patterns? Assuming build once read once/many, when do we recommend it? I
> think
> > > the thread has a good start at data for this.
> > > 
> > > Thank you for filing a bug about doing this, but I think we need *some*
> > guidance
> > > here before it reasonably belongs in base/. We can expand on that guidance
> by
> > > collecting data.
> > > 
> > > For instance, if you have a set with under 800 bytes of data, this seems
> like
> > a
> > > easy choice over std::set, to make an obvious claim. Can we start with
some
> > > guidance like that? This should be preferred for sets of small numbers of
> > small
> > > items, such as less than 800 bytes or 400 items of 8 bytes each. What do
you
> > > think is an obviously reasonable claim from the data in the thread?
> > > 
> > 
> > I have an old pc laptop, on weekend I can try to insert decreasing data of
> > different sizes on it and have some rough results. This would give an ok
> > upperbound I think. Does it work for you?
> > 
> 
> Writing a good microbenchmark turned out to be harder that I expected, I don't
> have much confidence in the results that I've got so far.
> I think we good for case when set doesn't mutate much -> stable_sort + unique
> should be better that set, so I wrote that as a guidance with the intent to
> update it in crbug.com/682215.
> Is this ok?

I think that you should give some size limit in the guidance, or describe how it
should be built (ie with the constructor), because calling insert a lot becomes
worse than set eventually probably?

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:76: using key_type = Key;
On 2017/01/30 00:07:12, dyaroshev wrote:
> On 2017/01/27 22:10:11, danakj (slow) wrote:
> > On 2017/01/27 00:46:36, dyaroshev wrote:
> > > On 2017/01/26 23:18:07, danakj (slow) wrote:
> > > > How many of these typedefs do we need? Things like ::iterator and
> ::key_type
> > > > will be potentially used by chromium code, tho that's almost
questionable
> > with
> > > > auto tbh. But what would break if we removed key_compare for instance?
or
> > > > size_type, we can just use size_t throughout.
> > > > 
> > > > I agree with vmpstr@ generally that we should keep this small as
possible.
> I
> > > > understand that we want to make it useful in places std::set would be.
And
> > to
> > > > that end I would like us to try keep things that we need to use std::set
> > with
> > > > STL such as in <algorithms>, but how many of these are needed for that?
I
> > > expect
> > > > few maybe zero thanks to auto. So then we should keep what would
> reasonably
> > > > expect to need when using the class. And otherwise, if they are helpful
to
> > the
> > > > implementation then make them private.
> > > 
> > > This has to do with C++ container concept
> > > http://en.cppreference.com/w/cpp/concept/Container
> > > I think if we write a container it should be a C++ container as much as
> > > possible, so that as much of generic code that works with containers would
> > work
> > > with this.
> > > 
> > > key_compare/value_compare - they are from std::set, they are here because
> this
> > > models an associative container, which requires certain typedefs. I think
> that
> > > differentiate from std::set where it's not necessary only introduces
> > unnecessary
> > > confusion.
> > > 
> > > I'm not sure that auto would cut it, because of vector<bool> for example.n
> the
> > code.
> > 
> > That's a good point you bring up. We should forbid flat_set<bool> with a
> > static_assert so we don't end up with vector<bool>s in the code.
> > 
> > I understand that these are for standard defined types but this is really
for
> > specific use in chromium. If they are needed for use with standard
algorithms
> > then great, but majority of these are not and a chromium developer will not
> need
> > to use them, right?
> > 
> > I don't want our approach to be that we're building something for boost or
for
> > the STL. I want it to be that we're building it for chromium, if that makes
> > sense. And we try to minimize our lines of code and don't add dead things.
> This
> > whole class is already somewhat exceptional, but I want to try to limit its
> > scope and let it grow later. Shrinking code is always harder.
> > 
> > If you look in chromium code today there are no uses of key_compare() or
> > value_compare() for instance. I don't expect that to change.
> > 
> >
>
https://cs.chromium.org/search/?q=key_compare+-f:src/v8+-f:src/third_party+-f...
> > 
> >
>
https://cs.chromium.org/search/?q=value_compare+-f:src/v8+-f:src/third_party+...
> 
> Ok, last attempt after which I give up.
> 
> a) I think these stl utils should utilise key/value compare, if it's
available,
> otherwise hard to find bugs might occur.
>
https://cs.chromium.org/chromium/src/base/stl_util.h?q=SetIntersect&sq=packag...
> 
> b) I was for some time trying to do some decent merge function for many sets
(so
> far - sort + unique beats me). Such function should utilise
> key_compare/value_compare.
> 
> c) flat_set are useful in cases where using std::set is wasteful - you can
> replace your vector with custom sorting with flat_set / flat_multiset fairly
> easy (especially after crbug.com/682254 where I suggest we either add some
> conversion from underlying_type and/or deffered_insert of some sort).
std::sort
> and std::sort + std::unique are quite common. If you do this - key_comp(),
> value_comp() might come in handy.
> 
> Considering how much time and effort it is to modify base and how small
> key_comp() and value_comp() are, I really think they should stay as a part of
a
> public interface.

You have some good arguments for key/value compare. How about the rest? Do we
need pointer/const_pointer/reference/const_reference/size_type/difference_type?

https://codereview.chromium.org/2552343003/diff/180001/base/containers/flat_s...
base/containers/flat_set.h:277: friend bool operator>(const flat_set& x, const
flat_set& y) { return y < x; }
On 2017/01/30 00:07:12, dyaroshev wrote:
> On 2017/01/27 22:10:11, danakj (slow) wrote:
> > On 2017/01/27 00:46:37, dyaroshev wrote:
> > > On 2017/01/26 23:18:06, danakj (slow) wrote:
> > > > nit: it would be nice if the operator was the same as the operator its
> > > > implementing, ie x > y.
> > > 
> > > Ok. This is original stl's style again.
> > > Here is an example https://www.sgi.com/tech/stl/stl_deque.h
> > 
> > That's ok I still prefer the other
> 
> If I were to implement it in terms of >, I would have to rewrite forwarding to
> the underling type. This is a place for a potential bug and annoying code
> duplication. Because you don't seem to mind very much I left it as is.

Oh, right ya I'm thinking this is implemented on the body. Nevermind.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:56: //                           ReversibleContainer.
just wrap lines normally

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:280: // rhs) <=>
dont line wrap here?

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:288: // have to store an instance of Compare. Putting
all internal state of
"Putting all internal state" => "Using this to store all internal state"

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:292: struct Impl : Compare {
make private explicit

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:343: auto flat_set<Key, Compare>::operator=(flat_set
&&) -> flat_set& = default;
no space before &&

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:460: // Currently we use hint the same way as eastl
or boost:
we use the position hint

danakj

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h#newcode276 base/containers/flat_set.h:276: std::stable_sort(begin(), end(), value_comp()); On 2017/01/30 00:07:13, dyaroshev wrote: > ...

3 years, 10 months ago (2017-01-30 20:28:38 UTC) #58

dyaroshev

On 2017/01/30 20:28:38, danakj (slow) wrote: > https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h > File base/containers/flat_set.h (right): > > https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h#newcode276 ...

3 years, 10 months ago (2017-01-30 22:28:06 UTC) #59

danakj

On Mon, Jan 30, 2017 at 5:28 PM, <dyaroshev@yandex-team.ru> wrote: > On 2017/01/30 20:28:38, danakj ...

3 years, 10 months ago (2017-01-30 22:39:18 UTC) #60

On Mon, Jan 30, 2017 at 5:28 PM, <dyaroshev@yandex-team.ru> wrote:

> On 2017/01/30 20:28:38, danakj (slow) wrote:
> >
> https://codereview.chromium.org/2552343003/diff/200001/
> base/containers/flat_set.h
> > File base/containers/flat_set.h (right):
> >
> >
> https://codereview.chromium.org/2552343003/diff/200001/
> base/containers/flat_set.h#newcode276
> > base/containers/flat_set.h:276: std::stable_sort(begin(), end(),
> value_comp());
> > On 2017/01/30 00:07:13, dyaroshev wrote:
> > > Stability bugs me, I would like your opinion on this.
> > > On one hand - changing from stable sort of a set to unstable has some
> > potential
> > > bugs to it.
> > > On the other hand - stability is rearly a requirement, it's about
> 10-15%
> > slower
> > > (I've seen some data in a course) and I would like not to have any
> overhead
> > > compared to a plain vector.
> > >
> > > What do you think? Are we ok with switching stability off?
> >
> > I don't think we need to preserve ordering. I would say don't use stable
> sort.
> >
> > In this case it's a set not a multi-set, so.. stable shouldn't be
> relative
> > except that it changes which one is kept if there are multiple? I think
> it's
> > fine for it to be arbitrary.
> >
> > Do you have an example bug you're particularly worried about?
>
> Well, for constructor no. But I think that it's crusial for insert (either
> with
> one element or with a range) to be stable with respect to the elements that
> already are in the containter. I think so because it seems like map should
> be
> implemented as set<pair> (at the very least behave like it).
> Than inserting new element with the same key should not override an already
> existing one - so, we have to be careful.
>

Yes that's a fair point, but seems specific to insert so we can ignore it
for now.  :)

-- 
You received this message because you are subscribed to the Google Groups
"Chromium-reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to chromium-reviews+unsubscribe@chromium.org.

dyaroshev

> On danakj wrote: > I think that you should give some size limit in ...

3 years, 10 months ago (2017-01-31 23:08:26 UTC) #61

> On  danakj wrote:
> I think that you should give some size limit in the guidance, or describe how
it
> should be built (ie with the constructor), because calling insert a lot
becomes
worse than set eventually probably?

I've tried my best without size. I'm really not comfortable about making size
claims - benchmarking sets is not an easy task, especially because I expect wins
on small sizes - and with smaller sizes we get bigger noise. And this is so much
machine dependent.

I found some benchmarks online:
http://pubby.github.io/proposal.html
http://stackoverflow.com/questions/21166675/boostflat-map-and-its-performance...
http://blog.fellstat.com/?p=376

I don't know if they are good. They do not cover many interesting cases.
I get it if you are against merging without some stand alone measuring but I
don't have good results.

>You have some good arguments for key/value compare. How about the rest? Do we
need >pointer/const_pointer/reference/const_reference/size_type/difference_type?

size_type, difference_type are implementation defined and not portable, I think
that getting an unexpected conversion here would be bad.
pointer/reference has to  do with allocator support, but for standard allocator
are guarantied to be T*/T&.

There are a few places where libraries might rely on such types provided by the
container. Smth like std::inserter, std::uses_allocater is written for a
container concept and can be used with flat_set. Standard has some other
adapters like priority_queue, stack, back_inserter etc, and people write their
own - not satisfying such concept would break our ability  to use flat_set with
them for no good reason.

I mean, there is a certain way to do things in c++ and when you step away from
it, you better have a good reason to.
For example:
Swap(*rhs) - and standard library does not pickup your swap inside algorithms -
so our protobufs are not swapped efficiently.
Doing something other than copy in copy constructor - and compiler might
eliminate your copies and break you.

I mean, eliminating insert(first, last) was a good thing - because it's
dangerously inefficient and not matching usual interface can help you.

But pointer/reference? Is it really that much worse? Two extra typedefs to match
the concept?

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
File base/containers/flat_set.h (right):

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:56: //                           ReversibleContainer.
On 2017/01/30 20:24:31, danakj (slow) wrote:
> just wrap lines normally

Done.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:276: std::stable_sort(begin(), end(), value_comp());
On 2017/01/30 20:28:38, danakj (slow) wrote:
> On 2017/01/30 00:07:13, dyaroshev wrote:
> > Stability bugs me, I would like your opinion on this.
> > On one hand - changing from stable sort of a set to unstable has some
> potential
> > bugs to it.
> > On the other hand - stability is rearly a requirement, it's about 10-15%
> slower
> > (I've seen some data in a course) and I would like not to have any overhead
> > compared to a plain vector.
> > 
> > What do you think? Are we ok with switching stability off?
> 
> I don't think we need to preserve ordering. I would say don't use stable sort.
> 
> In this case it's a set not a multi-set, so.. stable shouldn't be relative
> except that it changes which one is kept if there are multiple? I think it's
> fine for it to be arbitrary.
> 
> Do you have an example bug you're particularly worried about?

Done.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:280: // rhs) <=>
On 2017/01/30 20:24:31, danakj (slow) wrote:
> dont line wrap here?

Done.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:288: // have to store an instance of Compare. Putting
all internal state of
On 2017/01/30 20:24:31, danakj (slow) wrote:
> "Putting all internal state" => "Using this to store all internal state"

Done.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:292: struct Impl : Compare {
On 2017/01/30 20:24:31, danakj (slow) wrote:
> make private explicit

Done.  Had to do a few modifications - it wasn't private inheritance.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:343: auto flat_set<Key, Compare>::operator=(flat_set
&&) -> flat_set& = default;
On 2017/01/30 20:24:31, danakj (slow) wrote:
> no space before &&

Done.

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_s...
base/containers/flat_set.h:460: // Currently we use hint the same way as eastl
or boost:
On 2017/01/30 20:24:31, danakj (slow) wrote:
> we use the position hint

Done.

danakj

OK I feel u on the typedefs I guess. I would be expecting the stdlib ...

3 years, 10 months ago (2017-02-03 20:30:49 UTC) #62

dyaroshev

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h#newcode343 base/containers/flat_set.h:343: auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default; On ...

3 years, 10 months ago (2017-02-04 00:59:16 UTC) #63

Peter Kasting

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h#newcode343 base/containers/flat_set.h:343: auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default; On ...

3 years, 10 months ago (2017-02-04 01:03:35 UTC) #64

dcheng

https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/200001/base/containers/flat_set.h#newcode343 base/containers/flat_set.h:343: auto flat_set<Key, Compare>::operator=(flat_set &&) -> flat_set& = default; On ...

3 years, 10 months ago (2017-02-04 05:57:19 UTC) #65

danakj

LGTM w/ 2 last things: https://codereview.chromium.org/2552343003/diff/220001/base/containers/flat_set_unittest.cc File base/containers/flat_set_unittest.cc (right): https://codereview.chromium.org/2552343003/diff/220001/base/containers/flat_set_unittest.cc#newcode47 base/containers/flat_set_unittest.cc:47: MoveOnly(int data = 1) ...

3 years, 10 months ago (2017-02-07 16:35:51 UTC) #66

dyaroshev

> On 2017/02/03 20:30:49, danakj wrote: > L G T M Yey!!!!!!!!!!!! https://codereview.chromium.org/2552343003/diff/220001/base/containers/flat_set_unittest.cc File base/containers/flat_set_unittest.cc ...

3 years, 10 months ago (2017-02-07 23:47:24 UTC) #67

dyaroshev

The patchset sent to the CQ was uploaded after l-g-t-m from vmpstr@chromium.org, danakj@chromium.org Link to ...

3 years, 10 months ago (2017-02-07 23:48:15 UTC) #69

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/2552343003/260001

3 years, 10 months ago (2017-02-07 23:48:59 UTC) #70

commit-bot: I haz the power

The CQ bit was unchecked by commit-bot@chromium.org

3 years, 10 months ago (2017-02-07 23:49:05 UTC) #71

commit-bot: I haz the power

A disapproval has been posted by following reviewers: dcheng@chromium.org. Please make sure to get positive ...

3 years, 10 months ago (2017-02-07 23:49:07 UTC) #72

dyaroshev

On 2017/01/26 19:37:18, dcheng wrote: > On 2017/01/26 19:36:48, dcheng wrote: > > +vmpstr who ...

3 years, 10 months ago (2017-02-07 23:50:58 UTC) #73

dcheng

lgtm based on danakj's review https://codereview.chromium.org/2552343003/diff/260001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/260001/base/containers/flat_set.h#newcode267 base/containers/flat_set.h:267: return !operator==(lhs, rhs); Nit: ...

3 years, 10 months ago (2017-02-07 23:54:45 UTC) #74

dyaroshev

https://codereview.chromium.org/2552343003/diff/260001/base/containers/flat_set.h File base/containers/flat_set.h (right): https://codereview.chromium.org/2552343003/diff/260001/base/containers/flat_set.h#newcode267 base/containers/flat_set.h:267: return !operator==(lhs, rhs); On 2017/02/07 23:54:45, dcheng wrote: > ...

3 years, 10 months ago (2017-02-08 00:07:22 UTC) #75

dyaroshev

The patchset sent to the CQ was uploaded after l-g-t-m from danakj@chromium.org, vmpstr@chromium.org, dcheng@chromium.org Link ...

3 years, 10 months ago (2017-02-08 00:07:36 UTC) #77

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/2552343003/280001

3 years, 10 months ago (2017-02-08 00:08:37 UTC) #78

commit-bot: I haz the power

CQ is committing da patch. Bot data: {"patchset_id": 280001, "attempt_start_ts": 1486512456388730, "parent_rev": "b08ece22706fc672457dd030a563a744f75668a2", "commit_rev": "db07be4db9751369102b24cd8fe772200982f3e7"}

3 years, 10 months ago (2017-02-08 02:39:51 UTC) #79

commit-bot: I haz the power

Description was changed from ========== This patch introduces base::flat_set class in chromium. The interface is ...

3 years, 10 months ago (2017-02-08 02:40:26 UTC) #80

Message was sent while issue was closed.

Description was changed from

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters
instead of
                             // casting iterator to const_iterator.
   We can probably fix this, but it should be done later.

- No templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759
==========

to

==========
This patch introduces base::flat_set class in chromium.
The interface is based on the proposal for standardisation:
https://github.com/WG21-SG14/flat_containers/blob/master/proposals/P0460R0_fl...

Differences in the api with the proposal:
 - Key types are not const.   
   None of analysed flat_set implementations (boost, eastl, folly) do this.
Making them
   const forbids erase(remove_if) idiom, which is widely believed to be the
fastest way
   to erase elements from a vector - therefore from a flat_set. I've contacted
Sean 
   Middleditch (proposal's author) - he hasn't figure out this problem yet.

- Ranges are represented with {Iterator/Iterator} pair vs {Iterator/Sentinel}
pair.
   {Iterator/Sentinel} is an interface that is proposed for ranges from Ranges
TS (talk at   
   CppCon: https://youtu.be/mFUXNMfaciE). Currently in chromium we do not use
   this type of ranges, and introducing it without enable_if tricks make certain
 
   scenarios ambiguous.
   Example:
     base::flat_set<int> s;
     s.insert(s.begin(), 3); // Tries to insert with two template parameters
instead of
                             // casting iterator to const_iterator.
   We can probably fix this, but it should be done later.

- No templated overloads of find/count/lower_bound etc.
These overloads were introduced for std::set in C++14. They require a version of
std::less<> without parameters. They are useful and we should implement them,
but
not in initial CL.

- Default constructed iterators do not compare equal.
Library working group issue: LWG #2059
We currently use std::vector iterators, and they do not do this in our version
of the
standard library.

List of unclear issues:
 - Can we use libcpp tests? They seem to have permissive license, but this is
not my
    area of expertise.
    Their license file on github:
    https://github.com/llvm-mirror/libcxx/blob/master/LICENSE.TXT

 - Do we want an interface that specialise allocators?
    There are a few possible variations of template parameters:
    proposal, boost:
    <Key, Compare, Allocator>
    eastl:
    <Key, Compare, Allocator, RandomAccessContainer /*allocator is passed
here*/>
    another possibility:
    <Key, Compare, RandomAccessContainer>
    The possibility of customising underlying container seems to be useful for
some 
    cases in Chromium but it has to be investigated separately (this would lead
to
    introduction of different apis, that have to be benchmarked first). However,
we 
    typically  do not use allocators in chromium, do we want to keep the
possibility of 
    customising them in the interface, or do we want to rip it out?

 - Do we want to leave the possibility of a small buffer optimisation for
default flat_set?
    std::vector does not invalidate iterators on move and swap, which forbids
small 
    buffer optimisation. This optimisation sometimes proves to be very
beneficial.
    If we are willing not to give the same guarantee as std::vector, we can
introduce it 
    by default later.

Discussion at chrome-dev:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Proposal to add flat_set to chromium:
https://docs.google.com/document/d/1N9TeYduZj1OR4Qm_aEZ-hp5yq7HlpnGi06VThive5...

BUG=671759

Review-Url: https://codereview.chromium.org/2552343003
Cr-Commit-Position: refs/heads/master@{#448869}
Committed:
https://chromium.googlesource.com/chromium/src/+/db07be4db9751369102b24cd8fe7...
==========

commit-bot: I haz the power

3 years, 10 months ago (2017-02-08 02:40:27 UTC) #81

Message was sent while issue was closed.

Committed patchset #13 (id:280001) as
https://chromium.googlesource.com/chromium/src/+/db07be4db9751369102b24cd8fe7...

Issue 2552343003: First implementation of flat sets (Closed)

Description

Patch Set 1 : Initial commit #

Patch Set 2 : Review, round 1. #

Patch Set 3 : Review, round 2. #

Patch Set 4 : Review, round 3. #

Patch Set 5 : Review, round 4. #

Patch Set 6 : Fixing compilation error on linux. #

Patch Set 7 : Review, round 5. #

Patch Set 8 : Review, round 6. #

Patch Set 9 : Rewiew, round 7. #

Patch Set 10 : Review, round 8. #

Patch Set 11 : Review, round 9. #

Patch Set 12 : Review, round 10. #

Patch Set 13 : Review, round 11. #

Messages