Divide & Conquer divides, but doesn't conquer

[Adam D. Ruppe]

I ran a test to compare the two implementations. First was 
comparing 10,000 references to the same instance.

0.47user 0.11system 0:00.58elapsed 100%CPU (0avgtext+0avgdata 
399688maxresident)k

No significant difference between implementations. This is 
expected since it caches based on arguments.

Second test compared Phobos' impl vs the simple impl but this 
time with 10,000 different random instantiations: 
http://arsdnet.net/dcode/ala.d

I'd comment one impl out, uncomment the other, rerun 
/usr/bin/test dmd ala.d as well as dmd -c ala.d.

                simple impl     phobos impl
compile time:         3.1s            3.7s
dmd peak RAM:         1.5G            1.9G
  binary size:         6.2M            6.2M

The generated files (bin and object) are the same between them, 
but the simple implementation beats the Phobos impl in both 
compile time and dmd memory.

Note that all the user-visible static maps had 9 arguments, but 
the two separate implementations do different things.

It is possible my test is flawed, I encourage you to create your 
own and see what happens.


I also tried a string mixin version inside the static map 
template and it took 4.0s and used 1.2G of memory. Win on RAM, 
but lost on speed. (It was not the CTFE that hit it - that got 
cached - it was the mixin being run on each unique argument list).

And a hand-written static map because the number of arguments is 
known ahead of time: 1.4s compile, 0.7G memory. Absolutely 
crushed it. It might be worth seeing what lengths of static map 
are most common in the wild and just having hand expansions. 
Adding static if has a cost though (upped my test to 1.5s/720MB). 
But not as high as template constraints (1.5s/740MB). But this is 
all getting increasingly artificial.

So I am willing to say number of template instantiations is the 
probable key metric.


All this was done on a stock DMD64 D Compiler v2.091.1 on linux. 
Several enhancements were merged to dmd master recently that may 
change the results btw.

quick test: simple impl: 2s, 1.57G. phobos impl: 2.3s, 1.97G

hand impl: 1.1s, 725M. w/ static if: 1.2s, 775M

Decent time improvement across the board... but the binary got 
bigger at 6.4M :( (prolly druntime's fault more than anything 
else but idk, im not focusing on that rn)