So i think the whole point of the exercise was that he doesn't care about the first iteration. Only the subsequent ones when the keys are already cached. In these scenarios the misses on attempt 1 don't count, which is what you are optimizing. Look at the way he generates data 10 runs of 100k each and then selects 1000 points. Only 10 runs out of 1M incur the misses. Thus they almost never show up. Which brings to my very own comment - "Why not pre-allocate the future log(n) keys in a separate array and fill it up on run 1?". This is the natural way of looking at the solution. You are just helping the cache, store exactly what you need.