Hi,
On 2020-04-24 10:09:36 +1200, David Rowley wrote:
> If single comparison for a binary search costs about the same as an
> equality check, then wouldn't the crossover point be much lower than
> 64?
The costs aren't quite as simple as that though. Binary search usually
has issues with cache misses: In contrast to linear accesses each step
will be a cache miss, as the address is not predictable; and even if the
CPU couldn't predict accesses in the linear search case, often multiple
entries fit on a single cache line. Additionally out-of-order execution
is usually a lot more effective for linear searches (e.g. the next
elements can be compared before the current one is finished if that's
what the branch predictor says is likely).
Greetings,
Andres Freund