Re: How templates might be improved
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 :)
Re: How templates might be improved
On Sat, 17 Sep 2016 12:02:47 +, 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.
Re: How templates might be improved
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 :)
Re: How templates might be improved
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.
Re: How templates might be improved
On Fri, 16 Sep 2016 08:51:24 +, 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).
Re: How templates might be improved
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."