Advancing the state of the art for std:unordered_map implementations
bannalia.blogspot.com
bannalia.blogspot.com
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.
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.
For example, random number distributions are underspecified. The standard only defines the distributions but not the algorithms. If you need deterministic behavior after choosing the rng and the seed – for example for testing, reproducibility, or procedural content generation – you can't use the standard distributions.
C++ is typically used in applications where performance is important. If you want a "good enough" standard library, it must be good enough for most people who care about performance. A cross-platform implementation is rarely good enough, because performance often depends on platform-specific parameters and instructions.
Data structure APIs are particularly difficult if you care about performance. If you use a generic API, you will often end up using the data structure suboptimally. Your mental model is likely wrong, and the API may not pass through information that could help you avoid redundant work. You want an API that matches the actual implementation closely – but not so closely that every implementation change becomes a breaking API change.
I respectfully disagree with this.
We’re talking about std::unordered_map here. I don’t know of any platform that has done implementation work to make std::unordered_map not mediocre.
Let’s be specific. What platforms are we talking about? How many STL implementations are there? Which ones offer a significant improvement for which platforms?
C++ has been my daily driver for 15 years. I’ve shipped quite a lot of code that uses std::vector and std::unordered_map, amongst others! If I really cared about performance I’d pick a hash map implementation that wasn’t mediocre.
I would definitely not consider any std::unordered_map to be highly tuned for any platform. Quite the opposite. It’s over-specified but still stuck with different implementations. IMHO it would be much better if the C++ committee released C++XX libraries that were considered “pretty good” with support for common platforms. New or proprietary platforms can then add the relatively small bits of code necessary to support their platform (think PS5) or release a completely separate library with different constraints.
Part of the problem here is C++ also really, really sucks to compile. Maybe someday modules will make it easy to drop in new libraries and containers. Jury’s still out on that one though.
std::unordered_map is not a particularly good example of things that need platform-specific optimizations. The implementations I have seen are pretty close to standard C++. std::vector implementations, on the other hand, are often really weird and rely extensively on compiler-specific annotations.
Thus while your parent may have meant that types like std::unordered_map shouldn't be magic, it's true that for example you can't implement atomics from the standard library usefully without help from the vendor.
Just like some people have a pet peeve to correct people on this usage, I have a pet peeve to tell those people to look at the name of the MSVC implementation of the C++ standard library.
https://github.com/microsoft/STL
Yes, historically "the STL" was a subset of what became the C++ standard library. But unless you want to tell one of the big three standard library implementations that you know better than them what the name should be, using "STL" for the entire C++ standard library is simply not incorrect.
(Your point that this may be a misunderstanding between the other poster and me stands though.)
We're talking here about the company that has two very well known products "Active Directory" and "Visual Studio" but decided there was no reason it couldn't call unrelated products "Azure Active Directory" and "Visual Studio Code".
Here's how Sony named their video game consoles: PlayStation, PlayStation 2, PlayStation 3, and PlayStation 4. Makes sense. Microsoft decided to make video game consoles too. It named them (I am not kidding for anyone who doesn't play video games, this is real): Xbox, Xbox 360, Xbox One, Xbox Series. Why ?
There were good reasons for it to do so. C++ is often used for performance reasons, and requiring low level access was a means to prevent some implementation being standards compliant yet with horrible performance.
I once had a coworker who had spent some time on the standards committee. He said they would dive into the technical details and tradeoffs to an insane level (utilizing journal papers, theses, and real world benchmarks). He often would quip that the amount of times some coworker came to him with a claim that they have a better implementation than the standard's and were correct, was zero. Sure, if you're a Boost developer, you may have the chops to improve on the standard, but you really need to be at that level.
The other issue, of course, is that when you go into such detail, then yes - the standard is a bit brittle. The solution is for the standard to introduce another unordered_map (with a different name) that allows for open addressing to the standard, and keep the old one for backwards compatibility. Anyone who's spent time with the algorithms library knows that this is a common approach: Adding new functions to improve deficiencies in the previous ones.
Anti-disclaimer: I hate C++. Not a fan.
It is asserted that there were good reasons. I believe Facebook/ Meta openly tells you that in practice you can probably drop in their notionally incompatible hash map and it'll just work. So it seems that either somehow only internal secret source projects needed these details like the bucket API or else it was bullshit and - as seems far more likely - the bucket API was exposed because nobody on the committee had the imagination to see that a better unordered_map might not use buckets at all.
One of the things Rust gets to do here is the "Crater run". Since so much Rust (all popular libraries, much else of note) is on crates.io it's no problem to just "scrape" all that source code and run the toolchain over it to find crashes, compiler performance changes or whatever. This would have been completely unthinkable in C++ as it stood when standardised, and nothing comparable is done today so far as I know, but for Rust it was no big deal.
This puts the Rust maintainers in a much better place to judge the difference between "This is technically incompatible but will not break real uses" and "This is a change that will sow Python 3.x style chaos and discord" if it ever comes to that - rather than just guessing.
The article unintendedly makes kind of a similar point in the "Which hash container to choose" section: Often when using std::unordered_map, we don't rely on every single word of the API. All we care is that there is an insert(), find(), begin(), end() [and the associated iterator], size(), erase() and maybe clear(), with the correct function signatures and O(kay) performance class. Only when we rely on e.g. count() really being O(1) or being able to create pointer to objects inside the map (I never did that, but do other people really do that?), other parts of the API become relevant.
Yes, we do it at my day job in several places, where we take advantage of the pointer stability to improve our overall performance a lot. And a much more impactful performance improvement for our overall product, than micro-optimizations of the unordered_map's insert/erase times would achieve.
Think of, for example, multi-index containers. Or an ordered hash-map (one that is both a hash map and keeps insertion ordering).
In such cases you can keep the actual objects in an unordered_map, and only store pointers to the nodes in other containers (e.g., vectors).
Obviously you can achieve the same thing with open-addressing hashmaps, by making the map's nodes unique_ptrs (i.e., creating the actual objects on the heap externally), which is what such hashmaps tell you to do if you need pointer stability.
But you asked if anyone really used pointer stability, hence my answer.
Those guarantees are important for people who write non-trivial code.
The API guaranteed mediocre performance and prevented good performance.
Squeezing more efficiency out of something already used in millions of programs is very noble
May I introduce you to std::regex?
Although to be fair, that one's not so much a blunder due to the standard, as it is one of poor _implementations_, coupled with an overly restrictive standardization preventing fixing them.
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.
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.
That every serious project ends up with its own hashmap, etc is such a shame.
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-1a96150b49...
So, yes you can ;)
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.