Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

So I have been reading Inside the Machine by Jon Stokes. It is a FANTASTIC book, and it has got me thinking about the effects of programming on processors...

Given a branch unit in a CPU and a complex conditional statement that involves a procedure call (If IsTodayAHoliday( Now ) > 0 Then), is it faster to stick the results of that procedure call in a variable just before the IF statement? In terms of static and dynamic branch prediction, it seems logical that having the decision value before the branch unit has to evaluate causes the prediction algorithms to execute flawlessly. Is this true?

share|improve this question

5 Answers 5

Mabye, but you're talking about micro-optimizing. This is usually better left to the compiler.

share|improve this answer
    
But wouldn't this be good to know if you were writing a compiler? :) –  maple_shaft Jun 17 '11 at 17:43

The best answer I can think of is something I've seen repeated over and over:

Don't prematurely optimize.

The longer version of that is: The compiler (presumably) knows much more about the target architecture than you do. You should write your code to be correct and maintainable, if the underlying hardware changes, you don't want to have your code too tightly tied to a particular hardware.

For some architectures (Cell/BE for example) the penalty for a pipeline stall on a missed branch prediction is much higher than the cost of computing preparing both branches and making an unconditional jump based on the result of the computation... but I imagine this would be exactly the wrong thing to do on other hardware.

Also from my experience in compiler optimization, simpler, more recognizable patterns are much more likely to be optimized (the XOR swap vs temp variable swap comes to mind).

Hope this helps.

share|improve this answer
    
Well said. Thank you. The compiler definitely knows best! –  user28163 Jun 17 '11 at 17:10
    
How do you make an unconditional jump based on a condition (unless IsTodayAHoliday returns an address-offset...)? Also, what does that have to do with the question? –  BlueRaja - Danny Pflughoeft Jun 17 '11 at 19:00
    
@BlueRaja It's done by computing both sides of a the branch, using bit manipulation to clear out the invalid answer, removing the branch and jumping either to the next instruction or beyond the branch based on your answer. cas.mcmaster.ca/~anand/papers/AnandKahlMultiLoop.pdf should describe it in gory detail. Why it's relevant is that this optimization would be entirely the wrong way to structure your code for any other architecture that I can think of off the top of my head. –  Stephen Jun 17 '11 at 19:33

If you're using any language higher than assembler, assume the compiler would be smart enough to store the result of the procedure call in the appropriate place.

If you get into a spot where you need to wring a bit of performance out of a tiny piece of code in a tight loop, then try both options and do some experiments (profiling) to see which is faster in the real world. Then document (in comments) why you did what you did for the next poor sap.

share|improve this answer

The way I understand it, where the test value is stored will make no difference to branch prediction. And whether you have the call within the if statement, or store the result in the temporary variable, probably makes no difference to the generated code anyway - optimisers are pretty good at avoiding unnecessary memory accesses.

What affects branch prediction accuracy is which direction you branch. The following might have different performance.

while (condition ())   {  whatever ();  }

do {  whatever (); }  while (condition ());

One has a forward conditional jump, one has a backward conditional jump. Except that typical compilers are clever enough that they'll probably resolve that issue by ordering the object code differently from the source. Also, processors learn expected branch directions, so you'll probably only see a difference for the first iteration of a loop anyway.

In short, don't worry about it.

For pure curiosity purposes, you might want to look at some of Agner Fogs work - but don't expect light reading.

share|improve this answer
    
Wow...Agner.org is intense. Thank you. I can see that the compiler should optimize the issue. –  user28163 Jun 17 '11 at 18:04

If you're talking about the difference between:

if (isTodayAHoliday(now) > 0) { ... }

And:

int holiday = isTodayAHoliday(now);
if (holiday > 0) { ... }

Then the answer is simple: there is absolutely no difference in the machine code.

Remember that the CPU knows nothing about functions or expressions. The branch instruction doesn't take a function or an expression, it takes a value to compare to zero (or whatever). However you express it in the high-level language, the compiler is going to have to emit code which computes that value, puts it in a register, and then has the branch instruction.

share|improve this answer
1  
+1: This is correct, and also totally easy to verify: write the code and look at the generated assembly (and yes, I tried it -- even with optimisations turned off the generated assembly is identical except the version with the variable reserves some extra stack space). –  John Bartholomew Jun 17 '11 at 17:27
    
+1 for correct answer, I get the feeling that most voters/answers didn't understand the question –  BlueRaja - Danny Pflughoeft Jun 17 '11 at 18:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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