For loop condition evaluation

[Shill]

I have several questions.

In C, AFAIU, a for loop is just syntactic sugar for a while loop.

for (i1; i2; i3) i4;

is equivalent to

i1
while (i2) {
i4;
i3;
}

Now, assume I have the following:

for (i=0; i<foo(); ++i) bar();

If I understand correctly, foo() will be evaluated for every
iteration of the loop, EVEN IF the result does not depend on i?

If I recall correctly, the termination condition is evaluated only
once in some languages such as Pascal.

Is it my responsability to do:

n = foo();
for (i=0; i<n; ++i) bar();

to tell the compiler NOT TO evaluate foo() every iteration since I
know it is invariant?

Do optimizing compilers figure it out by themselves?

What if the termination condition is:

for (i=0; i<p->n; ++i) bar();

Will I similarly pay for one pointer dereferencing every iteration
and should I write instead:

n = p->n;
for (i=0; i<n; ++i) bar();

Thanks to all who care to reply!

 

[Philip Willoughby]

I have several questions.

In C, AFAIU, a for loop is just syntactic sugar for a while loop.

for (i1; i2; i3) i4;

is equivalent to

i1
while (i2) {
i4;
i3;
}

Almost. Pedants would make that:

do {
i1;
while (i2)
{
i4;
i3;
}
} while (0);

Because it behaves the same when used as the single statement between an
if and an else.

Now, assume I have the following:

for (i=0; i<foo(); ++i) bar();

If I understand correctly, foo() will be evaluated for every
iteration of the loop, EVEN IF the result does not depend on i?

Probably. Unless the compiler can work out that foo() does not depend
on i in any way it will have to evaluate it every time.

Since you usually use a for loop to go through a sequence of things
using pointers, this usually means that the compiler must know that
foo() does not access any area of memory that the body of the loop accesses.

The other question is how foo() bahaves in relation to globals -- if it
modifies any global, the compiler must invoke it every time to maintain
the correct semantics.

Is it my responsability to do:

n = foo();
for (i=0; i<n; ++i) bar();
>
to tell the compiler NOT TO evaluate foo() every iteration since I
know it is invariant?

Do optimizing compilers figure it out by themselves?

As you say, there are two approaches to this:

1: Help the compiler figure out it's invariant. If you have a C99-ish
compilation environment, you can use restrict pointers where appropriate
to help here. However, this may not help unless the compiler can see
the code of foo() -- if it's in another object file it can't determine
the effect on globals.

2: Just do it yourself.

Personally, I would try approach 1 firat, and swith to 2 when(!) it
doesn't work.

What if the termination condition is:

for (i=0; i<p->n; ++i) bar();

Will I similarly pay for one pointer dereferencing every iteration

