This bit is interestingly unintuitive - to go faster, do more iterations:
As far as the number of while loop iterations, I’m instead going to iterate a fixed number of times, log2 of the number of buckets. For some value this might involve a bit more work, if previously the bucket would be found in an iteration or two, but the saving in speed from avoiding branch mispredictions will make it worth it.
Comments
This bit is interestingly unintuitive - to go faster, do more iterations:
For small arrays that can fit in L1 cache, it's ok to do more loops. For bigger arrays, cache miss could remove all the gains.
Regardless of the array's size, the expected win from early exit on random keys is a constant number of iterations.