What exactly is code branching

Question

What is code branching? I've seen it mentioned in various places, especially with bit twiddling, but never really thought about it?

How does it slow a program down and what should I be thinking about while coding?

I see mention of if statements. I really don't understand how such code can slow down the code. If condition is true do following instructions, otherwise jump to another set of instructions? I see the other thread mentioning "branch prediction", maybe this is where I'm really lost. What is there to predict? The condition is right there and it can only be true or false.

I don't believe this to be a duplicate of this related question. The linked thread is talking about "Branch prediction" in reference to an unsorted array. I'm asking what is branching and why prediction is required.

If I understand correctly this has to two w/ bit twiddling tricks to save you a branch like this version of `abs`: http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs — Shafik Yaghmour, Jul 24 '13 at 16:06
You might want to view this for a lengthy discussion http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array/11227902#11227902 — Paul Renton, Jul 24 '13 at 16:06
The title of that post is a little misleading, but I see my answer is there. Thanks. — Twifty, Jul 24 '13 at 16:09
As far as the update you provided goes, the answer is a little difficult to simply. It's best if you research the general way in which the CPU pipeline works in modern processors. I'm tempted to provide an anlogy here, but it would be too long for a comment. As for branch prediction, yeah, the if condition is only going to evaluate to true or false. That's true. But sometimes you can use some statistics-gathering and theory to make the computer categorize different styles of if conditions, and for each style, basically look up whether its more commonly true or false and thus predict which — Panzercrisis, Jul 24 '13 at 16:26
`What is there to predict? The condition is right there and it can only be true or false.` What do you mean "right there"? Right there in the program code instructions? No, it's usually not... — Lightness Races in Orbit, Jul 24 '13 at 16:29
The problem here is that you're assuming that executing an "if" statement is _really easy_, because you're used to that in high-level languages. But, for transistors, it is not so easy. More than that, if your computer really simply executed your C++ program line by line, then your computer would be abominably slow. That's why. — Lightness Races in Orbit, Jul 24 '13 at 16:30
@Waldermort: It was already written up, in [the excellent answer to which you were linked by Paul](http://stackoverflow.com/a/11227902/560648), 31 minutes ago. In fact, your question has been marked as a duplicate of that one, for a full 12 minutes. It has nothing to do with assembly itself, but with how machine code is executed at the most basic level. I recognise that _you_ "don't see what the problem is", but that's because you don't understand how computers work; it's _not_ because there _isn't_ a problem after all. — Lightness Races in Orbit, Jul 24 '13 at 16:38
@Panzercrisis Thanks for that analogy. If I'm understanding this right, the hardware is trying to make a list of instructions and somewhere in that list is an if statement. At the time of making the list it doesn't know the condition, so it tries to guess. Am I right in assuming once this list is created it cannot be changed, but must be discarded and started again from scratch? — Twifty, Jul 24 '13 at 16:48
This question is not a duplicate of the question which has been claimed to be a duplicate. They ask completely different things. Remember, close voters, what counts is whether the **question** is a duplicate. — David Heffernan, Jul 24 '13 at 17:01

David Heffernan · Answer 1 · 2013-07-24T19:41:35.293

The most simple example of a branch is an if statement:

if (condition)
    doSomething();

Now if condition is true then doSomething() is executed. If not then the execution branches, by jumping to the statement that follows the end of the if.

In very simple machine pseudo code this might be compiled to something along these lines:

TEST condition
JZ   label1       ; jump over the CALL if condition is 0
CALL doSomething
@@label1

The branch point is the JZ instruction. The subsequent execution point depends on the outcome of the test of condition.

Branching affects performance because modern processors predict the outcome of branches and perform speculative execution, ahead of time. If the prediction turns out to be wrong then the speculative execution has to be unwound.

If you can arrange the code so that prediction success rates are higher, then performance is increased. That's because the speculatively executed code is now less of an overhead since it has already been executed before it was even needed. That this is possible is down to the fact that modern processors are highly parallel. Spare execution units can be put to use performing this speculative execution.

Now, there's one sort of code that never has branch prediction misses. And that is code with no branches. For branch free code, the results of speculative execution are always useful. So, all other things being equal, code without branches executes faster than code with branches.

Example where bit twiddling comes in: http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs — Shafik Yaghmour, Jul 24 '13 at 16:05

Panzercrisis · Accepted Answer · 2013-07-29T15:43:22.227

Essentially imagine an assembly line in a factory. Imagine that, as each item passes through the assembly line, it will go to employee 1, then employee 2, on up to employee 5. After employee 5 is done with it, the item is finished and is ready to be packaged. Thus all five employees can be working on different items at the same time and not having to just wait around on each other. Unlike most assembly lines though, every single time employee 1 starts working on a new item, it's potentially a new type of item - not just the same type over and over.

Well, for whatever weird and imaginative reason, imagine the manager is standing at the very end of the assembly line. And he has a list saying, "Make this item first. Then make that type of item. Then that type of item." And so on. As he sees employee 5 finish each item and move on to the next, the manager then tells employee 1 which type of item to start working on, looking at where they are in the list at that time.

Now let's say there's a point in that list - that "sequence of computer instructions" - where it says, "Now start making a coffee cup. If it's nighttime when you finish making the cup, then start making a frozen dinner. If it's daytime, then start making a bag of coffee grounds." This is your if statement. Since the manager, in this kind of fake example, doesn't really know what time of day it's going to be until he actually sees the cup after it's finished, he could just wait until that time to call out the next item to make - either a frozen dinner or some coffee grounds.

The problem there is that if waits until the very last second like that - which he has to wait until to be absolutely sure what time of day it'll be when the cup is finished, and thus what the next item's going to be - then workers 1-4 are not going to be working on anything at all until worker 5 is finished. That completely defeats the purpose of an assembly line! So the manager takes a guess. The factory is open 7 hours in the day and only 1 hour at night. So it is much more likely that the cup will be finished in the daytime, thus warranting the coffee grounds.

So as soon as employee 2 starts working on the coffee cup, the manager calls out the coffee grounds to the employee 1. Then the assembly line just keeps moving along like it had been, until employee 5 is finished with the cup. At that time the manager finally sees what time of day it is. If it's daytime, that's great! If it's nighttime, everything started on after that coffee cup must be thrown away, and the frozen dinner must be started on. ...So essentially branch prediction is where the manager temporarily ventures a guess like that, and the line moves along faster when he's right.

Pseudo-Edit:

It is largely hardware-related. The main search phrase would probably be "computer pipeline cpu". But the list of instructions is already made up - it's just that that list of instructions has branches within it; it's not always 1, 2, 3, etc. But as stage 5 of the pipeline is finishing up instruction 10, stage 1 can already be working on instruction 14. Usually computer instructions can be broken up like that and worked on in segments. If stages 1-n are all working on something at the same time, and nothing gets trashed later, that's just faster than finishing one before starting another.

score 0 · Answer 3 · answered Jul 24 '13 at 16:11

Any jump in your code is a branch. This happens in if statements function calls and loops.

Modern CPUs have long pipelines. This means the CPUs is processes various parts of multiple instructions at the same time. The problem with branches is that the pipeline might not have started processing the correct instructions. This means that the speculative instructions need to be thrown out and the processor will need to start processing the instructions from scratch.

When a branch is encountered, the CPU tries to predict which branch is going to be used. This is called branch prediction.

Most of the optimizations for branch prediction will be done by your compiler so you do not really need to worry about branching.

This probably falls into the category of only worry about branch optimizations if you have profiled the code and can see that this is a problem.

score 0 · Answer 4 · answered Jul 24 '13 at 16:12

0

A branch is a deviation from normal control flow. Processors will execute instructions sequentially, but in a branch, the program counter is moved to another place in memory (for example, a branch depending on a condition, or a procedure call).

answered Jul 24 '13 at 16:12

hdante

7,685
3
31
36

What exactly is code branching

4 Answers4

Linked