flat containers prototype

CL for a discussion in:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector$20based$20sets/chromium-dev/4uQMma9vj9w/HaQ-WvMOAwAJ

Using flat_set/flat_map to optimise HQP.
Things that are different from standard map/set:

1) Erasing/inserting causes iterator invalidation (like in a vector, which is the default implementation)
2) Has "unsafe_access" - gives a scoped object based on std::unique_ptr, that one can use to violate invariants of the map.
In a destructor restores the invariants, unless one calls release.

This is not even close to the production quality: tests are not sufficient, maybe some interface changes could be good. However this is good enough to advance the conversation.

[dyaroshev, 2016-09-13 12:07:07]

Description was changed from

==========
before cl


initial adding of flat sets/maps

BUG=
==========

to

==========
CL for a discussion in:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Using flat_set/flat_map to optimise HQP.
Things that are different from standard map/set:

1) Erasing/inserting causes iterator invalidation (like in a vector, which is
the default implementation)
2) Has "unsafe_access" - gives a scoped object based on std::unique_ptr, that
one can use to violate invariants of the map.
In a destructor restores the invariants, unless one calls release.

This is not even close to the production quality: tests are not sufficient,
maybe some interface changes could be good.

But this is good enough to help the conversation.

BUG=
==========

[dyaroshev, 2016-09-13 12:28:13]

https://codereview.chromium.org/2333253002/diff/20001/components/omnibox/brow...
File components/omnibox/browser/url_index_private_data.cc (right):

https://codereview.chromium.org/2333253002/diff/20001/components/omnibox/brow...
components/omnibox/browser/url_index_private_data.cc:645: auto unsafe =
history_id_set.unsafe_access();
Here is the tight spot I was talking about in chromium-dev. Without using unsafe
access here, I've seen conditions where flat was outperformed by std::sets/maps.

[dyaroshev, 2016-09-13 12:30:35]

Description was changed from

==========
CL for a discussion in:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Using flat_set/flat_map to optimise HQP.
Things that are different from standard map/set:

1) Erasing/inserting causes iterator invalidation (like in a vector, which is
the default implementation)
2) Has "unsafe_access" - gives a scoped object based on std::unique_ptr, that
one can use to violate invariants of the map.
In a destructor restores the invariants, unless one calls release.

This is not even close to the production quality: tests are not sufficient,
maybe some interface changes could be good.

But this is good enough to help the conversation.

BUG=
==========

to

==========
CL for a discussion in:
https://groups.google.com/a/chromium.org/forum/#!searchin/chromium-dev/vector...

Using flat_set/flat_map to optimise HQP.
Things that are different from standard map/set:

1) Erasing/inserting causes iterator invalidation (like in a vector, which is
the default implementation)
2) Has "unsafe_access" - gives a scoped object based on std::unique_ptr, that
one can use to violate invariants of the map.
In a destructor restores the invariants, unless one calls release.

This is not even close to the production quality: tests are not sufficient,
maybe some interface changes could be good. However this is good enough to
advance the conversation.
==========

[Peter Kasting, 2016-09-13 19:12:55]

pkasting@chromium.org changed reviewers:
+ pkasting@chromium.org

[Peter Kasting, 2016-09-13 19:12:56]

The Boost flat containers are on the list of things approved for use in Google
code.  It seems like, if we do want these data structures, we should just pull
in the necessary bits of Boost in a third_party dir and refer to those, rather
than add our own custom containers.

[dyaroshev, 2016-09-13 20:24:12]

On 2016/09/13 19:12:56, Peter Kasting wrote:
> The Boost flat containers are on the list of things approved for use in Google
> code.  It seems like, if we do want these data structures, we should just pull
> in the necessary bits of Boost in a third_party dir and refer to those, rather
> than add our own custom containers.

This is probably true. Actually - there are also vector based sets/maps in a
bunch of good libraries, not just boost.

Couple of issues:
1) boost::flat... do not have the unsafe_access feature (as far as I
understood). It can be emulated via constructors that accept sorted range. This
is much less convinient, so probably won't be used everywhere. So purely by
deciding to use boost:: we leave some performance on the table. Occasionally
there is a lot of performance there (like in this cl).
2) boost solution is very complex. I've tried to add to chromium -> 6mb of
sources of depending libs.
3) since it would not live in base, people would probably not find it, when
looking.
4) Optional is in boost. It would be interesting to find out why it wasn't taken
from it.

Of course using boost is way easier, it's super tested, well documented, widely
used etc.

This cl is just what I have right now, so we have the code to discuss with. I
think we ought to finish up with measurements and then decide how we wanna do
flat sets/maps. Using boost, eastl, locky, folly, reenventing a slightly cooler
wheel - all works for me.

