abt nested loops

[Pavan]

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]

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.

 

[Pavan]

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

please be clear

cheers
Pavan

 

[pete]

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

please be clear

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
*/

}

 

[bjrnove]

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.

 

[Fred L. Kleinschmidt]

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
*/

}

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.

 

[Kenneth Brody]

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:[email protected]>

 

[Emmanuel Delahaye]

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]

# 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
tiling for more information.

 

[Malcolm]

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.

 

[Chris McDonald]

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: (e-mail address removed)
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