How to optimize for loop?

[Bhan]

I heard for(i=0;i<20;i++)
{
do-something;
}

Can be optimized.
Is this can really optimized by an equivalent for loop or with while or
do while loops?

 

[Gordon Burditt]

I heard for(i=0;i<20;i++)

{
do-something;
}

Can be optimized.
Is this can really optimized by an equivalent for loop or with while or
do while loops?

Assuming for the moment that do-something does not contain break or
continue, and it uses but does not alter i, some people consider this an
optimization (loop unrolling):

do {
i = 0;
do-something;
i = 1;
do-something;
i = 2;
do-something;
i = 3;
do-something;
i = 4;
do-something;
i = 5;
do-something;
i = 6;
do-something;
i = 7;
do-something;
i = 8;
do-something;
i = 9;
do-something;
i = 10;
do-something;
i = 11;
do-something;
i = 12;
do-something;
i = 13;
do-something;
i = 14;
do-something;
i = 15;
do-something;
i = 16;
do-something;
i = 17;
do-something;
i = 18;
do-something;
i = 19;
do-something;
i = 20;
} while (0);

Gordon L. Burditt

 

[Zara]

Assuming for the moment that do-something does not contain break or
continue, and it uses but does not alter i, some people consider this an
optimization (loop unrolling):

do {
i = 0;
do-something;
i = 1;
do-something;
i = 2;
do-something;
i = 3;
do-something;
i = 4;
do-something;
i = 5;
do-something;
i = 6;
do-something;
i = 7;
do-something;
i = 8;
do-something;
i = 9;
do-something;
i = 10;
do-something;
i = 11;
do-something;
i = 12;
do-something;
i = 13;
do-something;
i = 14;
do-something;
i = 15;
do-something;
i = 16;
do-something;
i = 17;
do-something;
i = 18;
do-something;
i = 19;
do-something;
i = 20;
} while (0);

Gordon L. Burditt

In the same way, googlr for Duff's device


Zara

 

[g.kanaka.raju]

Hi,

It depends on what is "do-something". The optimization can be loop
unrolling, moving loop envarient code out side of the loop, common
sub-expression elimination,.... It depends on your code inside the
loop.

Regards,
Raju

 

[Alex Fraser]

I heard for(i=0;i<20;i++)
{
do-something;
}

Can be optimized.
Is this can really optimized by an equivalent for loop or with while or
do while loops?

The above is exactly equivalent to:

i = 0;
while (i < 20) {
do-something;
++i;
}

It is obvious that the first time the condition is tested (before entering
the loop) it will be true, so there is no need to actually do the test. The
test can be moved to the bottom of the loop:

i = 0;
do {
do-something;
++i;
} while (i < 20);

If the value of i is not used except to control the number of iterations,
the following may be better in some cases:

i = 20;
do {
do-something;
} while (--i);

Another possibility already mentioned is loop unrolling. This increases code
size but may not actually increase performance. In particular, unrolling
tests (eg if "do-something" contains one or more "if" statements) may
actually decrease performance.

The loop may be partially unrolled, eg:

/* if the value of i is used: */
i = 0;
do {
do-something;
++i;
do-something;
++i;
} while (i < 20);

/* or, if the value of i is not used */
i = 0;
do {
do-something;
do-something;
++i;
} while (i < 10);

Or the loop may be fully unrolled, in which case there is no loop anymore.

However, all of this is best left to the compiler to figure out, until and
unless such optimisation helps a previously-identified performance
bottleneck.

Alex

 

[Lawrence Kirby]

I heard for(i=0;i<20;i++)
{
do-something;
}

Can be optimized.
Is this can really optimized by an equivalent for loop or with while or
do while loops?

If the loop can be usefully optimised the compile will propbably do so.
There's no reason to assume that an EQUIVALENT while or do-while loop will
result in different generated code.

Lawrence

 

[Eric Sosman]

The above is exactly equivalent to:

i = 0;
while (i < 20) {
do-something;
++i;
}

.... provided `do-something' doesn't `continue' ...

 

[Alex Fraser]

... provided `do-something' doesn't `continue' ...

Indeed, I should have thought of that. All of what I wrote assumes no
"continue".

Alex

 

[Emmanuel Delahaye]

Bhan wrote on 06/09/05 :

I heard for(i=0;i<20;i++)
{
do-something;
}

Can be optimized.
Is this can really optimized by an equivalent for loop or with while or
do while loops?

Not really. You could eventually unroll the loop, but the benefit
should be negligible. Do measurements to be sure.

do-something; /* #1 */
do-something; /* #2 */
do-something; /* #3 */
....
do-something; /* #19 */
do-something; /* #20 */

(if you have a unixoïd box, use the times command... very handy)

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

I once asked an expert COBOL programmer, how to
declare local variables in COBOL, the reply was:
"what is a local variable?"

 

[Walter Bright]

I heard for(i=0;i<20;i++)
{
do-something;
}

Can be optimized.
Is this can really optimized by an equivalent for loop or with while or
do while loops?

Only if you're using a primitive compiler. Modern compilers will generate
the same code for:

for (i=0;i<20;i++) { ... }

i=0; while(i<20) { ... i++; }

i=0; do { ... } while (++i < 20);

and even:

i=0;
L1: if (i >= 20) goto L2;
{ ... }
i++;
goto L1;
L2:

Try the various forms and output the assembler language, and compare. If
you're interested in optimizing code, you'll need a precise way of timing it
to see how you're doing:
http://www.digitalmars.com/techtips/timing_code.html

-Walter
www.digitalmars.com free C, C++, D compilers

 

[Richard Tobin]

Not really. You could eventually unroll the loop, but the benefit
should be negligible. Do measurements to be sure.

And the compiler probably already knows how much to unroll it.

-- Richard