[Peter Kasting, 2016-09-13 20:44:54]

On 2016/09/13 20:24:12, dyaroshev wrote:
> On 2016/09/13 19:12:56, Peter Kasting wrote:
> > The Boost flat containers are on the list of things approved for use in
Google
> > code.  It seems like, if we do want these data structures, we should just
pull
> > in the necessary bits of Boost in a third_party dir and refer to those,
rather
> > than add our own custom containers.
> 
> This is probably true. Actually - there are also vector based sets/maps in a
> bunch of good libraries, not just boost.
> 
> Couple of issues:
> 1) boost::flat... do not have the unsafe_access feature (as far as I
> understood). It can be emulated via constructors that accept sorted range.
This
> is much less convinient, so probably won't be used everywhere. So purely by
> deciding to use boost:: we leave some performance on the table. Occasionally
> there is a lot of performance there (like in this cl).

Are you saying that even the emulation cannot achieve the perf wins of this CL?

I'm very uneasy about any API that is marked with "unsafe" in the name.  I would
want to bend over backwards to avoid doing that.

> 2) boost solution is very complex. I've tried to add to chromium -> 6mb of
> sources of depending libs.

It's impossible to pull just the flat containers out?  If we have to ship
hundreds of files for this, then pulling in the Boost version is much less
compelling.

> 3) since it would not live in base, people would probably not find it, when
> looking.

This is a non-issue.  If we truly cared, we could provide a type alias or
wrapper in base, but there is plenty of stuff in Chrome that isn't in base.

Also, in general we don't want to add things to base unless they have broad
utility.  One question not yet addressed here is how broadly interesting flat
containers are to other places in the codebase.

> 4) Optional is in boost. It would be interesting to find out why it wasn't
taken
> from it.

It's not on the approved list in the style guide.

[dyaroshev, 2016-09-13 22:08:50]

On 2016/09/13 20:44:54, Peter Kasting wrote:
> > 1) boost::flat... do not have the unsafe_access feature (as far as I
> > understood). It can be emulated via constructors that accept sorted range.
> This
> > is much less convinient, so probably won't be used everywhere. So purely by
> > deciding to use boost:: we leave some performance on the table. Occasionally
> > there is a lot of performance there (like in this cl).
> 
> Are you saying that even the emulation cannot achieve the perf wins of this
CL?
>

It can for the most part but it's ugly and some what a lot of code. One would
have to insert everything in a vector, then sort it, remove non unique elements
and call a special constructor with move iterators. Here it's just 1 line: start
a region where you can violate invariants of the set/map. After the end of the
region restoring the invariants is handeled by the map. Even with all these
manipulations you won't be as efficient because the CL version uses storage
avaliable in the map and the boost version would have to move. In case of HQP
the last ineficiency is insignificant. However, it can matter in more tight
conditions.

> I'm very uneasy about any API that is marked with "unsafe" in the name.  I
would
> want to bend over backwards to avoid doing that.

Fair point. We absolutely need to do many insertions without having to move
everything for each element. I think all versions support efficien erasures
(with std::remove_if). It would be nice to avoid sort + unique sometimes if you
know for sure that data is good (but I doubt that it's crusial, certanly not for
HPQ - sorting longs doesn't affect performance for most parts).

I was thinking about removing unsafe_access and insert methods and replacing
them with scoped_inserter. This helps to avoid the main reason for having unsafe
api and forces developers to do things efficiently.
{
  auto inserter = my_map.get_inserter();
  inserter.insert({"a", 3})
  inserter.insert({"b", 2});
} // does all the insertions

However - for the purpose of pure data structure testing I needed the ability to
do as close to the drop in replacement as possible. Another thing is -
developers know std::map - it's great when new is similar.

My point is: I agree with you, unsafe does sounds scary but something like this
is a good thing to have - I'm open to ideas.

> > 2) boost solution is very complex. I've tried to add to chromium -> 6mb of
> > sources of depending libs.
> 
> It's impossible to pull just the flat containers out?  If we have to ship
> hundreds of files for this, then pulling in the Boost version is much less
> compelling.
> 

I felt pretty uncofortable ripping boost libraries apart, so I've added the
whole library at once. Adding flat_* required a few dependent libraries (I
remember compiler macroses, I can come up with the list by your tommorow if
necessary). All of the sources added up to 6mb of code.

> > 3) since it would not live in base, people would probably not find it, when
> > looking.
> 
> This is a non-issue.  If we truly cared, we could provide a type alias or
> wrapper in base, but there is plenty of stuff in Chrome that isn't in base.
> 

Ok, this works.

