# abt nested loops

Discussion in 'C Programming' started by Pavan, May 6, 2005.

1. ### PavanGuest

Hi
i have two nested loops as shown below:
1.
for(i=0;i<=1000;i++)
{
for(i=0;i<=100;i++)
{
.....;
.....;
}

}

and other one is
2.
for(i=0;i<=100;i++)
{
for(i=0;i<=1000;i++)
{
.....;
.....;
}

}
so my question is which loop is best in terms of performance..please
comment why is it so ..
what i feel is 2nd loop is best in performance wise.

Regards'
Pavan

Pavan, May 6, 2005

2. ### peteGuest

Pavan wrote:
>
> Hi
> i have two nested loops as shown below:
> 1.
> for(i=0;i<=1000;i++)
> {
> for(i=0;i<=100;i++)
> {
> .....;
> .....;
> }
>
> }
>
> and other one is
> 2.
> for(i=0;i<=100;i++)
> {
> for(i=0;i<=1000;i++)
> {
> .....;
> .....;
> }
>
> }
> so my question is which loop is best in terms of performance..please
> comment why is it so ..
> what i feel is 2nd loop is best in performance wise.

2nd loop stops.
1st loop doesn't.

--
pete

pete, May 6, 2005

3. ### PavanGuest

Hi Pete
thx for replying ..i am afraid ,, i did't get you !!
why does 2nd loops stops and where it stops

cheers
Pavan

Pavan, May 6, 2005
4. ### peteGuest

Pavan wrote:
>
> Hi Pete
> thx for replying ..i am afraid ,, i did't get you !!
> why does 2nd loops stops and where it stops
>

2.
for(i=0;i<=100;i++)

/* first, i equals 0 */

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

/*
** second, i equals 1001,
** outer loop stops because i > 100
*/

}

--
pete

pete, May 6, 2005
5. ### bjrnoveGuest

Hi.

You should really do it something like this instead:

1.
for(i=0;i<=1000;i++)
{
for(j=0;j<=100;j++)
{
.....;
.....;
}

}

and other one is
2.
for(i=0;i<=100;i++)
{
for(j=0;j<=1000;j++)
{
.....;
.....;
}

}

Notice that I change i with j in one of the loops. If you don't do that
the value of i will be changed by both loops.

When it comes to performance I guess you wouldn't notice that bi a
difference. It would depend more upon what you're doing.

--
bjrnove

bjrnove, May 6, 2005
6. ### Fred L. KleinschmidtGuest

pete wrote:
>
> Pavan wrote:
> >
> > Hi Pete
> > thx for replying ..i am afraid ,, i did't get you !!
> > why does 2nd loops stops and where it stops
> >

>
> 2.
> for(i=0;i<=100;i++)
>
> /* first, i equals 0 */
>
> {
> for(i=0;i<=1000;i++)
> {
> .....;
> .....;
> }
>
> /*
> ** second, i equals 1001,
> ** outer loop stops because i > 100
> */
>
> }
>
> --
> pete

I think the OP is an extreme newbie, and isn't asking the question
properly. I fear his use of index "i" in both loops is not what he meant
- probably meant to inquire about two nested loops with different linit
on the outer loop and inner loop. The use of "<=" also shows probable
non-understanding of C.

If what the OP meant is
for (i=0; i<n; i++) {
for (j=0; j<m; j++) {
...
}
}
and then asking which is the better way: m<n or m>n?
The answer: it depends on what happens inside the inner loop, and what
happens only inside the outer loop, especially if i and j are used as
indices of multiple-dimensioned arrays.
--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Common User Interface Services
M/S 2R-94 (206)544-5225

Fred L. Kleinschmidt, May 6, 2005
7. ### Kenneth BrodyGuest

