Are there optimized c++ compilers for template use?
I expect that compiling templated code will be speed up with having variadic templates / rvalue references. Today, if we want to write template code that does something at compile time, we abuse rules of the language. We create dozens of overloads and template specializations that results in what we want, but not in a way that tells the compiler our intention. So there is little to shortcut for the compiler at build-time. See Motivation for variadic templates
Are there projects to develop a new generation of c++ compilers that would optimize this ?
Yes, there is CLang which is a C Language Frontend for the LLVM Compiler infrastructure. Both CLang and LLVM are coded using C++. Among the developers of CLang is Douglas Gregor, author of several C++1x Language Proposals like variadic templates and Concepts. For reference, see this test by Douglas Gregor of clang against GCC
Here are some quick-n-dirty performance results for template instantiation in Clang and GCC 4.2. The test is very simple: measure compilation time (-fsyntax-only) for a translation unit that computes the Nth Fibonacci number via a template metaprogram. Clang appears to be scaling linearly (or close to it) with the number of instantiations. And, although you can't see it in the chart, Clang is a little over 2x faster than GCC at the beginning (
Fibonacci<100>).
CLang is still in its early days but i think it's got good chances to become a great C++ Compiler.
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.
The main problem with templates is the following:
You cannot (usually) separate the definition of your templates class from its declaration and put it inside a .cpp file.
The consequence: Everyting is in header files. Whenever you include a header you include a whole lot of code that would in normal circumstances be nicely separated into .cpp files and compiled separately. Every compile unit includes a few headers, and so, with templates, every compile unit contains a lot of code, or almost all of your project, via the included headers.
If that is your problem, then look here, at a related question:
- Templates: Use forward declarations to reduce compile time?
It got a very good answer, which does solve that problem.
Basically, it involves instantiating the templates that you need once, and compile them into an object file. Later you can link against it, and you don't have to include that code everywhere. It's separated into a compiled object file. Note: That makes sense only if you use only just a few instantiated types of your templates (say, you only need MyType<int> and MyType<double> in your program).
It uses the g++ flag -fno-implicit-templates.
That technique is so helpful that I think it should be incorporated into the C++ faq: [35.12] Why can't I separate the definition of my templates class from it's declaration and put it inside a .cpp file?
It seems that g++ 4.5 has made tremendous progress dealing with templates. Here are the two unavoidable changes.
"When printing the name of a class template specialization, G++ will now omit any template arguments which come from default template arguments." That could be considered a subtle modification, but it will have an enormous impact on development with c++ templates (ever heard of unreadable error messages... ? No more !)
"Compilation time for code that uses templates should now scale linearly with the number of instantiations rather than quadratically." This is going to severely undermine compilation-time arguments against the use of C++ templates.
See on the gnu site for complete information
Actually, i am already wondering whether there still are issues with c++ templates ! Mmm, yes, there are, but let's focus on the bright side for now !