[rkagerer]

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.

[ww520]

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.

[pkhuong]

Regardless of the array's size, the expected win from early exit on random keys is a constant number of iterations.