4 ms·
> 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 open
by tialaramex 4y ago
> 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.
- archi42 4y ago> 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.
- witcher_rat 4y ago> 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.
- OskarS 4y agoI 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.
- mgaunard 4y agoopen 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.