How templates work (1)

[Stefan Koch]

On Friday, 29 May 2020 at 19:46:04 UTC, tsbockman wrote:
> On Friday, 29 May 2020 at 11:13:17 UTC, Stefan Koch wrote:
>> However:
>> We have not covered how names are resolved in scopes;
>> Nor the intricacies of how to pick the right overload for a 
>> template.
>> And which implicit conversion happen for that;
>> Neither have we talked about deferred resolution of templates 
>> or
>> which steps semantic analysis has to take.
>
> Don't forget to discuss template memoization. As I'm sure 
> you're well aware, it has massive performance consequences, 
> both good and bad, as well as being semantically essential to 
> some uses of templates.
>
> Greenspun's tenth rule of programming states: "Any sufficiently 
> complicated C or Fortran program contains an ad hoc, 
> informally-specified, bug-ridden, slow implementation of half 
> of Common Lisp." D very nearly fulfills this law (a 
> tongue-in-cheek version of the "inner-platform effect") through 
> its template system, except that it's probably not fair to call 
> it "informally-specified".
>
> I argue that the root causes of the terrible compile-time 
> performance, and especially memory consumption, of D's template 
> system are forced memoization of intermediate results, and the 
> lack of the tail recursion optimization. Who ever heard of a 
> pure functional language without tail recursion optimization, 
> or *any* programming language with inescapable memoization?
>
> There is no good reason to assign a long, permanent symbol to 
> each and every partially sorted scrap of an AliasSeq that is 
> generated in the midst of a compile-time sort, instead of just 
> garbage collecting them. But my understanding is currently 
> those intermediate results just stick around forever, massively 
> raising the asymptotic memory complexity of otherwise benign 
> algorithms.

Without memorization some things would be completely impractical 
to do.
Then again ignoring the implementation in dmd right now;
There is no fundamental reason why anything has to be cached in a 
purely functional system.
since computing it again should yield the same values.

As it stands the cache does only do good.
It is not the slow part.
Creating tons of ast nodes is however.

For practical reasons dmd does not free intermediate results, 
that would be the case
even if the template instances were not cached.