On Wed, Jun 3, 2009 at 1:46 PM, Eric Niebler <eric@boostpro.com> wrote:
Doug Gregor wrote:
Template instantiation is expensive, but you're probably seeing some O(n^2) or worse effects because of a poor choice in data structures.
Indeed, I recall Walter saying it's an N^2 problem. I've convinced him to write a blog entry about why template instantiation in C++ is inherently slow, so soon we'll know why he thinks so. Maybe your work in Clang can prove him wrong.
I hope so!
The cost of template *instantiation* for the Fibonacci example is quite small for both compilers, since we're just talking about creating a class with its special member functions and a single static data member.
Would it go faster if the compiler didn't have to create the special member functions? Could we use the declared-but-not-defined trick to suppress their generation and speed up template instantiations for metafunctions?
Yes. GCC already optimizes this case, in the sense that it doesn't build the declaration for a special member function until that declaration is actually needed. Other compilers most certainly have a similar optimization, but Clang does not have it (yet).
However, GCC is exhibiting quadratic behavior because every time we name Fibonacci<I> for some value I, it's doing a linear search to see if there's already a specialization for that value of I. Clang is scaling much better here because our search for an already-named specialization is constant time in the average case.
I can't promise that the improvements we see in Fibonacci will extend to real template metaprograms, because I haven't tried it. Nor can I: Clang lacks both member templates and class template partial specialization [*], which means that we can't compile a serious template metaprogram with Clang. Obviously, template metaprogramming is important to me, personally, so we'll do our best to scale this well for real template metaprograms.
Where can I read more and follow the team's progress?
Information about Clang is available here: http://clang.llvm.org/ Clang is open source, so the best way to follow the team's progress is to join us and help Clang progress faster :) Barring that, the developer and commit mailing lists can help watch progress at a course-grained level, and the C++ Status page shows roughly where we think we are. - Doug