Inherent inefficiency in domestic "for" loop?

[Frederick Gotham]

Is the domestic usage of the C "for" loop inefficient when it comes to
simple incrementation? Here's a very simple program that prints out the
bit-numbers in a byte.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
unsigned i;

for( i = 0; i != CHAR_BIT; ++i )
{
printf( "Bit Index %u\n", i );
}

system("PAUSE");
}


(Feel free to substitute "i != CHAR_BIT" with "i < CHAR_BIT".)


If I try to replicate that using "goto", I get the following:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
unsigned i;


Loop_Enter:

i = 0;

Loop_Condition:

if ( !(i != CHAR_BIT) ) goto Loop_End;

Loop_Body:

printf( "Bit Index %u\n", i );

Loop_Continue:

++i;
goto Loop_Condition;

Loop_End:

;


system("PAUSE");
}


However, we can see that the very first conditional test is redundant --
it would be better to test the condition AFTER each iteration, rather
than before. Something like:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
unsigned i;


Loop_Enter:

i = 0;

Loop_Body:

printf( "Bit Index %u\n", i );


Loop_Continue:

++i;

Loop_Condition:

if ( i != CHAR_BIT ) goto Loop_Body;

Loop_End:

;


system("PAUSE");
}


If we compare the execution of both code snippets, we can see:


Snippet 1: Tests the condition 9 times
Snippet 2: Tests the condition 8 times


Is the widely used C method of simple loop incrementation inherently
inefficient? At first glance, it appears so to me.


