5

I was told that the branches in the code

int value = //some number;
if(value > some_other_value)
   value *= 23;
else
   value -= 5; 

can be eliminated via bitwise masking (in order to enable SIMD optimization for the code):

const int Mask = (some_other_value-value)>>31;
value =      ((value * 23)&Mask)|((value-5)&~Mask);

However, I do not understand how this works (even though I understand what operations are being used here and how the results will look in binary). Furthermore, how generally applicable is this? What if the original code was instead something like

if(value & 1 == 1)
   value *= 23;
else
   value -= 5;

Would the branch-removed code still be the same? Otherwise, what is the purpose of the mask and how should I go about creating it? What is happening here?

9
  • 1
    That optimization is invalid. If the subtraction {over,under}flows, you get a wrong result. Think value == 1 and some_other_value = INT_MIN.
    – user784668
    Jan 29, 2013 at 14:00
  • 1
    You'd need to understand bit operations better to write something like that. Also, it's rarely needed, and please don't even try to put something like this into code before you profile. Jan 29, 2013 at 14:01
  • If I get it right, the purpose of the mask is to reflect the condition - it should be all 1's if the condition is true, and all 0's otherwise (note the comment from @Fanael though). Then, both possible values are calculated (value*23 and value-5), but only one of them taken by and-combining the results with the mask, and its negation respectively. One of the and-combinations will be 0, the other one will contain the calculation result. The final or-operation combines them (effectively being an assignment since one operand of the or-operation is 0) Jan 29, 2013 at 14:09
  • @Bartek Banachewicz As I said, I need it in order to make code SIMD-optimizable. I've profiled a lot, it's necessary :P
    – TravisG
    Jan 29, 2013 at 14:25
  • At the core, a CPU is logical circuit, that doesn't have branches. The wires are fixed -- even if there are FPGA components embedded. Jan 29, 2013 at 14:48

2 Answers 2

4

This works:

const int Mask = (some_other_value-value)>>31;
value =      ((value * 23)&Mask)|((value-5)&~Mask);

Mask becomes the sign bit of some_other_value - value - similar to:

if (value > some_other_value) mask = -1; else mask = 0; 

You could achieve the same thing with your second example, using:

mask = -(value & 1);

So, -0 = 0, -1 = all ones.

Edit: I would also bear in mind that if the calculation gets too complicated, you are not gaining anything over the branching version, particularly not if the branches are reasonably predictable.

2
  • That's a nice summary. Mask all ones for true, all zeroes for false. Then one of the two terms in the bitwise selection will be completely zero, and connected to the other term via bitwise OR. But since n | 0 = n, only one goes through.
    – TravisG
    Jan 29, 2013 at 14:28
  • The effect of left shifting a negative value is implementation defined, so you don't know what value Mask will take on if some_other_value is less than value. And with regards to what you might be gaining: a compiler is just as capable of making this sort of transformation as you are, except that it knows the implementation defined behavior. It's a fairly stanard transformation; I've seen as early as 1980. Jan 29, 2013 at 15:53
-3

This is a premature optimization in the best case, and an anti-optimization in the worst case.

If the code can be vectorized, it will use conditional moves anyway, since SIMD doesn't know anything else.

But even for scalar code, modern compilers usually generate conditional moves, so there is no branch (unless the compiler figures that evaluating both equations is sufficiently expensive so it's more efficient to branch).

Conditional moves have been a standard feature on RISC processors (say, e.g. ARM) pretty much forever, and are supported even on x86 for about 17 years. On a modern processor, a conditional move will take either exactly the same amount of cycles as a normal move, or maybe 2-3 cycles at most extra.
This obviously assumes that the condition is evaluated early enough (though it does not matter if there is no dependency on the value, since out-of-order execution will hide it), but that's the case with any kind of cryptic optimization hack that you apply, too. You just can't use a result that isn't there yet.

If you can help it, always write code that is comprehensible at first look, instead of some obfuscated

value = (((foo<<31)&bar, ++baz) -= (foo & 7121)) + PHASE_OF_MOON;

kind of stuff, which will not only be none faster and likely slower, but also confuse someone reviewing your code (including yourself, in 6-10 months from now!), is highly non-portable, and quite possibly also produce incorrect results in situations that you don't anticipate.

7
  • 5
    This isn't a premature optimization. I implemented the SIMD solution by now, and it's roughly 3.5 times faster than the old solution without SIMD instructions. Frankly I think you're missing the point here. It doesn't matter that the code is harder to read - the performance requirements are simply harsh enough that I wasn't going to get around SIMD optimization. And there's simply no way to manually insert SIMD optimization without getting those branches away - the language simply doesn't allow it.
    – TravisG
    Jan 30, 2013 at 16:00
  • 3
    By the way, it's pretty annoying that many people shout "PREMATURE OPTIMIZATION" even though they have no clue about the context of the project and the situation the programmer is in. Even worse: half the time they're objectively wrong (like you), because they disregard anything that isn't pretty code. Sometimes pretty code just isn't possible, and in those cases it's pretty easy to comment out the "plain C++" version and point out the the following is an optimization that was necessary because otherwise the project goals could not be met.
    – TravisG
    Jan 30, 2013 at 16:04
  • 2
    You did not make any mention of profiling and this particular statement being the hot spot. Insofar it is premature. That said, for a single if statement like the above to become significant, you have to execute it billions of times. If that's really the case, you should rather think about the algorithm or data layout. Besides, if you really want to (or need to) implement this via SIMD by hand, a much smarter solution would be to use the proper compare/cmov instructions rather than some obscure bit twiddling. Not only are they much faster, but also the intent is much clearer.
    – Damon
    Jan 30, 2013 at 16:48
  • 1
    Doesn't matter what I mentioned or didn't mention. You said "This is a premature optimization in the best case", which is an absolute statement and absolutely wrong. I shouldn't need to point out, in every question like this, that I have done enough profiling to know that these steps are necessary. This is not what StackOverflow is about. In this case, it was completely irrelevant to the question. Even if I tried to do this for shits and giggles, the question would still stand valid.
    – TravisG
    Jan 30, 2013 at 17:48
  • And you're talking nonsense in the second part as well. Data layout doesn't matter at all, branched code still can't be SSE optimized. Compare instructions in SSE don't matter at all, they only give you a comparison result, but you would still have to branch the code using that result, which is a no go. And I don't know what you're talking about when you mention SIMD cmov, google doesn't yield anything useful. Either way cmovs would only be useful here if the operations in different branches are the same. Also note that I'm not writing inline assembly.
    – TravisG
    Jan 30, 2013 at 17:50

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.