[Discuss] Port Scanning

[kentborg at borg.org (Kent Borg)]

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.)