Nice writeup! One thing though, I believe Rust's BTreeMap [1] is a B-Tree (not a binary tree, as suggested), i.e. it's a tree whose branch factor is generally greater than 2.
The docs say that if you don't give a branch factor, a sensible choice is made for you, probably to get nodes to fit neatly into cache lines, so seeing as we are storing 35 unsigned 64 bit integers, this would be around 16 or 32 elements in a single node, and a depth of about 2. This means that, because the current implementation of BTreeMap does linear searches at
insertion, for this particular use case, the BTreeMap isn't doing much better than a plain old array, that you are insertion sorting.
TL;DR: Storing the results in a vector and then in-placing sorting it could be faster, but not noticeably. I know this isn't the point of the article, but it was just an observation I had :)
The docs say that if you don't give a branch factor, a sensible choice is made for you, probably to get nodes to fit neatly into cache lines, so seeing as we are storing 35 unsigned 64 bit integers, this would be around 16 or 32 elements in a single node, and a depth of about 2. This means that, because the current implementation of BTreeMap does linear searches at insertion, for this particular use case, the BTreeMap isn't doing much better than a plain old array, that you are insertion sorting.
TL;DR: Storing the results in a vector and then in-placing sorting it could be faster, but not noticeably. I know this isn't the point of the article, but it was just an observation I had :)
[1]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht...