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