4 ms·

I can't think of a single thing in the C or C++ standard library that is state of the art. Often they are actually quite terrible. Some of them just can't be

I can't think of a single thing in the C or C++ standard library that is state of the art. Often they are actually quite terrible. Some of them just can't be fixed because of ABI compatibility issues. That's why, just as an example, C++'s std::unordered_map is an embarrassment compared to all recent hash tables.

voldacar 7y ago
That's so true and honestly it kind of gives me a pit in my stomach just thinking about all the C++ programs in particular that use STL and end up being so much slower than they could be. Hopefully Rust and Zig won't end up making this kind of mistake
- KMnO4 7y ago
  I think Rust has an intrinsic advantage simply in its power. Standard libraries (and really most code) are written by humans. Giving those humans the confidence to implement complex data structures and algorithms without worrying about null pointers or memory leaks has ripping effects on performance. See C’s (“simple”) AVL tree vs Rust’s B-Tree[0]. [0]: http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...
- pjscott 7y ago
  The most egregious offenders here IMO are C++'s map and unordered_map. The spec constrains the possible implementations, and it's hard to implement them as anything better than a red-black tree or a badly-unoptimized hash table, respectively. And really the unordered one should be the default with the nice short name. It looks like Rust is doing well on this. HashMap (the one everybody uses) is essentially a clone of Google's heavily-optimized C++ hash table: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables ... and if you need the collection to be sorted, their BTreeMap has much lower overhead than the C++ std::map, plus a big prominent note in its documentation saying that HashMap is usually the one you want. I'm impressed. (Haven't looked at Zig yet.)
  - RossBencina 7y ago
    > anything better than a red-black tree Is there an equivalent data structure that has better worst-case time complexity than red-black tree?
    - Dylan16807 7y ago
      There are plenty of algorithms that are also O(logn) that are much faster in practice, because of how caches work.
      - RossBencina 7y ago
        Could you name some please? I'm genuinely interested in learning of data structures with this property.
        Dylan16807 7y ago
        The simplest one is a B tree. It's like a self-balancing binary tree, except that you put more than two children in each node. Same big-O, but faster by a big linear multiplier.
      - vardump 7y ago
        If the data is small enough (up to about n=100 magnitude), linear scan O(n) often beats asymptotically faster algorithms.
  - scottlamb 7y ago
    > It looks like Rust is doing well on this. HashMap (the one everybody uses) is essentially a clone of Google's heavily-optimized C++ hash table It didn't start out this way, but their spec was not so constrained as C++, so they were able to switch to this implementation in a backward-compatible way. In particular, Rust's std::collections::HashMap doesn't guarantee that keys and values have stable addresses across mutations of unrelated entries, so they can use open addressing rather than chaining. (And they did use open addressing from the beginning; the SwissTables-like "hashbrown" implementation was just a refinement of that.) I think a lot of this is just that newer languages can learn from the mistakes of previous languages. It will be interesting to see how Rust (and other newer languages) are able to evolve when their standard library is 20+ years old and some parts don't age so well. (Although actually C++'s std::unordered_map only goes back to C++11 and still sucks...) One part of Rust's answer I think is to keep the standard library small. Less there, less to screw up. Make it easy to pull in crates instead. Crates can supply the same functionality but can bump their major version relatively easily if the interface has to change. There are advantages and disadvantages to this approach...
grandinj 7y ago
Terrible is hyperbole. They're not state of the art, but they are pretty decent. If you are using multi-G data structures, or chasing that last 2% of performance, then sure, they will make a difference. But in most large applications, switching to things like that don't make much difference compared to just writing a slightly better algorithm, or compacting your data-structures a little to improve cache-hit, or re-organising your code a little to do the expensive stuff outside the loop. Source: I regularly optimise C++ code in LibreOffice.

voldacar 7y ago

That's so true and honestly it kind of gives me a pit in my stomach just thinking about all the C++ programs in particular that use STL and end up being so much slower than they could be. Hopefully Rust and Zig won't end up making this kind of mistake

KMnO4 7y ago
I think Rust has an intrinsic advantage simply in its power. Standard libraries (and really most code) are written by humans. Giving those humans the confidence to implement complex data structures and algorithms without worrying about null pointers or memory leaks has ripping effects on performance. See C’s (“simple”) AVL tree vs Rust’s B-Tree[0]. [0]: http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performance-of-c-and-rust/ http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...
pjscott 7y ago
The most egregious offenders here IMO are C++'s map and unordered_map. The spec constrains the possible implementations, and it's hard to implement them as anything better than a red-black tree or a badly-unoptimized hash table, respectively. And really the unordered one should be the default with the nice short name. It looks like Rust is doing well on this. HashMap (the one everybody uses) is essentially a clone of Google's heavily-optimized C++ hash table: https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables ... and if you need the collection to be sorted, their BTreeMap has much lower overhead than the C++ std::map, plus a big prominent note in its documentation saying that HashMap is usually the one you want. I'm impressed. (Haven't looked at Zig yet.)
- RossBencina 7y ago
  > anything better than a red-black tree Is there an equivalent data structure that has better worst-case time complexity than red-black tree?
  - Dylan16807 7y ago
    There are plenty of algorithms that are also O(logn) that are much faster in practice, because of how caches work.
    - RossBencina 7y ago
      Could you name some please? I'm genuinely interested in learning of data structures with this property.
      - Dylan16807 7y ago
        The simplest one is a B tree. It's like a self-balancing binary tree, except that you put more than two children in each node. Same big-O, but faster by a big linear multiplier.
    - vardump 7y ago
      If the data is small enough (up to about n=100 magnitude), linear scan O(n) often beats asymptotically faster algorithms.
- scottlamb 7y ago
  > It looks like Rust is doing well on this. HashMap (the one everybody uses) is essentially a clone of Google's heavily-optimized C++ hash table It didn't start out this way, but their spec was not so constrained as C++, so they were able to switch to this implementation in a backward-compatible way. In particular, Rust's std::collections::HashMap doesn't guarantee that keys and values have stable addresses across mutations of unrelated entries, so they can use open addressing rather than chaining. (And they did use open addressing from the beginning; the SwissTables-like "hashbrown" implementation was just a refinement of that.) I think a lot of this is just that newer languages can learn from the mistakes of previous languages. It will be interesting to see how Rust (and other newer languages) are able to evolve when their standard library is 20+ years old and some parts don't age so well. (Although actually C++'s std::unordered_map only goes back to C++11 and still sucks...) One part of Rust's answer I think is to keep the standard library small. Less there, less to screw up. Make it easy to pull in crates instead. Crates can supply the same functionality but can bump their major version relatively easily if the interface has to change. There are advantages and disadvantages to this approach...

grandinj 7y ago

Terrible is hyperbole. They're not state of the art, but they are pretty decent. If you are using multi-G data structures, or chasing that last 2% of performance, then sure, they will make a difference. But in most large applications, switching to things like that don't make much difference compared to just writing a slightly better algorithm, or compacting your data-structures a little to improve cache-hit, or re-organising your code a little to do the expensive stuff outside the loop. Source: I regularly optimise C++ code in LibreOffice.