abt nested loops

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

  1. Pavan

    Pavan Guest

    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
    #1
    1. Advertising

  2. Pavan

    pete Guest

    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
    #2
    1. Advertising

  3. Pavan

    Pavan Guest

    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
    Pavan, May 6, 2005
    #3
  4. Pavan

    pete Guest

    Pavan wrote:
    >
    > 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
    */

    }

    --
    pete
    pete, May 6, 2005
    #4
  5. Pavan

    bjrnove Guest

    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
    #5
  6. 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
    > >
    > > 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
    > */
    >
    > }
    >
    > --
    > 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
    #6
  7. 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
    #7
  8. Emmanuel Delahaye, May 6, 2005
    #8
  9. Pavan

    SM Ryan Guest

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

    --
    SM Ryan http://www.rawbw.com/~wyrmwif/
    So basically, you just trace.
    SM Ryan, May 6, 2005
    #9
  10. Pavan

    Malcolm Guest

    "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
    #10
  11. "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
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Derek LaZard

    Re: Abt Datareader Count

    Derek LaZard, Jul 8, 2003, in forum: ASP .Net
    Replies:
    0
    Views:
    1,737
    Derek LaZard
    Jul 8, 2003
  2. Replies:
    5
    Views:
    552
    Ray Andraka
    Mar 3, 2005
  3. prasad

    abt floating point numbers

    prasad, Jan 27, 2006, in forum: VHDL
    Replies:
    1
    Views:
    577
    David Bishop
    Feb 4, 2006
  4. samrat

    question abt speech apllication

    samrat, Nov 5, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    367
    charles
    Nov 5, 2003
  5. Me
    Replies:
    2
    Views:
    237
Loading...

Share This Page