On 8/7/24 09:41, Kent Borg wrote:
Again, the posting says this requires further investigation with the
early guess that Rust is being nicer to the cache.
Turns out there was a followup post.
https://bcantrill.dtrace.org/2018/09/28/the-relative-performance-of-c-and-rust/
I think it is fair to summarize the performance difference thus:
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
<https://doc.rust-lang.org/std/collections/struct.BTreeSet.html>,
which implements a B-tree <https://en.wikipedia.org/wiki/B-tree>.
And...that was nicer to the cache, to the tune of being ~32% faster.
A day earlier, on 8/6/24 16:31, Kent Borg wrote:
In digging a little these all seem to be due to Rust "std" library
having some very well written data structures
Almost as if I knew what I was talking about. And that the people
building Rust do very good work.
I have to mention another followup post, from two-years later. Read
"Rust after the honeymoon", for the *real* dirt.
https://bcantrill.dtrace.org/2020/10/11/rust-after-the-honeymoon/
(Spoiler: No regrets.)
-kb, the Kent who is lazy and likes having fast data structures for
free, even though he is sure Mark could implement a faster B-tree in C*.
* The BTreeSet had some funny bumps in its performance curve, where it
turns out it is allocating memory. If I understand correctly these could
be avoided by initializing the data structure upfront to needed size,
instead of being dynamic. The catch in their case is they don't know in
advance how big the data will be. The AVL tree didn't have these bumps.
I don't know whether the B-tree could be implemented to avoid them,
while still being as fast. I'll leave that to others. (Maybe C's tree
could /add/ some bumps to get faster.)
_______________________________________________
Discuss mailing list
Discuss@driftwood.blu.org
https://driftwood.blu.org/mailman/listinfo/discuss
