Re: [boost] [fusion] improving compile times

Subject: Re: [boost] [fusion] improving compile times
From: Doug Gregor (doug.gregor_at_[hidden])
Date: 2009-06-03 17:12:56

On Wed, Jun 3, 2009 at 1:46 PM, Eric Niebler <eric_at_[hidden]> 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