Loop unrolling question. Does this make sense?

Discussion in 'C++' started by John Edwards, Jul 6, 2003.

  1. John Edwards

    John Edwards Guest

    Hello,

    I have sort of a newbie question. I'm trying to optimize a loop by
    breaking it into two
    passes.

    Example:

    for(i = 0; i < max; i++)
    {
    do this
    and this
    }

    (The value of max is not known)

    I want to change it to this:

    for(i = 0; i < max /2; i++)
    {
    do this
    and this
    }
    for(i = max /2; i < max; i++)
    {
    do this
    and this
    }


    Does this make sense and will I get anything out of it?
    John Edwards, Jul 6, 2003
    #1
    1. Advertising

  2. "John Edwards" <> wrote...
    > I have sort of a newbie question. I'm trying to optimize a loop by
    > breaking it into two
    > passes.
    >
    > Example:
    >
    > for(i = 0; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    > (The value of max is not known)
    >
    > I want to change it to this:
    >
    > for(i = 0; i < max /2; i++)
    > {
    > do this
    > and this
    > }
    > for(i = max /2; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    >
    > Does this make sense and will I get anything out of it?


    No, you will not. You might be able to get something out of

    if (max & 1)
    {
    do this
    and this
    }
    for (i = 0; i < max/2; ++i)
    {
    do this
    and this
    do this
    and this
    }

    Of course, if 'do this and this' uses 'i' somehow, it may not
    be worth unrolling, since any arithmetic will chew up any time
    you save by unrolling.

    Victor
    Victor Bazarov, Jul 6, 2003
    #2
    1. Advertising

  3. John Edwards

    Sam Holden Guest

    On Sun, 06 Jul 2003 20:06:24 GMT, John Edwards <> wrote:
    > Hello,
    >
    > I have sort of a newbie question. I'm trying to optimize a loop by
    > breaking it into two
    > passes.
    >
    > Example:
    >
    > for(i = 0; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    > (The value of max is not known)
    >
    > I want to change it to this:
    >
    > for(i = 0; i < max /2; i++)
    > {
    > do this
    > and this
    > }
    > for(i = max /2; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    >
    > Does this make sense and will I get anything out of it?


    Not really and it will run slower.

    Loop unrolling looks like:

    for(i=0;i<max;i+=2)
    {
    do this
    and this
    do this
    and this
    }

    If i is more than just a loop counter, then the i+=2 might change to ++i
    with a ++i inside the loop body as well.

    Of course this will do awful things for an odd length max, and two instances
    of the loop body isn't going to achieve much (especially when the check for
    odd max overhead is added).

    Don't even think of unrolling a loop until the loop has been shown to
    actually be contributing to unsatisfactory performance. And then benchmark
    before and after, since you can slow things down (by a lot if the code of
    the body (and loop overhead) now doesn't fit in cache on architectures
    which have such things - which I suspect is almost all architectures in
    which you would be trading code space for code speed in that direction).

    --
    Sam Holden
    Sam Holden, Jul 6, 2003
    #3
  4. "John Edwards" <> wrote...
    > So what you're saying is that unless they are using 'i', it may not be

    worth
    > it?


    No, I said exactly the opposite.

    >
    > 'Do this & that' is actually doing writes for vector graphics.
    >
    >
    >
    >
    >
    > "Victor Bazarov" <> wrote in message
    > news:...
    > > "John Edwards" <> wrote...
    > > > I have sort of a newbie question. I'm trying to optimize a loop by
    > > > breaking it into two
    > > > passes.
    > > >
    > > > Example:
    > > >
    > > > for(i = 0; i < max; i++)
    > > > {
    > > > do this
    > > > and this
    > > > }
    > > >
    > > > (The value of max is not known)
    > > >
    > > > I want to change it to this:
    > > >
    > > > for(i = 0; i < max /2; i++)
    > > > {
    > > > do this
    > > > and this
    > > > }
    > > > for(i = max /2; i < max; i++)
    > > > {
    > > > do this
    > > > and this
    > > > }
    > > >
    > > >
    > > > Does this make sense and will I get anything out of it?

    > >
    > > No, you will not. You might be able to get something out of
    > >
    > > if (max & 1)
    > > {
    > > do this
    > > and this
    > > }
    > > for (i = 0; i < max/2; ++i)
    > > {
    > > do this
    > > and this
    > > do this
    > > and this
    > > }
    > >
    > > Of course, if 'do this and this' uses 'i' somehow, it may not
    > > be worth unrolling, since any arithmetic will chew up any time
    > > you save by unrolling.
    > >
    > > Victor
    > >
    > >

    >
    >
    Victor Bazarov, Jul 6, 2003
    #4
  5. John Edwards

    Artie Gold Guest

    [OT] Re: Loop unrolling question. Does this make sense?

    John Edwards wrote:
    > Hello,
    >
    > I have sort of a newbie question. I'm trying to optimize a loop by
    > breaking it into two
    > passes.
    >
    > Example:
    >
    > for(i = 0; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    > (The value of max is not known)
    >
    > I want to change it to this:
    >
    > for(i = 0; i < max /2; i++)
    > {
    > do this
    > and this
    > }
    > for(i = max /2; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    >
    > Does this make sense and will I get anything out of it?
    >


    Unfortunately, you seem not to have a real understanding of what loop
    unrolling is. May I refer you to the following link?

    http://users.chariot.net.au/~matty/ultra/optcat/Loop_Unrolling.html

    BTW -- your question is really not topical here (as, at its heart, it is
    not a question about the C++ language).

    Your compiler may have an optimization option to unroll loops (see your
    documentation); in any event, micro-optimizations at the source code
    level should only be performed if you have empirically determined (by,
    e.g. profiling) that a particular piece of code is causing a bottleneck.

    HTH,
    --ag


    --
    Artie Gold -- Austin, Texas



    ----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
    http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
    ---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
    Artie Gold, Jul 6, 2003
    #5
  6. John Edwards wrote:
    > Hello,
    >
    > I have sort of a newbie question. I'm trying to optimize a loop by
    > breaking it into two
    > passes.
    >
    > Example:
    >
    > for(i = 0; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    > (The value of max is not known)
    >
    > I want to change it to this:
    >
    > for(i = 0; i < max /2; i++)
    > {
    > do this
    > and this
    > }
    > for(i = max /2; i < max; i++)
    > {
    > do this
    > and this
    > }
    >
    >
    > Does this make sense and will I get anything out of it?


    The standard technique of loop unrolling is to
    repeat the statements inside the loop and adjusting
    the counter; not to repeate the loops.

    The goal is to divide the cost (overhead) of updating
    and comparing the indices over the cost of the statements.
    For example, repeating the inner block twice will reduce
    the overhead cost by 1/2.

    Be aware that the number of iterations must be evenly
    divisible by the number of statement repetitions.

    Guide to Optimization
    ---------------------
    1. Don't. Get the program working correctly first.
    2. Don't. Use a profiler and analyze the program execution.
    The 80/20 rule states that 80% of the program's execution
    occurs in 20% of the code.
    3. Review function designs. A lot of execution gain can
    be obtained at the design level. Remove unused functions,
    operations, data and code. Simplify repetitive operations.
    Don't process data unless required to do so (lazy processing).
    4. Inline function calls for small sized functions. If the
    content of the function is smaller or slightly larger than
    the overhead of the function call, inline it.
    5. Factor out constant expressions and statements from loops.
    6. Review floating point operational costs. Some processors
    choke on fp operations, some have no extra cost. If there
    is a penalty (or additional cost) keep everything as integers
    until the last moment.
    7. Unroll loops, if you have the code space.
    8. Replace function contents with assembly language. Write
    the assembly language function to take advantage of any
    special (helpful) processor features, such as pipelining
    or caches.

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c /faq.html
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
    Thomas Matthews, Jul 7, 2003
    #6
    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. =?ISO-8859-1?Q?Per_Nordl=F6w?=

    g++ loop unrolling performance

    =?ISO-8859-1?Q?Per_Nordl=F6w?=, Aug 31, 2004, in forum: C++
    Replies:
    1
    Views:
    984
    Jack Klein
    Sep 1, 2004
  2. Richard Cavell

    Unrolling a loop

    Richard Cavell, Feb 23, 2005, in forum: C++
    Replies:
    3
    Views:
    2,214
    Phillip Jordan
    Feb 23, 2005
  3. V

    unrolling nested for-loop

    V, May 10, 2008, in forum: C Programming
    Replies:
    10
    Views:
    1,067
    Willem
    May 10, 2008
  4. mark

    ultra-fast loop unrolling with g++ -O3

    mark, Jun 12, 2008, in forum: C Programming
    Replies:
    2
    Views:
    731
    santosh
    Jun 12, 2008
  5. Isaac Won
    Replies:
    9
    Views:
    349
    Ulrich Eckhardt
    Mar 4, 2013
Loading...

Share This Page