StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>At the very lowest level (in the hardware), yes, <strong>if</strong>s are expensive. In order to understand why, you have to understand how <a href="http://en.wikipedia.org/wiki/Pipeline_(computing)" rel="noreferrer">pipelines</a> work.</p> <p>The current instruction to be executed is stored in something typically called the <em>instruction pointer</em> (IP) or <em>program counter</em> (PC); these terms are synonymous, but different terms are used with different architectures. For most instructions, the PC of the next instruction is just the current PC plus the length of the current instruction. For most RISC architectures, instructions are all a constant length, so the PC can be incremented by a constant amount. For CISC architectures such as x86, instructions can be variable-length, so the logic that decodes the instruction has to figure out how long the current instruction is to find the location of the next instruction.</p> <p>For <em>branch</em> instructions, however, the next instruction to be executed is not the next location after the current instruction. Branches are gotos - they tell the processor where the next instruction is. Branches can either be conditional or unconditional, and the target location can be either fixed or computed.</p> <p>Conditional vs. unconditional is easy to understand - a conditional branch is only taken if a certain condition holds (such as whether one number equals another); if the branch is not taken, control proceeds to the next instruction after the branch like normal. For unconditional branches, the branch is always taken. Conditional branches show up in <code>if</code> statements and the control tests of <code>for</code> and <code>while</code> loops. Unconditional branches show up in infinite loops, function calls, function returns, <code>break</code> and <code>continue</code> statements, the infamous <code>goto</code> statement, and many more (these lists are far from exhaustive).</p> <p>The branch target is another important issue. Most branches have a fixed branch target - they go to a specific location in code that is fixed at compile time. This includes <code>if</code> statements, loops of all sorts, regular function calls, and many more. <em>Computed</em> branches compute the target of the branch at runtime. This includes <code>switch</code> statements (sometimes), returning from a function, virtual function calls, and function pointer calls.</p> <p>So what does this all mean for performance? When the processor sees a branch instruction appear in its pipeline, it needs to figure out how to continue to fill up its pipeline. In order to figure out what instructions come after the branch in the program stream, it needs to know two things: (1) if the branch will be taken and (2) the target of the branch. Figuring this out is called <a href="http://en.wikipedia.org/wiki/Branch_prediction" rel="noreferrer">branch prediction</a>, and it's a challenging problem. If the processor guesses correctly, the program continues at full speed. If instead the processor guesses <em>incorrectly</em>, it just spent some time computing the wrong thing. It now has to flush its pipeline and reload it with instructions from the correct execution path. Bottom line: a big performance hit.</p> <p>Thus, the reason why if statements are expensive is due to <strong>branch mispredictions</strong>. This is only at the lowest level. If you're writing high-level code, you don't need to worry about these details at all. You should only care about this if you're writing extremely performance-critical code in C or assembly. If that is the case, writing branch-free code can often be superior to code that branches, even if several more instructions are needed. There are some cool bit-twiddling tricks you can do to compute things such as <code>abs()</code>, <code>min()</code>, and <code>max()</code> without branching.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload