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

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

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?

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

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.

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

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.

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.

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

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.