Bestcase seems like a poor metric when the CPU scheduler could certainly cause 7% variation. I would be interested to see, say, 100x the number of runs, and see mean rather than best, since one usually cares about average more than best.
I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has.
Because of noise in general, "best case" seems always like the best metric to me. Over a large number of run, you're likely to hit the "perfect" measurement with on a microbenchmark.
Otherwise, for an "adaptive" number of runs till enough time is spent to have some "confidence" on the measure, I've been fairly happy with: https://github.com/google/benchmark/
The timing _should_ be constant each run, so best case is the best way to remove the scheduler variations. I tried mean also, and the results aren't that different.
Optimization is -O3 (see the attached Makefile at the bottom).
Would march=native and fstrict-aliasing do any difference?
It would be interesting to compare the compiled asm with the hand rolled one.
The code has some potential improvements also but maybe the compiler is smart enough to find them, such as reading pivot.key in the loop even though it doesn't change.
I also wish I knew what optimization settings GCC/etc was using, and what effect tweaking those has.