www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - "temporary" templates

reply Steven Schveighoffer <schveiguy gmail.com> writes:
Every time you instantiate a template, it consumes memory in the 
compiler for the duration of compilation.

For example, consider the silly template:

```
template SumAll(size_t x)
{
    static if(x == 0) enum SumAll = 0;
    enum SumAll = x + SumAll!(x - 1);
}
```

Instantiate this for SumAll!100_000, and you generate... oh wait. It 
doesn't work (too much recursive templates). But THIS even sillier 
template does:

```
template SumAll(size_t x)
{
    static if(x == 0) enum SumAll = 0;
    enum SumAll = SumAllHelper!(1, x);
}

template SumAllHelper(size_t min, size_t max)
{
     static if(min == max)
     {
         enum SumAllHelper = min;
     }
     else
     {
         enum mid = (min + max) / 2;
         enum SumAllHelper = SumAllHelper!(min, mid) + SumAllHelper!(mid 
+ 1, max);
     }
}
```

Compiling a program with SumAll!100000 consumes 1.4GB of RAM.

You'll notice that I'm pretty much NEVER going to instantiate 
SumAllHelper directly, and never access ANY of the items inside the 
template. Yet the compiler stores every single instantiation of 
SumAllHelper "just in case" we need it again later. The cost for this 
convenience is astronomical.

Even if I do SumAll!100001, it still adds another 300MB of templates, 
saving *some* memory, but not enough to justify the caching.

If you look in std.meta, it's full of these style linear recursion or 
divide-and-conquer recursion algorithms, often with a "Impl" pair to the 
main template. Each one of these generates potentially hundreds or 
thousands of template instances that are used ONCE.

But what if we could MARK SumAllHelper such that it's result should be 
used once? That is, such that it's only generated temporarily, and then 
thrown to the GC? This means that the memory consumption only happens 
for SumAll, and not SumAllHelper (well, not permanently anyway). This 
means that each call to SumAll is going to re-generate some templates of 
SumAllHelper. But who cares? I'd rather have the thing compile with the 
RAM I have then be uber-concerned with caching everything under the sun.

With the compiler now supporting garbage collection, this can be a 
possibility. Is it feasible? Is it difficult? Do we actually need to 
mark SumAllHelper with some  temporary attribute or can the compiler 
figure it out?

Note, all these thoughts are happening because I am actually working on 
reducing the memory footprint of a project that makes heavy use of 
std.meta.NoDuplicates, which uses similar techniques as I've outlined 
above and generates a LOT of templates. By switching to a different 
design that avoids the need for it, I've reduced the compile-time 
footprint from over 10GB to 3.5GB. But I wish it would "just work"

-Steve
Nov 26 2019
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Tuesday, 26 November 2019 at 17:03:04 UTC, Steven 
Schveighoffer wrote:

 Every time you instantiate a template, it consumes memory in 
 the compiler for the duration of compilation.

 [...]


Ahh.

I've  been working on this particular  problem a few years ago.
In _general_ it's not possible to categorize a template  as being 
temporary or  not.
For language semantic reasons it is a requirement  for every 
re-instantiated template to forward  to  exactly the same symbol 
as was generated during the first instantiation.

The solution that  I came up with is to enhance CTFE to be able 
to take types as regular function arguments, and relax the 
semantic constraints on those type-functions.

If there is sufficient interested I can build a proof-of-conecpt.

Cheers,

Stefan
Nov 26 2019
next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 26 November 2019 at 18:35:42 UTC, Stefan Koch wrote:

 In _general_ it's not possible to categorize a template  as 
 being temporary or  not.
 For language semantic reasons it is a requirement  for every 
 re-instantiated template to forward  to  exactly the same 
 symbol as was generated during the first instantiation.


What if it kept *just* the symbol, but discarded its innards when 
under memory pressure, then could regenerate them if evaluated 
again?
Nov 26 2019
parent reply Paul Backus <snarwin gmail.com> writes:
On Tuesday, 26 November 2019 at 18:45:35 UTC, Adam D. Ruppe wrote:

 On Tuesday, 26 November 2019 at 18:35:42 UTC, Stefan Koch wrote:

 In _general_ it's not possible to categorize a template  as 
 being temporary or  not.
 For language semantic reasons it is a requirement  for every 
 re-instantiated template to forward  to  exactly the same 
 symbol as was generated during the first instantiation.


 What if it kept *just* the symbol, but discarded its innards 
 when under memory pressure, then could regenerate them if 
 evaluated again?


