Getting generic data structures that are more efficient than his specialized C data structures is exactly what happened to Bryan Cantrill when he ported a caref

Getting generic data structures that are more efficient than his specialized C data structures is exactly what happened to Bryan Cantrill when he ported a carefully optimized C program to naive Rust. > Yes, you read that correctly: my naive Rust was ~32% faster than my carefully implemented C.[0] > As a result, this code spends all of its time constantly updating an efficient data structure to be able to make this decision. For the C version, this is a binary search tree (an AVL tree), but Rust (interestingly) doesn’t offer a binary search tree — and it is instead implemented with a BTreeSet, which implements a B-tree. B-trees are common when dealing with on-disk state, where the cost of loading a node contained in a disk block is much, much less than the cost of searching that node for a desired datum, but they are less common as a replacement for an in-memory BST[1] > So, where does all of this leave us? Certainly, Rust’s foundational data structures perform very well. Indeed, it might be tempting to conclude that, because a significant fraction of the delta here is the difference in data structures (i.e., BST vs. B-tree), the difference in language (i.e., C vs. Rust) doesn’t matter at all.[1] > Implementing a B-tree this way, however, would be a mess. The value of a B-tree is in the contiguity of nodes — that is, it is the allocation that is a core part of the win of the data structure. I’m sure it isn’t impossible to implement an intrusive B-tree in C, but it would require so much more caller cooperation (and therefore a more complicated and more error-prone interface) that I do imagine that it would have you questioning life choices quite a bit along the way. (After all, a B-tree is a win — but it’s a constant-time win.)[1] > All of this adds up to the existential win of Rust: powerful abstractions without sacrificing performance.[1] [0]: http://dtrace.org/blogs/bmc/2018/09/18/falling-in-love-with-rust/ http://dtrace.org/blogs/bmc/2018/09/18/falling-in-love-with-... [1]: 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...