fib|⇒ gcc -O4 fib.c -o fib
fib|⇒ time ./fib
./fib 0.65s user 0.01s system 100% cpu 0.657 total
fib|⇒ gcc -O3 fib.c -o fib
fib|⇒ time ./fib
./fib 0.66s user 0.00s system 100% cpu 0.657 total
fib|⇒ gcc -O2 fib.c -o fib
fib|⇒ time ./fib
./fib 1.54s user 0.00s system 100% cpu 1.535 total
fib|⇒ gcc -O1 fib.c -o fib
fib|⇒ time ./fib
./fib 0.00s user 0.00s system 0% cpu 0.001 total
For some reason, it hates the O1 flag. Printing the result brings it close to the result without the optimization.
I just took a look at the output of gcc on -O1,-O2,-O3,and -Os (using the -S flag to output assembler.) It appears that with -O1 or -Os enabled, gcc turns the double recursion into single recursion. This makes the algorithm scale O(n) instead of O(fib(n)); i.e. much much faster. (Weirdly, -O2 and -O3 look to be double-recursing, but I didn't check closely. May be that gcc's smarter than me.)
It _also_ notices you're not using the result of fibonacci(40) and that it's a pure function, so it skips it. If you look at any optimized main function it's pretty much "set return code to 0 and get out of here."
To avoid this problem I've changed main to "return fibonacci(40)".
Now optimization becomes interesting. At -O3 main becomes 4 calls to fib(36), fib(35), fib(38), and fib(37). Crazy huh? It looks like it's unrolled fib(40) a few steps! At -Os I lost track of what's going on, but it starts with a call to fib(38) too. -O1 plays it pretty straight, and is what I'd recommend looking at for readable assembly.
-O2 and -O3 are easily the fastest. Something very clever is going on there.
One of the reasons I get why people advise against certain levels of optimization without understanding its implications. As I write few lines of C code, usually I don't bother with deep understanding of all the concepts of compiler optimization.
Comments
Good catch.
fib|⇒ gcc -O4 fib.c -o fib fib|⇒ time ./fib ./fib 0.65s user 0.01s system 100% cpu 0.657 total fib|⇒ gcc -O3 fib.c -o fib fib|⇒ time ./fib ./fib 0.66s user 0.00s system 100% cpu 0.657 total fib|⇒ gcc -O2 fib.c -o fib fib|⇒ time ./fib ./fib 1.54s user 0.00s system 100% cpu 1.535 total fib|⇒ gcc -O1 fib.c -o fib fib|⇒ time ./fib ./fib 0.00s user 0.00s system 0% cpu 0.001 total
For some reason, it hates the O1 flag. Printing the result brings it close to the result without the optimization.
I just took a look at the output of gcc on -O1,-O2,-O3,and -Os (using the -S flag to output assembler.) It appears that with -O1 or -Os enabled, gcc turns the double recursion into single recursion. This makes the algorithm scale O(n) instead of O(fib(n)); i.e. much much faster. (Weirdly, -O2 and -O3 look to be double-recursing, but I didn't check closely. May be that gcc's smarter than me.)
It _also_ notices you're not using the result of fibonacci(40) and that it's a pure function, so it skips it. If you look at any optimized main function it's pretty much "set return code to 0 and get out of here."
To avoid this problem I've changed main to "return fibonacci(40)".
Now optimization becomes interesting. At -O3 main becomes 4 calls to fib(36), fib(35), fib(38), and fib(37). Crazy huh? It looks like it's unrolled fib(40) a few steps! At -Os I lost track of what's going on, but it starts with a call to fib(38) too. -O1 plays it pretty straight, and is what I'd recommend looking at for readable assembly.
-O2 and -O3 are easily the fastest. Something very clever is going on there.
Moral of the story? Use -S! :)O1 probably sees you don't use the result or have side effects in fibonacci(40) and optimizes the call away...
One of the reasons I get why people advise against certain levels of optimization without understanding its implications. As I write few lines of C code, usually I don't bother with deep understanding of all the concepts of compiler optimization.