Alex Rivera | Logout

Eliminating recursive template instantiation in C++

Asked 2011-05-27T10:11:54.840
10

I want to define a macro that can be invoked in different places (at file scope) in order to create functions that do something. (In the example below the functions just print a message, but of course my real intent is to do some other useful stuff.) The challenge is that I want some "manager" function (in my example it will just be main()) to somehow succeed in getting them all invoked (in any order) without any of the code being dependent on the macro invocations (except for the macro invocations themselves, of course). What I mean is that once the file is written, another programmer would be able to just insert a few new macro invocations at various places or delete some of the existing invocations, and the code would still work without any further change. I realize this can be done using static objects but I want to explore a different approach. I'm going to use some template trickery and the fact that __LINE__ is monotone increasing.

#include <iostream>
using namespace std;

template<int i>
inline void f()
{
   f<i-1>();
}

#define START_REGISTRATION                                \
template<>                                                \
inline void f<__LINE__>() {}  /* stop the recursion */    \
template<> void f<__LINE__>()  /* force semicolon */

#define REGISTER(msg)                                     \
template<>                                                \
inline void f<__LINE__>()                                 \
{                                                         \
   cout << #msg << endl;                                  \
   f<__LINE__ - 1>();                                     \
}                                                         \
template<> void f<__LINE__>()  /* force semicolon */

// Unrelated code ...

START_REGISTRATION;

// Unrelated code ...

REGISTER(message 1);

// Unrelated code ...

R
c++ templates template-specialization
Edit
Report

2 Answers

5

The problem you face is that you're doing a linear search for f<i>, which causes an excessive number of instantiations.

The solution is to let f<i> call g<i,0>. This in turn calls g<i,i/2> and g<i/2,0>, which call g<i,i/2+i/4>, g<i/2+i/4,i/2>, g<i/2,i/4> and g<i/4, 0> ectetera. You'll of course specialize g<__LINE__, __LINE__> inside REGISTER().

Instantiating f<65536> will still cause 65536 template instantiations (you're effectively checking all previous 65536 lines), but the recursion depth is limited to log(65536), or 16 levels. That's doable.

answered 2011-05-27T13:51:26.270
1

Perhaps something like:

template<typename T>
struct register_struct {
    virtual void operator()() = 0;
    register_struct();
    register_struct *pNext;
};

template<typename T>
struct registry {
    static register_struct<T> *chain;
    static void walk() {
        register_struct<T> *p = chain;
        while (p) {
            (*p)();
            p = p->pNext;
        }
    }
};

template<typename T>
register_struct<T> *registry<T>::chain = NULL;

template<typename T>
register_struct<T>::register_struct()
{
    pNext = registry<T>::chain;
    registry<T>::chain = this;
}

#define DECL_REGISTRY(name) \
    struct tag_##name { } ; \
    void name() { registry<tag_##name>::walk(); }

#define JOIN_EXPAND(x, y) JOIN_EXPAND_2(x, y)
#define JOIN_EXPAND_2(x, y) x ## y

// Invoke REGISTER_PRINT at file scope!
#define REGISTER_PRINT(name, text) \
    namespace { \
    static struct : public register_struct<tag_##name> { \
        void operator()() { \
            std::cout << text << std::endl; \
        } \
    } JOIN_EXPAND(rs_##name##_, __LINE__); \
    }

DECL_REGISTRY(foo);

REGISTER_PRINT(foo, "hello")
REGISTER_PRINT(foo, "world")

int main() {
    foo();
    return 0;
}

This will fix the recursive instantiation issues, but you're still limited to one registration per line. However, since the registrations are at file scope, this should (hopefully!) be less of a problem.

Note that this is unsafe to use if you expect to invoke these prior to main() - you must allow static constructors to complete before using it.

answered 2011-05-27T14:08:35.350

Your Answer