www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - How templates might be improved

reply Stefan Koch <uplink.coder googlemail.com> writes:
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
Sep 16 2016
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 16 September 2016 at 08:51:24 UTC, Stefan Koch wrote:

 so big that the search for the saved instance if more expensive 
 that dumb reinstanciation without looking for saved instance 
 would be faster.


Supposed to say
"So big that search for the saved instance _can be_ as expensive 
as dumb re-instanciation would be."
Sep 16 2016
prev sibling next sibling parent reply Chris Wright <dhasenan gmail.com> writes:
On Fri, 16 Sep 2016 08:51:24 +0000, Stefan Koch wrote:

 The answer is to make every template-argument unique.
 Such that it can be uniquely identified with a numeric id.


So the compiler might intern or memoize some things, and if two templates 
take the same interned values as parameters, the cached template 
instantiation will be used. (This will happen with builtin types and 
possibly some literals.)

For instance, this will be a cache hit:

  alias TypeA = Typedef!int;
  alias TypeB = Typedef!int;

On the other hand, in a change of behavior, this will be a cache miss and 
the template is instantiated twice:

  alias myint = int;
  alias TypeA = Typedef!int;
  alias TypeB = Typedef!myint;

And this may or may not be a cache hit:

  alias TypeA = Typedef!(int, 0, "A");
  alias TypeB = Typedef!(int, 0, "A");

If someone tries implementing the recursive form of the Fibonacci 
function with your change in place, they'll have unusably long compile 
times. However, in the typical case, compile times will be faster (and 
specific types can more easily receive special treatment as needed).
Sep 16 2016
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 16 September 2016 at 23:44:42 UTC, Chris Wright wrote:


 On the other hand, in a change of behavior, this will be a 
 cache miss and the template is instantiated twice:

   alias myint = int;
   alias TypeA = Typedef!int;
   alias TypeB = Typedef!myint;


No It would not be a miss the type is the same

 And this may or may not be a cache hit:

   alias TypeA = Typedef!(int, 0, "A");
   alias TypeB = Typedef!(int, 0, "A");


This would be a hit.


 If someone tries implementing the recursive form of the 
 Fibonacci function with your change in place, they'll have 
 unusably long compile times. However, in the typical case, 
 compile times will be faster (and specific types can more 
 easily receive special treatment as needed).


If someone tries to implement fibobacci as a recursive template 
...
well there is no way that can be fast.
With interning or without.
Sep 17 2016
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Saturday, 17 September 2016 at 12:02:47 UTC, Stefan Koch wrote:

 On Friday, 16 September 2016 at 23:44:42 UTC, Chris Wright 
 wrote:


 On the other hand, in a change of behavior, this will be a 
 cache miss and the template is instantiated twice:

   alias myint = int;
   alias TypeA = Typedef!int;
   alias TypeB = Typedef!myint;


 No It would not be a miss the type is the same


Correction, typedef uses __traits(identifier, ) ?
I did not take that use into account that would miscompile :)
Sep 17 2016
prev sibling parent Chris Wright <dhasenan gmail.com> writes:
On Sat, 17 Sep 2016 12:02:47 +0000, Stefan Koch wrote:


 On Friday, 16 September 2016 at 23:44:42 UTC, Chris Wright wrote:
 
 

 On the other hand, in a change of behavior, this will be a cache miss
 and the template is instantiated twice:

   alias myint = int;
   alias TypeA = Typedef!int;
   alias TypeB = Typedef!myint;


 No It would not be a miss the type is the same


Can you give examples that would produce a cache miss?


 If someone tries implementing the recursive form of the Fibonacci
 function with your change in place, they'll have unusably long compile
 times. However, in the typical case,
 compile times will be faster (and specific types can more easily
 receive special treatment as needed).


 
 If someone tries to implement fibobacci as a recursive template ...
 well there is no way that can be fast.
 With interning or without.


If the compiler caches template instantiations, you get the memoized form 
and it can be computed in linear time. If it doesn't, exponential time.
Sep 17 2016
prev sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 16 September 2016 at 08:51:24 UTC, Stefan Koch wrote:

 [...]


I just found  
http://llvm.org/docs/doxygen/html/FoldingSet_8h_source.html,
So it looks like the llvm guys are already using the 
intern-everything approach,
It makes sense since in ssa based forms this is pretty easy to 
do, and a logical step.

This further strengthens by believe that this is worthwhile.

..

Aww it's everytime I think I came up with something really 
clever, I discover later that someone else has already done it 
... Well I guess that just means I am not too far of the mark :)
Sep 17 2016