3

Is it possible to branch code without using an if statement?

bobobobo
  • 64,917
  • 62
  • 258
  • 363

3 Answers3

5

Yes, you can, GPU-style.

Say you have a function that branches, and returns a value at the end.

float function( float input )
{
    if( input > 0 )
    {
        // do stuff
        finalValue = 2+4+8*input;
        return finalValue ;
    }
    else
    {
        // do other stuff
        finalValue = 1+input;
        return finalValue ;
    }
}

To do this without branching, you can write the code GPU-style: that is, evaluate both branches, then throw away the one you don't want at the end.

float function( float input )
{
    // do stuff..regardless
    finalValue1 = 2+4+8*input;

    // do other stuff..regardless
    finalValue2 = 1+input;

    bool resultMask = input > 0 ; // 1 if should use finalValue1.
    return finalValue1*resultMask   +   finalValue2*(1 - resultMask) ;
}

So there you have it. Branching without branching, if statements without if statementing.

bobobobo
  • 64,917
  • 62
  • 258
  • 363
  • But the actual `if` is still present in the `input > 0` expression, only the syntax has changed. From performance perspective it's probably worse then the original because of double evaluation – SomeWittyUsername Jan 06 '13 at 21:37
  • 1
    @icepack: I think you are wrong, there is no `if` here. most importantly, this code never branches or jumps, thus does not stop instruction pipelines – mvp Jan 06 '13 at 21:38
  • @mvp there is no `if` *syntactically* but it's present semantically in the `input > 0` expression, which is expected to yield assembly code similar to that of `if`. See @James answer below. I agree about the pipelining. – SomeWittyUsername Jan 06 '13 at 21:40
  • 1
    @icepack: Not really. `input > 0` on x86 for example is just a `cmp` instruction, which is purely arithmetic—`cmp a, b` sets the test flags as though you had calculated `a - b`. The “branching” only happens when you use a conditional jump instruction (e.g., `ja` or `jg`), which would not be generated by this code. I am simplifying—the specifics of working with floating-point numbers are a little different—but the principle holds. – Jon Purdy Jan 06 '13 at 21:41
  • @JonPurdy yes, it sets the flags. And what is done with the result next? – SomeWittyUsername Jan 06 '13 at 21:44
  • @icepack: It’s used in an expression, of course. For example, `CF & ZF` will give you whether the comparison was “above” (`ja`) or “below” (`jbe`). The point is that you avoid branching this way, not that you avoid conditionals at all. – Jon Purdy Jan 06 '13 at 22:01
  • @JonPurdy that's what I'm asking - in what kind of expression the flags will be used? The natural way is to use `ja`, `jbe` or similar expression. But I suppose it can be replaced with some load flags command into register and masking and shifting the result afterwards – SomeWittyUsername Jan 06 '13 at 22:07
  • [See also last reply on this thread](http://www.khronos.org/message_boards/viewtopic.php?f=9&t=3502), – bobobobo Jan 06 '13 at 22:44
  • @icepack: `setz` and friends are used for this purpose. –  Jan 06 '13 at 23:10
1

Depends on what you mean by "branch" and "if". Any of the below branch, with no "if".

switch (foo) {

}

Or ternary operators, if you don't count: 

x == 0 ? doFunc1() : doFunc2()

If your language supports function pointers: 

funcArray[selectedOption]()

You can be silly and do: 

boolean once = true;
while (condition && once) {
  doAWhichNeverReturns();
  once = false; 
} 
doB();

But I don't think this really answers your question, because I don't know what you're trying to do.

James
  • 8,512
  • 1
  • 26
  • 28
  • I was trying to figure out how the GPU does branching, because I read many places that [branching is a performance killer](http://stackoverflow.com/questions/315306/is-if-expensive/315382#315382). [This post](http://www.khronos.org/message_boards/viewtopic.php?f=9&t=3502) is where I realized this is how you can do it. – bobobobo Jan 06 '13 at 22:46
0

I was thinking about that because in mindastry game there is no dynamic if-statements, its simple script. If you know adresses, you can use a max function:

0: set adressFalse = 5;
1: set adressTrue = 7;
2: set boolean // 0 or 1
3: adress = max (adressTrue * boolean, adressFalse) // 7 or 5
4: goto adress
5: print("false");
6: goto 8
7: print("true");
8: // next code

Pay attention: goto input isnt a expression here.

VladisS
  • 11
  • 5