This will cause compilation to become non-deterministic, since 
the result of template evaluation can depend on the order in 
which declarations are semantically analyzed:

enum hasFoo(T) = __traits(hasMember, T, "foo");

struct S {
     // hasFoo!S is instantiated before the mixin is processed
     static if (hasFoo!S) {}
     mixin("int foo;");
}

pragma(msg, hasFoo!S); // false

If for some reason the "innards" of `hasFoo!S` are discarded due 
to memory pressure, reconstructing them later will give a 
different result.
Nov 26 2019
next sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 11/26/19 1:59 PM, Paul Backus wrote:

 On Tuesday, 26 November 2019 at 18:45:35 UTC, Adam D. Ruppe wrote:

 On Tuesday, 26 November 2019 at 18:35:42 UTC, Stefan Koch wrote:

 In _general_ it's not possible to categorize a template  as being 
 temporary or  not.
 For language semantic reasons it is a requirement  for every 
 re-instantiated template to forward  to  exactly the same symbol as 
 was generated during the first instantiation.


 What if it kept *just* the symbol, but discarded its innards when 
 under memory pressure, then could regenerate them if evaluated again?


 
 This will cause compilation to become non-deterministic, since the 
 result of template evaluation can depend on the order in which 
 declarations are semantically analyzed:
 
 enum hasFoo(T) = __traits(hasMember, T, "foo");
 
 struct S {
      // hasFoo!S is instantiated before the mixin is processed
      static if (hasFoo!S) {}
      mixin("int foo;");
 }
 
 pragma(msg, hasFoo!S); // false
 
 If for some reason the "innards" of `hasFoo!S` are discarded due to 
 memory pressure, reconstructing them later will give a different result.


But that's an evaluation order issue. hasFoo should be true in both 
cases. Otherwise, you have the paradox:

static assert(hasFoo!S == __traits(hasMember, T, "foo"))

Or we should essentially stop using templates to make __traits easier to 
write?

I ran into this recently as well:

https://issues.dlang.org/show_bug.cgi?id=20414

I do not agree that this is a "language" requirement for any good reason 
other than "that's how the compiler currently works."

-Steve
Nov 26 2019
parent reply Paul Backus <snarwin gmail.com> writes:
On Tuesday, 26 November 2019 at 19:11:14 UTC, Steven 
Schveighoffer wrote:

 On 11/26/19 1:59 PM, Paul Backus wrote:

 
 This will cause compilation to become non-deterministic, since 
 the result of template evaluation can depend on the order in 
 which declarations are semantically analyzed:
 
 enum hasFoo(T) = __traits(hasMember, T, "foo");
 
 struct S {
      // hasFoo!S is instantiated before the mixin is processed
      static if (hasFoo!S) {}
      mixin("int foo;");
 }
 
 pragma(msg, hasFoo!S); // false
 
 If for some reason the "innards" of `hasFoo!S` are discarded 
 due to memory pressure, reconstructing them later will give a 
 different result.


 But that's an evaluation order issue. hasFoo should be true in 
 both cases. Otherwise, you have the paradox:

 static assert(hasFoo!S == __traits(hasMember, T, "foo"))


There are situations where a particular evaluation order is 
forced. For example:

enum hasFoo(T) == __traits(hasMember, T, "foo");

struct S {
     static if (!hasFoo!S) {
         int foo;
     }
}

static assert(hasFoo!S == __traits(hasMember, S, "foo")); // fails

The condition of the static if *must* be evaluated before the 
body, so there is no way to have hasFoo!S evaluate to the same 
thing in both places without causing a paradox. Note that this is 
*not* an accident of the current compiler implementation; it 
follows directly from the definition of `static if` in the 
language spec.
Nov 27 2019
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 11/27/19 3:03 AM, Paul Backus wrote:

 On Tuesday, 26 November 2019 at 19:11:14 UTC, Steven Schveighoffer wrote:

 On 11/26/19 1:59 PM, Paul Backus wrote:

 This will cause compilation to become non-deterministic, since the 
 result of template evaluation can depend on the order in which 
 declarations are semantically analyzed:

 enum hasFoo(T) = __traits(hasMember, T, "foo");

 struct S {
      // hasFoo!S is instantiated before the mixin is processed
      static if (hasFoo!S) {}
      mixin("int foo;");
 }

 pragma(msg, hasFoo!S); // false

 If for some reason the "innards" of `hasFoo!S` are discarded due to 
 memory pressure, reconstructing them later will give a different result.


 But that's an evaluation order issue. hasFoo should be true in both 
 cases. Otherwise, you have the paradox:

 static assert(hasFoo!S == __traits(hasMember, T, "foo"))


 
 There are situations where a particular evaluation order is forced. For 
 example:
 
 enum hasFoo(T) == __traits(hasMember, T, "foo");
 
 struct S {
      static if (!hasFoo!S) {
          int foo;
      }
 }
 
 static assert(hasFoo!S == __traits(hasMember, S, "foo")); // fails
 
 The condition of the static if *must* be evaluated before the body, so 
 there is no way to have hasFoo!S evaluate to the same thing in both 
 places without causing a paradox. Note that this is *not* an accident of 
 the current compiler implementation; it follows directly from the 
 definition of `static if` in the language spec.


OK, this is more of a correct argument since obviously hasFoo must be 
false to add foo, but then it should be true after that. So it's still 
not ideal, and still a paradox.

What I am proposing is that you can mark items as  temporary or 
something like that, and those templates will be reevaluated each time. 
And in the case of something like hasFoo, I'd argue it's just a thin 
wrapper over a __traits call, so it probably should be reevaluated each 
time.

This does not make it non-deterministic, just determined differently. In 
fact, I'd say it's *more* deterministic, as evaluating templates does 
not depend on weird interactions like this. And it should be opt-in to 
avoid breaking code.

But it's also possible that Stefan's solution would work as well, if we 
can manipulate types like variables in CTFE mode.

-Steve
Nov 27 2019
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 11/27/19 11:15 AM, Steven Schveighoffer wrote:

 What I am proposing is that you can mark items as  temporary or 
 something like that, and those templates will be reevaluated each time. 
 And in the case of something like hasFoo, I'd argue it's just a thin 
 wrapper over a __traits call, so it probably should be reevaluated each 
 time.


Think of it like "weak pure". In strong pure functions, the result is 
always the same, because the data passed in is always the same. But weak 
pure functions can be used inside those functions even though their 
parameters and results can be mutable. It allows for much more pleasant 
experience.

It allows one to have the public template as "this is final, once it's 
evaluated, store it and it's always the same." But the innards, which 
can be hairy, complex, horribly performing and used only once (or maybe 
a couple times), can be left to the GC, because once the head is 
finalized, they won't be instantiated with those parameters again.

The more I think about it, the more I like the CTFE with Types as first 
class approach, because then I can use actual mutating code vs. 
immutable functional approach that is required with templates.

-Steve
Nov 27 2019
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Nov 27, 2019 at 11:32:13AM -0500, Steven Schveighoffer via
Digitalmars-d wrote:
[...]

 The more I think about it, the more I like the CTFE with Types as
 first class approach, because then I can use actual mutating code vs.
 immutable functional approach that is required with templates.


[...]

I've been following this thread, and am coming to the same conclusion
too.

While templates are expressive enough to encode complex computations,
they aren't exactly the most conducive to such, and in terms of code gen
they aren't really the best tool for the job. Strictly speaking
templates really should be about manipulating the AST; using them to
perform computations is possible but a poor choice of tool IMO.

CTFE with first class types is much better because then it becomes
obvious that this is for *computation*, and the compiler knows that it's
intended to be computation rather than AST manipulation, so it can
optimize accordingly (discard intermediate results, etc.). No need for
additional annotations on templates or other such additional
complexities.

