Context

The benchmarks uses of black_box as a "fence" around outputs to prevent compiler optimization such as optimizing them out (because the compiler would otherwise consider them not used). This is what criterion.rs applies by default.

For instance in this lookup benchmark:

However, the same must be done for inputs, or they might get optimized along with the code of the benched function. This can make a significant difference in some scenarios. This article explains it well:
https://gendignoux.com/blog/2022/01/31/rust-benchmarks.html#effect-of-stdhintblack_box-on-a-benchmarking-loop

a crucial point is to put a black_box both on the inputs and on the outputs

I have tested it on my side, and I do see significant differences (tested on a MacBook pro M1).

Todo

Change:

for i in $keydist.take(SIZE) {
     black_box(m.get(&i));
}

To:

for i in $keydist.take(SIZE) {
     black_box(m.get(black_box(&i)));
}

Same probably applies for other parts of this benchmark.