2
$\begingroup$

Disclaimer: I'm not a compiler expert. I'm simply curious and come seeking enlightenment.

I've seen people claim that -- for efficiency -- for loops should generally use a zero comparison for termination. So rather than:

void blink1(int n) {
    for (int i=0; i<n; i++) {
        blink_led();
    }
}

you should write:

void blink2(int n) {
    for (int i=n; i>0; i--) {
        blink_led();
    }
}

I thought that was a little silly: why put the burden on the human if a compiler could interpret both cases as "blink_led() n times"?

But using Mr. Godbolt's Compiler Explorer, I now think I'm wrong. For all the compilers I tried, the "compare against zero" always produced a shorter loop. For example, x86-64 gcc 10.2 with -O3 optimization produced the following inner loops:

blink1:
    ...
.L3:
        xor     eax, eax
        add     ebx, 1
        call    blink_led
        cmp     ebp, ebx
        jne     .L3

vs

blink2:
    ...
.L12:
        xor     eax, eax
        call    blink_led
        sub     ebx, 1
        jne     .L12

So here's the question

This seems like such a common case.

Why can't (or why doesn't) the compiler notice that the effect of the for loop is simply "do this thing N times" -- whether counting up or counting down -- and optimize for that?

$\endgroup$
2
  • 1
    $\begingroup$ From Agner Fog, Optimizing code in C++: "Comparing an integer to zero is sometimes more efficient than comparing it to any other number. Therefore, it is slightly more efficient to make a loop count down to zero than making it count up to some positive value, n. But not if the loop counter is used as an array index. The data cache is optimized for accessing arrays forwards, not backwards." Note that this is only one observation among many other characteristics that can influence the optimization of a loop. $\endgroup$ – plop Aug 7 '20 at 17:18
  • 2
    $\begingroup$ By the way you took only GCC as example, but Clang and MSVC do perform that transformation $\endgroup$ – harold Aug 7 '20 at 17:36
2
$\begingroup$

What you read is total nonsense, except for the most primitive of compilers. First, comparison with an integer is as fast, possibly even faster than comparison with a constant. Second, a good optimising compiler will take a loop written using some common pattern and turn it into the best possible code; it may not recognise your obfuscated pattern and produce less good code for it.

And lastly, you shouldn’t replace readable with unreadable code unless there is an actual need for it. If you spend an hour making the change, it needs to produce 20 hours saved CPU time at least. When you are at that level, better algorithms are very likely to give better savings.

$\endgroup$
0
$\begingroup$

I think I agree mostly with @gnasher729, but those people what worry about "efficiency" would criticize using the for loop at all -- the "i" variable doesn't add anything ...

Why not:

void blink3(int n) {
    while (n-- > 0) {
       blink_led();
    }
}

I've added the "> 0" for a couple of reasons: 1) just in case somebody asks for a NEGATIVE amount of blinking, don't want to roll backward for 2 billion times. 2) it's a bit more obvious to the unitiated (maybe).

By the way, in contrived example, the "blink_led()" function is weird and fishy -- gonna probably wait around to be able to see it go on, then off. So "efficiency" is a bit off the table.

But, in general, for most things, efficiency is mostly about how quickly it can be coded and also (more importantly) how quickly it is understood.

$\endgroup$
1
  • $\begingroup$ Well, maybe this "contrived example" is blinking an IR LED at high speed as part of a communication link! :) But, naw, you're right -- blink_led() was an odd choice. (Welcome to cs, by the way!) $\endgroup$ – fearless_fool Aug 7 '20 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.