And since we can already use CTFE results in template arguments, this is
not a loss to expressiveness. We just re-encode what we currently use
templates for into CTFE form, let the CTFE engine perform whatever
arbitrary computations we want on it, then return the result as a
template argument list that can be used to transform the AST as
previously intended.

We then have the nice paradigm:

	Computations -> CTFE
	AST transformations -> templates

and we can get rid of ugly recursive templates like staticMap, and
replace it with a much nicer CTFE implementation, or even outright just
drop staticMap and replace it with std.algorithm.map taking an alias
list as argument, thus staying DRY.


T

-- 
Recently, our IT department hired a bug-fix engineer. He used to work for
Volkswagen.
Nov 27 2019
parent reply Suleyman <sahmi.soulaimane gmail.com> writes:
On Wednesday, 27 November 2019 at 18:11:37 UTC, H. S. Teoh wrote:

 On Wed, Nov 27, 2019 at 11:32:13AM -0500, Steven Schveighoffer 
 via Digitalmars-d wrote: [...]

 [...]


 [...]

 I've been following this thread, and am coming to the same 
 conclusion too.

 While templates are expressive enough to encode complex 
 computations, they aren't exactly the most conducive to such, 
 and in terms of code gen they aren't really the best tool for 
 the job. Strictly speaking templates really should be about 
 manipulating the AST; using them to perform computations is 
 possible but a poor choice of tool IMO.

 CTFE with first class types is much better because then it 
 becomes obvious that this is for *computation*, and the 
 compiler knows that it's intended to be computation rather than 
 AST manipulation, so it can optimize accordingly (discard 
 intermediate results, etc.). No need for additional annotations 
 on templates or other such additional complexities.

 And since we can already use CTFE results in template 
 arguments, this is not a loss to expressiveness. We just 
 re-encode what we currently use templates for into CTFE form, 
 let the CTFE engine perform whatever arbitrary computations we 
 want on it, then return the result as a template argument list 
 that can be used to transform the AST as previously intended.

 We then have the nice paradigm:

 	Computations -> CTFE
 	AST transformations -> templates

 and we can get rid of ugly recursive templates like staticMap, 
 and replace it with a much nicer CTFE implementation, or even 
 outright just drop staticMap and replace it with 
 std.algorithm.map taking an alias list as argument, thus 
 staying DRY.


 T


Perhaps this is the opportunity to make a good runtime reflection 
system. We have typeid() for types, for an alias sequence which 
contains only types an no declarations we can implement 
NoDuplicates as a function that takes a TypeInfo[] and return the 
array with no duplicates in it, but we need a way to get a 
compile-time type from a TypeInfo, sort of a reversed typeid().
Dec 01 2019
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 12/1/19 4:04 PM, Suleyman wrote:

 Perhaps this is the opportunity to make a good runtime reflection 
 system. We have typeid() for types, for an alias sequence which contains 
 only types an no declarations we can implement NoDuplicates as a 
 function that takes a TypeInfo[] and return the array with no duplicates 
 in it, but we need a way to get a compile-time type from a TypeInfo, 
 sort of a reversed typeid()


I actually figured out a Type-only mechanism to CTFE a NoDuplicates 
list. Translate each type into a string name, then no-dup the string 
array, creating a string of AliasSeq references, then mixin the result.

But having CTFE actually give me the types to translate back into an 
AliasSeq list would be so much better.

-Steve
Dec 01 2019
next sibling parent Suleyman <sahmi.soulaimane gmail.com> writes:
On Monday, 2 December 2019 at 01:10:26 UTC, Steven Schveighoffer 
wrote:

 On 12/1/19 4:04 PM, Suleyman wrote:

 Perhaps this is the opportunity to make a good runtime 
 reflection system. We have typeid() for types, for an alias 
 sequence which contains only types an no declarations we can 
 implement NoDuplicates as a function that takes a TypeInfo[] 
 and return the array with no duplicates in it, but we need a 
 way to get a compile-time type from a TypeInfo, sort of a 
 reversed typeid()


 I actually figured out a Type-only mechanism to CTFE a 
 NoDuplicates list. Translate each type into a string name, then 
 no-dup the string array, creating a string of AliasSeq 
 references, then mixin the result.

 But having CTFE actually give me the types to translate back 
 into an AliasSeq list would be so much better.

 -Steve


