On 10 June 2013 21:41, Walter Bright <walter@digitalmars.com> wrote:

>
> On 6/9/2013 11:29 PM, Don Clugston wrote:
>
>>
>>
>> I'm not sure. That's the number of calls to the constructor of
>> TemplateInstance. I don't understand the code well enough to know
>> if it can eventually gets merged with an existing TemplateInstance.
>> If so, then perhaps there's something we could do to prevent them from
>> getting created in the first place if they are duplicates.
>>
>>
> The template instantiation code is short-circuited if the instantiation already exists. (It's a bad bug if this is broken.)
>
>
It's not a compiler bug. It's something more interesting.
I counted the number of instantiations in std.algorithm -unittest.
635 templates are instantiated, half of them only 1 to 10 times.
These ones here cover 70% of the total.

70763    isNarrowString
31279    binaryFun
24425    isInputRange
22308    Unqual
15563    startsWith
15381    isBidirectionalRange
11405    endsWith
7861    FormatSpec
7277    OriginalType
7275    to
6723    TypeTuple
5827    defaultInit
5713    from
5413    isRawStaticArray

Then, the question is, how do we get 71K different types to instantiate
isNarrowString with? There aren't nearly that many types declared in the
program!
Turns our it's things like:

Zip!(Sequence!("n", Tuple!(ulong)), Sequence!("n", Tuple!(int)), Result,
Repeat!(Sequence!("n", Tuple!(int))), Repeat!(Result))

So we've got a combinatorial explosion of types happening here. I'm sure that's true for the other massively-instantiated templates as well. If we could avoid this, we would get an order of magnitude improvement in memory usage and compilation time.

On 6/11/2013 12:35 AM, Don Clugston wrote:
>
>
> It's not a compiler bug. It's something more interesting.
> I counted the number of instantiations in std.algorithm -unittest.
> 635 templates are instantiated, half of them only 1 to 10 times.
> These ones here cover 70% of the total.
>
> 70763    isNarrowString
> 31279    binaryFun
> 24425    isInputRange
> 22308    Unqual
> 15563    startsWith
> 15381    isBidirectionalRange
> 11405    endsWith
> 7861    FormatSpec
> 7277    OriginalType
> 7275    to
> 6723    TypeTuple
> 5827    defaultInit
> 5713    from
> 5413    isRawStaticArray
>
> Then, the question is, how do we get 71K different types to instantiate isNarrowString with? There aren't nearly that many types declared in the program!
> Turns our it's things like:
>
> Zip!(Sequence!("n", Tuple!(ulong)), Sequence!("n", Tuple!(int)), Result, Repeat!(Sequence!("n", Tuple!(int))), Repeat!(Result))
>
> So we've got a combinatorial explosion of types happening here. I'm sure that's true for the other massively-instantiated templates as well. If we could avoid this, we would get an order of magnitude improvement in memory usage and compilation time.
>
>

This is great information. 71000 instantiations of isNarrowString!! Definitely need a hash rather than a linear list. I had no idea. You're right, though, about figuring out a way to avoid this. isNarrowString is nothing more than:

template isNarrowString(T)
{
    enum isNarrowString = (is(T : const char[]) || is(T : const wchar[])) && !isAggregateType!T;
}

Makes me wonder why isAggregateType is not 71000 instantiations, too?

Maybe we can avoid generating a mangled name for a template if it is an eponymous one that evaluates to a manifest constant? This will save a ton of memory.

_______________________________________________
dmd-internals mailing list
dmd-internals@puremagic.com
http://lists.puremagic.com/mailman/listinfo/dmd-internals

On 6/11/2013 1:06 AM, Walter Bright wrote:
>
>
> Maybe we can avoid generating a mangled name for a template if it is an eponymous one that evaluates to a manifest constant? This will save a ton of memory.
>
>

Maybe just generate the mangled name lazily.
_______________________________________________
dmd-internals mailing list
dmd-internals@puremagic.com
http://lists.puremagic.com/mailman/listinfo/dmd-internals

This is great information. 71000 instantiations of isNarrowString!! Definitely need a hash rather than a linear list. I had no idea. You're right, though, about figuring out a way to avoid this. isNarrowString is nothing more than:

>
> template isNarrowString(T)
> {
>     enum isNarrowString = (is(T : const char[]) || is(T : const wchar[]))
> && !isAggregateType!T;
> }
>
> Makes me wonder why isAggregateType is not 71000 instantiations, too?
>

It short-circuits through &&.


> Maybe we can avoid generating a mangled name for a template if it is an eponymous one that evaluates to a manifest constant? This will save a ton of memory.


Yeah.  Interestingly most of these instantiations are inside template constraints or static if, maybe we can do something with that. There's low-lying fruit here.

On 6/11/13 4:06 AM, Walter Bright wrote:
> This is great information. 71000 instantiations of isNarrowString!!
> Definitely need a hash rather than a linear list. I had no idea. You're
> right, though, about figuring out a way to avoid this. isNarrowString is
> nothing more than:
>
> template isNarrowString(T)
> {
> enum isNarrowString = (is(T : const char[]) || is(T : const wchar[])) &&
> !isAggregateType!T;
> }
>
> Makes me wonder why isAggregateType is not 71000 instantiations, too?

Could short-circuiting be the answer?

> Maybe we can avoid generating a mangled name for a template if it is an
> eponymous one that evaluates to a manifest constant? This will save a
> ton of memory.

Awesome. I think it would be fit to have compilation speed and memory consumed a focal point of 2.064. What do you all think?


Andrei

_______________________________________________
dmd-internals mailing list
dmd-internals@puremagic.com
http://lists.puremagic.com/mailman/listinfo/dmd-internals

On Tue, Jun 11, 2013 at 6:06 PM, Walter Bright <walter@digitalmars.com>wrote:

>
> Maybe we can avoid generating a mangled name for a template if it is an eponymous one that evaluates to a manifest constant? This will save a ton of memory.
>
>
For templates that do not generate any symbols, we could treat the instantiations like a cache and limit the total number stored.  The rest can then be GCed.

On 06/11/2013 10:06 AM, Walter Bright wrote:
>
> Maybe we can avoid generating a mangled name for a template if it is an eponymous one that evaluates to a manifest constant? This will save a ton of memory. 
What could you use as hash key other than the mangling?
_______________________________________________
dmd-internals mailing list
dmd-internals@puremagic.com
http://lists.puremagic.com/mailman/listinfo/dmd-internals

On 6/11/2013 2:08 PM, Martin Nowak wrote:
> On 06/11/2013 10:06 AM, Walter Bright wrote:
>>
>> Maybe we can avoid generating a mangled name for a template if it is an eponymous one that evaluates to a manifest constant? This will save a ton of memory. 
> What could you use as hash key other than the mangling?


Even just hashing the deco strings for the type arguments would be enough to way cut down on the lookup times.
_______________________________________________
dmd-internals mailing list
dmd-internals@puremagic.com
http://lists.puremagic.com/mailman/listinfo/dmd-internals