Yes, unless you have a very good compiler. However, making p a restrict
pointer will definitely help in this case -- it should optimise away the
dereference (provided the compiler heuristics feel it's worth it).

and should I write instead:

n = p->n;
for (i=0; i<n; ++i) bar();

If you're that bothered about eliminating a the pointer dereference,
then this is the only way to guarantee it. However I would suggest that
you check wheter the speed gain is significant -- assuming stuff's still
in a core-speed cache, you're only looking at a 1-3 cycle saving by
eliminating the dereference. For most systems you won't be able to
measure this unless your loop is very short.

It's probably worth eliminating the function calls, but I would make the
pointer dereference decision based on which method is morereadable
rather than which is theoretically faster.

Regards,

Phil

 

[pete]

I have several questions.

In C, AFAIU, a for loop is just syntactic sugar for a while loop.

The meaning of "break" is slightly different for "for" and "while"

for (i=0; i<foo(); ++i) bar();

If I understand correctly, foo() will be evaluated for every
iteration of the loop, EVEN IF the result does not depend on i?
Yes.

Is it my responsability to do:

n = foo();
for (i=0; i<n; ++i) bar();

to tell the compiler NOT TO evaluate foo() every iteration since I
know it is invariant?
Yes.

Do optimizing compilers figure it out by themselves?

An optimizing compiler is allowed to do
whatever it takes to produce a program with correct behavior,
but I wouldn't expect that much figuring
to be within the capabilities of a compiler.

What if the termination condition is:

for (i=0; i<p->n; ++i) bar();

Will I similarly pay for one pointer dereferencing every iteration
and should I write instead:

n = p->n;
for (i=0; i<n; ++i) bar();

You'd have to time it and know that your time results are
implementation dependant.

 

[Derk Gwen]

# for (i=0; i<foo(); ++i) bar();
#
# If I understand correctly, foo() will be evaluated for every
# iteration of the loop, EVEN IF the result does not depend on i?

If it is invariant and free of visible side effects, you can't tell if it's
evaluated once or with every iteration. If the optimiser can prove the
predicate is such, the optimiser is free to move all the evaluation outside
the loop.

# Is it my responsability to do:
#
# n = foo();
# for (i=0; i<n; ++i) bar();
#
# to tell the compiler NOT TO evaluate foo() every iteration since I
# know it is invariant?

If you want to guarentee the invariant code is moved out of the loop,
and your compiler does not provide that guarentee.

# Do optimizing compilers figure it out by themselves?

Depends. On whether it can analyze the predicate. Whether you asked it
to. Whether the compiler writer added the analysis.

# What if the termination condition is:
#
# for (i=0; i<p->n; ++i) bar();
#
# Will I similarly pay for one pointer dereferencing every iteration
# and should I write instead:

Optimisers deal with expressions in general. So it will deal as it can
with functions and pointers and anything else.

 

[Kevin Easton]

I have several questions.

In C, AFAIU, a for loop is just syntactic sugar for a while loop.

for (i1; i2; i3) i4;

is equivalent to

i1
while (i2) {
i4;
i3;
}

There is one important difference - if any part of the loop body
executes a continue; statement, the for loop will execute i3 before
testing i2, but the while loop version won't - it jumps straight to the
test.

Now, assume I have the following:

for (i=0; i<foo(); ++i) bar();

If I understand correctly, foo() will be evaluated for every
iteration of the loop, EVEN IF the result does not depend on i?

If I recall correctly, the termination condition is evaluated only
once in some languages such as Pascal.

Is it my responsability to do:

n = foo();
for (i=0; i<n; ++i) bar();

to tell the compiler NOT TO evaluate foo() every iteration since I
know it is invariant?

That's the only way to be certain.

Do optimizing compilers figure it out by themselves?

Some might - especially with standard library functions like strlen,
which the compiler knows more about than a general function written by
the user.

What if the termination condition is:

for (i=0; i<p->n; ++i) bar();

Will I similarly pay for one pointer dereferencing every iteration
and should I write instead:

n = p->n;
for (i=0; i<n; ++i) bar();

This is more of a microoptimisation - you really shouldn't do this
unless profiling shows that the dereference is having a measurable
effect on program speed - and make sure you test before and after,
because it's conceivable that this "optimisation" could actually make
the complete function *slower* - because you're now using one extra
variable, you may have caused an extra spill of a register-held variable
into memory...

- Kevin.

 

[Ivan Vecerina]

| Shill wrote:
| >
| > In C, AFAIU, a for loop is just syntactic sugar for a while loop.
|
| The meaning of "break" is slightly different for "for" and "while"

"break" is the same, it is actually "continue" that has a different
meaning: in the case of a for loop, the increment statement will
be executed before moving on to the next iteration.

Regards,
Ivan

 

[pete]

| Shill wrote:
| >
| > In C, AFAIU, a for loop is just syntactic sugar for a while loop.
|
| The meaning of "break" is slightly different for "for" and "while"

"break" is the same, it is actually "continue" that has a different
meaning: in the case of a for loop, the increment statement will
be executed before moving on to the next iteration.

Sorry about that.
Thank you.