4 ms·
I did some preliminary testing on this a few months ago, which we might pick up again someday and try to publish as a short paper. I haven't looked closely ye
by nkurz 11y ago
I did some preliminary testing on this a few months ago, which we might pick up again someday and try to publish as a short paper. I haven't looked closely yet at what the author did, and I've forgotten some details of what I did, but I can speak generally to our implementation comparing branching and branchless.
For repeated lookups, the first couple levels will all be hit in L1 cache regardless of which way the comparison goes. The branch prediction penalty is about 15 cycles, and the L1 access is about 5. The next level might be in L2 at 12 cycles, then the next few levels are in L3, with a ~40 cycle access time, then RAM with 100+ cycles of access. The last few accesses will be within the same 64B cacheline (128B with buddy prefetch), and thus will be in L1 after the first access.
The branchless conditional move approach has a data dependency, while the branching "if" approach is a control dependency. Modern processors "run ahead" with speculative execution past control dependencies (executing the instructions for one branch but not retiring them), while the conditional moves are issued but cannot be executed until the corresponding comparison has been made.
Because of speculative execution, the branching approach effectively has a 50% accurate automatic prefetcher that runs several iterations ahead. The math works out so that for some access patterns this can be a significant advantage. The speed gap can be closed (and if I remember correctly, reversed) by adding explicit prefetch instructions to branchless approach. The branching approach can also benefit from judicious use of prefetch, so that each branch fetches acts as a prefetch for the opposite branch, which makes for faster recover after a branch prediction error.
As the author concluded, we also found that a batch approach could be beneficial. You can mitigate latency from RAM (and even from L3) if you can arrange to have about 10 outstanding requests at a time. For a single core, batch and prefetch approaches had similar top speeds. For multicore (untested) presumably the excessive memory bandwidth of the "wrong" prefetches would give the advantage to batch. Similar to the author's experience on Broadwell, we found that on Haswell the SIMD gather had minimal advantage over repeated scalar loads. We have a Skylake machine coming soon, and are hoping the hardware gather approach might finally take the lead.
- pcwalton 11y ago> Similar to the author's experience on Broadwell, we found that on Haswell the SIMD gather had minimal advantage over repeated scalar loads. I've read that VPGATHERDD is microcoded to N separate loads on Haswell, unfortunately.
- acqq 11y agoOK, but binary search shouldn't have predictable patterns? So in a classic example, if the search isn't "obvious" 50% of the time we'd have an "unconditional" MOV, removing dependencies but also 50% of the time we'd have wrongly predicted branch. Maybe the testing was on a too obvious example?
- nkurz 11y agoSorry, my phrasing was poor. The searched for elements are indeed random, but the first few (and last few) accesses will hit cache. Depending on the size of the total array, the relative importance of the different access times vary. We were actually comparing some different memory layouts besides the standard "sorted" (http://cglab.ca/~morin/misc/arraylayout/ http://cglab.ca/~morin/misc/arraylayout/). Our conclusion was essentially that with proper implementation, there wasn't much if any advantage to alternative layouts. But there certainly were some subtle things about testing. In particular, there is a significant difference between preparing a list of random searches in advance (and loading them from memory), versus calculating a random number on the fly. Since the performance advantage of the branching approach depended on how far ahead the speculative execution would get, the additional µops for making the number sometimes slowed down enough to remove the speculative advantage. But to clarify my earlier answer: I think the author is seeing real effect, and the difference has to do with prefetching due to speculative execution of the branching approach. This doesn't mean that branching is the best approach, though, only that a "naive" approach can indeed beat branchless at certain sizes. Both the branching and branchless approaches can be improved significantly with either batching or explicit prefetching.
- gpderetta 11y agoAnother way to see this is that the 'branchy' version can have multiple loads pending at the same time. This is a big win for non L1-cached loads. Cmov forces each load to depend on the previous one, so you will have only one load pending at any time. With a 50% misprediction rate, the Nth load has only 0.5N probability of actually committing, but it is still better than just having a single load in flight.
- derf_ 11y agoYou can also change the memory layout to that of a binary heap, instead of the usual sorted order. That puts the next index at either (2i + 1) or (2i + 2). With proper alignment, those will be in the same cache line up to 4 iterations in the future, regardless of which way you descend the tree. So you can do a branchless prefetch version with much better than a 50% prefetch accuracy. This only helps once you're hitting L3 cache, though. See https://news.ycombinator.com/item?id=10410676 https://news.ycombinator.com/item?id=10410676 for previous discussion.