Eliminating recursive template instantiation in C++

Question

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.

1. Can't invoke REGISTER twice on the same line.
2. Will break if #line is played with.
3. Need to put the manager after all invocations of REGISTER.
4. Increased compile time due to the recursive instantiations.
5. 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.
6. Code bloat: unless the "dummy" instantiations of f are all inlined away, the number of instantiations will similarly be be as great.
7. 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();
}

Answer 1

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.