News for hackers. Stuff that matters.
Re:Advancing the state of the art for std:unordered_map impl... by OskarS on Sunday June 19, 2022 @04:40PM (#31803268)
The 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.
Re:Advancing the state of the art for std:unordered_map impl... by BeetleB on Sunday June 19, 2022 @06:33PM (#31804172)
> The fact that the STL api leaks these kind of implementation details is such a shame.

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.

Re:Advancing the state of the art for std:unordered_map impl... by tialaramex on Sunday June 19, 2022 @07:10PM (#31804408)
> There were good reasons for it to do so. C++ is often used for performance reasons

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.

Re:Advancing the state of the art for std:unordered_map impl... by archi42 on Monday June 20, 2022 @05:58AM (#31808350)
> in practice you can probably drop in their notionally incompatible hash map and it'll just work.

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.

Re:Advancing the state of the art for std:unordered_map impl... by witcher_rat on Monday June 20, 2022 @07:14PM (#31817462)
> being able to create pointer to objects inside the map (I never did that, but do other people really do that?)

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.

Re:Advancing the state of the art for std:unordered_map impl... by OskarS on Monday June 20, 2022 @06:26AM (#31808560)
I can totally see the line of reasoning that ended up with this decision. It was the wrong decision, but I absolutely can see how smart and competent people could've arrived there, or missed the reasons why (for instance) promising pointer stability was a bad idea. I've seen that Facebook/Meta talk as well, but they didn't have that data in 2003. Hindsight is 20/20.
Re:Advancing the state of the art for std:unordered_map impl... by mgaunard on Tuesday June 21, 2022 @03:54PM (#31828380)
open addressing of course gives completely different guarantees about pointer and iterator invalidation on insertion, and even removal.

Those guarantees are important for people who write non-trivial code.

Re:Advancing the state of the art for std:unordered_map impl... by duped on Monday June 20, 2022 @11:38AM (#31811602)
> 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.

The API guaranteed mediocre performance and prevented good performance.

Re:Advancing the state of the art for std:unordered_map impl... by nly on Monday June 20, 2022 @03:19AM (#31807237)
On the bright side, constraints breed innovation. Joaquín wouldn't be bringing this great content to us, and furthering the state if the art for node based hash maps, if the standard library wasn't constrained.

Squeezing more efficiency out of something already used in millions of programs is very noble

Re:Advancing the state of the art for std:unordered_map impl... by witcher_rat on Monday June 20, 2022 @07:28PM (#31817620)
> Has to be one of the biggest library design blunders in the history of the industry

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.

Re:Advancing the state of the art for std:unordered_map impl... by forrestthewoods on Sunday June 19, 2022 @04:44PM (#31803311)
C++ 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.
Re:Advancing the state of the art for std:unordered_map impl... by MauranKilom on Sunday June 19, 2022 @04:57PM (#31803429)
Sorry, 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/

Re:Advancing the state of the art for std:unordered_map impl... by forrestthewoods on Sunday June 19, 2022 @05:25PM (#31803668)
STL 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.

Re:Advancing the state of the art for std:unordered_map impl... by jltsiren on Sunday June 19, 2022 @09:27PM (#31805296)
STL is simultaneously overspecified and underspecified. In some situations, like std::unordered_map, the specification mandates an implementation that is suboptimal for many applications. In other situations, the specification is so vague that those parts of the library are often useless.

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.

Re:Advancing the state of the art for std:unordered_map impl... by forrestthewoods on Sunday June 19, 2022 @10:00PM (#31805514)
> A cross-platform implementation is rarely good enough, because performance often depends on platform-specific parameters and instructions.

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.

Re:Advancing the state of the art for std:unordered_map impl... by jltsiren on Monday June 20, 2022 @12:00AM (#31806142)
I also have something like 15 years of serious C++ experience, but I've used it more for data processing than software engineering. While std::vector has almost always been good enough for me, I've often had to replace std::unordered_map with something smaller or faster, or with something where I have more control over memory layout or serialization.

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.

Re:Advancing the state of the art for std:unordered_map impl... by kwillets on Tuesday June 21, 2022 @01:10PM (#31826452)
random was what came to my mind after your first sentence. It could really use a deterministic test harness for the different layers.
Re:Advancing the state of the art for std:unordered_map impl... by tialaramex on Sunday June 19, 2022 @07:28PM (#31804552)
There's no reason the standard template library (basically Generic container types and their support) should require compiler support in C++. However C++ programmers tend (incorrectly) to use the abbreviation STL to mean the entire standard library for their language. So this can result in talking at cross purposes.

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.

Re:Advancing the state of the art for std:unordered_map impl... by MauranKilom on Monday June 20, 2022 @02:49AM (#31807072)
> However C++ programmers tend (incorrectly) to use the abbreviation STL to mean the entire standard library for their language.

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.)

Re:Advancing the state of the art for std:unordered_map impl... by tialaramex on Monday June 20, 2022 @05:53PM (#31816569)
Microsoft in abysmal naming shock: Surprise as company notorious for giving products useless or misleading names gives its variant of the C++ standard library a bad name.

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 ?

Re:Advancing the state of the art for std:unordered_map impl... by pmcjones on Sunday June 19, 2022 @08:27PM (#31804927)
For the record, Alexander Stepanov's original focus for the Standard Template Library was generic _algorithms_. Of course, he provided generic data structures ("containers") too. See http://stepanovpapers.com .