3 ms·

In spite of some technically incorrect statements this is a generally very useful observation and not just in C++: it’s easy to pay for traversal properties you

In spite of some technically incorrect statements this is a generally very useful observation and not just in C++: it’s easy to pay for traversal properties you don’t need in an associative data structure. Hash tables and red black trees shine in different applications :) Still pretty low-effort but slightly higher cost and benefit is to switch to more modern data structures that have to break a little backwards compatibility to get big wins. Things like Folly’s F14 and Abseil’s collections (Abseil has both faster hash tables and faster tree-style maps). I think languages like Rust with a little less backwards compatibility burden are shipping with cache-aware and SIMD-exploiting data structures “out of the box” these days, but but my knowledge of e.g. Rust stops short of “read the standard library a bunch of times” so check with someone who has :)

tialaramex 4y ago
Rust promises its language and standard library have full backward compatibility however that promise only refers to the actual documented API behaviour and this is intentionally narrow in places where it matters for performance. Thus for example, the HashMap in Rust 1.0 is different from the HashMap shipped in any recent Rust, but they both implement the API described in the documentation, the new one is just much faster because it's actually HashBrown, a re-implementation in Rust of Google's Swiss Tables C++ hash map. Hyrum's Law means that to some extent even though the defined API is narrow, people will write Rust code, by mistake or on purpose which depends on internals that were never guaranteed. For example, sort_unstable_by() is, as its name says, an unstable sort, you should not assume that it leaves ['a', 'A', 'B', 'b'] in the same order when you provide a case-insensitive comparison operator - you should have used sort_by() if you could not accept instability in your sort results. Rust gets to measure the impact of Hyrum's Law and re-consider potential changes which have large real impact because it does Crater Runs, which compile and test large volumes of Rust software from the crates.io package site and GitHub, with to-be-released Rust versions. If you made a change that you thought was basically a typographical fix, and it's technically not a breaking change by Rust's rules but it blew up 15000 widely used crates, you need to think harder about whether that's OK and most likely revert your change. C++ has no analogue of the Crater Run as of yet, and it offers a lot of needlessly broad APIs which lock it into choices that are terrible because it promised something that in hindsight nobody cares about, but now you daren't change that. The ABI promises in real world C++ implementations make this even worse. Rust's Mutex<Option<CompactString>> [[CompactString is a 3rd party library type]] is significantly smaller than a std::mutex on most popular C++ platforms, and yet std::mutex is literally just a mutex, whereas Mutex<Option<CompactString>> is a mutex protecting an optional Small String Optimized string containing up to 24 bytes of UTF-8 encoded string all in line in your smaller data type.
- humanrebar 4y ago
  > C++ has no analogue of the Crater Run as of yet... It does in the form of large organizations with large codebases that try out candidate releases and file bug reports. It's not managed by a central "C++ team" as such if that's what you mean, but there are N independent C++ implementations. At some point we're comparing organizational structure and not technology outcomes.
  - tialaramex 4y ago
    It's like Continuous Integration versus previous practices of "Jim has a working checkout, and I think he built the release version last time, ask Jim to make you a fresh release CD, remind him to switch off the debug symbols though. Oh also I think we're over 650MB now, so he might need to change settings in the CD burner app". It's not that the previous practices didn't work, more or less, it's that they were manual and so you couldn't really rely on them. CI is categorically better, despite being in some sense just an automation of what should be existing practice.
    - humanrebar 4y ago
      Except in this case we're literally talking about established CI processes. They're just not triggered by the "C++ contributor" because those don't exist as such. We have GCC contributors, Clang contributors, etc. Periodically a batch of those contributions get marked for testing and they get pushed through various CI processes and bug reports or even PRs get generated. The C++ compiler vendors I am aware of also have access to nontrivial C++ codebases that give them access to these sorts of "see what broke" speculative build jobs: Red Hat has RHEL and CentOS repositories, Microsoft has the presumably massive Microsoft codebases, everyone has access to vcpkg, and so on. I'll also note that this is just normal for sufficiently popular systems languages. If Rust as successful as it seems like it will be, there will some day be far more code outside of public crates than inside them. Anyway, there are some differences for sure, but it's not night and day they way you describe it.
- humanrebar 4y ago
  > The ABI promises in real world C++ implementations make this even worse. There are legitimate use cases that require good performance and some ABI stability guarantees. Like various kinds of closed-source client libraries. Rust doesn't have to serve those use cases, of course. But "stable ABI is bad" is a very broad statement. The real problem here is the lack of packaging solutions for systems programming, which are frequently multi-language in some way. And in the case of closed-source use cases, that would look like binary packages. If we had quality dependency management, we would have different options for different use cases and standard libraries could focus on 90% use cases instead of 99.99% ones. Being all things to all users isn't a winning strategy.
