George V. Reilly

Decrementing Loops

The canonical for-loop in C and C++ is written thus, counting up i = 0, i = 1, …, i = N-1:

for (int i=0; i < N; i++) {
    // loop body

(In C, you have to declare int i before the for-loop.)

Let’s unpack that for-loop into an equivalent while-loop:

int i = 0;
while (i < N) {
    // loop body
    i = i + 1

In other words, we initialize i to zero. Then, before every execution of either loop, we check i < N. If i is still within bounds, we execute the loop body. Then we postin­cre­ment i. Then back to the top of the loop, checking i < N again. And so on, executing the loop N times, with i = 0, i = 1, …, i = N-1.

There’s a more efficient way to write that loop—if you don’t mind counting down from N-1 to 0:

for (int i=N; --i >= 0; ) {
    // loop body

Trans­form­ing it into the equivalent while-loop may make it clearer:

int i = N;
while (--i >= 0) {
    // loop body

We initialize i=N. Then, before every execution of either loop, we (a) pre­decre­ment i, that is, set i = i-1 and use the new value of i; then (b) check i >= 0. If the new value of i is still non-negative, the loop body is executed. This loop is also executed N times, with i = N-1, i = N-2, …, i = 1, i = 0.

In the count-up loop, the compiler has to emit an explicit comparison against N, which must be executed on every iteration of the loop. If N is not stored in a register (ia32 doesn’t have many), it will have to be fetched on each iteration. The count-up loop overhead then is a possible fetch of N, a comparison against N, and a postin­cre­ment.

For the count-down loop however, the compiler won’t emit an explicit comparison against zero, as the pre­decre­ment is enough to condition the CPU’s negative flag. If the result of the pre­decre­ment is a negative number, the sign bit will be set.

Using a count-down loop, you can shave one in­struc­tion off every iteration. Fur­ther­more, N is only read once and won’t occupy a register. The pre­decre­ment is un­avoid­able. For a tight loop, these savings may be important.

However, I would use this idiom sparingly.

blog comments powered by Disqus
Obfuscating Passwords in URLs in Python » « Review: Hide Me Among The Graves