C is Lower Level Than You Think

Here's a bit of code that many new C programmers have written:

for (int i = 0; i < strlen(s); i++) {
    ...
}

The catch is that strlen is executed in each iteration, and as it involves looking at every character in search of a null, it's an unintentional n-squared loop. The right solution is to assign the length of the string to a local variable before the loop and check that.

"That's just busywork," says our novice coder, "modern compilers are smart enough to do that kind of trivial optimization."

As it turns out, this is much trickier to automate than may first appear. It's only safe if it can be guaranteed that the body of the loop doesn't modify the string, and that guarantee in C is hard to come by. All bets are off after a single external function call, because memory used by the string could be referenced somewhere else and modified by that call. Most bets are off after a single store through a pointer inside the loop, because it could be pointing to the string passed to strlen. Actually, it's even worse than that: any time you write a value to memory you could be changing the value of any variable in memory. Determining that a[i] can be cached in a register across even a single memory write is unsolvable in the general case.

(To control the chaos, the C99 standard includes a way to assert that a pointer is used in a restricted manner. It's only an affirmation on the part of the programmer, and is not checked by the compiler. If you get this wrong the results are undefined.)

The GCC C compiler, as it turns out, will move the strlen call out of the loop in some cases. Don't get too excited, because now you've got an algorithm that's either n-squared or linear depending on the compiler. You could also say the hell with all of this and write a naive optimizer that always lifts the strlen out of a for-loop expression. Great! It works in the majority of real-life cases. But now if you go and write an algorithm, even a contrived one, that's dependent on the string length changing inside the loop...uh oh, now the compiler is transforming your valid intent into code that doesn't work. Do you want this kind of nonsense going on behind the scenes?

The clunky "manually assign the length to a constant" solution is a better one across the board. You're clearly stating that it doesn't matter what external functions do or that there are other writes to memory. You've already grabbed the value you want and that's that.

(If you liked this, you might enjoy How much memory does malloc(0) allocate?)

permalink November 25, 2013

C is Lower Level Than You Think

previously

archives