8 ms·
Advancing the state of the art for std:unordered_map implementations
- syspec 4y agoReally interesting post, love reading these kind of details into how collection types I take for granted work, and are iterated on
- kccqzy 4y ago> Back in the day, open-addressing approaches were not regarded as sufficiently mature, so closed addressing was taken as the safe implementation of choice. I always chuckle when I read statements like this because it didn't match my own experience as a learner. When I learned computer science, I was taught hash tables right after arrays, but before linked lists or even pointers. So open addressing had always been the default for hash tables for me. I'm curious to hear what other people's learning journeys are like.
- RicoElectrico 4y agoI lack experience to tell - does anybody use chaining in production?
- zeroonetwothree 4y agounordered_map uses chaining
- masklinn 4y agoIIRC php and go use separate chaining (unless php switched while I wasn’t looking).
- ghusbands 4y agoIt is conceptually simpler, especially once deletion is involved, and is the more common implementation.
- adgjlsfhk1 4y agoI think it was a while ago, but at this point, the cost of pointer chasing and memory overhead of separate chaining mean that is is being phased out.
- dlp211 4y agoI thought Java's Hashmap used chaining.
- utopcell 4y agoWhy would any, when absl::flat_hash_map<> and absl::node_hash_map<> is available ?
- colinmhayes 4y agostd uses chaining because deletion isn't allowed to invalidate iterators.
- imron 4y agoI guess what we need now then is std::open_unordered_map ;-)
- jlokier 4y agoThe Linux kernel uses chained hash tables in many places. https://github.com/torvalds/linux/blob/master/include/linux/hashtable.h https://github.com/torvalds/linux/blob/master/include/linux/...
- gjulianm 4y agoIt's a tradeoff. Open addressing is faster due to cache locality, but needs a good hash function. If the hash function tends to cluster values and generate collisions you might (key word here "might", as usual you need to do profiling to check each case) end up with way more operations per query. But for 90% of cases, you don't really care that much about performance and whether it's open or closed addressing, as long as the mapping works.
- OskarS 4y agoThe fact that the STL api leaks these kind of implementation details is such a shame. Multiplied globally over all users of unordered_map, the amount of CPU time that has been wasted because of that decision boggles the mind. Has to be one of the biggest library design blunders in the history of the industry (up there with C strings being null-terminated). They should just add a new map to the standard with a better API.
- forrestthewoods 4y agoC++ STL design is broken. The language shouldn’t define an API for std, it should provide an implementation. AFAIK no other major language defines the std library the way C++ does. It’s so bad and problematic.
- MauranKilom 4y agoSorry, can you elaborate? Some things in the STL require compiler support, so you can't really "provide" an implementation in the narrow sense. Also, how does providing a concrete/reference implementation prevent the API problems? Hyrum's law [0] means that you would make the situation worse because now people will depend on every detail you can think of. And if you want to improve the implementation in a new version, you now are (most likely) breaking ABI on every platform at once, instead of giving different platforms the ability to find compromises as needed. Just look at the recent "no ABI break in C++23" discussions to see how contentious that topic is. [0]: https://www.hyrumslaw.com/ https://www.hyrumslaw.com/
- forrestthewoods 4y agoSTL should “just” be a library written against the language spec. The fact that there are so many different, unrelated implementations is crazy. The STL spec is so over designed that they strongly imply, if not mandate, a particular implementation. But they don’t actually provide an implementation so every platform has to implement one. However those implementations select different trade-offs which means different behaviors so actually developers wind up writing their own version that is consistent. It’s basically the worst outcome.
- olliej 4y agoI am always sad that the default STL collections leak so much implementation detail that they are stuck on such abysmally performing algorithms. That every serious project ends up with its own hashmap, etc is such a shame.
- usefulcat 4y agoIME, if you want a fast hash map, the very first thing you should do is ignore anything that uses closed addressing. If you really d I need one of the extra guarantees provided by std::unordered_map, see if you can’t get it by using a container of unique_ptr<T> or shared_ptr<T> instead of unordered_map<T>.
- 0x23 4y agoThere also has been a lot research lately in the field. For example, [1,2] has a lot of new methods on concurrent or space efficient hash tables. [1] http://algo2.iti.kit.edu/maier.php http://algo2.iti.kit.edu/maier.php [2] https://github.com/TooBiased/growt https://github.com/TooBiased/growt
- londgine 4y agoWhat's the problem with iterator increment being (amortized) constant time for closed addressing? The algorithm could iterate over each bucket and on each bucket iterate over each element. Going from the end of one bucket to the start of the next one may be slower than within the same bucket, but still constant time.
- tomerv 4y agoThere's a link in the article to a paper (N2023) proving this is not constant time. The issue is that as you delete elements, and the hash table becomes sparse, finding the next nonempty bucket is not so fast. However, I believe that the paper conveniently glosses over the fact that there will be rehashing into a smaller table which would fix this issue.
- londgine 4y agothanks. I got confused between constant time relative to the number of elements in the table (as typically calculated) and constant time relative to the number of slots in the table.
- jeffbee 4y agoIt seems like the relevant benchmarks would be vs. absl, folly, etc, not libc++.
- uluyol 4y agoBoth are relevant. This is supposed to be a drop in replacement for std::unordered_map whereas the other implementations break from the std API contract in various ways (either by not supporting certain operations, or not providing the same runtime complexity for certain operations). So you'd expect the performance to fall in between std implementations and the others, with folly/absl/etc essentially serving as an upper bound on the possible gains.
- phkahler 4y agoCan I just settle for O(log n) lookup and forget about the theoretical O(1) and constant struggle to find the "best" hash function and data structure?
- adrianN 4y agoIf you don't care about performance at all you can of course do that. For many real world applications however asymptotic runtimes are not enough, you need to care about constant factors too.
- merijnv 4y agostd::map (as opposed to std::unordered_map) uses a balanced binary search tree approach and thus guarantees O(log n) lookup for anything that has a well-defined total order (i.e. comparison function), without worrying about hash functions, etc. So, yes you can ;)
- Sharlin 4y agoSure, just use a tree-based map such as `std::map`. (Which, as the name implies, was the OG associative container in C++.)
- hoseja 4y agoThe problem with STD requirements is they choose an implementation and then tailor the requirements to it tightly, thus preventing any other set of tradeoffs.
- dataangel 4y agoThat's not actually what drove it here. std::unordered_map has the requirements it does in order to make it a drop in replacement for std::map in cases where you don't care about traversal order. They wanted it to be as easy as possible for people to find/replace in their code.
- tomerv 4y agoNow I'm curious to know what's the state of the art for open addressing implementations in C++.
- ErikCorry 4y agoNot only can't you do standards-conformant closed addressing hash map implementations of std::unordered_map I don't think you can do cuckoo- or robin-hood-hashing either. It's just so restrictive. Unordered maps are also annoying for a completely different reason: You generally want your program to run in a reproducible way and unordered maps will undermine that goal again and again in subtle ways you will discover too late. std::map doesn't scratch that itch because you have to provide an ordering function when 99% of the time insertion ordering would be just fine. I wrote about this at https://blog.toit.io/hash-maps-that-dont-hate-you-1a96150b492a https://blog.toit.io/hash-maps-that-dont-hate-you-1a96150b49...
- dxuh 4y agoFeatures and containers have been deprecated before. Could it be an option to deprecate only the complexity requirements on some of the operations on std::unordered_map, so that we don't need a whole new container and standard library implementers get the option to use open addressing?