julien-j 4y ago
Can you expand on the technically incorrect statements part? If I can fix the post I would love to do it :)

tialaramex 4y ago

Rust promises its language and standard library have full backward compatibility however that promise only refers to the actual documented API behaviour and this is intentionally narrow in places where it matters for performance. Thus for example, the HashMap in Rust 1.0 is different from the HashMap shipped in any recent Rust, but they both implement the API described in the documentation, the new one is just much faster because it's actually HashBrown, a re-implementation in Rust of Google's Swiss Tables C++ hash map. Hyrum's Law means that to some extent even though the defined API is narrow, people will write Rust code, by mistake or on purpose which depends on internals that were never guaranteed. For example, sort_unstable_by() is, as its name says, an unstable sort, you should not assume that it leaves ['a', 'A', 'B', 'b'] in the same order when you provide a case-insensitive comparison operator - you should have used sort_by() if you could not accept instability in your sort results. Rust gets to measure the impact of Hyrum's Law and re-consider potential changes which have large real impact because it does Crater Runs, which compile and test large volumes of Rust software from the crates.io package site and GitHub, with to-be-released Rust versions. If you made a change that you thought was basically a typographical fix, and it's technically not a breaking change by Rust's rules but it blew up 15000 widely used crates, you need to think harder about whether that's OK and most likely revert your change. C++ has no analogue of the Crater Run as of yet, and it offers a lot of needlessly broad APIs which lock it into choices that are terrible because it promised something that in hindsight nobody cares about, but now you daren't change that. The ABI promises in real world C++ implementations make this even worse. Rust's Mutex<Option<CompactString>> [[CompactString is a 3rd party library type]] is significantly smaller than a std::mutex on most popular C++ platforms, and yet std::mutex is literally just a mutex, whereas Mutex<Option<CompactString>> is a mutex protecting an optional Small String Optimized string containing up to 24 bytes of UTF-8 encoded string all in line in your smaller data type.

humanrebar 4y ago
> C++ has no analogue of the Crater Run as of yet... It does in the form of large organizations with large codebases that try out candidate releases and file bug reports. It's not managed by a central "C++ team" as such if that's what you mean, but there are N independent C++ implementations. At some point we're comparing organizational structure and not technology outcomes.
- tialaramex 4y ago
  It's like Continuous Integration versus previous practices of "Jim has a working checkout, and I think he built the release version last time, ask Jim to make you a fresh release CD, remind him to switch off the debug symbols though. Oh also I think we're over 650MB now, so he might need to change settings in the CD burner app". It's not that the previous practices didn't work, more or less, it's that they were manual and so you couldn't really rely on them. CI is categorically better, despite being in some sense just an automation of what should be existing practice.
  - humanrebar 4y ago
    Except in this case we're literally talking about established CI processes. They're just not triggered by the "C++ contributor" because those don't exist as such. We have GCC contributors, Clang contributors, etc. Periodically a batch of those contributions get marked for testing and they get pushed through various CI processes and bug reports or even PRs get generated. The C++ compiler vendors I am aware of also have access to nontrivial C++ codebases that give them access to these sorts of "see what broke" speculative build jobs: Red Hat has RHEL and CentOS repositories, Microsoft has the presumably massive Microsoft codebases, everyone has access to vcpkg, and so on. I'll also note that this is just normal for sufficiently popular systems languages. If Rust as successful as it seems like it will be, there will some day be far more code outside of public crates than inside them. Anyway, there are some differences for sure, but it's not night and day they way you describe it.
humanrebar 4y ago
> The ABI promises in real world C++ implementations make this even worse. There are legitimate use cases that require good performance and some ABI stability guarantees. Like various kinds of closed-source client libraries. Rust doesn't have to serve those use cases, of course. But "stable ABI is bad" is a very broad statement. The real problem here is the lack of packaging solutions for systems programming, which are frequently multi-language in some way. And in the case of closed-source use cases, that would look like binary packages. If we had quality dependency management, we would have different options for different use cases and standard libraries could focus on 90% use cases instead of 99.99% ones. Being all things to all users isn't a winning strategy.

julien-j 4y ago

Can you expand on the technically incorrect statements part? If I can fix the post I would love to do it :)