It can work with some declarations I don't to what extend though 
since __traits(isSame) does a range of comparisons depending on 
the arguments. But string manipulation with CTFE is not cheap 
either. Here is a challenge for you, try to make a string with 
CTFE that has 1 million times the word int separated by a comma 
like "int, int, int, ..." in under 4GB of memory use if you can 
go below 4GB then lower the bar from there to 1.5GB.
Dec 01 2019
prev sibling parent Petar Kirov [ZombineDev] <petar.p.kirov gmail.com> writes:
On Monday, 2 December 2019 at 01:10:26 UTC, Steven Schveighoffer 
wrote:

 On 12/1/19 4:04 PM, Suleyman wrote:

 Perhaps this is the opportunity to make a good runtime 
 reflection system. We have typeid() for types, for an alias 
 sequence which contains only types an no declarations we can 
 implement NoDuplicates as a function that takes a TypeInfo[] 
 and return the array with no duplicates in it, but we need a 
 way to get a compile-time type from a TypeInfo, sort of a 
 reversed typeid()


 I actually figured out a Type-only mechanism to CTFE a 
 NoDuplicates list. Translate each type into a string name, then 
 no-dup the string array, creating a string of AliasSeq 
 references, then mixin the result.

 But having CTFE actually give me the types to translate back 
 into an AliasSeq list would be so much better.

 -Steve


I had a similar idea for optimizing NoDuplicates, as used by 
std.typecons.Tuple:

https://github.com/dlang/phobos/pull/5725#issuecomment-327767020

;)
Dec 01 2019
prev sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Wednesday, 27 November 2019 at 16:32:13 UTC, Steven 
Schveighoffer wrote:

 On 11/27/19 11:15 AM, Steven Schveighoffer wrote:

 The more I think about it, the more I like the CTFE with Types 
 as first class approach, because then I can use actual mutating 
 code vs. immutable functional approach that is required with 
 templates.

 -Steve


Yes that is the point.
first class types during ctfe allows you to use weak purity 
instead of strong purity!
And therefore makes AST manipulation or introspection much more 
efficient!

I'll build a tiny POC shortly. The thing that I got stuck with 
last time was the lexer/parser modification that is required to 
flag type arguments to ctfe functions.
Nov 27 2019
parent reply Suleyman <sahmi.soulaimane gmail.com> writes:
On Wednesday, 27 November 2019 at 20:02:52 UTC, Stefan Koch wrote:

 On Wednesday, 27 November 2019 at 16:32:13 UTC, Steven 
 Schveighoffer wrote:

 On 11/27/19 11:15 AM, Steven Schveighoffer wrote:

 The more I think about it, the more I like the CTFE with Types 
 as first class approach, because then I can use actual 
 mutating code vs. immutable functional approach that is 
 required with templates.

 -Steve


 Yes that is the point.
 first class types during ctfe allows you to use weak purity 
 instead of strong purity!
 And therefore makes AST manipulation or introspection much more 
 efficient!

 I'll build a tiny POC shortly. The thing that I got stuck with 
 last time was the lexer/parser modification that is required to 
 flag type arguments to ctfe functions.


The problem with going the path of giving super powers to CTFE 
functions is that it creates a division between runtime and CTFE 
then we will get functions which only work in CTFE which may or 
may not be a good thing.
Dec 01 2019
parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 12/1/19 4:14 PM, Suleyman wrote:

 On Wednesday, 27 November 2019 at 20:02:52 UTC, Stefan Koch wrote:

 On Wednesday, 27 November 2019 at 16:32:13 UTC, Steven Schveighoffer 
 wrote:

 On 11/27/19 11:15 AM, Steven Schveighoffer wrote:

 The more I think about it, the more I like the CTFE with Types as 
 first class approach, because then I can use actual mutating code vs. 
 immutable functional approach that is required with templates.

 -Steve


 Yes that is the point.
 first class types during ctfe allows you to use weak purity instead of 
 strong purity!
 And therefore makes AST manipulation or introspection much more 
 efficient!

 I'll build a tiny POC shortly. The thing that I got stuck with last 
 time was the lexer/parser modification that is required to flag type 
 arguments to ctfe functions.


 
 The problem with going the path of giving super powers to CTFE functions 
 is that it creates a division between runtime and CTFE then we will get 
 functions which only work in CTFE which may or may not be a good thing.


