GCC optimization differences in recursive functions using globals

Question

The other day I ran into a weird problem using GCC and the '-Ofast' optimization flag. Compiling the below program using 'gcc -Ofast -o fib1 fib1.c'.

#include <stdio.h>

int f1(int n) {
    if (n < 2) {
        return n;
    }
    int a, b;
    a = f1(n - 1);
    b = f1(n - 2);
    return a + b;
}

int main(){
    printf("%d", f1(40));
}

When measuring execution time, the result is:

peter@host ~ $ time ./fib1
102334155
real    0m0.511s
user    0m0.510s
sys     0m0.000s

Now let's introduce a global variable in our program and compile again using 'gcc -Ofast -o fib2 fib2.c'.

#include <stdio.h>

int global;

int f1(int n) {
    if (n < 2) {
        return n;
    }
    int a, b;
    a = f1(n - 1);
    b = f1(n - 2);

    global = 0;

    return a + b;
}

int main(){
    printf("%d", f1(40));
}

Now the execution time is:

peter@host ~ $ time ./fib2
102334155
real    0m0.265s
user    0m0.265s
sys     0m0.000s

The new global variable does not do anything meaningful. However, the difference in execution time is considerable.

Apart from the question (1) what the reason is for such behavior, it also would be nice if (2) the last performance could be achieved without introducing meaningless variables. Any suggestions?

Thanks Peter

Answer 1

I believe you hit some very clever and very weird gcc (mis-?)optimization. That's about as far as I got in researching this.

I modified your code to have an #ifdef G around the global:

$ cc -O3 -o foo foo.c && time ./foo
102334155

real    0m0.634s
user    0m0.631s
sys     0m0.001s
$ cc -O3 -DG -o foo foo.c && time ./foo
102334155

real    0m0.365s
user    0m0.362s
sys     0m0.001s

So I have the same weird performance difference.

When in doubt, read the generated assembler.

$ cc -S -O3 -o foo.s -S foo.c
$ cc -S -DG -O3 -o foog.s -S foo.c

Here it gets truly bizarre. Normally I can follow gcc-generated code pretty easily. The code that got generated here is just incomprehensible. What should be pretty straightforward recursion and addition that should fit in 15-20 instructions, gcc expanded to a several hundred instructions with a flurry of shifts, additions, subtractions, compares, branches and a large array on the stack. It looks like it tried to partially convert one or both recursions into an iteration and then unrolled that loop. One thing struck me though, the non-global function had only one recursive call to itself (the second one is the call from main):

$ grep 'call.*f1' foo.s | wc
      2       4      18

While the global one one had:

$ grep 'call.*f1' foog.s | wc
     33      66     297

My educated (I've seen this many times before) guess? Gcc tried to be clever and in its fervor the function that in theory should be easier to optimize generated worse code while the write to the global variable made it sufficiently confused that it couldn't optimize so hard that it led to better code. This happens all the time, many optimizations that gcc (and other compilers too, let's not single them out) uses are very specific to certain benchmarks they use and might not generate faster running code in many other cases. In fact, from experience I only ever use -O2 unless I've benchmarked things very carefully to see that -O3 makes sense. It very often doesn't.

If you really want to research this further, I'd recommend reading gcc documentation about which optimizations get enabled with -O3 as opposed to -O2 (-O2 doesn't do this), then try them one by one until you find which one causes this behavior and that optimization should be a pretty good hint for what's going on. I was about to do this, but I ran out of time (must do last minute christmas shopping).

Answer 2

On my machine (gcc (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010) I've got this:
time ./fib1 0,36s user 0,00s system 98% cpu 0,364 total
time ./fib2 0,20s user 0,00s system 98% cpu 0,208 total

From man gcc:

-Ofast
Disregard strict standards compliance. -Ofast enables all -O3 optimizations. It also enables optimizations that are not valid for all standard-compliant programs. It turns on -ffast-math and the Fortran-specific -fno-protect-parens and -fstack-arrays.

Not so safe option, let's try -O2:
time ./fib1 0,38s user 0,00s system 99% cpu 0,377 total
time ./fib2 0,47s user 0,00s system 99% cpu 0,470 total

I think, that some of aggressive optimizations weren't applied to fib1, but were applied to fib2. When I switched -Ofast for -O2 - some of optimizations weren't applied to fib2, but were applied to fib1.

Let's try -O0:
time ./fib1 0,81s user 0,00s system 99% cpu 0,812 total
time ./fib2 0,81s user 0,00s system 99% cpu 0,814 total

They are equal without optimizations.
So introducing global variable in recursive function can break some optimizations on one hand and improve other optimizations on other hand.

Answer 3

This results from inline limits kicking in earlier in the second version. Because the version with the global variable does more. That strongly suggests that inlining makes run-time performance worse in this particular example.

Compile both versions with -Ofast -fno-inline and the difference in time is gone. In fact, the version without the global variable runs faster.

Alternatively, just mark the function with __attribute__((noinline)).