5

I'm learning to program the Game Boy Advanced (an old Nintendo console.) I was reading one of the best tutorials about it and it said this about how branching can be done with arithmetic.

[To optimise your code] avoid branches. Things that redirect program flow (ifs, loops, switches) generally cost more than other operations such as arithmetic. Sometimes it's possible to effectively do the branch with arithmetic (for example, (int)x>>1 gives −1 or 0, depending on the sign of x)

(Emphasis mine. Taken from https://www.coranac.com/tonc/text/first.htm)

But if it returns 0 or -1, wouldn't you still need a branch to check which one it is and execute the according instructions? Obviously the above explanation is missing some details but I don't see how this avoids a branch.

  • 1
    I don't believe he's saying that this can replace any arbitrary branch. See this SO answer for an example of this sort of optimization in practice. – JETM Nov 21 '18 at 19:11
  • (I'm making no claims as to whether this particular example is actually any faster or not.) – JETM Nov 21 '18 at 19:11
  • 2
    I don't know what Jasper Vijn had in mind when he wrote that (you could try sending him an email and ask him directly). But a classic optimization technique which avoids branching is called Loop Unrolling, the Wikipedia article has some examples. – Doc Brown Nov 21 '18 at 19:14
12

This kind of microoptimization is usually avoided because it hurts code readability – and microoptimizations is the job of the compiler. But sometimes these techniques can be legitimately useful.

Often, instead of branching we can make use of how bit patterns interact. E.g. instead of testing if a boolean is set with a conditional, we could perhaps multiply the boolean with a value. Silly example:

int some_condition = ...;  // boolean, either 0 or 1
/* if (some_condition) {
 *   return x;
 * } else {
 *   return y;
 * }
 */
return some_condition * x + !some_condition * y;

If multiplication is assumed to be expensive, note that -1 is the all-ones bit pattern on a twos-complement system, so we might equivalently use:

return (-some_condition & x) | (-!some_condition & y);

It is sometimes possible to structure larger computations in a way so that some bit pattern (e.g. all-zeros or all-ones) propagates. This is especially useful when we have a list of conditions that are all cheap to evaluate. But e.g. C's || operator is a branching operator! It might then be faster to replace testA() || testB() || testC() with:

int ok = 0;
ok |= testA();
ok |= testB();
ok |= testC();

Whether any of this helps has to be benchmarked. On modern systems, the answer is almost universally “no”. Branches are not the problem, false branch prediction is. On your system, you might want to look at the assembly code and count instruction cycles (which should be listed in the CPU's manual). You can then get a feeling whether additional instructions save any cycles compared to a branch.

5

But if it returns 0 or -1, wouldn't you still need a branch to check which one it is and execute the according instructions?

Not necessarily. As written, the explanation leaves out what to do with the value of the expression once computed. With a number in hand, you can use it as the index for an array:

// Return one value for odd inputs and another for even.
int x_factor(int value)
{
  static int factors[] = {
    123,  // For odd values                                                                                                         
    456   // For even values
  };

  int index = (value % 2) == 0;
  return factors[index];
}

...or as part of a cleverly-written expression:

// Same as above.
int x_factor(int value)
{
  int multiplier = (value % 2) == 0;
  return (456 * multiplier) + (123 * (!multiplier));
}

As amon correctly points out in his answer, tricks like these can reduce readability and optimizations like this should rightly be left to the compiler. The thing is, you don't always have a compiler and, of course, someone has to figure this stuff out to write the compilers in the first place.

The logical next question would be why you have to do any of it at all. The answer to that lies in the pipelines processors use to make sure there are always instructions on hand to execute instead of sitting idle waiting for instruction fetches.

Some architectures are single-pipelined, meaning they keep fetching instructions and stuffing them into the pipe as long as they can know for sure what the program counter will look like after the instruction executes. This holds true for all classes of instruction except two: those involving conditional branching and those involving a jump or call to an address stored in a volatile location (register or memory). Encountering one of those instructions means the pipeline has to stop fetching because it has no idea how things will turn out until all prior instructions have been executed. That results in an empty pipeline and a CPU that has to be idle during instruction fetches until it fills back up. If you're trying to wring every bit of performance you can out of the processor or you have hard real-time requirements that require predictability of execution times, this is the last thing you want to happen.

Intel and others have worked around this problem by using multiple pipelines that do speculative fetching of instructions from both possible outcomes of the branch. Once the outcome has been determined, the pipe full of instructions on the "true" side of the branch gets used and the contents of the pipe from the "false" side is thrown away. That's a very clever solution, but it comes at a price: it takes more gates to implement the additional pipeline and decision making. More gates means more physical size, more power consumption and more heat. This is acceptable if you're building processors to be put in servers but not so much for something that will have to run on a handful of AA batteries in a small package.

  • There's only one kind of instruction that stalls the pipe, (conditional) branches are (conditional) jumps – Caleth Nov 22 '18 at 12:55
  • @Caleth Branches and a jumps have the same net effect (changing the program counter), but the similarity ends there. Processors with simple pipelines like the ARM7 in the GBA have to stall when the course of action depends on the outcome of yet-to-be-executed instructions. There's no way around that without a more-sophisticated pipeline that understands the dependencies. – Blrfl Nov 22 '18 at 14:17
  • ? In each case there are dependencies. It's certainly simpler to make a prediction when the possible targets are known, than to also predict the target, but both are possible. And it's simpler to prefetch (and conditionally discard) one path than prefetch both paths. Is that what you are getting at? – Caleth Nov 22 '18 at 16:01
  • @Caleth More to what I'm getting at is simple being a matter of what gets traded off. Fetch-one is simpler in terms of the hardware required but makes it harder for the programmer if the CPU is to be kept busy. Fetch-both is simpler for the programmer from having to avoid stall-causing branches but costs in hardware, power and heat. OP's platform is fetch-one, so that decision has been taken out of the picture and the question becomes what has to be done to get the most out of it. – Blrfl Nov 23 '18 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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