Recursive inline expansion
Since I’m talking about recursive templates today I thought I’d mention recursive inline expansion. Suppose we define factorial (with no bounds checking) like this.
template< int N > inline int factorial( )
{
return N * factorial< N - 1 >( );
}
template<> inline int factorial< 0 >( )
{
return 1;
}
The template language will calculate values of N and only generate the necessary code. If the compiler chose to follow the “inline” request it would generate a good optimization. factorial< 5 >( ) would become the constant (5*4*3*2*1*1), or 120.
Now let’s do the same thing without templates.
inline int factorial( int N)
{
return (N == 0) ? 1 : (N * factorial( N - 1));
}
An inline expansion of this function could go forever unless N is a compile-time constant and the compiler trims the code by watching for (N==0). You can see something similar when using #define.
// You cannot recurse with #define, but this kludge works. # define FACTORIAL( N ) (((N)==0)?1:((N)*FACTORIAL_1((N)-1))) // Helper macros: # define FACTORIAL_1( N ) (((N)==0)?1:((N)*FACTORIAL_2((N)-1))) # define FACTORIAL_2( N ) (((N)==0)?1:((N)*FACTORIAL_3((N)-1))) # define FACTORIAL_3( N ) (((N)==0)?1:((N)*FACTORIAL_4((N)-1))) # define FACTORIAL_4( N ) (((N)==0)?1:((N)*FACTORIAL_5((N)-1))) # define FACTORIAL_5( N ) (((N)==0)?1:((N)*FACTORIAL_6((N)-1))) # define FACTORIAL_6( N ) (((N)==0)?1:((N)*FACTORIAL_7((N)-1))) # define FACTORIAL_7( N ) (((N)==0)?1:((N)*FACTORIAL_8((N)-1))) # define FACTORIAL_8( N ) 0
This only works though FACTORIAL( 7). FACTORIAL( 8) is zero. Something trivial like FACTORIAL( 2) expands into a huge mess.
FACTORIAL( 2 ) becomes: (((2)==0)?1:((2)* ((((2)-1)==0)?1:(((2)-1)* (((((2)-1)-1)==0)?1:((((2)-1)-1)* ((((((2)-1)-1)-1)==0)?1:(((((2)-1)-1)-1)* (((((((2)-1)-1)-1)-1)==0)?1:((((((2)-1)-1)-1)-1)* ((((((((2)-1)-1)-1)-1)-1)==0)?1:(((((((2)-1)-1)-1)-1)-1)* (((((((((2)-1)-1)-1)-1)-1)-1)==0)?1:((((((((2)-1)-1)-1)-1)-1)-1)* ((((((((((2)-1)-1)-1)-1)-1)-1)-1)==0)?1:(((((((((2)-1)-1)-1)-1)-1)-1)-1)* 0))))))))))))))))
Imagine how big that’d be if we defined it all the way through FACTORIAL( 20).
So you see that recursive inline expansion can get out of hand. That’s why the C++ preprocessor doesn’t allow it, and why compilers usually don’t attempt it. But it is not always a bad idea, as the template example shows. Templates force the compiler to look at values and trim code accordingly. Code generation is a wonderful thing, and intelligent code generation is much more useful than simple macro expansion.
Comments
Leave a Reply