7

I'm stuck there trying to figure out how to convert the last two "if" statements of the following code to a branchless state.

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

u = rand() % 4;
if ( y > x) u = 5;
if (-y > x) u = 4;

Or, in case the above turns out to be too difficult, you can consider them as:

if (x > 0) u = 5;
if (y > 0) u = 4;

I think that what gets me is the fact that those don't have an else catcher. If it was the case I could have probably adapted a variation of a branchless abs (or max/min) function.

The rand() functions you see aren't part of the real code. I added them like this just to hint at the expected ranges that the variables x, y and u can possibly have at the time the two branches happen.

Assembly machine code is allowed for the purpose.

EDIT:

After a bit of braingrinding I managed to put together a working branchless version:

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

u = rand() % 4;
u += (4-u)*((unsigned int)(x+y) >> 31);
u += (5-u)*((unsigned int)(x-y) >> 31);

Unfortunately, due to the integer arithmetic involved, the original version with if statements turns out to be faster by a 30% range.

Compiler knows where the party is at.

15
  • 1
    u += (5 - u) * (y > x);? Feb 15, 2015 at 11:07
  • 2
    @pmg The comparisons ">" and "<" imply a branch, no? Feb 15, 2015 at 11:10
  • 1
    @pmg mmh but to yield those 0 and 1 the machine has to evaluate somewhere said condition... I'm trying to avoid that. Feb 15, 2015 at 11:16
  • 2
    FWIW, gcc already compiles this using cmov. So is it even necessary to rewrite it?
    – harold
    Feb 15, 2015 at 11:46
  • 1
    Why does this matter? You're already calling "rand" 3x in this code, and doing 2 divides (by 100); I would expect that further optimization buys you very little overall advantage.
    – Ira Baxter
    Feb 15, 2015 at 16:49

2 Answers 2

2

[All: this answer was written with the assumption that the calls on rand() were part of the problem. I offer improvement below under that assumption. OP belatedly clarifies he only used rand to tell us ranges (and presumably distribution) of the values of x and y. Unclear if he meant for the value for u, too. Anyway, enjoy my improved answer to the problem he didn't really pose].

I think you'd be better off recoding this as:

int u, x, y;
x = rand() % 100 - 50;
y = rand() % 100 - 50;

if ( y > x) u = 5;
else if (-y > x) u = 4;
else u = rand() % 4;

This calls the last rand only 1/4 as often as OP's original code. Since I assume rand (and the divides) are much more expensive than compare-and-branch, this would be a significant savings.

If your rand generator produces a lot of truly random bits (e.g. 16) on each call as it should, you can call it just once (I've assumed rand is more expensive than divide, YMMV):

int u, x, y, t;
t = rand() ;
u = t % 4;
t = t >> 2;
x = t % 100 - 50;
y = ( t / 100 ) %100 - 50;

if ( y > x) u = 5;
else if (-y > x) u = 4;

I think that the rand function in the MS C library is not good enough for this if you want really random values. I had to code my own; turned out faster anyway.

You might also get rid of the divide, by using multiplication by a reciprocal (untested):

int u, x, y;
unsigned int t;
unsigned long t2;
t = rand() ;
u = t % 4;

{ // Compute value of x * 2^32 in a long by multiplying.
  // The (unsigned int) term below should be folded into a single constant at compile time.
  // The remaining multiply can be done by one machine instruction
  // (typically 32bits * 32bits --> 64bits) widely found in processors.
  // The "4" has the same effect as the t = t >> 2 in the previous version
  t2 = ( t * ((unsigned int)1./(4.*100.)*(1<<32));
}
x = (t2>>32)-50; // take the upper word (if compiler won't, do this in assembler)
{ // compute y from the fractional remainder of the above multiply,
  // which is sitting in the lower 32 bits of the t2 product
  y = ( t2 mod (1<<32) ) * (unsigned int)(100.*(1<<32));
}

if ( y > x) u = 5;
else if (-y > x) u = 4;

If your compiler won't produce the "right" instructions, it should be straightforward to write assembly code to do this.

5
  • While I entirely agree about the rand() and modulo functions not being exactly the best for performance-critical code, I actually merely put them there just to give the reader a hint on the expected range of values that the "x", "y" and "u" variables can possibly hold at the time of the on-topic section of code (most importantly "u"). Sorry about the inconvenience, I promise I will be more clear the next time around. Feb 15, 2015 at 20:11
  • As the branch condition is random, it will actually be very expensive, as the CPU branch predictor is powerless to help. I imagine at least as expensive as the divide or the call to rand() (that's speculation, not backed up evidence, though...). Feb 15, 2015 at 20:38
  • 1
    As with everything, measure, measure, measure... and then consider what happens when the implementation technology changes. (If the branches are still relatively expensive, in all my variations they can be turned into conditional moves as suggested by other answers.
    – Ira Baxter
    Feb 15, 2015 at 20:57
  • @user2464424: Ah. You just intended to tell us the range of x and y. Oh well. Yes, next time you should be clearer. Instead, you could have written an assert statement: assert ( x >-50 && x < 50) . [My misunderstanding made the puzzle a bit of fun, though].
    – Ira Baxter
    Feb 15, 2015 at 20:59
  • @user2464424: ... you should fix your question; it isn't "next time", people are continuing to read it :-{
    – Ira Baxter
    Feb 15, 2015 at 21:00
0

Some tricks using arrays indices, they may be quite fast if the compiler/CPU has one-step instructions to convert comparison results to 0-1 values (e.g. x86's "sete" and similar).

int ycpx[3];

/* ... */
ycpx[0] = 4;
ycpx[1] = u;
ycpx[2] = 5;
u = ycpx[1 - (-y <= x) + (y > x)];

Alternate form

int v1[2];
int v2[2];

/* ... */
v1[0] = u;
v1[1] = 5;
v2[1] = 4;
v2[0] = v1[y > x];
u = v2[-y > x];

Almost unreadable...

NOTE: In both cases the initialization of array elements containing 4 and 5 may be included in declaration and arrays may be made static if reentrancy is not a problem for you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.