[Issue 22310] New: Template instantiation failures can be *very* costly

[d-bugmail at puremagic.com]

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

          Issue ID: 22310
           Summary: Template instantiation failures can be *very* costly
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: major
          Priority: P1
         Component: dmd
          Assignee: nobody at puremagic.com
          Reporter: kinke at gmx.net

Failed template instantiations appear not to be cached, and this can have a
huge effect on compile-time and memory requirements. Here's a standalone
version of std.traits.BooleanTypeOf as of v2.097.2 incl. a little benchmark,
with `-version=DontFail` yielding a `void` instead of `static assert(0)`, just
for illustration:

```
template ModifyTypePreservingTQ(alias Modifier, T)
{
         static if (is(T U ==          immutable U)) alias
ModifyTypePreservingTQ =          immutable Modifier!U;
    else static if (is(T U == shared inout const U)) alias
ModifyTypePreservingTQ = shared inout const Modifier!U;
    else static if (is(T U == shared inout       U)) alias
ModifyTypePreservingTQ = shared inout       Modifier!U;
    else static if (is(T U == shared       const U)) alias
ModifyTypePreservingTQ = shared       const Modifier!U;
    else static if (is(T U == shared             U)) alias
ModifyTypePreservingTQ = shared             Modifier!U;
    else static if (is(T U ==        inout const U)) alias
ModifyTypePreservingTQ =        inout const Modifier!U;
    else static if (is(T U ==        inout       U)) alias
ModifyTypePreservingTQ =              inout Modifier!U;
    else static if (is(T U ==              const U)) alias
ModifyTypePreservingTQ =              const Modifier!U;
    else                                             alias
ModifyTypePreservingTQ =                    Modifier!T;
}

template OriginalType(T)
{
    static if (is(T == enum))
    {
        template Impl(T)
        {
            static if (is(T U == enum)) alias Impl = OriginalType!U;
            else                        alias Impl =              T;
        }

        alias OriginalType = ModifyTypePreservingTQ!(Impl, T);
    }
    else
    {
        alias OriginalType = T;
    }
}

alias AliasThisTypeOf(T) = typeof(__traits(getMember, T.init,
__traits(getAliasThis, T)[0]));

template BooleanTypeOf(T)
{
    static if (is(AliasThisTypeOf!T AT) && !is(AT[] == AT))
        alias X = BooleanTypeOf!AT;
    else
        alias X = OriginalType!T;

    static if (is(immutable X == immutable bool))
        alias BooleanTypeOf = X;
    else
    {
        version (DontFail)
            alias BooleanTypeOf = void;
        else
            static assert(0, T.stringof~" is not boolean type");
    }
}

alias AliasSeq(T...) = T;
// 10 types
alias SampleTypes = AliasSeq!(bool, char, wchar, dchar, byte, ubyte, short,
ushort, int, uint);

void main()
{
    enum count = 5_000;
    static foreach (i; 0 .. count)
        foreach (T; SampleTypes)
            enum _ = is(BooleanTypeOf!T);
}
```

Compiling with `-c -vtemplates` using DMD v2.097.2 on Linux x64 takes about 1.0
seconds and ~942 MB of RAM:
```
aliasThisTypeOf.d(34): vtemplate: 50000 (45001 distinct) instantiation(s) of
template `BooleanTypeOf(T)` found
aliasThisTypeOf.d(32): vtemplate: 45001 (45001 distinct) instantiation(s) of
template `AliasThisTypeOf(T)` found
aliasThisTypeOf.d(14): vtemplate: 45001 (10 distinct) instantiation(s) of
template `OriginalType(T)` found
aliasThisTypeOf.d(52): vtemplate: 1 (0 distinct) instantiation(s) of template
`AliasSeq(T...)` found
```

Compiling with `-c -vtemplates -version=DontFail` takes ~0.46 seconds and ~308
MB:
```
aliasThisTypeOf.d(34): vtemplate: 50000 (10 distinct) instantiation(s) of
template `BooleanTypeOf(T)` found
aliasThisTypeOf.d(14): vtemplate: 10 (10 distinct) instantiation(s) of template
`OriginalType(T)` found
aliasThisTypeOf.d(32): vtemplate: 10 (10 distinct) instantiation(s) of template
`AliasThisTypeOf(T)` found
aliasThisTypeOf.d(52): vtemplate: 1 (0 distinct) instantiation(s) of template
`AliasSeq(T...)` found
```

Note that failing to instantiate BooleanTypeOf!T for non-bool T also seems to
lead to all successfully instantiated templates in there not to be cached
(AliasThisTypeOf!T, OriginalType!T).

--