Reputation: 3500

Eliminating recursive template instantiation in C++

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 ...

REGISTER(message 2);

// Unrelated code ...

REGISTER(message 3);

// Unrelated code ...

// manager function (in this case main() )
int main()
{
   f<__LINE__>();
}

This prints

message 3
message 2
message 1

as expected.

This solution has a few drawbacks.

Can't invoke REGISTER twice on the same line.
Will break if #line is played with.
Need to put the manager after all invocations of REGISTER.
Increased compile time due to the recursive instantiations.
Unless the "dummy" instantiations of f are all inlined away, the call-stack depth at runtime will be as great as the number of lines between START_REGISTRATION; and f<__LINE__>(); in the manager.
Code bloat: unless the "dummy" instantiations of f are all inlined away, the number of instantiations will similarly be be as great.
The excessive instantiation recursion depth is likely to hit the compiler's limit (500 by default on my system).

Issues 1-4 I don't really mind. Issue 5 can be eliminated by having each function return a pointer to the previous one, and having the manager use these pointers to call the functions iteratively rather than having them call each other. Issue 6 can be eliminated by creating a similar class template construct that is able to compute for each invocation of REGISTER what function was instantiated in the previous invocation and thus only instantiate the functions that actually do something. The excessive instantiation will then be shifted from the function template to the class template, but the class instantiations would only tax the compiler; they wouldn't trigger any code generation. So my real concern is Issue 7, and the question is: is there a way to restructure things so that the compiler does the instantiations iteratively rather than recursively. I am also open to different approaches altogether (apart from those involving static objects). One simple solution is to group all registrations together right before the manager (or add a STOP_REGISTRATION macro to end the block of registrations) but that would defeat a significant part of my purpose (registering stuff next to the code that defines it).

Edit: There have been some interesting suggestions, but I'm afraid I wasn't making myself clear in terms of what I hope to achieve. I'm really interested in two things: solving the problem as posed (i.e., no statics, single line per registration, no additional changes when adding/removing registrations, and, although I neglected to say so, only standard C++ --- hence, no boost). As I said in the comments below, my interest is more theoretical in nature: I'm hoping to learn some new techniques. Hence, I would really like to focus on restructuring things so the recursion is eliminated (or at least reduced) or finding a different approach that satisfies the constraints I laid out above.

Edit 2: MSalter's solution is a large step forward. At first I thought that every registration would incur the full cost of lines up to it, but then I realized that of course a function can be instantiated only once, so in terms of instantiations we pay the same price as in linear search, but the recursion depth becomes logarithmic. If I get around to it, I'll post a full solution eliminating Issues 5-7. It would still be nice, though, to see if it can be done in constant recursion depth, and best, with the number of instantiations linear in the number of invocations (a-la the boost solution).

Edit 3: Here's the full solution.

#define START_REGISTRATION                                          \
template<int lo, int hi>                                            \
struct LastReg {                                                    \
  enum {                                                            \
     LINE_NUM = LastReg<(lo + hi)/2 + 1, hi>::LINE_NUM ?            \
        static_cast<int>(LastReg<(lo + hi)/2 + 1, hi>::LINE_NUM) :  \
        static_cast<int>(LastReg<lo, (lo + hi)/2>::LINE_NUM)        \
  };                                                                \
};                                                                  \
template<int l>                                                     \
struct LastReg<l, l> {                                              \
   enum { LINE_NUM = 0 };                                           \
};                                                                  \
template<int l>                                                     \
struct PrevReg {                                                    \
   enum { LINE_NUM = LastReg<__LINE__ + 1, l - 1>::LINE_NUM };      \
};                                                                  \
template<int l> void Register() {}                                  \
template<int l> void Register()  /* force semicolon */


#define REGISTER(msg)                                               \
template<>                                                          \
struct LastReg<__LINE__, __LINE__> {                                \
   enum { LINE_NUM = __LINE__ };                                    \
};                                                                  \
template<>                                                          \
void Register<__LINE__>()                                           \
{                                                                   \
   cout << __LINE__ << ":" << #msg << endl;                         \
   Register<PrevReg<__LINE__>::LINE_NUM>();                         \
}                                                                   \
template<> void Register<__LINE__>()  /* force semicolon */


