Unrolling loops using templates in C++ with partial specialization

Question

I'm trying to use templates to unroll a loop in C++ as follows.

#include <iostream>

template< class T, T i >
struct printDown {
    static void run(void) {
        std::cout << i << "\n";
        printDown< T, i - 1 >::run();
    }
};

template< class T >
struct printDown< T, 0 > {
    static void run(void) {
        std::cout << 0 << "\n";
    }
};

int main(void) {
    printDown< int, 10 >::run();
    return 0;
}

When I compile w/ g++ 3.4.4 in Cygwin, I get the following error.

tmp.cpp:12: error: type T' of template argument0' depends on template parameter(s)

What am I doing wrong? Do I need to somehow annotate the 0 to say that it's of type T?

Thanks in advance.

Introspect

Answer 1

Have you tried int i instead of T i?

Thirteenth

(And by that I mean: leave out class T, use a single template parameter int i for the first specialization, and an empty template <> for the zero-case.) – Thirteenth

@phooji: I'd rather recommend an unsigned integer (whichever you want) – Cherilyncherilynn

@Matthieu M: I'm not sure what you mean -- are you saying that unsigned is more appropriate (since we're generally counting down to zero)? – Thirteenth

@phooji: I am saying that given that in his particular implementation he is counting toward 0, using a negative value would play havoc with the compilation, and so proposing to switch to an unsigned integer. – Cherilyncherilynn

@Matthieu M: That's true, but an integer value (signed or unsigned) of 30 would be equally bad on most compilers, I think (i.e., it would fail to instantiate the template expression). In other words, unsigned would yield just as many values that do not work. – Thirteenth

@phooji: for this particular implementation, I guess, but a clever implementation use binary decomposition with a logarithmic depth. – Cherilyncherilynn

Answer 2

Why this happens? From 14.5.5/8,

— The type of a template parameter corresponding to a specialized non-type argument shall not be dependent on a parameter of the specialization. [ Example:

template <class T, T t> struct C {};
template <class T> struct C<T, 1>; // error
template< int X, int (*array_ptr)[X] > class A {};
int array[5];
template< int X > class A<X,&array> { }; // error

—end example ]

Therefore when you apply partial specialization, the type of 0 is T (dependent on a parameter of the specialization). There are two choices, one is to make it none dependent, e.g., change T i to int i, and second is to apply explicit specialization rather than partial specialization.

Both solutions have been given out by others, so I'm not gonna to repost them here. At least you know the reason. It's defined by standard.

Salmi

Thanks for the explanation. I didn't know about this rule. The problem is that making the non-recursive case "struct printDown< unsigned, 0 >" means that the type is specialized for unsigned, or int if I change it to that. But it's not general. I wanted to generalize this for any type that can have 1 subtracted from it & that can be compared with 0. How can I accomplish that? – Introspect

Answer 3

As pointed out by phooji your implementation suffers from a small issue: it quickly generates a long list of calls, which will make compilers choke quickly.

You could work around this by implementing a slightly more complicated version, using binary decomposition. I'll make it generic on a functor too, cause I am lazy.

// Signature
template <Functor F, unsigned N>
struct UnrolledLoop;

We need a helper template, which keeps an offset of the parameter to pass

template <Functor F, unsigned N, unsigned OffSet>
struct UnrolledImpl;

template <Functor F, unsigned OffSet>
struct UnrolledImpl<F, 0, OffSet>
{
  static F run(F f) { return f; }
};

template <Functor F, unsigned OffSet>
struct UnrolledImpl<F, 1, OffSet>
{
  static F run(F f) { f(OffSet); return f; }
};

template <Functor F, unsigned N, unsigned OffSet>
struct UnrolledImpl
{
  static F run(F f) {
    F f2 = UnrolledImpl<F, N/2, OffSet>::run(f);
    return UnrolledImpl<F, N - N/2, OffSet + N/2>::run(f2);
  }
};

And you can implement UnrolledLoop simply:

template <Functor F, unsigned N>
struct UnrolledLoop
{
  static F run(F f) { return UnrolledImpl<F, N, 0>::run(f); }
}

Note that you could provide specialization for more values of N (3, 4 for example) to be nicer on the compiler.

Cherilyncherilynn

+1 Perhaps not a compliment, but you're my kind of crazy :) At this point, it might be worth pointing out the Boost MPL: boost.org/doc/libs/1_46_0/libs/mpl/doc/index.html . – Thirteenth

@phooji: I'll take it as a compliment :) I like to fiddle with the MPL, Fusion... and the Preprocessor ^^ I do have to restrain myself at work though :/ – Cherilyncherilynn

Answer 4

What about adding this to your example:

template struct printDown< int, 0 >{
    static void run(void) {
    std::cout << 0 << "\n";
} };

The compiler cannot cast 0 to int automatically without knowing T's type in advance.

Shelter

Answer 5

Just found this out. Apparently one can do something like this.

template< class T, T i, bool b = (i == 0) >
struct printDown {
    static void run(void) {
        std::cout << i << "\n";
        printDown< T, i - 1 >::run();
    }
};

template< class T, T i >
struct printDown< T, i, true > {
    static void run(void) {
        std::cout << 0 << "\n";
    }
};

I had no idea that could be done. Very Prologish & very nice.

Introspect

Answer 6

You can make the parameter a type parameter to work this around

template< bool > struct bool_ { };

template< class T, T i, typename = bool_<true> >
struct printDown {
    static void run(void) {
        std::cout << i << "\n";
        printDown< T, i - 1 >::run();
    }
};

template< class T, T i >
struct printDown< T, i, bool_<i == 0> > {
    static void run(void) {
        std::cout << 0 << "\n";
    }
};

int main(void) {
    printDown< int, 10 >::run();
    return 0;
}

This way you can specify any conditions you want in the partial specializations.

Ligialignaloes