Are there optimized c++ compilers for template use?

Question

C++ templates have been a blessing in my everyday work because of its power. But one cannot ignore the (very very very very long) compilation time that results from the heavy use of templates (hello meta-programming and Boost libraries). I have read and tried quite a lot of possibilities to manually reorganize and modify template code to make it compile as fast as possible.

Now I am wondering if there are any c++ compilers that try and minimize the needed time to interpret template classes. I might be wrong, but i feel that the compilers i do know have only added template interpretation to their previous versions.

My questions are :

• Is c++ template code so difficult to interpret that there is not much to optimize ? (i highly doubt that)
• Are there c++ compilers that truly optimize "c++ templates" interpretation ?
• Are there projects to develop a new generation of c++ compilers that would optimize this ?
• If you were to participate in such a project, what would your guidelines be ?

Answer 1

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.

Answer 2

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:

1. Construct a dependency graph for the initial values of the "size" enum value
2. Construct a template type for each edge in the graph
3. Bind all the symbols referenced by each constructed template type
4. Topologically sort the dependency graph
5. 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.