Branchless Conditionals (2011)
blueraja.com
Branchless Conditionals (2011)
1–10 of 24 posts
Re: Branchless Conditionals (2011)
#2It's interesting that ARM32 has conditional execution and I like them a lot for writing readable assembly code. Short jumps that result from a simple if can be encoded in three successive instructions, no branches.
However, it's now falling out of favor (mostly gone from ARM 64) and apparently it's due to the relative cost of putting conditional execution on the die vs. relying on smarter compilers.
Re: Branchless Conditionals (2011)
#3x86 branch predictors are not 60% correct... Any decent branch predictor is over 90% correct and I believe modern ones are over 96% correct.
Re: Branchless Conditionals (2011)
#4Nice article. It inspired me to look around for some more straightforward way of optimizing, and I found the setcc class of instructions: http://www.nynaeve.net/?p=178
I'm thinking that this combined with some CAS (CMPXCHG8B) could acheive the same, right?
Something like (pseudo):
Comparewith(4)
Ifequalstore(54)
Ifnotequalstore(2)
Return
Re: Branchless Conditionals (2011)
#5It's interesting that ARM32 has conditional execution and I like them a lot for writing readable assembly code. Short jumps that result from a simple if can be encoded in three successive instructions, no branches. However, it's now falling out of favor (mostly gone from ARM 64) and apparently it's due to the relative cost of putting conditional execution on the die vs. relying on smarter compilers.
Nice! How do you do this on ARM exactly?
Re: Branchless Conditionals (2011)
#6x86 branch predictors are not 60% correct... Any decent branch predictor is over 90% correct and I believe modern ones are over 96% correct.
That's completely dependent on your algorithms.
Branch prediction in some search in a hash will fail 50% of the time, however it's done. Branch prediction on a long for loop was more than 99% correct by the end of the 90's already.
Intel claims their prediction algorithms are over 96% correct on an average program, whatever that beast is. (To be fair, you'll find a definition for it at their papers. That's a perfectly legit claim, it just does not mean what you think it means.)
Re: Branchless Conditionals (2011)
#7One simple branchless optimization form I've used is collision detection across an array of values: instead of testing each one, i add their value to a counter(perhaps with some mapping of data to collision value). After iterating over a lot of them, I can do just one test. This is very cpu-friendly as the pipeline gets to crunch all the numbers in one go.
Re: Branchless Conditionals (2011)
#8One simple branchless optimization form I've used is collision detection across an array of values: instead of testing each one, i add their value to a counter(perhaps with some mapping of data to collision value). After iterating over a lot of them, I can do just one test. This is very cpu-friendly as the pipeline gets to crunch all the numbers in one go.
Sounds interesting, can you provide a code example?
Re: Branchless Conditionals (2011)
#9Nice article. It inspired me to look around for some more straightforward way of optimizing, and I found the setcc class of instructions: http://www.nynaeve.net/?p=178 I'm thinking that this combined with some CAS (CMPXCHG8B) could acheive the same, right? Something like (pseudo): Comparewith(4) Ifequalstore(54) Ifnotequalstore(2) Return
Aren't setcc/cmov* instructions effectively similar to a branch? To compute the result you need to execute the previous instruction.
I suppose that these instructions do not cause the instruction pipeline to be flushed, compared to an incorrectly predicted jump, but they still stall until the previous instruction has been executed.
jmp < setcc/cmov* < branchless conditionals
Re: Branchless Conditionals (2011)
#10Nice article. It inspired me to look around for some more straightforward way of optimizing, and I found the setcc class of instructions: http://www.nynaeve.net/?p=178 I'm thinking that this combined with some CAS (CMPXCHG8B) could acheive the same, right? Something like (pseudo): Comparewith(4) Ifequalstore(54) Ifnotequalstore(2) Return
Aren't setcc/cmov* instructions effectively similar to a branch? To compute the result you need to execute the previous instruction. I suppose that these instructions do not cause the instruction pipeline to be flushed, compared to an incorrectly predicted jump, but they still stall until the previous instruction has been executed. jmp < setcc/cmov* < branchless conditionals
Conditional moves have data dependencies on their input arguments, but so do the "branchless" versions presented in the article.