> Also, in general we don't want to add things to base unless they have broad
> utility.  One question not yet addressed here is how broadly interesting flat
> containers are to other places in the codebase.
> 

Cache locality (why flat containers are faster) is a subject of many many
performance talks. On top of my head: I've seen talks by Scott Meyers, Herb
Sutter, Alexandr Stepanov, Alex Alexandrescu, Chandler Carruth and some more on
the subject. One of the main points: prefer vector to any other container.
flat_* are vector based, in general they are faster. I would use them over
std::set/map unless profiling says you should really do hashing (if trees do
better, you do something really weired). My point is, they have a good potential
to be broadly interesting.

> > 4) Optional is in boost. It would be interesting to find out why it wasn't
> taken
> > from it.
> 
> It's not on the approved list in the style guide.

Oh, ok.

[Peter Kasting, 2016-09-13 22:20:20]

On 2016/09/13 22:08:50, dyaroshev wrote:
> > I'm very uneasy about any API that is marked with "unsafe" in the name.  I
> would
> > want to bend over backwards to avoid doing that.
> 
> Fair point. We absolutely need to do many insertions without having to move
> everything for each element. I think all versions support efficien erasures
> (with std::remove_if). It would be nice to avoid sort + unique sometimes if
you
> know for sure that data is good (but I doubt that it's crusial, certanly not
for
> HPQ - sorting longs doesn't affect performance for most parts).
> 
> I was thinking about removing unsafe_access and insert methods and replacing
> them with scoped_inserter. This helps to avoid the main reason for having
unsafe
> api and forces developers to do things efficiently.
> {
>   auto inserter = my_map.get_inserter();
>   inserter.insert({"a", 3})
>   inserter.insert({"b", 2});
> } // does all the insertions

Yeah, something like this would probably be better.

> > > 2) boost solution is very complex. I've tried to add to chromium -> 6mb of
> > > sources of depending libs.
> > 
> > It's impossible to pull just the flat containers out?  If we have to ship
> > hundreds of files for this, then pulling in the Boost version is much less
> > compelling.
> > 
> 
> I felt pretty uncofortable ripping boost libraries apart, so I've added the
> whole library at once. Adding flat_* required a few dependent libraries (I
> remember compiler macroses, I can come up with the list by your tommorow if
> necessary). All of the sources added up to 6mb of code.

The rest of boost/container/ is not approved, so it'd be nice to avoid making it
available to developers to prevent easy misuse.  My hope was that if we just had
the flat_xxx C++ files and their dependencies, things would be pretty small.

> > Also, in general we don't want to add things to base unless they have broad
> > utility.  One question not yet addressed here is how broadly interesting
flat
> > containers are to other places in the codebase.
> > 
> 
> Cache locality (why flat containers are faster) is a subject of many many
> performance talks. On top of my head: I've seen talks by Scott Meyers, Herb
> Sutter, Alexandr Stepanov, Alex Alexandrescu, Chandler Carruth and some more
on
> the subject. One of the main points: prefer vector to any other container.
> flat_* are vector based, in general they are faster. I would use them over
> std::set/map unless profiling says you should really do hashing (if trees do
> better, you do something really weired). My point is, they have a good
potential
> to be broadly interesting.

Yeah, I buy all that.  I think it's worth getting something into the codebase.

[dyaroshev, 2016-09-13 23:19:38]

On 2016/09/13 22:20:20, Peter Kasting wrote:
> On 2016/09/13 22:08:50, dyaroshev wrote:
> > I was thinking about removing unsafe_access and insert methods and replacing
> > them with scoped_inserter. This helps to avoid the main reason for having
> unsafe
> > api and forces developers to do things efficiently.
> > {
> >   auto inserter = my_map.get_inserter();
> >   inserter.insert({"a", 3})
> >   inserter.insert({"b", 2});
> > } // does all the insertions
> 
> Yeah, something like this would probably be better.
>
Great, let's merge the measurements and then get some (other =) ) smart people
here and decide smth.

> 
> The rest of boost/container/ is not approved, so it'd be nice to avoid making
it
> available to developers to prevent easy misuse.  My hope was that if we just
had
> the flat_xxx C++ files and their dependencies, things would be pretty small.
>

I'll try to rip it apart as much as I can and come back with the results. It can
make migration to the next versions harder but it's ok.

> ...
> 
> Yeah, I buy all that.  I think it's worth getting something into the codebase.

Horray!

[dyaroshev, 2016-09-14 12:17:54]

On 2016/09/13 22:20:20, Peter Kasting wrote:
> The rest of boost/container/ is not approved, so it'd be nice to avoid making
it
> available to developers to prevent easy misuse.  My hope was that if we just
had
> the flat_xxx C++ files and their dependencies, things would be pretty small.
> 

