Velocity Reviews > abt nested loops

# abt nested loops

Pavan
Guest
Posts: n/a

 05-06-2005
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

pete
Guest
Posts: n/a

 05-06-2005
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

Pavan
Guest
Posts: n/a

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

cheers
Pavan

pete
Guest
Posts: n/a

 05-06-2005
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

bjrnove
Guest
Posts: n/a

 05-06-2005
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

Fred L. Kleinschmidt
Guest
Posts: n/a

 05-06-2005

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

Kenneth Brody
Guest
Posts: n/a

 05-06-2005
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: <(E-Mail Removed)>

Emmanuel Delahaye
Guest
Posts: n/a

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

Because you are using the same counter. 2 loops, 2 counters.

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

"C is a sharp tool"

SM Ryan
Guest
Posts: n/a

 05-06-2005
"Pavan" <(E-Mail Removed)> 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[i][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.

Malcolm
Guest
Posts: n/a

 05-06-2005

"Pavan" <(E-Mail Removed)> 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.