Pavan wrote:
>
> Hi
> i have two nested loops as shown below:
> 1.
> for(i=0;i<=1000;i++)
> {
> for(i=0;i<=100;i++)
> {
> .....;
> .....;
> }
>
> }
>
> and other one is
> 2.
> for(i=0;i<=100;i++)
> {
> for(i=0;i<=1000;i++)
> {
> .....;
> .....;
> }
>
> }
> so my question is which loop is best in terms of performance..please
> comment why is it so ..
> what i feel is 2nd loop is best in performance wise.

I can't say which one is "better in performance", but I can tell you that
the outer loop in the first example is an infinite loop, while the second
will have the outer loop execute only once.

--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody/at\spamcop.net | www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:>

Kenneth Brody, May 6, 2005
8. ### Emmanuel DelahayeGuest

Emmanuel Delahaye, May 6, 2005
9. ### SM RyanGuest

"Pavan" <> wrote:
# Hi
# i have two nested loops as shown below:
# 1.
# for(i=0;i<=1000;i++)
# {
# for(i=0;i<=100;i++)
# {
# .....;
# .....;
# }
#
# }

Presumably you mean for(i...) for(j...) instead of really for(i...) for(i...)

In that case, it depends on details like whether you're using machine with caches
and virtual memory and memory access patterns, as well as register access patterns,
etc. Putting the small loop outside means 101 loop initialisations compared to 1001,
but the loop overhead is trivial compared to cache and page miss overheads.

What's more important is the pattern of memory access. If you're using arrays like
a[j] with virtual memory, then it's almost always better to have i in the outer
loop and j in the inner so that loads and stores tend to be clusterred in the same
pages. This also improves automated vectorisation if your compiler provides that.

More complicated access patterns can optimise the use of caches. You can look up

--
SM Ryan http://www.rawbw.com/~wyrmwif/
So basically, you just trace.

SM Ryan, May 6, 2005
10. ### MalcolmGuest

"Pavan" <> wrote in message
> i have two nested loops as shown below:
> 1.
> for(i=0;i<=1000;i++)
> {
> for(i=0;i<=100;i++)
> {
> .....;
> .....;
> }
>
> }
>
>
> and other one is
> 2.
> for(i=0;i<=100;i++)
> {
> for(i=0;i<=1000;i++)
> {
> .....;
> .....;
> }
>
> }
> so my question is which loop is best in terms of performance..please
> comment why is it so ..
> what i feel is 2nd loop is best in performance wise.
>

I'd expect the second loop to be marginally faster on some machines, because
the inner loop counter may be held in a register whilst the outer loop
counter may not be. So if the loop body is completely trivial you may have a
measureable speed difference.
However this is likely to be overwhelmed by the caches issues that other
people have mentioned in typical real code that loops to access arrays of
memory.

Malcolm, May 7, 2005
11. ### Chris McDonaldGuest

"Malcolm" <> writes:

>"Pavan" <> wrote in message
>> i have two nested loops as shown below:
>> 1.
>> for(i=0;i<=1000;i++)
>> {
>> for(i=0;i<=100;i++)
>> {
>> .....;
>> .....;
>> }
>>
>> }
>>
>>
>> and other one is
>> 2.
>> for(i=0;i<=100;i++)
>> {
>> for(i=0;i<=1000;i++)
>> {
>> .....;
>> .....;
>> }
>>
>> }
>> so my question is which loop is best in terms of performance..please
>> comment why is it so ..
>> what i feel is 2nd loop is best in performance wise.
>>

>I'd expect the second loop to be marginally faster on some machines, because
>the inner loop counter may be held in a register whilst the outer loop
>counter may not be. So if the loop body is completely trivial you may have a
>measureable speed difference.
>However this is likely to be overwhelmed by the caches issues that other
>people have mentioned in typical real code that loops to access arrays of
>memory.

I would expect a big performance impact because the two loops use the same
loop index variable.

______________________________________________________________________________
Dr Chris McDonald E:
Computer Science & Software Engineering W: http://www.csse.uwa.edu.au/~chris
The University of Western Australia, M002 T: +618 6488 2533
Crawley, Western Australia, 6009 F: +618 6488 1089

Chris McDonald, May 7, 2005