Compiler performance with my ridiculous Binderoo code

Stefan Koch via Digitalmars-d digitalmars-d at puremagic.com
Sun Dec 11 11:00:23 PST 2016


On Sunday, 11 December 2016 at 18:08:04 UTC, safety0ff wrote:
> On Sunday, 11 December 2016 at 17:20:24 UTC, Stefan Koch wrote:
>>
>> That means you have to compute the mangled name which is crazy 
>> expensive.
>> And you can't cache the parent part of mangle because it all 
>> freshly generated by the template.
>
> How often would the mangle be needed regardless later on in 
> compilation?
> I don't know too much about dmd internals.
> It seemed that Martin Nowak had a viable proof of concept, but 
> the bugzilla discussion is quite terse.
>
>>
>> It seems like I fail to express the problem properly so let me 
>> try again.
>>
>> AliasSeq's that are append to look like this
>> : AliasSeq!(AliasSeq!(AliasSeq!(...)))
>> An aliasSeq that is "appended to" n times will produce (n^2) 
>> with ((n-1)^2) sub instances in them all the way till n is 0.
>>
>> When you want to compare their parameter times you need to go 
>> through all of them and recursively call findTemplateInstance.
>
> I don't see the n^2 instances, I'm likely missing an 
> implementation detail.
> However, I understand the quadratic nature of comparing:
> AliasSeq!(AliasSeq!(AliasSeq!(...)))
> to:
> AliasSeq!(AliasSeq!(...))
>
> I also don't see why you'd need to do this comparison often 
> (assuming good hash functions are used.)
> The comment "Hash collisions will happen!" seems to 
> overestimate the current implementation IMO.
>
>
> All in all, it would probably be best to have some degenerate 
> code so that the issue can be investigated on a common footing.

Just use this little program to simulate the process.
It assumes you always hit the l1 cache and that there are no hash 
collisions.

int templateTime(uint n, uint k = 300)
{
   uint result = k;
   foreach(_;0 .. n-1)
     result += templateTime(n/2, k);
   return result;
}

void main(string[] args)
{
import std.stdio;
import std.conv : to;
uint n = to!uint(args[1]);
writeln("AliasSeq with ", n, "Elements will take around ", 
templateTime(n), " us to intanciate" );
}


More information about the Digitalmars-d mailing list