> For larger arrays, I believe the branchy search algorithms start to do better since half their branches get predicted correctly.
(not sure if this is what you meant by "conflict misses")
I believe the reason branchy binary search algorithms do better on large arrays is that the CPU's speculative execution will cause it to prefetch data to the caches.
That means that, for around half of the steps, the data needed for the comparisons will not need to be fetched from memory.
You can get the best of both world by using a branchless implementation and manually prefetching data as in [^0].
That's not what's meant by 'conflict misses', no. The issue is that, with pot, the hottest elements (logically the ones which represent the highest nodes in the tree) will be spaced at pot intervals. If the array is large, that means their addresses will differ only in the high bits; in the case of the higher-level caches, then, they'll map to the same cache set and kick each other out, even though the cache as a whole has enough capacity to fit them all.
(not sure if this is what you meant by "conflict misses") I believe the reason branchy binary search algorithms do better on large arrays is that the CPU's speculative execution will cause it to prefetch data to the caches. That means that, for around half of the steps, the data needed for the comparisons will not need to be fetched from memory.
You can get the best of both world by using a branchless implementation and manually prefetching data as in [^0].
[0^]: https://en.algorithmica.org/hpc/data-structures/binary-searc...