«

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.

Spidey wrote:
> is there any ulternative metho to optimize the following piece of code
> (for loop)
>
>
> main()

int main(void), please.

> {
> int i,j;
> for(i=0;i<40000000;i++)

40000000 is well out of the range provided by the standard for an int.
Make it a long.

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

Your post makes no sense. The loop you've shown is equivalent to doing
nothing at all, and the only statement it contains is not to be moved
outside of the loop. There's nothing to optimize. A good compiler will
optimize this by generating code for "i = 40000000; j = 1", and that's
assuming the variables aren't optimized out of existence too.

You can't "restructure" what isn't there. You may be thinking of the
machine language instructions that might be generated by a compiler in
order to implement this loop. That's a question for another newsgroup
that discusses your compiler/platform, however. Also, no compiler worth
its salt will generate faster code if you implement the same loop with a
different loop construct, be it a while, a do-while or a goto.

S.

On 25 Nov 2005 21:17:59 -0800, "Spidey" <> wrote:

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

That's kind of the problem. Once you get some clue about the logic,
then you can look at what's going on and see if it's doing anything
that's not necessary and whether you can make some assumptions along
the way if you already know the answer to some calculations. In this
case, since the for loop doesn't do anything, you can cut out the for
loop and skip to the end:

int main (void)
{
long int i=39999999;
int j=1;
return 0;
}

Still does nothing, but it'll do it a bit faster.

Right now, you're just setting j=1 about 40,000,000 times, which is
kind of nuts.
---------------------------------------------
Thanks.


MCheu

MCheu wrote:
> On 25 Nov 2005 21:17:59 -0800, "Spidey" <> wrote:
>
>
>>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.
>
>
> That's kind of the problem. Once you get some clue about the logic,
> then you can look at what's going on and see if it's doing anything
> that's not necessary and whether you can make some assumptions along
> the way if you already know the answer to some calculations. In this
> case, since the for loop doesn't do anything, you can cut out the for
> loop and skip to the end:
>
> int main (void)
> {
> long int i=39999999;
ITYM 40000000
> int j=1;
> return 0;
> }
>
> Still does nothing, but it'll do it a bit faster.
>
> Right now, you're just setting j=1 about 40,000,000 times, which is
> kind of nuts.
> ---------------------------------------------
> Thanks.
>
>
> MCheu


--
E-Mail: Mine is an /at/ gmx /dot/ de address.

On 25 Nov 2005 21:17:59 -0800, "Spidey" <> wrote:

>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,
http://home.tiac.net/~cri, http://www.varinoma.com
I started out in life with nothing.
I still have most of it left.

On 2005-11-26, Spidey <> wrote:
> The j=1 assignment must be kept inside the loop.

Why? Unless it's not really a j=1 assignment?

In article <>,
(Richard Harter) wrote:

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

And any compiler worth its money will do that much better if you leave
your loops alone and let the compiler do its job.

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

The most important thing is to write readable code; the compiler is much
better at micro-optimisations than you will ever be.

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

And any compiler worth its money will do that much better if you leave
your loops alone and let the compiler do its job.

On Sat, 26 Nov 2005 09:17:31 +0100, Michael Mair
<> wrote:

>MCheu wrote:
>> On 25 Nov 2005 21:17:59 -0800, "Spidey" <> wrote:
>>
>>
>>>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;
>>>}
>>>
<SNIP>

>> int main (void)
>> {
>> long int i=39999999;
>ITYM 40000000

Took me a while to figure out your acronym ITYM="I Think You Mean."

You're right. I forgot the final iteration that finally kicks you out
of the loop, so by the end of the loop, it would be 40,000,000.


---------------------------------------------
Thanks.


MCheu

On Sat, 26 Nov 2005 17:45:43 -0500, in comp.lang.c , MCheu
<> wrote:
>
>Took me a while to figure out your acronym ITYM="I Think You Mean."

http://www.gaarde.org/acronyms/

and about a zillion other places on the web.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Skarmander wrote:

> Spidey wrote:
>> is there any ulternative metho to optimize the following piece of
>> code (for loop)
>>
>>
>> main()
>
> int main(void), please.
>
>> {
>> int i,j;
>> for(i=0;i<40000000;i++)
>
> 40000000 is well out of the range provided by the standard for an
> int. Make it a long.


During my course in programming, I've never seen a 16-bit int, even it
is said in (old) books that size of int is 16-bit. Only 16-bit
environment I know is 16-bit dos, but that can be regarded as
obsolete (DJGPP is 32-bit environment and has 32-bit ints).

You should use limits.h if portability is important.