(Yes, I realise that most compilers will "unroll" that loop, so lets
pretend we're working with a more complicated loop whose amount of
iterations isn't determined until runtime.)

 

[Ben Pfaff]

Is the domestic usage of the C "for" loop inefficient when it comes to
simple incrementation? Here's a very simple program that prints out the
bit-numbers in a byte.
[...]

However, we can see that the very first conditional test is redundant --
it would be better to test the condition AFTER each iteration, rather
than before. Something like:
[...]

Is the widely used C method of simple loop incrementation inherently
inefficient? At first glance, it appears so to me.

Only if the loop always executes at least once. In the more
general case where you have something like
for (i = start; i < end; i++)
then you do want the test before the first iteration.

I would never translate a loop into the awful form of labels +
gotos that you suggest. Use a do { ... } while loop if you
really want to avoid the test on the first iteration. But this
is usually a pointless micro-optimization.

Also, I have no idea why you refer to this as the "domestic" for
loop. The word does not make sense in this context.

 

[Alf P. Steinbach]

* Ben Pfaff -> Someone:

Also, I have no idea why you refer to this as the "domestic" for
loop. The word does not make sense in this context.

It seems that some AI story-generating programs are on the loose.
They're used by spammers and some Usenet posters, I guess with some
human fixup added. Some of the "poetry" that turns up in [no.test] is
amazing.

 

[Gordon Burditt]

Is the domestic usage of the C "for" loop inefficient when it comes to

simple incrementation?

It's equally inefficient if you outsource it.

However, we can see that the very first conditional test is redundant --

It is *NOT* redundant if you're going to invoke this:

>(Yes, I realise that most compilers will "unroll" that loop, so lets
>pretend we're working with a more complicated loop whose amount of
>iterations isn't determined until runtime.)

it would be better to test the condition AFTER each iteration, rather
than before.

If you are speaking in general, rather than with a specific example,
anything can be made to execute in 0 time and 0 bytes if it doesn't
have to give the correct result. A for loop is *supposed* to, under
the right conditions, execute 0 iterations. Especially when the
loop variable is being used as an array index, being able to loop
for 0 iterations is useful.

If we compare the execution of both code snippets, we can see:

Snippet 1: Tests the condition 9 times
Snippet 2: Tests the condition 8 times

Condition testing is not the only thing that takes time. And due to
specialized instructions for looping, it may be more efficient
to use the 9th test.

Is the widely used C method of simple loop incrementation inherently
inefficient? At first glance, it appears so to me.

You haven't demonstrated that. For the C method and your suggested
method, count branches. Which is more expensive by that measure?

(Yes, I realise that most compilers will "unroll" that loop, so lets
pretend we're working with a more complicated loop whose amount of
iterations isn't determined until runtime.)

Gordon L. Burditt

 

[Richard Tobin]

However, we can see that the very first conditional test is redundant --

In cases like this the compiler can see it too.

-- Richard

 

[Frederick Gotham]

Alf P. Steinbach posted:

* Ben Pfaff -> Someone:

Also, I have no idea why you refer to this as the "domestic" for
loop. The word does not make sense in this context.

It seems that some AI story-generating programs are on the loose.
They're used by spammers and some Usenet posters, I guess with some
human fixup added. Some of the "poetry" that turns up in [no.test] is
amazing.

My original post in this thread is genuine.

I program in C and C++.

For a while now, I've been contemplating whether a "for" loop performs
one more evaluation than it should (when there'll always be at least one
iteration.)

My original post wasn't any sort of attack or diatribe on the programming
language either -- simply an expression of my pondering.

I'd be happy if you'd like to discuss the topic of this thread sincerely,
and would ask you to take anything orthogonal to the topic elsewhere --
particularly discussion alleging my original post to have some
association with spam.

 

[Frederick Gotham]

Gordon Burditt posted:

A for loop is *supposed* to, under
the right conditions, execute 0 iterations.

Yes, exactly. But about 90% of the time, we're dealing with a loop which
will always execute at least once. For this 90% of the time, there's one
extra redudant evaluation performed.

I don't think the "for" loop should have been shaped to accomodate the 10%
of the time where we might not want the loop to run at all. If anything,
there should have been another kind of loop availabe, analogous as to how a
"while loop" has a sister "do loop".

Even something like a "do for" loop would be nice:

unsigned i;

do for( i = 0; i != some_value; ++i)
{
/* Body */
}

 

[Frederick Gotham]

Ben Pfaff posted:

Also, I have no idea why you refer to this as the "domestic" for
loop. The word does not make sense in this context.

In using the word "domestic", I refer to the widespread, accepted way of
using a "for" loop to perform simple incremental loops.

 

[Gryff Stokoe]

G'day,

Is the domestic usage of the C "for" loop inefficient when it comes to
simple incrementation? Here's a very simple program that prints out the
bit-numbers in a byte.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
unsigned i;

for( i = 0; i != CHAR_BIT; ++i )
{
printf( "Bit Index %u\n", i );
}

system("PAUSE");
}


(Feel free to substitute "i != CHAR_BIT" with "i < CHAR_BIT".)


If I try to replicate that using "goto", I get the following:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
unsigned i;


Loop_Enter:

i = 0;

Loop_Condition:

if ( !(i != CHAR_BIT) ) goto Loop_End;

Loop_Body:

printf( "Bit Index %u\n", i );

Loop_Continue:

++i;
goto Loop_Condition;

Loop_End:

;


system("PAUSE");
}


However, we can see that the very first conditional test is redundant --
it would be better to test the condition AFTER each iteration, rather
than before. Something like:

Only if you know that there will always be at least one iteration in
which case a do loop is more appropriate.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
unsigned i;


Loop_Enter:

i = 0;

Loop_Body:

printf( "Bit Index %u\n", i );


Loop_Continue:

++i;

Loop_Condition:

if ( i != CHAR_BIT ) goto Loop_Body;

Loop_End:

;


system("PAUSE");
}


If we compare the execution of both code snippets, we can see:


Snippet 1: Tests the condition 9 times

Allows for 0..n iterations

Snippet 2: Tests the condition 8 times

Allows for 1..n iterations

Is the widely used C method of simple loop incrementation inherently
inefficient? At first glance, it appears so to me.


