This really isn't an answer to your question. It's more of a side observation.
I'm not an C++ language lawyer either , and so I could be way off base with some of the details.
But, the rough idea should be correct.
The main reason that C++ compilers take such a long time to compile template meta-programs is because of the way template meta-programs are specified.
They aren't specified directly as code that you want the compiler to run at compile time. Take the example of computing the length of a type list.
If you could write code like this:
compile_time size_t GetLength(TypeList * pTypeList)
{
return DoGetLength(pTypeList, 0);
}
compile_time size_t DoGetLength(TypeList * pTypeList, size_t currentLength)
{
if (pTypeList)
{
return DoGetLength(pTypeList->Next, ++currentLength);
}
else
{
return currentLength;
}
}
That was some how compiled separately from the code where it was used, and was exposed to the language via some syntax, then the compiler would be able to execute it very quickly.
It would just be a simple recursive function call.
It's possible to design language that allows those sorts of things. Most of the ones that do this (like lisp) are dynamically typed, but it is possible to do with static typing. However, it's not likely to ever be something you would see implemented in C++.
The problem in C++, however, is that the code is written like:
template <typename First, typename Second>
struct TypeList
{
typedef First Head;
typedef Second Tail;
};
template <>
struct ListSize<NullType>
{
enum { size = 0 };
};
template <typename Head, typename Tail>
struct ListSize<TypeList<Head, Tail> >
{
enum { size = 1 + ListSize<Tail>::size };
};
In order for the compiler to "execute" the meta-program it has to:
- Construct a dependency graph for the initial values of the "size" enum value
- Construct a template type for each edge in the graph
- Bind all the symbols referenced by each constructed template type
- Topologically sort the dependency graph
- Traverse the graph and evaluate the constants
This is much more expensive than just simply running a O(N) recursive algorithm.
The worst case would be something like O(N * M * L), with N equal to the length of the list, M being the level of scope nesting , and L being the number of symbols in each scope.
My advice would be to minimize the amount of C++ template meta-programming that you use.