Unrolling a loop

Discussion in 'C++' started by Richard Cavell, Feb 23, 2005.

  1. I have a recursive function like this:

    void MyFunction(int i)
    {
    i++;
    // do something with i
    if (we're not finished) MyFunction(i);
    }

    I keep count of how far nested we are with i. Now, it would give the
    compiler more chances at optimisation if I could give each loop its own
    block of code, like this:

    void MyFunctionNextedThrice()
    {
    // do something with the number two
    // if (we're not finished) MyFunctionNestedFourTimes();
    }

    void MyFunctionNestedTwice()
    {
    // do something with the number zero
    // if (we're not finished) MyFunctionNestedThrice();
    }

    void MyFunctionNextedOnce()
    {
    // do something with the number one
    // if (we're not finished) MyFunctionNestedTwice();
    }

    void MyFunction()
    {
    // do something with the number zero
    // if (we're not finished) MyFunctionNestedOnce();
    }

    What would be orgasmic is if I could 'inline' them inside each other.
    Is there some way of creating a template (not in the C++ sense)? Do I
    use macros (which, as the FAQ points out, are evil)?
     
    Richard Cavell, Feb 23, 2005
    #1
    1. Advertising

  2. Richard Cavell wrote:
    > I have a recursive function like this:
    >
    > void MyFunction(int i)
    > {
    > i++;
    > // do something with i
    > if (we're not finished) MyFunction(i);
    > }
    >
    > I keep count of how far nested we are with i. Now, it would give the
    > compiler more chances at optimisation if I could give each loop its own
    > block of code, like this:
    >
    > void MyFunctionNextedThrice()
    > {
    > // do something with the number two
    > // if (we're not finished) MyFunctionNestedFourTimes();
    > }
    >
    > void MyFunctionNestedTwice()
    > {
    > // do something with the number zero
    > // if (we're not finished) MyFunctionNestedThrice();
    > }
    >
    > void MyFunctionNextedOnce()
    > {
    > // do something with the number one
    > // if (we're not finished) MyFunctionNestedTwice();
    > }
    >
    > void MyFunction()
    > {
    > // do something with the number zero
    > // if (we're not finished) MyFunctionNestedOnce();
    > }
    >
    > What would be orgasmic is if I could 'inline' them inside each other. Is
    > there some way of creating a template (not in the C++ sense)?


    Why "not in the C++ sense"? Recursive template definitions are very
    common and form the foundation of "meta-programming".

    > Do I use
    > macros (which, as the FAQ points out, are evil)?


    I don't know what you use. I use templates:

    template<int depth> void MyFunction(int i) {
    blahblah
    if (something)
    MyFunction<depth-1>(i);
    }

    template<> void MyFunction<0>(i) {
    whatever you use at depth 0
    // no recursion any more
    }

    Or you could go positive, then limit yourself from above:

    template<int depth> void MyFunction(int i) {
    blahblah
    if (something)
    MyFunction<depth+1>(i);
    }

    template<> void MyFunction<5>(i) {
    whatever you use at depth 5
    // no recursion any more
    }

    V
     
    Victor Bazarov, Feb 23, 2005
    #2
    1. Advertising

  3. Richard Cavell wrote:
    >
    > I have a recursive function like this:
    >
    > void MyFunction(int i)
    > {
    > i++;
    > // do something with i
    > if (we're not finished) MyFunction(i);
    > }
    >
    > I keep count of how far nested we are with i. Now, it would give the
    > compiler more chances at optimisation if I could give each loop its own
    > block of code, like this:


    or like this:

    void MyFunction( int i )
    {
    do {
    i++;
    // do something with i
    } while( we're not finished )
    }

    Look up: Tail recursion elimination

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Feb 23, 2005
    #3
  4. Richard Cavell wrote:
    > ["unrolling" a recursion cascade]


    Well, the first (obvious) thing to check is whether it really is
    necessary to use a recursive function to do the job. In most cases, a
    loop will be just as good, or better.

    If not -
    > What would be orgasmic is if I could 'inline' them inside each other. Is
    > there some way of creating a template (not in the C++ sense)? Do I use
    > macros (which, as the FAQ points out, are evil)?


    You've actually inadvertently hit the nail right on the head there -
    it's possible to "unroll" recursion using C++ templates.

    Unrolling is only possible if the recursion depth is known at compile
    time, which is also necessary for using templates.

    The technique is described extensively in [1], but the general gist of
    it is to create a template and to pass your recursion data to the next
    level using template parameters rather than function parameters.

    [1] uses class templates, but for more involved operations you'll
    probably want to use an inline function template. Using one of the
    typical examples for recursion, (for which you'd never use recursion in
    the real world...) calculating factorials:

    ////////////////////////////////////////
    template <int i> inline int Factorial();
    // termination specialisation
    template <> inline int Factorial<1>();

    template <int i> inline int Factorial()
    {
    return i * Factorial<i - 1>();
    }

    template <> inline int Factorial<1>()
    {
    return 1;
    }
    ////////////////////////////////////////

    Factorials can then be evaluated using

    Factorial<5>();

    Whether the technique is effective depends heavily on your compiler,
    however; there is no *guarantee* that your compiler will expand it
    properly. If in doubt, look at the compiler's assembly output.

    [1] Mark DeLoura, Game Programming Gems. 2000, Charles River Media
    Gem 1.2, "Fast Math Using Template Metaprogramming"

    ~phil
     
    Phillip Jordan, Feb 23, 2005
    #4
    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. John Edwards
    Replies:
    5
    Views:
    386
    Thomas Matthews
    Jul 7, 2003
  2. =?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:
    1,073
    Jack Klein
    Sep 1, 2004
  3. V

    unrolling nested for-loop

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

    ultra-fast loop unrolling with g++ -O3

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

Share This Page