Cache associativity, conflict miss. When too many memory addresses which are far apart map to the same cache lines while being used and reused in quick succession, causing cache evictions.

Scott Meyers had a very good talk which contained this information: <https://youtu.be/WDIkqP4JbkE?t=3614>

Size also matters for this problem. The effect of it is to slash your processor's cache size. If your problem is small enough that it fits in the cache anyway you won't see the effects. That said, unless the cache is hot, it shouldn't make a difference in the first place. Moreover I'm pretty confident in guessing that with a cold cache, the difference between the algorithms would vanish.

I vaguely remembered reading something about this too. I think it's a great use case for ChatGPT, I copy-pasted the blog post and asked: "why could there be spikes for powers of 2?"

> The spikes in the performance for std::lower_bound at powers of 2 might be due to the nature of how binary search works and the specific implementation of std::lower_bound in the standard library.

> Binary search works by continually halving the search space. When the size of the array is a power of 2, every subdivision during the binary search is a clean halving of the array. This could result in an idealized number of comparisons in theory.

> However, in practice, modern CPU performance is heavily influenced by memory access patterns due to caching effects. When an array size is a power of 2, elements that are frequently compared may end up located at memory addresses that conflict in the CPU cache (a phenomenon known as "cache aliasing" or "cache line collisions"). The CPU cache works by storing data that is spatially and temporally close together, and it uses certain bits of the memory address to determine where in the cache to place that data.

> When the size of the array is a power of 2, it's more likely that two distinct memory locations will map to the same cache line, leading to cache eviction where one piece of data pushes out the other, causing a cache miss the next time that evicted location is accessed. This results in extra memory latency, slowing down the execution of the algorithm.

> The performance spikes you see are likely a combination of these factors. While the algorithm is doing an optimal number of comparisons, the cache line collisions might be causing additional memory latency that slows down the overall performance.

> This would also explain why the branchless binary search algorithm does not show the same performance spikes at powers of 2 - its memory access pattern is different and may not result in the same level of cache line collisions.