Re:Rust is now overall faster than C in benchmarks
by josephg on Tuesday January 05, 2021 @09:28PM
(#25654076)
Oh interesting! What CPU was that on? 136 the optimal number I found benchmarking on an old intel based laptop I was using a few years ago. I wonder if modern CPUs (with much larger caches) have changed the ideal array size.
When I changed the hardcoded node size from 136 to 1024 bytes, time went down from 3.6 secs to 2.6 secs on my laptop. It kind of plateaued at 1024 bytes. I didn't do more extensive testing.
What's the rationale for the choice of 136? A cache line is usually 64, so the CPU will always end up loading a multiple of that in any case.
When I did a rope implementation myself (I don't know how it compares in terms of performance) I think I ended up with nodes of 4096 or 8192 bytes size. That was based on a Red-black tree. When I load ~1Gig of data, even with a node size of 4096, there will still be 2^18 nodes, meaning each access requires sth. like 17 child traversals, which seems a lot to me. So I can't see myself going down to 200 bytes or less.