4 ms·

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 tim

by OskarS 4y ago

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.

forrestthewoods 4y ago
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.
- MauranKilom 4y ago
  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/ https://www.hyrumslaw.com/
  - forrestthewoods 4y ago
    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.
    - jltsiren 4y ago
      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.
      - forrestthewoods 4y ago
        > 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.
  - tialaramex 4y ago
    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.
    - pmcjones 4y ago
      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 http://stepanovpapers.com .
    - MauranKilom 4y ago
      > 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 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.)
      - tialaramex 4y ago
        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 ?
BeetleB 4y ago
> 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.
nly 4y ago
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
witcher_rat 4y ago
> 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.

by OskarS 4y ago

forrestthewoods 4y ago

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.

MauranKilom 4y ago
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/ https://www.hyrumslaw.com/
- forrestthewoods 4y ago
  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.
  - jltsiren 4y ago
    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.
    - forrestthewoods 4y ago
      > 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.
- tialaramex 4y ago
  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.
  - pmcjones 4y ago
    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 http://stepanovpapers.com .
  - MauranKilom 4y ago
    > 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 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.)
    - tialaramex 4y ago
      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 ?

BeetleB 4y ago

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

nly 4y ago

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

witcher_rat 4y ago

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