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

Reply via email to