#define END_REGISTRATION                                            \
void RegisterAll()                                                  \
{                                                                   \
   Register<PrevReg<__LINE__>::LINE_NUM>();                         \
}                                                                   \
void RegisterAll()  /* force semicolon */


START_REGISTRATION;

REGISTER(message 1);

REGISTER(message 2);

END_REGISTRATION;


int main()
{
   RegisterAll();
}

Upvotes: 10

Answers (4)

Luc Touraille

Reputation: 82161

Here is a solution that limits recursion to the number of functions actually registered. Instead of using __LINE__ as the id, I used BOOST_PP_COUNTER, which is an incrementing counter available to the preprocessor.

The trick is that you can't increment the counter inside a macro since the increment is done through the inclusion of a header file. Consequently, I had to rely on file inclusion too, hence needing two lines instead of one to register a message (one line to define the message, and one line to actually register it).

Here is the code:

//register.hpp

#include <boost/preprocessor/slot/counter.hpp>

// general template function, not defined
template <unsigned int ID>
void f();

// base case, to stop recursion
template <>
void f<0>() {}


// macro to "hide" the name of the header to include (which should be in a
// "hidden" folder like "detail" in Boost 
#define REGISTER() "actually_register_msg.hpp"

//actually_register_msg.hpp

#include <boost/preprocessor/stringize.hpp>

// increment the counter
#include BOOST_PP_UPDATE_COUNTER()

template<>
inline void f< BOOST_PP_COUNTER >()
{
    std::cout << BOOST_PP_STRINGIZE( MSG_TO_REGISTER ) << std::endl;
    f< BOOST_PP_COUNTER - 1 >(); // call previously registered function
}

// to avoid warning and registering multiple times the same message
#undef MSG_TO_REGISTER

// id of the last registered function
#define LAST_FUNCTION_ID BOOST_PP_COUNTER

// main.cpp

#define MSG_TO_REGISTER message 1
#include REGISTER()

#define MSG_TO_REGISTER message 2
#include REGISTER()

#define MSG_TO_REGISTER message 3
#include REGISTER()

int main()
{
    f< LAST_FUNCTION_ID >();
}

Like your code, this prints

message 3
message 2
message 1

Of course, the registering call is a bit less pretty (one #define and one #include instead of a single macro call), but you avoid a lot of unecessary template instantiations.

Upvotes: 0

vines

Reputation: 5225

I've once done something similar, which instantiates only a limited count of specializations. The goal was to aggregate all the specializations into an array of pointers and access them with a single method via the enum, but you easily can adapt it to your similar (as I suppose) needs.

#include <iostream>

using namespace std;

class I {
public:
    virtual ~I() {};

    virtual void P(int index) = 0;

    enum Item {
        Item0,
        Item1,
        Item2,
        Item3,
        Item4,
        ItemNum
    };
};


template <class T> class A: public I {
public:
    A() {
        Unroll<A<T>, ItemNum> tmp (m_F);
    }
    virtual ~A() {
    }

    void P(int index) { (this->*m_F[index])(); }

protected:
    typedef void (A<T>::*F)();
    F m_F[ItemNum];

    template <int N> void p() { cout << "default!" << endl; }

    template <class W, int C> struct Unroll
    {
        Unroll(typename W::F * dest)
        {
            dest[C-1] = & W::template p<C-1>;
            Unroll<W, C-1> u(dest);
        }
    };
};

template <class T> template <class W> struct A<T>::Unroll<W, 0>
{ public: Unroll(typename W::F * dest) {} };

class B: public A<B>
{
public:

};

template <> template <> void A<B>::p<A<B>::Item1>() { cout << 1 << endl; }
template <> template <> void A<B>::p<A<B>::Item2>() { cout << 2 << endl; }
template <> template <> void A<B>::p<A<B>::Item4>() { cout << "it hacking works!" << endl; }


int main()
{
    I *a = new B;
    for (int i = 0; i < I::ItemNum; ++i) a->P(i);
    return 0;
}

Upvotes: 0

bdonlan

Reputation: 231451

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.

Upvotes: 1

MSalters

Reputation: 180305

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.

Upvotes: 5

Eliminating recursive template instantiation in C++

Answers (4)

Related Questions