So, we have base/containers/hash_tables.h. C++11 has std::unordered_*. We should switch to those.With https://groups.google.com/a/chromium.org/d/msg/chromium-dev/cjiUwbUhQXM/wCn8D4A1c2UJ, base/containers/hash_tables.h’s semantics were largely aligned with std::unordered_*. Now we can use the real thing everywhere.I did an initial CL and the try jobs pass. It’s not meant to land as-is, just to show that std::unordered_* works. (After you fix tons of IWYU violations...)Some issues:1) hash_tables.h has a base::string16 specialization. C++11 only provides it for std::string, std::wstring, etc., and not any std::basic_string instantiation, so a priori we’d get a hasher on Windows (string16 = wstring) and not other platforms (string16 = custom basic_string<T>). This is easy to resolve: move the std::hash specialization into string16.h[*]. Whether specializations are allowed in general (below), I think keeping base::string16 aligned across platforms is correct.2) hash_tables.h defines a std::pair specialization and C++11 does not. We have a lot of hash tables which use a std::pair key. We could define it in some utility header in base or we could provide a base::PairHash<A, B> which consumers explicitly pass into std::unordered_*. I prefer the latter. I don’t like having std::unordered_set<std::pair<int, int>> change based on whether a third header, distinct from std::pair’s header or std::unordered_set’s header. is included.
3) The Google style guide prohibits specializations of std::hash altogether:We do it a lot:The style guide talks about reducing to size_t too many times, but all our custom hashes already do that. I also don’t know much about hash algorithms, so I could be misunderstanding. I don’t have an opinion as to which way we go here. (If we decide to move to explicit custom hashes, I'm happy to do the conversion of current things.
So, we have base/containers/hash_tables.h. C++11 has std::unordered_*. We should switch to those.
With https://groups.google.com/a/chromium.org/d/msg/chromium-dev/cjiUwbUhQXM/wCn8D4A1c2UJ, base/containers/hash_tables.h’s semantics were largely aligned with std::unordered_*. Now we can use the real thing everywhere.I did an initial CL and the try jobs pass. It’s not meant to land as-is, just to show that std::unordered_* works. (After you fix tons of IWYU violations...)Some issues:1) hash_tables.h has a base::string16 specialization. C++11 only provides it for std::string, std::wstring, etc., and not any std::basic_string instantiation, so a priori we’d get a hasher on Windows (string16 = wstring) and not other platforms (string16 = custom basic_string<T>). This is easy to resolve: move the std::hash specialization into string16.h[*]. Whether specializations are allowed in general (below), I think keeping base::string16 aligned across platforms is correct.2) hash_tables.h defines a std::pair specialization and C++11 does not. We have a lot of hash tables which use a std::pair key. We could define it in some utility header in base or we could provide a base::PairHash<A, B> which consumers explicitly pass into std::unordered_*. I prefer the latter. I don’t like having std::unordered_set<std::pair<int, int>> change based on whether a third header, distinct from std::pair’s header or std::unordered_set’s header. is included.
3) The Google style guide prohibits specializations of std::hash altogether:We do it a lot:The style guide talks about reducing to size_t too many times, but all our custom hashes already do that. I also don’t know much about hash algorithms, so I could be misunderstanding. I don’t have an opinion as to which way we go here. (If we decide to move to explicit custom hashes, I'm happy to do the conversion of current things.)
Thoughts?David[*] I toyed with using std::u16string instead, but some code around ICU breaks because char16_t and uint16_t aren’t the same. (Really?! How are you supposed to avoid strict aliasing problems with all existing APIs ever?) Since the fix is easy, I propose starting with the std::hash specialization and we adopt std::u16string later, if ever.
--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAF8qwaDsfsCoOb-%2Bk8ZMfJMjE1o0YcwNQFwbCO0KUg%3Df0myCCA%40mail.gmail.com.
On Mon, Dec 21, 2015 at 3:20 PM David Benjamin <davi...@chromium.org> wrote:So, we have base/containers/hash_tables.h. C++11 has std::unordered_*. We should switch to those.Is there a compelling reason to differ from Google style here? It recommends using std::unordered_* for types that std::hash natively supports, and otherwise just falling back to the legacy hash containers or using a custom hasher.
On Mon, Dec 21, 2015 at 3:20 PM David Benjamin <davi...@chromium.org> wrote:So, we have base/containers/hash_tables.h. C++11 has std::unordered_*. We should switch to those.Is there a compelling reason to differ from Google style here? It recommends using std::unordered_* for types that std::hash natively supports, and otherwise just falling back to the legacy hash containers or using a custom hasher.
So, we have base/containers/hash_tables.h. C++11 has std::unordered_*. We should switch to those.
--
On Mon, Dec 21, 2015 at 3:20 PM, David Benjamin <davi...@chromium.org> wrote:So, we have base/containers/hash_tables.h. C++11 has std::unordered_*. We should switch to those.Blink also has a hash table implementation, which to my understanding (citation required) performs much better than std::unordered_map. I'd like us to converge between chromium and blink more than I'd like us to use whatever google3 does in chromium, and something else in blink.I've avoided pushing us toward unordered_* because I'd like someone to do the work of figuring out if the blink Hash* classes are better and provide data for that and move us all to sharing them if possible.Also, we would need to use better hash functions than std::hash with such a hash table, as it (AIUI) uses power-of-2 table sizes instead of primes, which is much better for performance (especially on ARM which has very slow integer division/mod) but requires the hash function to evenly distribute its outputs. So for instance, identity hash functions for integers can be problematic if the input set is not contiguous.
I think the STL code is the way it is because that's what you end up with optimizing for "not wrong" usage. For the majority of Chrome code, we should also be optimizing for "not wrong." This does mean that certain specialized workloads may want something else more elaborate and we end up with two ways to do something. Or maybe we can come up with something magical that allows for both.
--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CABiGVV-7ezZp%3D-hoHr7r60TLoeQkK4-%2BRLGuKx%2B387K6nGJwBQ%40mail.gmail.com.
styleguide/OWNERS discussed this thread today. We should allow unordered_* for new code, and implement hash_tables.h on top of them. Use explicit hashers where possible, but provide a string16 hasher specialization (and maybe GURL, depends a bit on how very often this is used in practice). davidben@, do you think you can get your patch into landable shape?
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAMGbLiHnuZZT5qZaYOHZpakZ6TjZiNgRVC%3De%2BfO1EKtTtdDu1g%40mail.gmail.com.
styleguide/OWNERS discussed this thread today. We should allow unordered_* for new code, and implement hash_tables.h on top of them. Use explicit hashers where possible, but provide a string16 hasher specialization (and maybe GURL, depends a bit on how very often this is used in practice). davidben@, do you think you can get your patch into landable shape?
On Thu, Jan 7, 2016 at 1:52 PM Nico Weber <tha...@chromium.org> wrote:styleguide/OWNERS discussed this thread today. We should allow unordered_* for new code, and implement hash_tables.h on top of them. Use explicit hashers where possible, but provide a string16 hasher specialization (and maybe GURL, depends a bit on how very often this is used in practice). davidben@, do you think you can get your patch into landable shape?Sure. I'm at Real World Crypto this week, but I can toy with this when I'm back (and after I dig myself out of the email pit from being at a conference three days :-) ).I assume by "allow unordered_* for new code", you mean "allow and prefer unordered_* for new code" with hash_tables.h implemented just for transition?
Now that std::unordered_* is being allowed, can we use std::unordered_multimap::emplace?
--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/44b52a7a-d864-4cc2-880c-02f7fbe421a2%40chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CACuR13edVncjMC8iWx4Sc8t%2BYpzQNf%3De3iyy9F3Q0ErRxmW7jQ%40mail.gmail.com.
My 2¢: Don't be fancy. map.emplace(key, value) is more concise and a bit easier to read than map.insert(make_pair(key, value)), and map.emplace(KeyType(arg1, arg2), ValueType(arg3, arg4)) is also more concise and much easier to read than map.emplace(std::piecewise_construct, forward_as_tuple(arg1, arg2), forward_as_tuple(arg3, arg4)). If you have a benchmark showing that avoiding the move-construction is important, then you have to decide between making the move constructor more efficient and obfuscating the map code, but without that benchmark, just do the simple thing.
On Fri, Jan 15, 2016 at 10:55 AM Jeffrey Yasskin <jyas...@chromium.org> wrote:My 2¢: Don't be fancy. map.emplace(key, value) is more concise and a bit easier to read than map.insert(make_pair(key, value)), and map.emplace(KeyType(arg1, arg2), ValueType(arg3, arg4)) is also more concise and much easier to read than map.emplace(std::piecewise_construct, forward_as_tuple(arg1, arg2), forward_as_tuple(arg3, arg4)). If you have a benchmark showing that avoiding the move-construction is important, then you have to decide between making the move constructor more efficient and obfuscating the map code, but without that benchmark, just do the simple thing.Using the move-construction with emplace is equivalent to passing rvalues to insert, right?
map.insert(std::make_pair<std::string, ComplexValue>("hello", ComplexValue(1, 2, 3)));
On Fri, Jan 15, 2016 at 10:55 AM Jeffrey Yasskin <jyas...@chromium.org> wrote:My 2¢: Don't be fancy. map.emplace(key, value) is more concise and a bit easier to read than map.insert(make_pair(key, value)), and map.emplace(KeyType(arg1, arg2), ValueType(arg3, arg4)) is also more concise and much easier to read than map.emplace(std::piecewise_construct, forward_as_tuple(arg1, arg2), forward_as_tuple(arg3, arg4)). If you have a benchmark showing that avoiding the move-construction is important, then you have to decide between making the move constructor more efficient and obfuscating the map code, but without that benchmark, just do the simple thing.Using the move-construction with emplace is equivalent to passing rvalues to insert, right?
On Fri, Jan 15, 2016 at 8:43 AM, <joh...@google.com> wrote:Now that std::unordered_* is being allowed, can we use std::unordered_multimap::emplace?I don't see why not.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAMGbLiFF%2BRB35xN3O5jxYMw_LeSyGEjgSR9oqBbQwK1Xim7qSQ%40mail.gmail.com.