Missing: conventional wisdom turned into lie

Posted Oct 24, 2007 20:29 UTC (Wed) by khim (subscriber, #9252) [Link]

If you just have 4-5 elements in the array then initial complexity of binary search will dominate - with or without memory access effects. At some point binary search will win - but it'll be good exercise to find this point today...

Actually it's true for most algorithms: bubble sort also wins for small arrays, for example. Usually trivial algorithms work well for small sizes but not-so-well for medium-to-large sizes. Usually it's not worth the effort to optimize for small sizes: it's fast not matter what algorithm you are using. If your program is spending 90% of time searchive 5-element arrays - it's different story, of course, but it's rare in practice...

Posted Oct 25, 2007 10:48 UTC (Thu) by mmutz (subscriber, #5642) [Link]

> 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.

This is exactly the conventional wisdom I think isn't true anymore for 
some realistic examples. You're missing the effect of the hardware 
prefetcher, which will, for some sizes, and esp. for cold caches lead to a 
performance increase for the linear search, as opposed to binary search, 
which looks like random access to the prefetcher, and therefore incurs the 
RAM->cache latency cost typically hidden by the prefetcher.