Here is what I could shrink it to (140 files, 1.4mb of sources)
https://drive.google.com/open?id=0B5pZ4

Maybe we can remove support for some compilers and standard libraries but
anyways - this is not going to be much smaller than, let's say, 50 files without
modifications of the sources, which is not easier that to wrap our own
implementation. Another thing - boost files are quite a hard reading.

[dyaroshev, 2016-09-14 15:01:50]

On 2016/09/14 12:17:54, dyaroshev wrote:
> Here is what I could shrink it to (140 files, 1.4mb of sources)
> https://drive.google.com/open?id=0B5pZ4
Url haven't copied entirely
https://drive.google.com/open?id=0B5pZ43DhqaQDRXVoOWY4anpRWG8

[Peter Kasting, 2016-11-29 19:17:45]

https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
File components/omnibox/browser/url_index_private_data.cc (right):

https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
components/omnibox/browser/url_index_private_data.cc:256: cache_iter =
search_term_cache_.erase(cache_iter);
FWIW, now that C++11 provides this on std::map, we should just make this change
anyway (assuming it doesn't break one of our archaic libstdc++ implementations),
since it's more clearly safe.

[dyaroshev, 2016-11-29 20:09:14]

https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
File components/omnibox/browser/url_index_private_data.cc (right):

https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
components/omnibox/browser/url_index_private_data.cc:256: cache_iter =
search_term_cache_.erase(cache_iter);
On 2016/11/29 19:17:45, Peter Kasting wrote:
> FWIW, now that C++11 provides this on std::map, we should just make this
change
> anyway (assuming it doesn't break one of our archaic libstdc++
implementations),
> since it's more clearly safe.

Some time ago there was a problem with the standard library on linux -
map::erase didn't provide modern interface.
(and vector erase too - there are work arounds against that in
flat_sorted_container_base.h and some tests here are disabled on linux).
I don't know if we updated since.

In my opinion this patch is good for illustrating purpose - maybe keep it as is,
at least for now?

[Peter Kasting, 2016-11-29 20:29:06]

https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
File components/omnibox/browser/url_index_private_data.cc (right):

https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
components/omnibox/browser/url_index_private_data.cc:256: cache_iter =
search_term_cache_.erase(cache_iter);
On 2016/11/29 20:09:14, dyaroshev wrote:
> On 2016/11/29 19:17:45, Peter Kasting wrote:
> > FWIW, now that C++11 provides this on std::map, we should just make this
> change
> > anyway (assuming it doesn't break one of our archaic libstdc++
> implementations),
> > since it's more clearly safe.
> 
> Some time ago there was a problem with the standard library on linux -
> map::erase didn't provide modern interface.
> (and vector erase too - there are work arounds against that in
> flat_sorted_container_base.h and some tests here are disabled on linux).
> I don't know if we updated since.

I don't either.

> In my opinion this patch is good for illustrating purpose - maybe keep it as
is,
> at least for now?

We'd only update this patch to not have this if we were able to land this
separately :)

It'd probably be pretty easy to write a separate CL with just this line, to see
if it compiles everywhere.

[dyaroshev, 2016-11-30 21:34:15]

On 2016/11/29 20:29:06, Peter Kasting wrote:
>
https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
> File components/omnibox/browser/url_index_private_data.cc (right):
> 
>
https://codereview.chromium.org/2333253002/diff/40001/components/omnibox/brow...
> components/omnibox/browser/url_index_private_data.cc:256: cache_iter =
> search_term_cache_.erase(cache_iter);
> On 2016/11/29 20:09:14, dyaroshev wrote:
> > On 2016/11/29 19:17:45, Peter Kasting wrote:
> > > FWIW, now that C++11 provides this on std::map, we should just make this
> > change
> > > anyway (assuming it doesn't break one of our archaic libstdc++
> > implementations),
> > > since it's more clearly safe.
> > 
> > Some time ago there was a problem with the standard library on linux -
> > map::erase didn't provide modern interface.
> > (and vector erase too - there are work arounds against that in
> > flat_sorted_container_base.h and some tests here are disabled on linux).
> > I don't know if we updated since.
> 
> I don't either.
> 
> > In my opinion this patch is good for illustrating purpose - maybe keep it as
> is,
> > at least for now?
> 
> We'd only update this patch to not have this if we were able to land this
> separately :)
> 
> It'd probably be pretty easy to write a separate CL with just this line, to
see
> if it compiles everywhere.

I've created a cl: https://codereview.chromium.org/2545603002/

[Peter Kasting, 2017-02-11 01:56:03]

Now that flat sets have landed in base, this CL should presumably be rebased on
top of those.