9 ms·

in CppCon 2016: Chandler Carruth “High Performance Code 201: Hybrid Data Structures"[1] he says: "but the standard deque data type is really quite bad. I would

by 04091948 6y ago

in CppCon 2016: Chandler Carruth “High Performance Code 201: Hybrid Data Structures"[1] he says: "but the standard deque data type is really quite bad. I wouldn't recommend anyone use it for anything. if you look at the implementation constraints, the constraints placed upon its iterators, and its invalidation constraints, it's painted into a very unpleasant corner and it has very few opportunities to be an efficient data structure." [1] https://www.youtube.com/watch?v=vElZc6zSIXM https://www.youtube.com/watch?v=vElZc6zSIXM

pansa2 6y ago
For a language whose purpose is high-performance, the std:: containers are an embarrassment. `deque` is slow, `map` is slow - so the language added `unordered_map` which is also slow... Are any of the containers (other than `vector`) worth using in high-performance code? I’m sympathetic to the game developers who I’ve heard say “we use C++, but nothing from std::”.
- Leherenn 6y ago
  Array is great as far as I know.
  - kllrnohj 6y ago
    std::array is great except it's annoying to statically initialize. Really wish make_array or to_array were non-experimental a lot sooner (to_array finally did land in C++20 at least). But yeah it does mean you can finally stop doing that silly `sizeof(a)/sizeof(a[0]);` trick.
- 59nadir 6y ago
  STL is mostly garbage, which is a big reason it's not used in places that actually need performance, both for build times and runtime. Yes, it's embarrassing. I think it should be noted that the performance mantra is mostly for show with C++, though. The same people who spout it will also blatantly use pessimizing language features just because, when normal, procedural code would've done the job faster and ultimately simpler. I think the performance overhead of a few things in C++ make sense, but in general you get performance in C++ by turning things off and abstaining from most of the features. Exceptions complicate mostly everything, so the best thing to do is to turn them off and not rely on anything that uses them, for example. Modern C++ isn't fast and most of C++ wasn't even before the modern variant was invented. The C "subset" is.
  - pjmlp 6y ago
    About 1% of developers actually need to deliver µs fast code. The remaining 99% are happy to be able to deliver fast enough portable code without having to reinvent data structures all the time.
  - adev_ 6y ago
    > STL is mostly garbage, which is a big reason it's not used in places that actually need performance, both for build times and runtime. It is NOT garbage. It is more than sufficient for the 99% of devs that need key in hand data structure and good enough performance (Meaning faster than 99% of over programming languages already). If what you need is sub micro-second perf, then yes, redefined your data-structure. BTW, you will very likely have to do that in any language anyway. Because it is impossible to design fast forever-living data structure. They (almost) all become obsolete when architectures evolve. Red-Black Trees where state of art DS, teached-at-school 10 years ago, they are useless garbage nowadays if you seek for performance.
    - kouteiheika 6y ago
      > It is more than sufficient for the 99% of devs that need key in hand data structure and good enough performance (Meaning faster than 99% of over programming languages already). I really don't get this argument. If you don't need pedal-to-the-metal performance then why are you using C++ in the first place? (Unless, of course, your answer is "legacy code".) C++ is being touted as being high performance, but basically every standard data structure besides `std::vector` is garbage for high performance, pedal-to-the-metal code. And not only data structures - `std::regex`'s performance is bad, `std::unique_ptr` doesn't optimize as well as a plain pointers, no vendor has a best-in-class `std::hash` implementation (they're neither DoS-safe nor the fastest), etc. > BTW, you will very likely have to do that in any language anyway. Because it is impossible to design fast forever-living data structure. They (almost) all become obsolete when architectures evolve. Do you, though? Rust already replaced their standard hash map implementation with a completely different one which was faster, so it shows that it can be done.
      - 6y ago
tom_mellior 6y ago
Thanks for the reference. But this is still specific to access patterns: You can use a deque as a queue without iterating, so iterators and their invalidation constraints should not matter.

pansa2 6y ago

For a language whose purpose is high-performance, the std:: containers are an embarrassment. `deque` is slow, `map` is slow - so the language added `unordered_map` which is also slow... Are any of the containers (other than `vector`) worth using in high-performance code? I’m sympathetic to the game developers who I’ve heard say “we use C++, but nothing from std::”.

Leherenn 6y ago
Array is great as far as I know.
- kllrnohj 6y ago
  std::array is great except it's annoying to statically initialize. Really wish make_array or to_array were non-experimental a lot sooner (to_array finally did land in C++20 at least). But yeah it does mean you can finally stop doing that silly `sizeof(a)/sizeof(a[0]);` trick.
59nadir 6y ago
STL is mostly garbage, which is a big reason it's not used in places that actually need performance, both for build times and runtime. Yes, it's embarrassing. I think it should be noted that the performance mantra is mostly for show with C++, though. The same people who spout it will also blatantly use pessimizing language features just because, when normal, procedural code would've done the job faster and ultimately simpler. I think the performance overhead of a few things in C++ make sense, but in general you get performance in C++ by turning things off and abstaining from most of the features. Exceptions complicate mostly everything, so the best thing to do is to turn them off and not rely on anything that uses them, for example. Modern C++ isn't fast and most of C++ wasn't even before the modern variant was invented. The C "subset" is.
- pjmlp 6y ago
  About 1% of developers actually need to deliver µs fast code. The remaining 99% are happy to be able to deliver fast enough portable code without having to reinvent data structures all the time.
- adev_ 6y ago
  > STL is mostly garbage, which is a big reason it's not used in places that actually need performance, both for build times and runtime. It is NOT garbage. It is more than sufficient for the 99% of devs that need key in hand data structure and good enough performance (Meaning faster than 99% of over programming languages already). If what you need is sub micro-second perf, then yes, redefined your data-structure. BTW, you will very likely have to do that in any language anyway. Because it is impossible to design fast forever-living data structure. They (almost) all become obsolete when architectures evolve. Red-Black Trees where state of art DS, teached-at-school 10 years ago, they are useless garbage nowadays if you seek for performance.
  - kouteiheika 6y ago
    > It is more than sufficient for the 99% of devs that need key in hand data structure and good enough performance (Meaning faster than 99% of over programming languages already). I really don't get this argument. If you don't need pedal-to-the-metal performance then why are you using C++ in the first place? (Unless, of course, your answer is "legacy code".) C++ is being touted as being high performance, but basically every standard data structure besides `std::vector` is garbage for high performance, pedal-to-the-metal code. And not only data structures - `std::regex`'s performance is bad, `std::unique_ptr` doesn't optimize as well as a plain pointers, no vendor has a best-in-class `std::hash` implementation (they're neither DoS-safe nor the fastest), etc. > BTW, you will very likely have to do that in any language anyway. Because it is impossible to design fast forever-living data structure. They (almost) all become obsolete when architectures evolve. Do you, though? Rust already replaced their standard hash map implementation with a completely different one which was faster, so it shows that it can be done.
    - 6y ago

tom_mellior 6y ago

Thanks for the reference. But this is still specific to access patterns: You can use a deque as a queue without iterating, so iterators and their invalidation constraints should not matter.