3 ms·

I am not sure why is he talking about branching prediction when this is really about caching. The next integer to look at is unlikely to be in the CPU data cach

by js8 7y ago

I am not sure why is he talking about branching prediction when this is really about caching. The next integer to look at is unlikely to be in the CPU data cache, and so each time we have to go to main memory. If we interleave the searches, we interleave the memory requests, and get higher throughput. Or am I wrong?

cshenton 7y ago
If I had to hazard a guess, I’d say the conditional move means that both next values are prefetched into cache, whereas a branch means that fetch doesn’t happen until the comparison is made.
- nkurz 7y ago
  Unfortunately I think that's backwards on both sides. Conditional moves create a data dependency, and thus do not involve speculative execution. While the program can explicitly try to preload both possible values (and can benefit from doing so) the processor doesn't ever do this automatically. Other instructions can still be executed (out-of-order) but the path of execution does not change. With a branch, rather than waiting for the results of the comparison to be known, the processor guesses at the result and chooses a path of execution. It thus executes the fetch immediately, but (about) half the time it's the wrong fetch. If after the original load completes it realizes that it guessed the wrong side of the branch, an 'exception' occurs, the speculative work is thrown away, and the execution begins again with the correct branch.
nkurz 7y ago
He's talking about branch prediction because it's intimately tied with speculative execution. He's trying to explain why the standard 'branchy' version of binary search has faster performance than one might naively expect, thus why the speedup from increasing MLP (memory level parallism) is less than one might expect. When the processor reaches a conditional branch (the 'if' statement comparing the test value), rather than waiting for the actual results of the comparison to be known (and thus waiting for the test value to be loaded), it blindly guesses one of the branches and continues executing instructions as fast as it can. It doesn't commit the results of these instructions ('retire' the instructions) until the real answer is known, but crucially, it executes the loads sooner than they would otherwise be executed. Most of these early loads are along the wrong path and the load is wasted, but half the time, the first guess is right, and half the time, the branch after that, etc. The end result is that branchy binary search ends up roughly twice as fast as a branchless version that waits for the loads to complete and efficiently makes only the loads that need to be made.

by js8 7y ago

cshenton 7y ago

If I had to hazard a guess, I’d say the conditional move means that both next values are prefetched into cache, whereas a branch means that fetch doesn’t happen until the comparison is made.

nkurz 7y ago
Unfortunately I think that's backwards on both sides. Conditional moves create a data dependency, and thus do not involve speculative execution. While the program can explicitly try to preload both possible values (and can benefit from doing so) the processor doesn't ever do this automatically. Other instructions can still be executed (out-of-order) but the path of execution does not change. With a branch, rather than waiting for the results of the comparison to be known, the processor guesses at the result and chooses a path of execution. It thus executes the fetch immediately, but (about) half the time it's the wrong fetch. If after the original load completes it realizes that it guessed the wrong side of the branch, an 'exception' occurs, the speculative work is thrown away, and the execution begins again with the correct branch.

nkurz 7y ago

He's talking about branch prediction because it's intimately tied with speculative execution. He's trying to explain why the standard 'branchy' version of binary search has faster performance than one might naively expect, thus why the speedup from increasing MLP (memory level parallism) is less than one might expect. When the processor reaches a conditional branch (the 'if' statement comparing the test value), rather than waiting for the actual results of the comparison to be known (and thus waiting for the test value to be loaded), it blindly guesses one of the branches and continues executing instructions as fast as it can. It doesn't commit the results of these instructions ('retire' the instructions) until the real answer is known, but crucially, it executes the loads sooner than they would otherwise be executed. Most of these early loads are along the wrong path and the load is wasted, but half the time, the first guess is right, and half the time, the branch after that, etc. The end result is that branchy binary search ends up roughly twice as fast as a branchless version that waits for the loads to complete and efficiently makes only the loads that need to be made.