4 ms·
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 woul
by stochastic_monk 8y ago
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.
- ummonk 8y agoYes, especially when b trees tend to be easier to implement too.
- marcosdumay 8y agoRust 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.
- stochastic_monk 8y agoThen Heng Li’s kbtree.h from klib is your generic, fast implementation. I’d love to see this repeated using it for a fair comparison. For example, the benchmark shootout recommends his khash for a hash table.
- marcosdumay 8y agoThe 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.
- stochastic_monk 8y agoThat’s fair. klib (I assume) was not easy to develop, but it easy to use.
- marcosdumay 8y agoIt's easy to use. What is not easy is to take a large code-base that doesn't use it and change it so it now uses.
- kbsletten 8y agoI 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.
- bjourne 8y agoThe 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
- stochastic_monk 8y agoThere 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.