Re: C++ Frequently Questioned Answers
on Sun Nov 04 2007, Walter Bright <walter-AT-digitalmars-nospamm.com> wrote:
David Abrahams wrote:
on Fri Nov 02 2007, Walter Bright <walter-AT-digitalmars-nospamm.com>
wrote:
I know very well how and why templates slow down compilation, and this
is inherent to how C++ templates work. It is not fixable.
We did a fair amount of testing of template instantiation speed for
http://www.amazon.com/Template-Metaprogramming-Concepts-Techniques-Depth/dp/0321227255
and we found a huge variation between the slowest and fastest template
instantiators. So there's great room for improvement in at least some
compilers.
Yes.
But even the fastest ones have performance problems because they do a
linear walk through a list of template specializations each time a
specialization is mentioned. An O(1) hash table lookup should make a
big difference. Why do you think it's not fixable?
Because a template must be generated for every state.
You mean "instantiated," and I'm not sure what you mean by "state."
Template metaprogramming is purely functional and thus stateless.
So, given
something like a factorial template:
template<int n> class factorial
{
public:
enum
{
result = n * factorial<n - 1>::result
};
};
template<> class factorial<1>
{
public:
enum { result = 1 };
};
void test()
{
// prints 24
printf("%d\n", factorial<4>::result);
}
If we try to do a factorial<10>, then 10 templates get
instantiated.
One template gets instantiated ten times. But look, there's
memoization, so in theory you can ask for factorial<10>::result as
many times as you want after that without penalty. In fact there's a
linear search in all compilers I know of, so you pay :(.
If you're using templates to do metaprogramming, this can consume a
serious amount of memory for even fairly simple loops (and a lot of
computation just to generate all those templates).
Yeah, that's why it's a good idea to use overload resolution instead
of class template instantiations wherever possible. The MPL
associative containers do that to get lookups in O(1) instantiations.
Essentially, you're reduced to doing only simple things with TMP
because of the problem of an explosion in the number of template
instantiations.
I don't see how this is fixable.
Oh, sure... it's fixable by ece.colorado.edu/~siek/phd-advert.html, a
project for which there is serious NSA grant money ;-)
But yeah, it won't be "_template_ metaprogramming" any more; at least,
I doubt it will.
P.S. You're right that a hash lookup will deal with one aspect of
the template instantiation explosion. But the compiler still must
generate some data structure for that template just to look it up,
and it's got to do it for *every* state in the template
metaprogram.
There's no state, but I think I know what you're talking about.
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]