(Yes, I realise that most compilers will "unroll" that loop, so lets
pretend we're working with a more complicated loop whose amount of
iterations isn't determined until runtime.)

And that number of iterations may be 0.

 

[Ben Pfaff]

Ben Pfaff posted:

In using the word "domestic", I refer to the widespread, accepted way of
using a "for" loop to perform simple incremental loops.

Perhaps you should use a word more evocative of that meaning,
such as "traditional", "common", "ordinary".

 

[pete]

unsigned i;

do for( i = 0; i != some_value; ++i)
{
/* Body */
}

unsigned i;

i = 0;
do {
/* Body */
} while(i++ != some_value);

Sometimes, if I have what seems like a do loop
that I want to enter from the middle:

goto entry;
do {
/* first thing */
entry:
/* second thing */
} while(i++ != some_value);

I unroll it half way into:

/* second thing */
while(i++ != some_value) {
/* first thing */
/* second thing */
}

 

[Gordon Burditt]

A for loop is *supposed* to, under

Yes, exactly. But about 90% of the time, we're dealing with a loop which
will always execute at least once. For this 90% of the time, there's one
extra redudant evaluation performed.

Unless the compiler unrolls it. And you haven't demonstrated that
performing the extra redundant evaluation isn't faster. And it is
possible for the compiler to generate code that skips the redundant
comparison if it can determine that it is redundant.

If you want a do while loop, you known where to find it.

I don't think the "for" loop should have been shaped to accomodate the 10%
of the time where we might not want the loop to run at all.

In other words: speed trumps all, incorrectness 10% of the time
is unimportant. And if correctness is unimportant, anything can
run in 0 time and 0 bytes.

If anything,
there should have been another kind of loop availabe, analogous as to how a
"while loop" has a sister "do loop".

Why is this worthwhile? Assuming such a loop WAS available, why
should I spend 1,000,000 comparisons in CPU time re-compiling a
program in order to save one comparison?

Even something like a "do for" loop would be nice:

unsigned i;

do for( i = 0; i != some_value; ++i)
{
/* Body */
}

The first time someone has to debug using a do for () instead of a for(),
you'll probably use up 100 years of savings from that redundant comparison.

Gordon L. Burditt

 

[Richard Tobin]

Yes, exactly. But about 90% of the time, we're dealing with a loop which
will always execute at least once.

I just grepped the for loops in a fairly substantial piece of code
that I wrote. About a third of the for loops can execute zero times.
But almost all of the loops that execute at least once are
initializing data, and are only executed once each. So the proportion
of at-least-once loops executed is probably very small.

For this 90% of the time, there's one
extra redudant evaluation performed.

The vast majority of the at-least-once loops were cases where the
initial value and the valued tested against were constant, so the
compiler can generate code that tests at the end if that is more
efficient. Don't assume that something is inefficient without
considering how it can be implemented.

I don't think the "for" loop should have been shaped to accomodate the 10%
of the time where we might not want the loop to run at all.

Perhaps the authors of C had a better insight into what the common case
is and what the costs are.

-- Richard

 

[Frederick Gotham]

A few people have suggested using a "do" loop in order to skip the first
redundant comparison; the reason I don't do that is because a "for" loop is
handy because it has nice compartments in which to specify:

(1) What to do before the loop
(2) What condition to evaluate
(3) What to do after each iteration

 

[Eric Sosman]

Gordon Burditt posted:





Yes, exactly. But about 90% of the time, we're dealing with a loop which
will always execute at least once. For this 90% of the time, there's one
extra redudant evaluation performed.

... by the abstract machine. What the actual machine does,
operating under the "as if" rule, is another matter. The only
way to see what happens is to find a few compilers that allow
you to examine the generated machine code, and experiment with
them. The results, of course, pertain to the compilers and not
to C as such.

If you want a loop that does not make an "extra" comparison,
consider do...while. Consider also that this might change the
meaning of your program.

 

[L7]

Gordon Burditt posted:



Yes, exactly. But about 90% of the time, we're dealing with a loop which
will always execute at least once. For this 90% of the time, there's one
extra redudant evaluation performed.

Depends on exactly what you are doing.
If you are dealing with pointers, this eliminates an explicit check for
null.
If you _know_ that you will always execute the loop at least once, sure
- a do while would prove useful (although, I don't think you are going
to see any performance increase...).

I don't think the "for" loop should have been shaped to accomodate the 10%
of the time where we might not want the loop to run at all. If anything,
there should have been another kind of loop availabe, analogous as to how a
"while loop" has a sister "do loop".

The for loop isn't 'shaped' in any certain way.
You always have the option to change the flow of your code: do while,
for, while.

 

[L7]

A few people have suggested using a "do" loop in order to skip the first
redundant comparison; the reason I don't do that is because a "for" loop is
handy because it has nice compartments in which to specify:

(1) What to do before the loop
(2) What condition to evaluate
(3) What to do after each iteration

All of which can be coded in another manner.
In other words, it's the responsibility of the programmer to correctly
handle the specific circumstances - not the language.

 

[pete]

A few people have suggested using
a "do" loop in order to skip the first
redundant comparison;
the reason I don't do that is because a "for" loop is
handy because it has nice compartments in which to specify:

(1) What to do before the loop
(2) What condition to evaluate
(3) What to do after each iteration

A do loop does what you want
but you don't like the way it looks.

Your complaint about for loops
doesn't really have a lot substance to it.

 

[Thad Smith]

Is the domestic usage of the C "for" loop inefficient when it comes to
simple incrementation? Here's a very simple program that prints out the
bit-numbers in a byte.

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int main(void)
{
unsigned i;

for( i = 0; i != CHAR_BIT; ++i )
{
printf( "Bit Index %u\n", i );
}

system("PAUSE");
} ....
However, we can see that the very first conditional test is redundant --
it would be better to test the condition AFTER each iteration, rather
than before.

This is a Quality of Implementation issue. If the initial value and
limit value are compile-time constants and the initial value of i
satifies the loop condition, the compiler is free to execute the body
immediately and move the comparison to the end of the loop, after the
increment clause.

Bottom line: it's the compiler, not the language, that is inefficient.

 

[Chris Torek]

for( i = 0; i != CHAR_BIT; ++i )

[tests, at least in the abstract machine, whether 0 != CHAR_BIT]

Any "real" C compiler that optimizes will see that, at the top of
the loop the first time, i == 0 and 0 != CHAR_BIT, so will move
the test from the top of the loop to the bottom (or unroll the
loop, as you mention; or do both).

If the compiler does not optimize, you probably have more important
things to worry about than simple "for" loops.

(Yes, I realise that most compilers will "unroll" that loop, so lets
pretend we're working with a more complicated loop whose amount of
iterations isn't determined until runtime.)

OK:

for (i = start; i != stop; i++)

where "start" and "stop" are not constants:

% cat t.c
extern void bar(void);
void foo(int start, int stop) {
int i;

for (i = start; i != stop; i++)
bar();
}

GCC produces:

% gcc -O3 -S t.c
% cat t.s
[some setup code omitted]
movl 12(%ebp), %esi # load stop into %esi
movl 8(%ebp), %ebx # load start into %ebx
cmpl %esi, %ebx # compare start (aka i) vs stop
je .L8 # skip loop entirely if already equal
.p2align 2,,3
.L6:
incl %ebx # i++ -- moved up from bottom of loop
call bar # bar()
cmpl %esi, %ebx # compare i vs stop
jne .L6 # keep looping if not equal
.L8:
[cleanup code omitted]

Clearly, it *is* necessary to compare start vs stop, in this case.

With loops over linked lists:

for (p = head; p != NULL; p = p->next)

the initial test is also important (and as with the above loop, gcc
tends to hoist out a "head != NULL" test and move the remaining tests
to the bottom of the loop, provided this is profitable on the target
hardware).