How is Rust encouraging a different data structure besides providing a btree set and not an avl tree set?
The C stdlib does not come with an AVL tree. Why would one not implement a b-tree in C for this comparison? It’s not as if K&R has “Use binary, not b-trees!” on the front cover.
I think he mentioned this briefly in the article. In C it's common to use intrusive data structures like linked lists and AVL trees because that's how the language works, you can embed data structures easily. This wouldn't work with a B tree because it's allocation pattern is very specific. Rust on the other hand is very pro-generics where you can write a B-tree and painlessly have it store whatever anybody wants it to. It's more about what the language makes easy and idiomatic than anything.
The comment is wrong for C, but could be right for C++. The data structures in STL are all implemented as red-black trees. They can't be rewritten as B-trees because of some iterator/synchronization/backwards compatibility mess.
I once did a similar benchmark to the one in the article and found that Rust outperformed C++ because the C++ code was using the builtin std::map. But for reeeeeeally big datasets PostgreSQL beats them both so who cares. :p
There are STL-compatible B-tree implementations in C++, so I would still use one of those instead of std::map. Besides, std::*map implementations are all rather slow.
Rust encourages the creation of more generic code, that makes switching into non-DIY more complex data structures easier. The difference is even larger after the code is written and you are able to profile it.
The point is entirely that it is harder to take a typical C code and change it to use something like this than it is to do the same in Rust. Much harder.
I don't think anybody will find any consistent performance enhancement in Rust that can not be replicated in C. The problem is how to run it out on real code.
The C stdlib does not come with an AVL tree. Why would one not implement a b-tree in C for this comparison? It’s not as if K&R has “Use binary, not b-trees!” on the front cover.