Carefully using sorted vector based sets/maps (Standardisation paper http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0038r0.html) I've managed to get more then 10 times speed up of this particular function, which lead to 3-5 times speed up of whole suggest.Have you tried it? Would you be interested in such optimisation?
In order to do it, we need:
- sorted vector based set/map. I used my own implementation, there are ones in boost::container, eastl, locky, folly. Mine has the advantage of being third party independent, but it's not as tested as boost or eastl.
- suggest benchmarks on a big profile. I can modify the benchmark i have, but I need a profile that is ok to commit in chromium repo.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
Thanks for looking into this kind of thing.Can you quantify more the conditions under which you see a speedup? In other words, do we expect this is for vectors below a certain size, or for certain workloads? Also, I'm curious for more information about the times involved. If this makes something that is already fast faster, then it's less interesting. To me, a lot of whether or not this is a good idea or not is whether we can write clear advice for when to use it and when not to use it that any programmer can understand.
I often write code where I know searching a vector would be faster than using a set or a map, but I've concluded it's almost always better to just use the standard thing that has the semantic meaning you want and not worry about it. There is also a danger that adding many custom contains makes the codebase overall more difficult to understand. As an example, I added base/containers/small_map.h which does brute-force searching for small containers, but because of code bloat (probably doesn't apply to your proposal) and the fact that the operations one would expect for small maps are small to begin with, performance doesn't really end up mattering. In retrospect, I'm not sure me adding this concept was a good idea.
--
If you have a reproducible case involving large profiles, I do think
it would be worthwhile to log a bug with repro instructions, perhaps
in the form of a unit test which generates synthetic input data.
-scott
In order to add a generic container we should be able to say in a general case what it would be used for and how much it would help.
With what you've posted, I can't tell that case apart from the URL index code doing silly things and needing to be fixed.
In order to add a generic container we should be able to say in a general case what it would be used for and how much it would help.According to some research, flat containers are generally preferable to node based like std::set/std::map. For example Chandler Carruth touches the subject: https://youtu.be/fHNmRkzxHWs There is an exception - a case when one does lots of insertions and deletions in a mix with searches, in which case careful measurements are required.
IIUC, Blink has a non-node-based hashed container which might be even better than a flat_map: https://cs.chromium.org/chromium/src/third_party/WebKit/Source/wtf/HashSet.h. Have you tried that sort of container too, or just sorted vectors?
I could imagine sorted vectors being better if all the operations are pure unions, intersections, and differences. I'm having trouble navigating HistoryItemsForTerms well enough to tell whether that's the case. Where are the sets there?
Legend:
I've measured 3 cases: current situation, using std::set/std::map; replacing typedefs to flat version (requires careful handling of iterators); optimising insertions here https://cs.chromium.org/chromium/src/components/omnibox/browser/url_index_private_data.cc?q=url_index_pri&sq=package:chromium&l=651 The last optimization doesn't give that much of a boost on current test but I've seen data where it's crucial. If chromium is going to accept these changes, I'm planning to use such an optimization wherever I can, so we don't get sudden regression. History for each test is same 10'000 generated urls - it's a lot for one url but can happen in real data. For each code modifications I did 6 texts - 3 inputing url, 3 - backspacing it.Summary: pure typedefs replacement can give 4 - 16 times improvement, with small tweaking - 6 - 30 times. I think - flat_sets/maps are very useful.
I've been looking at the url_index_private_data code (the interior of
HQP), and I'm wondering if this kind of flat-container solution is
worthwhile in the long term. Right now, the code has a lot of
maps-of-sets, and it looks like some of the inner loop does things
like "Get a bunch of sets, then intersect them" to implement what
seems to be a prefix match. It seems kind of antagonistic to the
cache.
On Wed, Sep 21, 2016 at 2:01 PM, Scott Hess <sh...@chromium.org> wrote:* Flat maps/sets are a good idea anyway. In general, the majority of places in Chrome that use maps/sets today should probably just be defaulting to flat maps/sets.
So while I very much encourage you to keep quantifying the problem, and if you want to jump in and work on the engineering of how to get this to the best place, I would personally choose to proceed with trying to add the relevant data structures to the tree, make the existing HQP code use them, and possibly update our style guides to suggest the use of these types. (I think there was a relevant internal G+ post about this last recently, but G+ search sucks.)
Do you have a particular implementation of btree based maps/sets that I could reasonably easy try? I would like to compare measurements.
--
Hi.
Hi.
Hi again.
I finally finished the proposal to add flat containers to Chromium to the stage where we can discuss it.Lots of measurements for different libraries on windows and mac!
Questions, comments, tomatoes - all welcome.
This is very interesting. I am encouraged that the patch to add a prototype makes no changes to the HQP's code other than typedefs and one small iterator fix that we should just make anyway (commented on CL). The earlier prototypes requiring some changes to access patterns to get optimal performance were more worrisome.I found it noteworthy that a B-tree performed 50% worse in your tests than the flat container. Yuri may have thoughts there.
Some things not necessarily clear in the doc:* What's the confidence level/error bars for the measurements?
* How representative of typical user workloads is this particular benchmark? Having 10K similar URLs as the benchmark does seems a bit artificial to me, but perhaps the effects are similar in more "typical" cases, just less pronounced?
* You commented that significant work would still be needed to bring the prototype container implementations up to production quality. Broadly, what kind of work is still needed?
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.
I didn't end up landing it but fairly recently I looked into flat sets and maps, and I think they are worth considering. See https://codereview.chromium.org/2396533004/I wrote a few benchmarks to try and explore the performance (note the graphs are log scale) and for small data stets they seemed to be pretty fast, but folks where concerned about the linear worst case performance for insert and erase.
I didn't try a comparison with boot's containers but that would be interesting to see since the boost flat_map looks like it's using a much more complicated data structure.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
* You commented that significant work would still be needed to bring the prototype container implementations up to production quality. Broadly, what kind of work is still needed?First and the most important - tests. flat_set/flat_map have lot's of methods, each can do all kinds of different staff and have many corner cases.
On top of that something like a good implementation of void insert(first, last) has to have a few versions for different types of iterators (this type of staff can probably be added later, but boost has that and it works). Whatever I've tried so far was just oh so much copy and paste - this is no good, we would have to do smth like boost does for it's maps.
Second: design of a few things: like separate key/value storage, what do we want to pass as a template parameter : container vs allocator, special iterators etc, etc (this is something I would love to do, but this is still quite some time).It would be nice to do benchmarks for different type of things, how well do they perform in different conditions. Maybe a small buffer optimisation?
Some of the things I've mentioned are not on the first order of business but good tests are most certainly are.On top of that I'm sure that I won't do this at work, I will have to work on this mostly in my spare time, and it's never fast. I would say, optimistically, a few weeks it would take to commit tests for set (I think I would wanna do them in a separate patch and test std::set). Then simple version of flat_set is not that hard - algorithms on a vector are not very complicated . As far as I can tell flat map is a flat set + a parallel vector, but I would have to write an iterator. I can't tell right now how much of flat set's tests could be reused for flat maps (different interface, pair<Key&, Value&> all those things), but we would definitely need more, map specific. I think we would get multiset/multimap mostly for free (many versions utilise one base class with unique/non_unique methods).After that we can think about more serious tweaking performance tweaking.
So - 4-5 complicated patches over next few months would be my optimistic estimate.
Or we can pull in some boost.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
Awesome research! If we would have a decent tested container, we could try out different implementations for different sizes, iterator_categories etc.
Can I upload the code of your profiling somewhere?
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.
* How representative of typical user workloads is this particular benchmark? Having 10K similar URLs as the benchmark does seems a bit artificial to me, but perhaps the effects are similar in more "typical" cases, just less pronounced?
Histogram: Omnibox.HistoryIDSetFromWordsForked recorded 950 samples, average = 1.6 (flags = 0x1)24 ...
0 ------------------------------------------------------------------------O (388 = 40.8%)
1 ------------------------------------------O (225 = 23.7%) {40.8%}
2 --------------------------O (140 = 14.7%) {64.5%}
3 ---------------O (83 = 8.7%) {79.3%}
4 --------O (41 = 4.3%) {88.0%}
5 -----O (28 = 2.9%) {92.3%}
6 --O (12 = 1.3%) {95.3%}
7 -O (8 = 0.8%) {96.5%}
8 -O (9 = 0.9%) {97.4%}
10 -O (7 = 0.7%) {98.3%}
12 O (4 = 0.4%) {99.1%}
14 O (1 = 0.1%) {99.5%}
17 O (2 = 0.2%) {99.6%}
20 O (2 = 0.2%) {99.8%}
0 ---O (1 = 0.7%)
1 ...
5 ---------------------------O (10 = 6.7%) {0.7%}
6 -------------------------------------------O (16 = 10.7%) {7.4%}
7 ------------------------------------------------------------------------O (27 = 18.1%) {18.1%}
8 ---------------------------------------------O (17 = 11.4%) {36.2%}
9 ------------------------------------------------O (18 = 12.1%) {47.7%}
10 --------------------------------O (12 = 8.1%) {59.7%}
11 -----------O (4 = 2.7%) {67.8%}
12 -------------O (10 = 6.7%) {70.5%}
14 -----------O (8 = 5.4%) {77.2%}
16 -------O (5 = 3.4%) {82.6%}
18 -----------O (8 = 5.4%) {85.9%}
20 ----O (5 = 3.4%) {91.3%}
23 -----O (6 = 4.0%) {94.6%}
26 -O (1 = 0.7%) {98.7%}
29 ...
37 -O (1 = 0.7%) {99.3%}
42 ...
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
* How representative of typical user workloads is this particular benchmark? Having 10K similar URLs as the benchmark does seems a bit artificial to me, but perhaps the effects are similar in more "typical" cases, just less pronounced?Found some real data for you - my machine) It's yandex browser, but in terms of performance here we don't differ much.
HistoryIDSetFromWordsForked doesn't differ much in terms of performance from chrome's version in terms of performance. As you can see, from time to time there are some pretty awful numbers.
It sounds to me like making a nice interface and using std::vector, std::lower_bound, std::set_intersection, etc as the implementation of it would be an easy first step to some big performance wins, and we could do guided profiling and optimization to improve its performance (such as the search implementation below) afterward. This would immediately allow us to start replacing sets and maps in chromium and see wins, right? An interesting part up-front is defining a good API that will not end up letting developers re-sort the vector between inserts accidentally.
And, as I mentioned in one of my fist comments - this number (on previously bad inputs) goes down to 0.5ms.
I would say we should gain some experience (with benchmarks =) ) before doing any massive changes)
However, I think that flat containers could be a good default choice)
I would mention again, that this is not a very sintetic benchmark's data - this a real person's history, we run an interactive test, and type symbols into omnibox.
Sure, I chose the most popular url in history and the person has a big profile and not the most common worload in the world etc, but I would bet that we'll see at least some improvements.
среда, 30 ноября 2016 г., 0:32:53 UTC+3 пользователь Alex Clarke написал:I didn't end up landing it but fairly recently I looked into flat sets and maps, and I think they are worth considering. See https://codereview.chromium.org/2396533004/I wrote a few benchmarks to try and explore the performance (note the graphs are log scale) and for small data stets they seemed to be pretty fast, but folks where concerned about the linear worst case performance for insert and erase.
I will definetly take a closer look tommorow.
About linear worst case: it's not entirely correct to compare flat_set/flat_map to the std::set/std::map in terms of insertions erasures one to one.
It has an assumption to it that you constantly modify your map by one element. This is typically not true (especially in HQP).
You can do an erase(remove) idiom and it will do all your erasures at one linear time. You can do sort + insert, if you insert multiple elements at once.
Anyways, I don't think that it's fare to judge flat containers from insertion/erasure speed (at least on the big sizes) the same way as judging lists for their iteration time. This is not what they are made for.
I didn't try a comparison with boot's containers but that would be interesting to see since the boost flat_map looks like it's using a much more complicated data structure.It's not - it's just a sorted vector that has some staff over it. Actually your ring buffer solution us much more unusual, I would say)
Is there a good reason why you deviated from tipical interfaces so much?
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
On Wed, Nov 30, 2016 at 12:28 PM, Денис <dyar...@yandex-team.ru> wrote:Awesome research! If we would have a decent tested container, we could try out different implementations for different sizes, iterator_categories etc.
Can I upload the code of your profiling somewhere?The code is kind of one off with all kinds of one letter variables and commented code :) I'll clean it up and send it in a follow-up email.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
The critical bits are:* Do we want these containers in Chromium at all? (It seems like sentiment is positive)
* Do we want to build them ourselves or import e.g. Boost? (The doc recommends Boost, but I think the former is better)
I can see how there can be some problems with map interface but isn't C++17 std::set interface (except for the node parts, it's not applicable) is good enough?
Most of these things are for maps. Container vs Allocators are the only thing concerning sets, but I still can't test it without some working implementation of flat_sets.
I can write an api, if you think this is a good idea but an api without tests can be buggy: for example I tried to implement "void insert(It, Sent)" like in the proposal and found out that then it conflicts with overload iterator "insert (const_iterator, const value_type&)".
However, if you think that this is the way to go - ok.
On Tue, Nov 29, 2016 at 8:49 AM, Денис <dyar...@yandex-team.ru> wrote:I finally finished the proposal to add flat containers to Chromium to the stage where we can discuss it.Lots of measurements for different libraries on windows and mac!
I found it noteworthy that a B-tree performed 50% worse in your tests than the flat container. Yuri may have thoughts there.
On Tue, Nov 29, 2016 at 11:33 AM, Peter Kasting <pkas...@chromium.org> wrote:On Tue, Nov 29, 2016 at 8:49 AM, Денис <dyar...@yandex-team.ru> wrote:I finally finished the proposal to add flat containers to Chromium to the stage where we can discuss it.Lots of measurements for different libraries on windows and mac!Very interesting! Thanks for doing this. :)I took a look at the code review link. I'm not familiar at all with the HQP code or design, so I'm probably misinterpreting what we are measuring and which map containers were being replaced for these tests. Perhaps you could share a code review link that has the exact patch you were using for testing the flat_set/map replacement, and also point us to the exact benchmark functions used to get the data for each graph? For me, it's otherwise hard to reason about the access patterns on the data structures.BTW--At line 173-175 in components/omnibox/browser/history_quick_provider_performance_unittest.cc in this CL, you should use base::TimeTicks instead of base::Time. The latter is not a high-resolution monotonic clock.I found it noteworthy that a B-tree performed 50% worse in your tests than the flat container. Yuri may have thoughts there.I think this result makes sense if the vast majority of operations in this code are look-ups. To do each look-up, the B-Tree must scan through a few layers of nodes to find each one value (of 10,000); whereas the flat_map is just searching an ordered array. BTW--I'm not sure there exists a data structure that could perform look-ups better than a sorted array (assuming randomly-distributed queries and elements).
On Fri, Dec 2, 2016 at 12:09 PM, Денис <dyar...@yandex-team.ru> wrote:Most of these things are for maps. Container vs Allocators are the only thing concerning sets, but I still can't test it without some working implementation of flat_sets.
I can write an api, if you think this is a good idea but an api without tests can be buggy: for example I tried to implement "void insert(It, Sent)" like in the proposal and found out that then it conflicts with overload iterator "insert (const_iterator, const value_type&)".
However, if you think that this is the way to go - ok.I would try to match the C++11 APIs for map/set for now, and not add anything fancy. We can do that later if need be.
On Fri, Dec 2, 2016 at 12:20 PM, Peter Kasting <pkas...@chromium.org> wrote:On Fri, Dec 2, 2016 at 12:09 PM, Денис <dyar...@yandex-team.ru> wrote:Most of these things are for maps. Container vs Allocators are the only thing concerning sets, but I still can't test it without some working implementation of flat_sets.
I can write an api, if you think this is a good idea but an api without tests can be buggy: for example I tried to implement "void insert(It, Sent)" like in the proposal and found out that then it conflicts with overload iterator "insert (const_iterator, const value_type&)".
However, if you think that this is the way to go - ok.I would try to match the C++11 APIs for map/set for now, and not add anything fancy. We can do that later if need be.I'm not sure that's the right approach. There are proposals for flat_set in STL linked to in your document which both seem to be better starting points than the worst example of std::set.The 2nd proposal exposes the underlying iterators and container to provide the maximum flexibility of the flat_set adapter. I'm not convinced that we need that here, tho allowing specifying a different underlying container does seem very interesting, as possibly very useful for blink which may want to use WTF::Vector for instance to allow garbage collected objects to be stored.I'd like to see a design proposal that considers and explains its choices with respect to the boost API, these proposals linked from your explainer document, and takes into consideration Oilpan and Mojo.
On Mon, Dec 5, 2016 at 3:41 PM, <dan...@chromium.org> wrote:On Fri, Dec 2, 2016 at 12:20 PM, Peter Kasting <pkas...@chromium.org> wrote:On Fri, Dec 2, 2016 at 12:09 PM, Денис <dyar...@yandex-team.ru> wrote:Most of these things are for maps. Container vs Allocators are the only thing concerning sets, but I still can't test it without some working implementation of flat_sets.
I can write an api, if you think this is a good idea but an api without tests can be buggy: for example I tried to implement "void insert(It, Sent)" like in the proposal and found out that then it conflicts with overload iterator "insert (const_iterator, const value_type&)".
However, if you think that this is the way to go - ok.I would try to match the C++11 APIs for map/set for now, and not add anything fancy. We can do that later if need be.I'm not sure that's the right approach. There are proposals for flat_set in STL linked to in your document which both seem to be better starting points than the worst example of std::set.The 2nd proposal exposes the underlying iterators and container to provide the maximum flexibility of the flat_set adapter. I'm not convinced that we need that here, tho allowing specifying a different underlying container does seem very interesting, as possibly very useful for blink which may want to use WTF::Vector for instance to allow garbage collected objects to be stored.I'd like to see a design proposal that considers and explains its choices with respect to the boost API, these proposals linked from your explainer document, and takes into consideration Oilpan and Mojo.My concern here is that we set the bar so high to get anything into the codebase that we don't actually ship major, meaningful improvements to users in a timely way.
The improvements proposed to the omnibox here will have significant user impact. They have already been delayed a couple of months in the process of trying to get more data to support this change than I thought we needed. Since this is effectively volunteer-time work from an external contributor, I'm concerned about adding Yet More Months onto that process. Can we create something that's a workable improvement now, and leave "make the perfect ultimate API that solves Oilpan and Mojo and Chromium and considers C++11 and boost and all the other external implementations" as a followup?
This has other advantages as well. Using C++11 APIs lets these be a drop-in replacement for map/set today, maximizing the ease of porting existing Chromium code to them (which then increases the surface area that will be improvable if we later improve the API/implementation). It also provides the greatest chance for migration to a future std::flat_map/set.
Are there ways in which using the C++11 APIs _prevents_ us from adding more power and customizability later? If such capabilities are purely "added value", then staging their addition also makes the initial API more reviewable.
Here's a possible path forward. What do you think?1. Take the prototype written by dyaroshev, and specialize it for omnibox.- Drop methods that omnibox doesn't need. This lowers the test coverage requirements.- Can we add tests based on what boost tests?- Change APIs if they can produce much better performance. With fewer methods this evaluation is easier.- We can do this iteratively as needed.2. Survey the differences in API between STL, the proposed flat_set, boost's, and what we end up from step 1. Explain the differences and choose the best for each variation.3. Generalize the class with templates, extend/change the API based on step 2, and move it to base.4. Use it more widely.
Thanks for the detailed reply. I had read the whole paper but had not recalled that the proposed future flat_set/map API didn't match today's set/map API. That is a crucial detail.
--
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
What's HQP?Daniel
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
--
For the curious, this is in:Is a flat_map planned also? If so, can we replace small_map with it? I think the performance properties will overlap enough such that having the super-small small_map optimization is no longer necessary, especially given the code bloat associated with small_map.
On Wed, Feb 8, 2017 at 9:30 AM, Brett Wilson <bre...@chromium.org> wrote:For the curious, this is in:Is a flat_map planned also? If so, can we replace small_map with it? I think the performance properties will overlap enough such that having the super-small small_map optimization is no longer necessary, especially given the code bloat associated with small_map.+1 for flat_map as well. I think it would be very useful and should be pretty straightforward to implement with the flat_set as an example.
On Wed, Feb 8, 2017 at 2:28 PM, Vladimir Levin <vmp...@chromium.org> wrote:On Wed, Feb 8, 2017 at 9:30 AM, Brett Wilson <bre...@chromium.org> wrote:For the curious, this is in:Is a flat_map planned also? If so, can we replace small_map with it? I think the performance properties will overlap enough such that having the super-small small_map optimization is no longer necessary, especially given the code bloat associated with small_map.+1 for flat_map as well. I think it would be very useful and should be pretty straightforward to implement with the flat_set as an example.I think it's a good idea but it'd be nice to get a better handle on the perf for flat_set and where it is good/bad to use. The guidance in the .h should be fairly conservative right now. And it doesn't support any kind of bulk insertion yet. So there's a few avenues that we could go next.Also it's worth considering how we can evolve dealing with keys for both flat_set and flat_map. Specifically if you have std::string keys, it'd be nice if find("literal") didn't have to construct a std::string. Also it'd be nice to be able to use unique_ptr as a key and be able to find() them based on the value inside. I'm not sure if we can do those things and not break the container's API compatibility with STL.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
On Wed, Feb 8, 2017 at 12:23 PM <dan...@chromium.org> wrote:On Wed, Feb 8, 2017 at 2:28 PM, Vladimir Levin <vmp...@chromium.org> wrote:On Wed, Feb 8, 2017 at 9:30 AM, Brett Wilson <bre...@chromium.org> wrote:For the curious, this is in:Is a flat_map planned also? If so, can we replace small_map with it? I think the performance properties will overlap enough such that having the super-small small_map optimization is no longer necessary, especially given the code bloat associated with small_map.+1 for flat_map as well. I think it would be very useful and should be pretty straightforward to implement with the flat_set as an example.I think it's a good idea but it'd be nice to get a better handle on the perf for flat_set and where it is good/bad to use. The guidance in the .h should be fairly conservative right now. And it doesn't support any kind of bulk insertion yet. So there's a few avenues that we could go next.Also it's worth considering how we can evolve dealing with keys for both flat_set and flat_map. Specifically if you have std::string keys, it'd be nice if find("literal") didn't have to construct a std::string. Also it'd be nice to be able to use unique_ptr as a key and be able to find() them based on the value inside. I'm not sure if we can do those things and not break the container's API compatibility with STL.Another problem with strings comes up in interactions with StringPiece:- It's nice to use StringPiece, especially if the arguments are often string literals. This avoids binary bloat, since there won't be N conversions to a temporary std::string; there's just the one conversion when actually invoking find()/insert()/emplace().- However, if the supplied argument is already a std::string, this results in an extra std::string copy.- The "solution" is to overload each method on const std::string& and const char*. Ugh!It's things like this that make me wonder if we're not just better off with a StringSet/StringMap container for string keys: then code can just use StringPiece throughout and convert it to a std::string only when it needs to store it.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev+unsubscribe@chromium.org.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
On Wed, Feb 8, 2017 at 4:59 PM, Daniel Cheng <dch...@chromium.org> wrote:On Wed, Feb 8, 2017 at 12:23 PM <dan...@chromium.org> wrote:On Wed, Feb 8, 2017 at 2:28 PM, Vladimir Levin <vmp...@chromium.org> wrote:On Wed, Feb 8, 2017 at 9:30 AM, Brett Wilson <bre...@chromium.org> wrote:For the curious, this is in:Is a flat_map planned also? If so, can we replace small_map with it? I think the performance properties will overlap enough such that having the super-small small_map optimization is no longer necessary, especially given the code bloat associated with small_map.+1 for flat_map as well. I think it would be very useful and should be pretty straightforward to implement with the flat_set as an example.I think it's a good idea but it'd be nice to get a better handle on the perf for flat_set and where it is good/bad to use. The guidance in the .h should be fairly conservative right now. And it doesn't support any kind of bulk insertion yet. So there's a few avenues that we could go next.Also it's worth considering how we can evolve dealing with keys for both flat_set and flat_map. Specifically if you have std::string keys, it'd be nice if find("literal") didn't have to construct a std::string. Also it'd be nice to be able to use unique_ptr as a key and be able to find() them based on the value inside. I'm not sure if we can do those things and not break the container's API compatibility with STL.Another problem with strings comes up in interactions with StringPiece:- It's nice to use StringPiece, especially if the arguments are often string literals. This avoids binary bloat, since there won't be N conversions to a temporary std::string; there's just the one conversion when actually invoking find()/insert()/emplace().- However, if the supplied argument is already a std::string, this results in an extra std::string copy.- The "solution" is to overload each method on const std::string& and const char*. Ugh!It's things like this that make me wonder if we're not just better off with a StringSet/StringMap container for string keys: then code can just use StringPiece throughout and convert it to a std::string only when it needs to store it.I'm not sure I understand which part of this isn't resolved by C++14-style heterogeneous lookup (in std::set/map, at least, and as you point out we can do the same for our own containers).
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
For flat_set I took tests from C++, I suggest to do the same here.
The issue of stability comes up: I would suggest that new elements can not override existing elements - this is consistent with the constructor.
flat_map/flat_multiset/flat_multimap:
I think implementing these containers in a similar to flat_set fashion is the way to go. I've seen a few implementations for std::set/std::map/flat_set/flat_map - most use common base class - I think this could be a way to go. For flat_set I took tests from C++, I suggest to do the same here.
1) brettw is working on flat_maps here: https://codereview.chromium.org/2715433007/
2) actually the big problem for HQP is sets, most maps don't affect it much, except for one, that has already been addressed: https://codereview.chromium.org/1482443002 - flat_map didn't win over unordered when I tried it. So - just switching to sets is good enough I think, at least for now.