Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Weird Concept of Branchless Programming

sanixdk.xyz

Post reply on HN
Print view View original

71–80 of 92 posts

Re: The Weird Concept of Branchless Programming

#71

Post by mwkaufma »

stevefan1999 wrote: post #63
mwkaufma wrote: post #47

Is cmov branchless, or just branching by another name?

That depends on how you define branch. Say in Rust: let foo = if bar { 1 } else { 2 }; And let mut foo; if bar { foo = 1; } else { foo = 2; } Despite they looked the same, functions the same and effectively the same, but the first one is the conditional move, and the second one would be a jump initially (until further compiler optimization kick in) You will notice that for conditional move, you "get" a predictable ex…

Lotsa detail, but not to the point: does cmov depend on branch prediction or not?

Re: The Weird Concept of Branchless Programming

#72

Post by toast0 »

vdupras wrote: post #67
toast0 wrote: post #58

Earlier quoted context omitted.

> In that context, it's not very small, it's 20% (all instructions are register-to-register instructions, so they all have the same weight). It's huge. Huge in space sure. Not in execution time.

It's 20% of the execution time. All these instructions use the same number of cycles.

Do they? I put together two quick and dirty nonsense test programs this is option2:

   int main (void) {
       for (int i = 0; i
option1 has the extraneous mov ecx, eax, and then add with ecx.

I confirmed with objdump -d that the assembly hadn't been touched and that the loops were the same. On my otherwise mostly idle dual L5640 system and pinned to a single cpu (just in case), option1 consistently runs in 3.14 seconds and option2 consistently runs in 3.15 seconds.

Adding an extra zero, both option1 and option2 runs in 30.94-30.95 user seconds. The extraneous move doesn't seem to cost any actual time.

Re: The Weird Concept of Branchless Programming

#73

Post by recursivecaveat »

adrianmonk wrote: post #14

I've always wondered if any CPUs have tried to reduce the branch penalty by speculatively executing both ways at once in parallel. You'd have two of everything (two pipelines, two ALUs, two sets of registers, etc.) and when you hit a conditional branch, instead of guessing which way to go, you'd essentially fork. Obviously that requires a lot of extra transistors and you are doing computation that will be thrown away…

They do this on FPGA a lot. Since you know statically the content of the branches, and you need to have resources there to run either of them, it is pretty low overhead to set them up to run in parallel and select the appropriate result afterwards.

Re: The Weird Concept of Branchless Programming

#74

Post by adastra22 »

jasonwatkinspdx wrote: post #28
adrianmonk wrote: post #14

I've always wondered if any CPUs have tried to reduce the branch penalty by speculatively executing both ways at once in parallel. You'd have two of everything (two pipelines, two ALUs, two sets of registers, etc.) and when you hit a conditional branch, instead of guessing which way to go, you'd essentially fork. Obviously that requires a lot of extra transistors and you are doing computation that will be thrown away…

Yes, it's been looked at. If you wanna skim the research use "Eager Execution" and "Disjoint Eager Execution" as jumping off points. It doesn't require duplicating everything. You just need to add some additional bookkeeping of dependencies and what to retire vs kill at the end of the pipeline. In practice branch predictors are so good that speculating off the "spine" of most likely path just isn't worth it. In fact…

I think you’re missing the context: that good branch prediction is what causes these security holes. “Wasteful” multi path execution is a security feature.

Re: The Weird Concept of Branchless Programming

#75

Post by userbinator »

toast0 wrote: post #72
vdupras wrote: post #67

Earlier quoted context omitted.

It's 20% of the execution time. All these instructions use the same number of cycles.

Do they? I put together two quick and dirty nonsense test programs this is option2: int main (void) { for (int i = 0; i option1 has the extraneous mov ecx, eax, and then add with ecx. I confirmed with objdump -d that the assembly hadn't been touched and that the loops were the same. On my otherwise mostly idle dual L5640 system and pinned to a single cpu (just in case), option1 consistently runs in 3.14 seconds and o…

Microbenchmarks don't usually tell the whole story. Once the bloat adds up the cache misses and macro-scale benchmarks will show a difference.

Re: The Weird Concept of Branchless Programming

#76

Post by stevefan1999 »

mwkaufma wrote: post #71
stevefan1999 wrote: post #63

Earlier quoted context omitted.

That depends on how you define branch. Say in Rust: let foo = if bar { 1 } else { 2 }; And let mut foo; if bar { foo = 1; } else { foo = 2; } Despite they looked the same, functions the same and effectively the same, but the first one is the conditional move, and the second one would be a jump initially (until further compiler optimization kick in) You will notice that for conditional move, you "get" a predictable ex…

Lotsa detail, but not to the point: does cmov depend on branch prediction or not?

No, predicated instructions like CMOV do not depend on branch prediction.

Re: The Weird Concept of Branchless Programming

#78

Post by yccs27 »

zackmorris wrote: post #31

I need something like this for a switch() command (technically a list of arbitrary functions). Sort of like up to N branches in one step. The idea is to take some number of inputs A, B, C, ... and conceptually perform all of the possible functions simultaneously, then keep the one that's desired and throw the rest away. For any arbitrary logic. Ideally using fewer operations than all of that, but that's optional. Dri…

The most general approach is to calculate all the different cases, and then do a branchless selection:

    var4 = (var1==1)*(var2+var3) | (var1==2)*(var2-var3) | ...
Of course this is basically the slowest possible option, but it might work as a starting point for a general-purpose optimizer to find a faster solution. If it doesn't, this will likely compile to conditional move instructions.

It might help if you replace the comparison and multiplication with an equivalent expression made from bitwise operations, but I believe most compilers already know how to do this transformation.

Re: The Weird Concept of Branchless Programming

#79

Post by wucke13 »

FooBarBizBazz wrote: post #21

I used to do stuff like this (ok, not half as smart), but stopped around 2013 or so, as the distinction between "implementation defined" behavior (ok) and "undefined" behavior (not ok) started to matter and bite. After thinking through this carefully, though, I do not see UB (except for signed overflow in a corner case): Step 1, bit shift. I understand that, until C++20, left shift of a signed int was UB. But this ri…

Rust in particular with miri is quite impressive at catching them. You just run your testcases via

    cargo miri run
And if your code actually touches UB, mirei will most likely point out exactly where and why.

Re: The Weird Concept of Branchless Programming

#80

Post by okaleniuk »

Some safety critical real time systems have strict time predictability requirements. This means that the whole loop should pass in exactly X microsecond, not more not less. For this, all the programming should be pretty much branchless.

For instance, all the sorting algorithm turn to, effectively, bubble sort since without branches, you always go with the worst case - and the sorting complexity is always the O(n^2). But it's okay, since the algorithm becomes predictable. You just swap a conditional swap:

    if a
with arithmetic swap:

    c = (a+b)/2
    d = |a-b|/2
    a = c + d 
    b = c - d
and that's it.
Post reply on HN