We already have CTFE-only functions (assert(__ctfe)) Sometimes CTFE is 
far preferable to using template expansion.

-Steve
Dec 01 2019
parent reply Suleyman <sahmi.soulaimane gmail.com> writes:
On Monday, 2 December 2019 at 01:11:57 UTC, Steven Schveighoffer 
wrote:

 On 12/1/19 4:14 PM, Suleyman wrote:

 On Wednesday, 27 November 2019 at 20:02:52 UTC, Stefan Koch 
 wrote:

 On Wednesday, 27 November 2019 at 16:32:13 UTC, Steven 
 Schveighoffer wrote:

 On 11/27/19 11:15 AM, Steven Schveighoffer wrote:

 The more I think about it, the more I like the CTFE with 
 Types as first class approach, because then I can use actual 
 mutating code vs. immutable functional approach that is 
 required with templates.

 -Steve


 Yes that is the point.
 first class types during ctfe allows you to use weak purity 
 instead of strong purity!
 And therefore makes AST manipulation or introspection much 
 more efficient!

 I'll build a tiny POC shortly. The thing that I got stuck 
 with last time was the lexer/parser modification that is 
 required to flag type arguments to ctfe functions.


 
 The problem with going the path of giving super powers to CTFE 
 functions is that it creates a division between runtime and 
 CTFE then we will get functions which only work in CTFE which 
 may or may not be a good thing.


 We already have CTFE-only functions (assert(__ctfe)) Sometimes 
 CTFE is far preferable to using template expansion.

 -Steve


Not to this extent though. What we're potentially discussing here 
is functions which have a reusable body like a runnable template. 
For example a CTFE function `bool isSame(alias A, alias B) { 
return __traits(isSame, A, B); }` this is unlike any regular 
function that we have today.
Dec 01 2019
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Monday, 2 December 2019 at 02:02:04 UTC, Suleyman wrote:

 Not to this extent though. What we're potentially discussing 
 here is functions which have a reusable body like a runnable 
 template. For example a CTFE function `bool isSame(alias A, 
 alias B) { return __traits(isSame, A, B); }` this is unlike any 
 regular function that we have today.


Interesting this is exactly the syntax I wanted to use ;)

Any ctfe function that has an alias parameter is a ctfe only 
function.
Using this you can give a function a default alias parameter if 
you want it to be compile time only.

it's a simple rule, and not confusing at all.
Dec 01 2019
parent Suleyman <sahmi.soulaimane gmail.com> writes:
On Monday, 2 December 2019 at 02:26:33 UTC, Stefan Koch wrote:

 On Monday, 2 December 2019 at 02:02:04 UTC, Suleyman wrote:

 Not to this extent though. What we're potentially discussing 
 here is functions which have a reusable body like a runnable 
 template. For example a CTFE function `bool isSame(alias A, 
 alias B) { return __traits(isSame, A, B); }` this is unlike 
 any regular function that we have today.


 Interesting this is exactly the syntax I wanted to use ;)

 Any ctfe function that has an alias parameter is a ctfe only 
 function.
 Using this you can give a function a default alias parameter if 
 you want it to be compile time only.

 it's a simple rule, and not confusing at all.


It looks like the discardable template but branded as  a 
function. I guess the plan on each call is to run semantic 
analysis to get the result then reset the function to an initial 
state.
Dec 01 2019
prev sibling parent reply FeepingCreature <feepingcreature gmail.com> writes:
On Tuesday, 26 November 2019 at 18:59:26 UTC, Paul Backus wrote:

 On Tuesday, 26 November 2019 at 18:45:35 UTC, Adam D. Ruppe 
 wrote:

 On Tuesday, 26 November 2019 at 18:35:42 UTC, Stefan Koch 
 wrote:

 In _general_ it's not possible to categorize a template  as 
 being temporary or  not.
 For language semantic reasons it is a requirement  for every 
 re-instantiated template to forward  to  exactly the same 
 symbol as was generated during the first instantiation.


 What if it kept *just* the symbol, but discarded its innards 
 when under memory pressure, then could regenerate them if 
 evaluated again?


 This will cause compilation to become non-deterministic, since 
 the result of template evaluation can depend on the order in 
 which declarations are semantically analyzed:


