Inherent inefficiency in domestic "for" loop?

[Skarmander]

Is the domestic usage of the C "for" loop inefficient when it comes to
simple incrementation?
No.

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".)

No, I rather like formally precise tests. (Of course, if you screw them up,
you're much more likely to get an infinite loop then your fellow programmer
who used an inexact comparison and got infinity as wiggle room.)

If I try to replicate that using "goto",

<snip>

Don't. There are good reasons to use goto. This isn't one of them.

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:

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.

Then glance harder. There's nothing "inherently" inefficient about it. For
most loops it's perfectly valid and desirable to potentially execute 0
times. A pretest loop will handle this; a posttest loop will not.

(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.)

Then, as I said above, use do-while. You might as well communicate your
knowledge (or assumption) about the loop's behavior to the esteemed maintainers.

Upthread, I see you don't want to use do-while because you like the way the
for-statement looks better. To that my educated response would be: tough
noogies. You can't have your cake and eat it too.

S.

 

[av]

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 --

yes but here the compiler sees it and does the right.

the original
"
#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 );
printf("Charatter\n");
getchar();
return 0;
}
"

the traslation
"; int main(void)
;
push ebp
mov ebp,esp
push ebx
;
; {
; unsigned i;
;
; for( i = 0; i != CHAR_BIT; ++i )
;
@1:
xor ebx,ebx
;
; printf( "Bit Index %u\n", i );
;
?live1@32: ; EBX = i
@2:
push ebx
push offset s@
call _printf
add esp,8
inc ebx
cmp ebx,8
jne short @2
.....
xor eax,eax
;
; }

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

yes the C compiler here does it

 

[SuperKoko]

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.

I randomly looked at a few for loops spread into several of my programs
and found 14 for loops that might be executed zero-times out of 25.
Most of the time, these loops would execute with a few iterations, and
seldomly with zero iterations, but my programs would be buggy if this
seldom case was not taken in account.
14/25 = 56%, not 10%


25 loops is not a very large sample (moreover, it was C++ programs, not
C programs), but I think it is enough revelant.

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 is shaped such as the condition is true when the body is
entered... It is easy to understand & use (i.e. you don't have to think
about special cases during 5 minutes).

 

[Mark McIntyre]

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

(snip examples)

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

"Its a poor workman who blames his tools". Not trying to be rude, but
if 'for' is inefficient in the cases above, you're doing it wrong.

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Mark McIntyre]

Gordon Burditt posted:



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

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

Only if you write the algo wrong.

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

Kinda like do {stmt;} while(condition); then ?

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Mark McIntyre]

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

Right. So you're ignoring the right way to avoid your problem because
you dislike its aesthetics...
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

 

[Anders Arnholm]

On Mon, 26 Jun 2006 01:07:23 GMT, in comp.lang.c , Frederick Gotham
Right. So you're ignoring the right way to avoid your problem because
you dislike its aesthetics...

One could also notice that in many cases the average C compiler
finguers out what the for loop does and creates the same code for the
for(; {} and do {} while() loops.

/ Anders

 

[lawrence.jones]

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

Which is exactly why I have proposed generalizing the do-while loop:

do statement while ( expression ) statement

with the obvious semantics: the first statement is executed, the
expression is evaluated and the loop exited if zero, otherwise the
second statment is executed and then control returns to the first
statement. If the second statement is a null statement, you get the
traditional do-while loop.

Unfortunately, no one has taken me up on it and actually implemented it.

-Larry Jones

ANY idiot can be famous. I figure I'm more the LEGENDARY type! -- Calvin

 

[Roberto Waltman]

Which is exactly why I have proposed generalizing the do-while loop:

do statement while ( expression ) statement

with the obvious semantics: the first statement is executed, the
expression is evaluated and the loop exited if zero, otherwise the
second statment is executed and then control returns to the first
statement. If the second statement is a null statement, you get the
traditional do-while loop.

Known in FORTH as "BEGIN statement(s) condition WHILE statement(s)
REPEAT" with the same semantics.
I always missed not having it in C.

 

[Skarmander]

Which is exactly why I have proposed generalizing the do-while loop:

do statement while ( expression ) statement

Syntactically, this is a bad idea.

do {
statement
} while (expression) /* Oops: forgot semicolon */

give_me_a_ping_vasily_one_ping_only_please();

Although easy enough to detect, C's potential for syntactical slip-ups is
big enough as it is.

with the obvious semantics: the first statement is executed, the
expression is evaluated and the loop exited if zero, otherwise the
second statment is executed and then control returns to the first
statement. If the second statement is a null statement, you get the
traditional do-while loop.

Unfortunately, no one has taken me up on it and actually implemented it.

for (;
statement
if (!expression) break;
statement
}

You can use while(1) if you prefer.

I don't know when you proposed this, but loop-with-test-in-the-middle is not
exactly news.

http://en.wikipedia.org/wiki/Control_flow#Loop_with_test_in_the_middle

Of course, the syntax is not in C, and although people could "take you up on
it" and implement it, there wouldn't be any point. I doubt the standard
would get amended for this.

S.

 

[Richard Tobin]

Which is exactly why I have proposed generalizing the do-while loop:

do statement while ( expression ) statement

Some Lisps have a loop construct in which any number of (while condition)
and (until condition) statements can appear in the body.

-- Richard

 

[av]

Which is exactly why I have proposed generalizing the do-while loop:

do statement while ( expression ) statement

"goto label; do{...;label: ;...}while(exp);"
is for me enought for doing all. it is the general loop (so no more
for, while etc.)

 

[lawrence.jones]

I don't know when you proposed this, but loop-with-test-in-the-middle is not
exactly news.

Not at all. I'm just the first person I know of demented enough to
suggest extending the syntax of the existing do loop to provide it in C
with absolutely no disruption of existing code. It seems to produce the
same mixture of feelings of elegance and revulsion that Duff's Device
does. Whether that's good or bad, I'll leave to others to judge.

I originally proposed it (informally) for the initial ANSI standard, but
other committee members made discusted noises and threw things at me, so
I dropped it.

-Larry Jones

Mr. Subtlety drives home another point. -- Calvin

 

[Skarmander]

Not at all. I'm just the first person I know of demented enough to
suggest extending the syntax of the existing do loop to provide it in C
with absolutely no disruption of existing code.

You forget the most important thing: without addition of new keywords!

Though admittedly the C committee seems less reserved about this than the
C++ committee.

It seems to produce the same mixture of feelings of elegance and
revulsion that Duff's Device does. Whether that's good or bad, I'll leave
to others to judge.

I originally proposed it (informally) for the initial ANSI standard, but
other committee members made discusted noises and threw things at me, so
I dropped it.

Heresy requires a strong stomach. To propose changing the very grammar of
our beloved language without adding anything we couldn't already accomplish!
I'm surprised you didn't get tarred and feathered...

S.

 

[ena8t8si]

Not at all. I'm just the first person I know of demented enough to
suggest extending the syntax of the existing do loop to provide it in C
with absolutely no disruption of existing code. It seems to produce the
same mixture of feelings of elegance and revulsion that Duff's Device
does. Whether that's good or bad, I'll leave to others to judge.

I originally proposed it (informally) for the initial ANSI standard, but
other committee members made discusted noises and threw things at me, so
I dropped it.

I like it!