Compiler performance with my ridiculous Binderoo code

[Chris Wright via Digitalmars-d]

On Sun, 11 Dec 2016 18:08:04 +0000, safety0ff wrote:
> However, I understand the quadratic nature of comparing:
> AliasSeq!(AliasSeq!(AliasSeq!(...)))
> to:
> AliasSeq!(AliasSeq!(...))

That's one option. Here's another:

Template instantiations are interned as they are constructed (or at least 
should be). You must construct their arguments before you instantiate the 
template. Therefore you can do a reference equality check instead of 
checking the values of the parameters.

Specifically, we have:

AliasSeq!(AliasSeq!(1, 2), 3)

To construct this, the compiler first constructs AliasSeq!(1, 2). It's 
already been instantiated, so instead of creating it anew, it grabs a 
pointer to the existing instantiation -- we'll call it 0xC0FE.

Now it looks if AliasSeq!(0xC0FE, 3) has already been instantiated. It 
hasn't, so we instantiate it and add it to the cache.

I looked at the compiler's implementation, and it seems like it *maybe* 
could take better advantage of interning. The difference is a handful of 
casts, some jumps, and some virtual function calls. Which isn't *great* 
but won't yield more than a modicum of improved performance.

> I also don't see why you'd need to do this comparison often (assuming
> good hash functions are used.)

The current hash function simply sums symbol pointers and integer values 
in the template arguments. It ignores all other values. So if I have a 
simple template:

template Just(T, T value)
{
  enum T Just = value;
}

All instantiations with T=double will hash to the same value. When I 
tested this with 5,000 instantiations, it took twice as long with doubles 
as with longs (1.07s vs 0.50s). At 10,000, over three times as long 
(6.89s vs 2.05s). Short strings perform about the same as doubles.

TemplateInstance uses druntime's associative arrays, which are standard 
hashtables. The interaction has some wonky parts:

* It starts out with eight buckets.
* It grows by a factor of four.
* Hashes tend to be sums of pointers.
* Pointers are aligned.

This means you're in collision city most of the time.

I tried addressing that, but I'm seeing no improvement, so I obviously 
did something wrong. (And then I messed up an invocation of `find` and 
deleted my entire dmd source tree, including the .git directory...)

> All in all, it would probably be best to have some degenerate code so
> that the issue can be investigated on a common footing.

I agree entirely.