Unexpected ways memory subsystem interacts with branch prediction
johnnysswlab.com
johnnysswlab.com
The archive version seems to be missing the branchless versions of the algorithms - is that missing from the article itself as well? It’d be interesting to put the different versions into compiler explorer.
> You can use arithmetics to go branchless.
if (a[i] > 0) {
cnt++;
}
cnt += a[i]if (a[i] > 0) return 1 else return 0 end
But why would a compiler do that?
Comparison operations are basic primitives that usually store their result into a register. With branching comparison operators potentially also available, but if there’s a branching comparator operation in your ISA, then there’s almost certainly also a pure comparator operation in your ISA, because you can always compose a branching comparator from simple comparison operation followed by a basic equality comparison of the result.
So I guess my question is, while it’s technically possible for a compiler to compile this into a branching operations, under what circumstances would a compiler actually choose to do that, given there’s isn’t a clear benefit?
In one of the most common processor architectures (the x86 family), comparison operations do store their result into a register, but it's the flags register, which can't be used directly in arithmetic operations. So you have to follow a comparison operation with either a conditional branch or a conditional move (and earlier processors in the x86 family didn't have conditional moves).
> So I guess my question is, while it’s technically possible for a compiler to compile this into a branching operations, under what circumstances would a compiler actually choose to do that, given there’s isn’t a clear benefit?
It depends on the compiler heuristics and on the surrounding code; for instance, it might decide that "compare; conditional branch over next instruction; increment" is better than "copy to second register; increment second register; compare; conditional move from second register", because it uses one less register (the x86 family is register starved) and one less instruction (relevant when optimizing for size).
The x86 family has the `setCC` instructions [^1] that move bits from the flag register to a general purpose one. Example from godbolt, see `setg`:
If I alter the code slightly to do `result += (a[i] == 0) * 2`, gcc emits a branch if the comparison is predictable: https://godbolt.org/z/df3fsoYK8
Here is a benchmark: https://quick-bench.com/q/NSGHu_wfhrMXp0-pZQp9qybCIok. Note how the branchless version takes the same time for the random and the zeroes vector, while the branch version is faster when the branch is predictable but slower when the branch is not predictable.
Of course when optimising code like this, I think it’s important to look at the generated assembly anyway and then you can be sure that it does what you expect on the compilers you intend on supporting (doubly so when you want to generate conditional moves — I’ve found that to be a bit of a puzzle where I sometimes need to move things around as the obvious code still generated a branch), but at least GCC and Clang won’t generate a branch for using just a comparison. Maybe it’s not the compiler and instead the target architecture? In x86, comparisons set flags, so by themselves aren’t branches. In any case, I recommend using compiler explorer when working on code where this matters.
https://offlinemark.com/2023/07/29/til-arm64-doesnt-include-...
No, you've changed the right-hand side expression. Now you're adding a[i] to cnt and nowhere has it stated that a[i] is 1. But a[i] > 0's result is always zero or one.
I suggest what you want is this:
cnt += !!a[i]
or this, depending on your style:
cnt += bool(a[i])
x86_64 assembly for me is just the transition step before the actual RISC-V jump. This is "register-ization" of some code paths. Once done, it is kind of easy to do a port to another modern ISA. Bu then, I am thinking about all that branch prediction on RISC-V:
Will we have a way to hint a core/hart to dodge prediction for some branches, fine-grained and "cleanly"? I was thinking about implicit branch prediction exclusion via some "known" instruction fusions, but the 'implicit' here is scary.
Why would you want to avoid the branch predictor? All it can do is speedup your code.
However, it's not specified to completely disable speculation, only "to the extent that such speculation can be observed through side-channels as a result of control flow speculation or data value speculation". So e.g. an implementation could decide to disable speculative memory access while still allowing arithmetic operations.
Preventing Spectre vulnerabilities is pretty much the only reason you'd want to disable branch prediction though (except for curiosity of course). Without prediction, performance would be as bad as if every branch was mispredicted, since the pipeline has to stop and wait at every single branch. The idea of branch prediction is that the "wasted" cycles waiting for the branch to resolve can instead be used to do some computation that may or may not be useful; if it turned out to be useful you saved some time, if not you didn't lose anything (besides maybe some electricity). So even a branch predictor that randomly guesses with 50% accuracy is a huge performance win over not speculating at all.