>Eventually I rewrote my btree on top of Vecs. My node & leaf pointers are now array indices. The result? There is no longer any unsafe code. The code has become significantly simpler and it now runs ~10% faster than it did before, which is shocking to me. I guess bounds checks are cheaper than memory fragmentation on modern computers.
Optimizations are very complex and potentially fragile in Rust, LLVM has to sort through tons of generated IR, so it might be just that native Rust structures are optimized better for compilation. Particulary, Rust is able to optimize out some bound checks.
Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly. I mean you could have written similar code in C++ using std::vector or std::dequeue and get the bounds checking too.
>Everyone talks about memory safety but IMO rust’s best features are enums, traits, cargo, match expressions and so on
C++20 with concepts mostly reproduce the traits. C++17 with std::variants emulate enum/tagged union. Match is unmatched by C++, that's true.
Cargo is good for as long as there are few packages in there. Large projects already suffer from five versions of serde in one build and dependencies on FFI-connected libs that cargo itself cannot build. I mean look at the NPM nightmare — and they've mostly dodged FFI-s.
> Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly. I mean you could have written similar code in C++ using std::vector or std::dequeue and get the bounds checking too.
As a sibling comment said, its a b-tree not a binary tree. B-trees are - as far as I know - the fastest data structure on modern computers for the class of problems they solve.
And yes, I think if I ever go back to C/C++ I'll try this approach out. It might also work great in GC languages like JS/TS/C#/Go because there's fewer pointers to keep track of.
> Cargo is good for as long as there are few packages in there. Large projects already suffer from five versions of serde in one build and dependencies on FFI-connected libs that cargo itself cannot build. I mean look at the NPM nightmare — and they've mostly dodged FFI-s.
I haven't run into the "five versions of serde" problem, but I can easily imagine it. I've lived NPM nightmares more times than I can count. But I'd still prefer that to all the problems you get from CMake, autotools and Makefiles. At this rate we're going to get self driving cars before we have a single sane build system for C.
> Particulary, Rust is able to optimize out some bound checks.
It doesn’t optimise out the bounds checks. I checked the assembly.
Bounds checks in rust always look so ugly if you look at the assembly output because there’s all this panic string building and whatnot. But in practice, I think it’s just that modern CPUs have excellent branch prediction. A branch that follows the same path 100% of the time is cheap. Especially when it has UNLIKELY() annotation hints in the code. This is the case for bounds checks. They just don’t really show up in benchmarks as much you’d think.
>Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly. I mean you could have written similar code in C++ using std::vector or std::dequeue and get the bounds checking too.
This is simply not true, it's an ongoing thorn of mine that the Rust community seems to decide that anything which cannot be programmed in rust is obsolete legacy. This is a silly stance which is harming adoption.
I for one have coded dozens or even hundreds of tree structures. My most recent tree was a hierarchical context management system for an LLM agent!
> it's an ongoing thorn of mine that the Rust community seems to decide that anything which cannot be programmed in rust is obsolete legacy.
Nobody is arguing that you can't program a binary tree or b-tree in rust.
I think its true that binary trees almost always perform worse than b-trees in programming in general. But that isn't a comment about rust. Its a comment about modern CPU memory & cache behavior.
> Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly
BTree is not Binary Tree. It's B-Tree and is cache-friendly
> C++20 with concepts mostly reproduce the traits.
C++20 concepts are not the same as traits. Concepts are structural and awkward to use compared to Traits which are nominal. There are other important differences, too.
Optimizations are very complex and potentially fragile in Rust, LLVM has to sort through tons of generated IR, so it might be just that native Rust structures are optimized better for compilation. Particulary, Rust is able to optimize out some bound checks.
Do note that binary trees are mostly an obsolete legacy today — they are way too cache-unfriendly. I mean you could have written similar code in C++ using std::vector or std::dequeue and get the bounds checking too.
>Everyone talks about memory safety but IMO rust’s best features are enums, traits, cargo, match expressions and so on
C++20 with concepts mostly reproduce the traits. C++17 with std::variants emulate enum/tagged union. Match is unmatched by C++, that's true.
Cargo is good for as long as there are few packages in there. Large projects already suffer from five versions of serde in one build and dependencies on FFI-connected libs that cargo itself cannot build. I mean look at the NPM nightmare — and they've mostly dodged FFI-s.