Unrolling a loop

[Richard Cavell]

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)?

[Victor Bazarov]

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

[Karl Heinz Buchegger]

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
kb******@gascad.at

[Phillip Jordan]

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