View all comments
Even with only 100 elements a binary search should be about 5 times faster. I think it just comes down to people in this class not knowing what they are doing.
A linear search on such a small array can be super fast in hardware, it fits better in the pipeline (less pipeline stalls) and its possible to parallelize with SIMD instructions. Binary search is a lot harder for the compiler to optimize.
I found a cool blog post that compared exactly this, link the best binary search Implementation (which is kinda involved) is just as fast as the linear search for 100 elements.
When you say pipeline stalls do you man branch mispredictions? Cache misses don't stall right?
Of course a cache miss can stall. It takes hundreds of cycles to fetch from RAM, for example.
But I was thinking of branch mispredicts, since for 100 elements a cache miss is rather unlikely to occur. For large arrays, linear search also has an advantage in that regard but its outweighed by the much higher complexity at that point.
Hundreds of cycles to fetch RAM? Really? Damn. I knew it was bad, but not that bad.