3 ms·
I'm surprised that conditional moves make much difference here. Aren't they essentially a compressed form of branch, and so still require speculation? Perhaps
by rwmj 5y ago
I'm surprised that conditional moves make much difference here. Aren't they essentially a compressed form of branch, and so still require speculation? Perhaps the fact that the code has a smaller size is what is making the difference. (Of course that's still a good outcome)
- gpderetta 5y agoThe branch predictor can't do a great job here as the branching is very data dependent. The conditional move prevents speculative execution (at the cost of adding a dependency).
- Filligree 5y agoI'm vaguely aware of this, but also honestly surprised the CPU isn't speculating on the move anyway.
- gpderetta 5y agoIn principle it could. But A) it would be a bit pointless because cmov is used to avoid badly predictable branches and B) IIRC after the whole spectre affair Intel gave the guarantee that cmov is never speculated. Regarding A, you could have a meta predictor that decides whether you should speculate or not, trained on the misprediciton rate. But then you do not need the cmov in the first place and you can just dynamically convert non-diverging jumps to predication. This is, I think, called Dynamic Hammock Predication and was implemented, in some restricted cases (IIRC jumping over a single instruction) in some recent POWER cpus from IBM. I think that RISC-V also doesn't have predication and an implementation is supposed to use this optimization instead.
- rwmj 5y agoSo the dependency is taken care of with register renaming? Trading renamed registers (which are basically "free" as modern processors have so many of them) for speculation. Interesting ...
- gpderetta 5y agoWell, renaming allows removing false dependencies due to reuse of registers (for example allowing multiple iterations of a loop to partially overlap or even execute in parallel), but in this case it is a true dependency: the iteration variables depends on the values loaded off it, which prevent out of order execution. Branch prediction would break the dependency, but the misprediction rate here is high enough for this specific algorithm to be usually a net negative.
- rwmj 5y agoRight, essentially loop unrolling through the renamed registers (if I remember my lessons on Hennessey and Patterson 25+ years ago).