3 ms·

Someone tell me if there's an error in my takeaway: For short sequences, linear searches can be faster than binary searches because a short sequence of mostly

Someone tell me if there's an error in my takeaway: For short sequences, linear searches can be faster than binary searches because a short sequence of mostly predictable branches (no,no,no,no,yes) is usually faster than an even shorter sequence of unpredictable branches (yes,no,yes). To work around this, the author restricts his searches to compile-time constant sequence lengths so that GCC can unroll the fixed-size binary searches into short, fixed, linear series of branchless conditional move instructions. That setup executes reliably faster than optimized linear searches for in-cache sequences of size 8, 16, 32 and 64. However, if the data is uncached, then memory latency dominates ALU execution time and the memory prefetcher's preference for forward, linear scans leads to linear searches being faster than branches binary because of the difference in memory access patterns. Interestingly, the behavior of the prefetcher on the author's machine appears to prefer forward scans over backward scans at a sub-cache-line level.

nkurz 12y ago
Yes, I think your first paragraph is the correct takeaway, but I'm not sure about the second. Using Haswell as the example (because it's current and I'm more familiar with it right now), the linear search comparisons are really fast: the processor can handle 2 correctly-predicted branches-not-taken per cycle. But the single branch misprediction at the end costs about 15 cycles, plus the latency of reloading from L1 any registers where the load had already been speculatively executed (about another 5 cycles). The conditional moves are slower than simple comparisons, but still very fast: the CMP/CMOVcc pair can have a throughput of 1 per cycle if unrolled, so half as fast as a CMP/JMPcc that is correctly predicted as not taken. But there is no penalty at the end of the loop, so the overall speed is better for small sizes out to a 64-byte cacheline or so. I haven't tested, but I think the branchless approach has extended his lead in recent years. He's using Westmere, which is pre-Sandy Bridge, which is pre-Ivy Bridge, which is pre-Haswell. But the question of how this changes for data that needs to be brought into a cacheline from memory is probably more complicated than just the memory latency. I think the issue is more that the memory latency swamps the reading, and it isn't (or shouldn't be) that linear searches can take advantage of prefetching but binary can not. It just might take some 'trickery'. For the small sizes he's dealing with, you should be able to just load it all without waiting to see what you need. And I don't think that there is currently any advantage of forward versus reverse scans regarding prefetch, although one or the other might allow the loop to be structured differently.

nkurz 12y ago

Yes, I think your first paragraph is the correct takeaway, but I'm not sure about the second. Using Haswell as the example (because it's current and I'm more familiar with it right now), the linear search comparisons are really fast: the processor can handle 2 correctly-predicted branches-not-taken per cycle. But the single branch misprediction at the end costs about 15 cycles, plus the latency of reloading from L1 any registers where the load had already been speculatively executed (about another 5 cycles). The conditional moves are slower than simple comparisons, but still very fast: the CMP/CMOVcc pair can have a throughput of 1 per cycle if unrolled, so half as fast as a CMP/JMPcc that is correctly predicted as not taken. But there is no penalty at the end of the loop, so the overall speed is better for small sizes out to a 64-byte cacheline or so. I haven't tested, but I think the branchless approach has extended his lead in recent years. He's using Westmere, which is pre-Sandy Bridge, which is pre-Ivy Bridge, which is pre-Haswell. But the question of how this changes for data that needs to be brought into a cacheline from memory is probably more complicated than just the memory latency. I think the issue is more that the memory latency swamps the reading, and it isn't (or shouldn't be) that linear searches can take advantage of prefetching but binary can not. It just might take some 'trickery'. For the small sizes he's dealing with, you should be able to just load it all without waiting to see what you need. And I don't think that there is currently any advantage of forward versus reverse scans regarding prefetch, although one or the other might allow the loop to be structured differently.