Optimization

I'd always heard that compiler optimization1 is uniformly risk-positive -- i.e. turning on optimizations might make your code not run, but never the other way around.

On a seemingly-unrelated note, I'd always heard that you can't do proper tail calls in C, because it is so tightly wedded to the function call paradigm -- with the result that recursive algorithms can't be safely used in C.

The other day, I discovered that, taken together, both of the above statements are under some circumstances false.

Consider the following program:

#include <stdio.h>

int x;

unsigned long long int foo(unsigned long long int a) {
if(a % 2 == 0) ++x;
return a > 0 ? foo(--a) : a;
}

int main() {
unsigned long long int i = 2;
while(1) {
printf("Recursing %llu levels (got x = %d)\n", i, x);
x = 0;
foo(i);
i *= 2;
}
return(0);
}

Formally, you can see that foo() is recursive, so as the variable i gets bigger and bigger, the program should run forever, taking twice as long each time through. In practice, if you compile this program normally, the stack will overflow because it can only hold so many function calls, and the program will abruptly crash after a fraction of a second.

With gcc, turn on "-foptimize-sibling-calls" (which happens by default if you use "-O2" or higher), and the compiler will employ tail call optimization, meaning that the recursive bit (call a function and return the result) gets turned into an iterative operation (jump to a new function and let it return its own result as if it was a simple continuation of this function). As a result, that recursive call at the end of foo() doesn't take up an extra slot in the call stack, so the program really will run forever, exactly like it should. (Eventually the variable i will overflow and wrap around, so you'll get the wrong number, but the program will never crash. And since I used a 64-bit integer (that's what the "long long" thing means), you probably won't be around for the billions of years it will take your computer to actually count that high.)

1: For non-programmers, a compiler is the program that turns a programming language source code -- something that usually looks like written instructions or mathematical formulas -- into the binary instructions that a CPU can run as a program. Compiler optimizations are tricks the compiler can use, that result in binary instructions that don't exactly reflect what you wrote in the source code, but should have the same effect and run faster or take less space. C is one of the older programming languages, and one of the most widespread.

About this Entry

This page contains a single entry by Milligan published on August 10, 2008 4:24 PM.

Some Provocative Bits was the previous entry in this blog.

Overheard is the next entry in this blog.

Find recent content on the main index or look in the archives to find all content.

Pages

Powered by Movable Type 4.31-en