3 ms·

> 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 performa

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

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 ago
  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.
- mgaunard 4y ago
  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.
duped 4y ago
> 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.

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 ago
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.
mgaunard 4y ago
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.

duped 4y ago

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