Why would an unconditional print have any effect on whether the branch predictor is invoked or not? The if statement is there in both cases, so branch prediction should kick in for both. I didn't find an explanation for this behaviour in the article.
Print(“lol”) doubled the speed of my Go function
21–30 of 130 posts
Re: Print(“lol”) doubled the speed of my Go function
#22Earlier quoted context omitted.
Yeah, after reading the blog post I felt reasonably confident that this is a compiler bug (in terms of perf). Hopefully someone with a deeper understanding can verify or discredit this here. I'm curious to see the fix for this (I assume it will generate a fix).
Confused, why do you think this is a compiler bug? You should definitely expect a predictable branch to be faster than a conditional move, and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it).
> and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it).
Would you mind expanding? If the conditional move isn't needed, and given that it's costly in terms of perfs, how is that “totally sensible” to have one here?
Re: Print(“lol”) doubled the speed of my Go function
#23Earlier quoted context omitted.
Confused, why do you think this is a compiler bug? You should definitely expect a predictable branch to be faster than a conditional move, and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it).
> and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it). Would you mind expanding? If the conditional move isn't needed, and given that it's costly in terms of perfs, how is that “totally sensible” to have one here?
The performance of branches is data-dependent. The performance of conditional moves is data-independent. In this case the branches are predictable, so they perform better here. In general, though, the compiler has no idea whether that's the case, so it makes sense to insert a conditional move to avoid branch misprediction penalties.
Re: Print(“lol”) doubled the speed of my Go function
#24I read it and I still don't get it, can someone (re-)explain what the presence of the print() is doing that is helpful for branch prediction (or any other aspect of the CPU)? Update: It seems to be the conditional move, see https://news.ycombinator.com/item?id=37245325
As to branch prediction, for anyone interested: https://stackoverflow.com/a/11227902
Re: Print(“lol”) doubled the speed of my Go function
#25Earlier quoted context omitted.
It's interesting that you say conditional move here. I am confused by this behaviour, and although I definitely don't know what the answer is here; the non-lol version does have a CSEL ( https://developer.arm.com/documentation/dui0802/b/CSEL ) which is totally missing from the lol version. Non-lol https://godbolt.org/z/ds1raTYc9 lol https://godbolt.org/z/c3afrb6bG
Ah there you go, that's the conditional move on ARM. Yeah, those are slow.
"Conditional move is slow" is not the right takeaway. (In fact, conditional move can be much /faster/ than a branch in certain circumstances (e.g. hard-to-predict branches, like binary search).)
The reason why this code is slow is because the conditional move is on the critical path for resolving a loop-carried data dependency. In other words, to execute the assignment `maxV = (v if (v > maxV) else maxV)`, the CPU has to test v > maxV. But in order to make this test, the CPU has to wait until the conditional move in the previous loop iteration finishes (to know what the new value of maxV is). So the overall execution time of the loop is worse, because each iteration depends on the previous iteration. (This is analogous to why traversing a linked list is slower than an array.)
However, for the branch version, there is no data dependency on the previous loop, so the CPU really can (speculatively) execute multiple loop iterations in parallel. The the next loop iteration can start before the previous finishes. And with the large reorder buffers on modern CPUs, maybe up to 4-8 loop iterations can execute in parallel!
On the other hand, conditional moves would be much faster for a loop like:
bigs := make([]int, len(numsA))
for idx, v : range numsA {
if numsA[idx] > numsB[idx] {
bigs[idx] = numsA[idx]
} else {
bigs[idx] = numsB[idx]
}
}
Re: Print(“lol”) doubled the speed of my Go function
#26Earlier quoted context omitted.
Confused, why do you think this is a compiler bug? You should definitely expect a predictable branch to be faster than a conditional move, and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it).
> and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it). Would you mind expanding? If the conditional move isn't needed, and given that it's costly in terms of perfs, how is that “totally sensible” to have one here?
Re: Print(“lol”) doubled the speed of my Go function
#27Earlier quoted context omitted.
> and the insertion of a conditional move in the original is totally sensible (albeit not intuitive if you haven't seen it). Would you mind expanding? If the conditional move isn't needed, and given that it's costly in terms of perfs, how is that “totally sensible” to have one here?
The performance of branches is data-dependent. The performance of conditional moves is data-independent. In this case the branches are predictable, so they perform better here. In general, though, the compiler has no idea whether that's the case, so it makes sense to insert a conditional move to avoid branch misprediction penalties.
This is a very good answer. Thanks.
Re: Print(“lol”) doubled the speed of my Go function
#28Earlier quoted context omitted.
Ah there you go, that's the conditional move on ARM. Yeah, those are slow.
Yeah, after reading the blog post I felt reasonably confident that this is a compiler bug (in terms of perf). Hopefully someone with a deeper understanding can verify or discredit this here. I'm curious to see the fix for this (I assume it will generate a fix).
I don't know if I would classify it as a bug, but definitely a heuristic that could use tuning.
At least (at a high level) in LLVM, branches and cmovs are represented with the exact same construct, and one of the codegen passes looks at the condition and the two sides and heuristically determines whether to emit a branch or a cmov.
I don't know how Go codegen works, but I assume they do something similar.
Re: Print(“lol”) doubled the speed of my Go function
#29Why would an unconditional print have any effect on whether the branch predictor is invoked or not? The if statement is there in both cases, so branch prediction should kick in for both. I didn't find an explanation for this behaviour in the article.
It has to make a decision to jump over the print sequence or not, whereas without the print it can eliminate the branch with a conditional move and only have to predict the loop variable. It just makes a bad guess as to whether branch prediction or conditional move will be faster, as explained above by tylerhou.
Re: Print(“lol”) doubled the speed of my Go function
#30Earlier quoted context omitted.
Ah there you go, that's the conditional move on ARM. Yeah, those are slow.
"Conditional move is slow" is not the right takeaway. (In fact, conditional move can be much /faster/ than a branch in certain circumstances (e.g. hard-to-predict branches, like binary search).) The reason why this code is slow is because the conditional move is on the critical path for resolving a loop-carried data dependency. In other words, to execute the assignment `maxV = (v if (v > maxV) else maxV)`, the CPU ha…
So would you say in the general case, i.e. the compiler obviously doesn't know how predictable a branch may be, using conditional move is a poor choice when writing to an address which is repeatedly written to inside the loop?
What I am trying to get a feel for, is whether this represents a bad choice of assembly in general for this kind of loop.