is there any ulternative metho to optimize the following piece of code
(for loop)
main()
{
int i,j;
for(i=0;i<40000000;i++)
j=1;
}
just wanna know how to optimize the for loop; i know the code has no
logic...........
but i heard that there is a way to optimize by restructuring the aboce
code. The j=1 assignment must be kept inside the loop.
As a preliminary remark loop optimization gains very little unless the
loop body is quite short. The reason for this is that all that loop
optimization gains is reducing the cost of the loop test and increment
which is dominated by the cost of the loop body. Furthermore it is
often the case that a good compiler can do the optimizations itself.
That said: There are a couple of common loop optimizations, counting
down to zero, and loop unrolling.
The reason for counting down to zero is that many machines have a
decrement and branch instruction or the equivalent, which means that
the loop test can be a single instruction. Even if it doesn't, it is
generally cheaper to test against zero/nonzero than it is to compare
against a value. To illustrate with your code:
int main ()
{
long i,j;
for (i=N; --i >= 0
{
LOOP_BODY(i);
}
}
where N is the number of times the loop is to be executed and
LOOP_BODY is the loop body, both defined elsewhere so that we don't
confuse ourselves with irrelevancies.
It turns out that there are a variety of ways of counting down. Thus
the above code counts down from N-1 to 0 and terminates with i being
negative; the value of i being tested is the same as that used in the
loop body. (This may or may not matter.) Some alternatives for the
for body are:
for (i = N; i-- > 0
for (i = N; i>0; i--)
for (i = N; i-- != 0
for (i = N; i != 0; i--)
The important thing here is to make sure that the loop body is
formulated so that counting down works.
A second trick is loop unrolling. The basic idea here is that the
loop body code is to be repeated several times within the loop. This
eliminate a large percentage of the loop tests. There are two gotchas
to take into consideration. The first is that we have some left over
iterations if N is not a multiple of the loop unrolling factor. The
second is that the loop index doesn't change between instances of the
loop body within the loop.
There are various ways to handle the left over iterations. A
convenient way is to use two loops, one to handle the left overs and
the other to use that part of N that is divisible by the loop
unrolling factor. I find it convenient to make the loop unrolling
factor a power of two and use the general formula:
for (i = (N&7) ; --i >= 0
/* remainder loop */
{
LOOP_BODY;
}
for (i = (N>>3) ; --i >= 0
/* main loop */
{
LOOP_BODY; LOOP_BODY;
LOOP_BODY; LOOP_BODY;
LOOP_BODY; LOOP_BODY;
LOOP_BODY; LOOP_BODY;
}
Generally speaking LOOP_BODY should not depend on i.
Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri,
http://www.varinoma.com
I started out in life with nothing.
I still have most of it left.
