5 ms·

Source? A hash map should in principle be faster than a tree, with far fewer comparisons, and against a computed hash value instead of the whole object, in prin

Source? A hash map should in principle be faster than a tree, with far fewer comparisons, and against a computed hash value instead of the whole object, in principle.

einpoklum 5y ago
Well, std::unordered_map is faster than than std::map, but it is still slow, since it uses lists for its buckets, with lots of dynamic allocation. See also: https://stackoverflow.com/a/42588384/1593077 https://stackoverflow.com/a/42588384/1593077 and the link there. Not sure that's what GP meant though.
- agent327 5y ago
  I don't believe it has to, some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type. And I don't like it when people use ridiculous hyperbole to describe what is in reality barely perceptible overhead, so it would be good if the person I originally responded to came out and defended his POV. Hopefully using actual numbers instead of agitated handwaving and screaming...
  - beached_whale 5y ago
    Abseil has a btree based hash map and it performs much better. I think it maintains the same constrains(iterator invalidation/exception safety...) as std::unordered_map. The issue is that the implementors won't change their implementation of unordered_map as it's an ABI break, to say it simply. It could be better. But also, there are other tools like flat maps/open addressing that are not done in the std library.
  - MauranKilom 5y ago
    > some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type Pretty sure that makes it impossible to implement merge without pointer/iterator invalidation, which is a constraint imposed by the standard (https://en.cppreference.com/w/cpp/container/unordered_map/merge https://en.cppreference.com/w/cpp/container/unordered_map/me...). > it would be good if the person I originally responded to came out and defended his POV See https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... if you want numbers, or for example this talk by the same author https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ.

Source? A hash map should in principle be faster than a tree, with far fewer comparisons, and against a computed hash value instead of the whole object, in principle.

einpoklum 5y ago

Well, std::unordered_map is faster than than std::map, but it is still slow, since it uses lists for its buckets, with lots of dynamic allocation. See also: https://stackoverflow.com/a/42588384/1593077 https://stackoverflow.com/a/42588384/1593077 and the link there. Not sure that's what GP meant though.

agent327 5y ago
I don't believe it has to, some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type. And I don't like it when people use ridiculous hyperbole to describe what is in reality barely perceptible overhead, so it would be good if the person I originally responded to came out and defended his POV. Hopefully using actual numbers instead of agitated handwaving and screaming...
- beached_whale 5y ago
  Abseil has a btree based hash map and it performs much better. I think it maintains the same constrains(iterator invalidation/exception safety...) as std::unordered_map. The issue is that the implementors won't change their implementation of unordered_map as it's an ABI break, to say it simply. It could be better. But also, there are other tools like flat maps/open addressing that are not done in the std library.
- MauranKilom 5y ago
  > some kind of bucket-optimisation (multiple elements per allocation, instead of one element per allocation) should also meet all constraints the standard sets for this type Pretty sure that makes it impossible to implement merge without pointer/iterator invalidation, which is a constraint imposed by the standard (https://en.cppreference.com/w/cpp/container/unordered_map/merge https://en.cppreference.com/w/cpp/container/unordered_map/me...). > it would be good if the person I originally responded to came out and defended his POV See https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/ https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... if you want numbers, or for example this talk by the same author https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ.