In the C if-else statement, should the condition which is more likely to be true come first?

Question

I happened to write a if-else statement, the condition would be false at most time(check a static pointer is assigned or not). Which one would be better for the compiler to optimize? Or they are just equal?. The function would be called so many times, so it is critical to optimize its performance.

void foo() {
  static int * p = NULL;
  if (p == NULL) {
     p = (int *) malloc( SIZE * sizeof(int)); 
  }
  //do something here
} 

void foo() {
  static int * p = NULL;
  if (p != NULL) {
    //do something here 
  } else {
    p = (int *) malloc( SIZE * sizeof(int));  
    //do something
  }
}

Use `gcc file.c -S -o file.S` to generate the assembly language code for your C source. And observe the pattern of instruction generated. Also try compiling after enabling optimization flags `-O2`, and then see. — 0xF1, Dec 02 '13 at 09:39
I'd prefer the first one, not for speed (it's almost the same) but for the logic — Thomas Ayoub, Dec 02 '13 at 09:39
Aside from the sweating a `jz` vs `jnz` instruction, these two things are not even equivalent. You will have to *double* your non-null-case code effort in the second example, since everything being done in the non-null-case will have to be done following allocation in the null-case. Thus, to me, the only one of these that makes sense *at all* is the first one, and it has *nothing to do with performance*. — WhozCraig, Dec 02 '13 at 09:43
In general I wouldn't worry about these sort of optimization issues unless I was using a prehistoric compiler, but like @WhozCraig notes, your two examples aren't equivalent. — sashang, Dec 02 '13 at 09:46
@WhozCraig I think that it is most likely that the compiler will create same assembly there, just because the second one doensn't make sense (as NE does nothing) and it will converted into the same EQ as the first one (static bp), unless any optimization is disabled. — Jekyll, Dec 02 '13 at 09:46
If you are using gcc, you should take a look at the likely()/unlikely() macros. [1]: http://stackoverflow.com/questions/1668013/can-likely-unlikely-macros-be-used-in-user-space-code — Sevauk, Dec 02 '13 at 09:52
Ashamed to admit it, but you *could* eliminate the doubled-up code logic mentioned in my prior comment by fulfilling `p` via allocation, then invoking the function recursively. (and I'm going to positively kick myself for planting that idea in your head, just letting you know right now). — WhozCraig, Dec 02 '13 at 09:52

egur · Accepted Answer · 2013-12-02T11:30:17.900

5

Some compilers can allow the dev to specify which is condition is more likely or unlikely to occur. This is heavily used in the Linux kernel.

In gcc, there's the likely(x) or unlikely(x) macros. Example:

if (unlikely(p == NULL)) {
    p = malloc(10);
}

edited Dec 02 '13 at 11:30

answered Dec 02 '13 at 09:52

egur

7,830
2
27
47

Furthermore compilers with the PGO (Profile Guided Optimization) will do that automatically if you have a good test case. – Alexander Oh Dec 02 '13 at 09:58

score 2 · Answer 2 · answered Dec 02 '13 at 09:45

If the function is called often enough to not be evicted from the branch predictor, then the predictor will take care of everything for you, since it will learn very quickly which is the "likely" branch.

Some compilers allow you to decorate conditionals with prediction hints. Check your vendor's documentation, and add a hint if you can.

Specific platforms document the default predictor behaviour (e.g. see the Intel Optimization Manual for x86), but it's best left to your compiler to implement that via the aforementioned hints. In fact, you don't really have a choice, since you don't control your compilers code generation anyway, so the only last measure left to you would be to write the code in machine code yourself and implement the platform's advice on default prediction.

score 1 · Answer 3 · answered Dec 02 '13 at 09:41

At the end, it depends on the compiler and the optimization it does, which changes from compiler version, processor, compiler family...

My rule of thumb on this kind of subjects is to check on your actual platform by doing some extensive profiling. I usually also follow the rule "code first correctly, optimize later only if required". Trying to optimize upfront often leads to less readable code and design (and sometime, not even better performance).

score 0 · Answer 4 · answered Dec 02 '13 at 09:41

0

Conditions are checked in order from left to right, this is in the C standard, thus allowing for conditionals like

if( ptr != NULL && ptr->member == value )

This also means that it makes sense to place the condition which is most likely to be false first.

http://msdn.microsoft.com/en-us/library/2bxt6kc4.aspx

answered Dec 02 '13 at 09:41

DusteD

1,400
10
14

This is true for && operator while for || operator is true the opposite, as with OR operator no matter the others, when the first is 1 the condition is true. – Jekyll Dec 02 '13 at 09:49

Boris Ivanov · Answer 5 · 2013-12-02T10:13:57.017

0

If you looking for performance I wouldn't use malloc at all. Get Huge chunk of RAM and use it directly without allocation deallocation wrappers. Also consider using macros code will be bigger but performance also will increase.

#define ASSURE_PTR(a)      if (!a){ \
        a = (int *) malloc (SIZE * sizeof(int)); \
    }

edited Dec 02 '13 at 10:13

answered Dec 02 '13 at 09:42

Boris Ivanov

4,145
1
32
40

3

Premature optimization, on just about the lowest *possible* level. – Jongware Dec 02 '13 at 09:45
1

Though foo will be called too many times, malloc only be called once. It is critically necessary to optimize it here? – notbad Dec 02 '13 at 09:51
Make it as macros. Why u make call? – Boris Ivanov Dec 02 '13 at 10:02
Here "Do something" is really to do many things. So it maybe not easy to make macros here or even inline. – notbad Dec 02 '13 at 10:05

score 0 · Answer 6 · answered Dec 02 '13 at 09:43

If the function gets called often, any decent branch predictor would learn to predict the common path very quickly. Note that the code may be compiled differently than you expect since some compilers rely on static branch prediction, and may recognize this pattern.

In the C if-else statement, should the condition which is more likely to be true come first?

6 Answers6