How templates might be improved

Stefan Koch via Digitalmars-d digitalmars-d at puremagic.com
Fri Sep 16 01:51:24 PDT 2016


Hi Guys,

I have decided to shed some light upon the plan I have for 
templates.

First let's focous on the problem(s) with them.

The main problem is instanciation, here is how it works:

When we encounter a TemplateInstance in an expression,
We search for the declaration on that template,
If there are multiple declarations we initiate a search trough 
them for the most fitting one, i.e. the most specialized one 
whose constraint evaluate to true and which can produce a valid 
body (yes D has SFINAE).
After we have found a match we look for a match in the know 
instanciations, for that first we hash the template-parameters 
and look for a match in a hashtable.

That process is much more expensive then one would think because 
in order to be sure the entry in the hashtable matches we have to 
do a deep comarision of the whole AST-Subsection the of the 
template parameters. Which if another template is a parameter of 
the this template includes it's whole parameter sub-tree as well.

This can touch many AST nodes.
So many in fact that the cache misses for the comparison become 
so big that the search for the saved instance if more expensive 
that dumb reinstanciation without looking for saved instance 
would be faster.

So with that in mind, how can we avoid the deep comparison of 
AST-Subtrees.
The answer is to make every template-argument unique.
Such that it can be uniquely identified with a numeric id.
Then the comparison would touch much less memory  (AST-Nodes are 
really huge when compared to a a 64bit id)
And we don't have to recursively decent into template-parameters 
which are templates.

That's it :)

Please ask me question if this was unclear or point out errors in 
my reasoning if you find them.

Cheers,
Stefan


More information about the Digitalmars-d mailing list