Re: C++ PATCH to use hash tables for template specialization lookup

["H.J. Lu" <hjl dot tools at gmail dot com>]

On Thu, Jul 2, 2009 at 10:27 AM, Jason Merrill <jason@redhat.com> wrote:
> Someone recently sent me an expression template testcase, complaining about
> how slow compilation was; looking at it with callgrind, I saw that fully 64%
> of compilation was spent in retrieve_specialization, walking lists of
> specializations and comparing all the arguments. ?So I set out to switch GCC
> over to use hash tables for template lookup.
>
> The good news: the patch significantly reduces compile time (~25%) for that
> example.
>
> The mediocre news: the patch doesn't significantly affect compile time for
> the regression testsuite; testrun time is about the same before and after
> the patch.
>
> So, less improvement than I was hoping to see, but still a win.
>
> Basically, rather than look up template instances on the
> DECL_TEMPLATE_SPECIALIZATIONS and DECL_TEMPLATE_INSTANTIATIONS lists, the
> patch creates two global hash tables, one for decls and one for types. ?We
> generate a hash value for any comtemplate bination of template and
> arguments, and store and retrieve them as appropriate.
>
> Unfortunately, we still need those lists: the former to store partial
> specializations, since we need to look at the whole set to do partial
> ordering, and the latter because in certain situations we need to reassign
> all instances of a template to a different template.
>
> For classes, this happens as in g++.dg/template/spec8.C: We have an explicit
> specialization of A<int>::B<int> followed by an explicit specialization of
> A<int>::B<U>. ?Before this patch, G++ incorrectly gave an error for this
> situation; this patch corrects the behavior so that the earlier
> specialization is reassigned to the later specialized template.
>
> For functions, this happens when we have a declaration of a namespace-scope
> function template followed by a matching definition of a friend template
> within a class template. ?The first time the class template is instantiated,
> the namespace-scope function template becomes a partial instantiation of the
> friend template, so we need to move any instances of the original function
> template onto the friend template. This is in the testsuite somewhere, but I
> can't remember which testcase it was, nor find it at the moment.
>
> I considered putting a hash table in each template so that we could traverse
> them instead of the above lists, but that seemed expensive.
>
> I also tried to reduce the number of redundant lookups we do.
>
> Tested x86_64-pc-linux-gnu, applied to trunk.
>

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41785

-- 
H.J.