5

I will try to be as clear as I can with my question (not easy...it's not that clear for me as well). Suppose you have a set of IF...THEN instructions with multiple operands, for example 

IF ((a==0) && (b==1) && (c==1)) THEN x=1
ELSE IF ((a==0) && (b==0) && (c==1)) THEN x=2-

and so on

Suppose I could replace all those IFs with a single mathematical function like x = a * n1 + b * n2 + c * n3 (this is just to give you an idea, in real it's more complex, but also the IFs and operands are many more)

The function comes from a previously trained artificial neural network.

My gut feeling is that when it comes to execution, the function should take lots less time than the IFs, but it's just a gut feeling that comes from my old background in assembly where they taught us that a conditional instruction takes way more time than an arithmetical one.

Can you confirm this? maybe even provide me some link where I could find an explanation?

Thank you in advance guys!

Karthikeyan
  • 1,119
  • 1
  • 15
  • 33
Maxyone
  • 47
  • 7
  • I think your gut feeling is right. I have followed a few optimization questions here on SO about surprising results from eliminating branches. – Peter - Reinstate Monica Apr 06 '16 at 11:14
  • https://en.wikipedia.org/wiki/Branch_predictor and the articles it links to will provide a start. The relative gains depend on complexity of the function and versus possible branches but, with modern processors, pipelining and branch predictors are often relevant. – Peter Apr 06 '16 at 11:25
  • 2
    Maybe you ought to check first that your compiler [cannot already do this](http://stackoverflow.com/questions/26124620/why-does-msvc-emit-a-useless-movsx-before-performing-this-bit-test) before you fubar your program. And of course *always* verify first that it is actually *can* make a difference, use a profiler. Programmer's dictum is to measure three times, cut once. – Hans Passant Apr 06 '16 at 11:25

1 Answers1

4

Your gut feeling is correct.

The problem is that modern processors have a pipeline, and in the pipeline the next x instructions are loaded sequentially ready for execution. If you have a branch, an if statement, then the processor doesn't know which code path you're going to be taking next, and so it guesses using the branch predictor, but if it gets it wrong it has to throw out all of the pipeline and start again down the correct branch.

Branch predictors in modern processors are quite good, but if you have something that has a 50/50 chances of going one way or the other, you are going to have a lot of pipeline stalls.

This is why eliminating if statements are good, especially in tight loops.

This seems to have some good explanation: http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

Salgar
  • 7,687
  • 1
  • 25
  • 39