Missing: conventional wisdom turned into lie
Posted Oct 24, 2007 16:21 UTC (Wed) by JoeBuck
In reply to: Missing: conventional wisdom turned into lie
Parent article: Memory part 5: What programmers can do
If the array all fits in cache, binary search wins: both linear and binary search, at most, load the data into cache once. If the array is extremely large, binary search still wins despite the wasted reads of entire cache lines, because at some point N/log(N) exceeds the miss penalty. There may be intermediate values where binary search loses, when the random access causes the cache miss rate to soar and this isn't compensated for adequately by the reduced expected number of element accesses.
to post comments)