...

Snapshot the lexical environment at the point of instantiation? 
Could make namespaces linked list of arrays so you can 
copy-on-write them for relatively cheap. Compilation is pure 
enough that this should be sufficient.

Imo templates are mostly split into two halves: large templates 
that are usually evaluated once with the same parameters, and 
small templates that are evaluated repeatedly with the same 
parameters. So a logic of "discard template contents beyond a 
certain cutoff size" should already do it.

And of course, mixin templates don't need to save anything 
because they're always reevaluated anyways.
Nov 27 2019
parent Paul Backus <snarwin gmail.com> writes:
On Wednesday, 27 November 2019 at 08:45:55 UTC, FeepingCreature 
wrote:

 On Tuesday, 26 November 2019 at 18:59:26 UTC, Paul Backus wrote:

 This will cause compilation to become non-deterministic, since 
 the result of template evaluation can depend on the order in 
 which declarations are semantically analyzed:


 ...

 Snapshot the lexical environment at the point of instantiation? 
 Could make namespaces linked list of arrays so you can 
 copy-on-write them for relatively cheap. Compilation is pure 
 enough that this should be sufficient.


The lexical environment is not enough. Due to the power of D's 
reflection, the result of template instantiation depends, in the 
worst case, on the state of the entire AST at time of 
instantiation.

Using an immutable AST with copy-on-write semantics would 
probably work.
Nov 27 2019
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 11/26/19 1:35 PM, Stefan Koch wrote:

 On Tuesday, 26 November 2019 at 17:03:04 UTC, Steven Schveighoffer wrote:

 Every time you instantiate a template, it consumes memory in the 
 compiler for the duration of compilation.

 [...]


 
 Ahh.
 
 I've  been working on this particular  problem a few years ago.
 In _general_ it's not possible to categorize a template  as being 
 temporary or  not.
 For language semantic reasons it is a requirement  for every 
 re-instantiated template to forward  to  exactly the same symbol as was 
 generated during the first instantiation.


If the template ends up being an alias or an enum, then I don't know why 
we need the templates used to get there to stay in memory. In my 
example, the "SumAllHelper" template is an implementation detail. Nobody 
ever actually uses it, just SumAll does. I can understand why SumAll 
instantiations must refer to the exact same thing, but once SumAll is 
done evaluating, why do we need the SumAllHelpers it used?

Can you give me an example where this breaks down if we throw it away?


 
 The solution that  I came up with is to enhance CTFE to be able to take 
 types as regular function arguments, and relax the semantic constraints 
 on those type-functions.


If CTFE can take over the job of things like NoDuplicates, it might be 
an alternative solution. In fact, exactly what I want is for CTFE-like 
behavior -- once the function is over, everything used to make the 
return value can be garbage.

In fact, using CTFE, I get:

size_t SumAllHelper(size_t val)
{
     size_t result = 0;
     while(val > 0)
        result += val--;
     return result;
}

enum SumAll(size_t x) = SumAllHelper(x);

Memory usage: 51MB. Way way better (and runs faster BTW, not 
unexpectedly). But of course CTFE cannot manipulate types like this, 
which is what I gather is your solution. NoDuplicates would be trivial 
(just call sort and filter adjacent duplicates!) if we could use CTFE.

The benefit of instrumenting existing templates, however, may be that we 
don't have to change much code. This in itself is not so much a huge 
deal, because something like NoDuplicates could potentially be just 
reimplemented and the usage doesn't change.


 If there is sufficient interested I can build a proof-of-conecpt.


I'm always interested in something that reduces compiler memory 
footprint! I'm pushing the upper limits of my RAM, and having to 
redesign my projects to fit the compiler's needs is painful.

-Steve
Nov 26 2019