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
