Re: C++ Frequently Questioned Answers
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. 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. 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). 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.
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. Such effort
makes even the worst interpreter run like a tachyon in comparison <g>.
----
Walter Bright
Digital Mars C, C++, D programming language compilers
http://www.digitalmars.com
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]