www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - DMD performance issues with deeply-recursive templates

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
I just noticed this bug today:

	http://d.puremagic.com/issues/show_bug.cgi?id=10693

From what I can tell from a cursory glance, it's caused by the
implementation of cartesianProduct using too many template expansions (esp. in the variadic version of cartesianProduct), causing DMD to run very slowly and eventually exhaust all available memory and crash. It's not too difficult to rewrite cartesianProduct to use less templates, of course, but the reason I wrote cartesianProduct the way I did in the first place was because I wanted to use it to prove that functional style programming and deep range composition in D is viable. So I didn't write anything from scratch, but just put existing ranges together to produce the desired result. However, now I'm starting to wonder if we need to be taking a look at how DMD handles template expansions to see if we can reduce the memory footprint as well as compile-time performance. Or perhaps whether we need some way of managing combinatorial explosion when it comes to expanding recursive templates. Maybe it's also time for us to start thinking about how we might optimize deeply-composed ranges -- perhaps with some compiler built-in help? Or are we stuck with needing to implement Phobos ranges from scratch in order to have acceptable compile performance (and template bloat minimization), because dogfooding is simply not viable with the current state of things? T -- "The number you have dialed is imaginary. Please rotate your phone 90 degrees and try again."
Jul 24 2013
parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Thursday, 25 July 2013 at 04:33:59 UTC, H. S. Teoh wrote:
 From what I can tell from a cursory glance, it's caused by the
 implementation of cartesianProduct using too many template 
 expansions
 (esp. in the variadic version of cartesianProduct), causing DMD 
 to run
 very slowly and eventually exhaust all available memory and 
 crash.
Actually, it's probably caused by the exponential size of template symbol names thanks to mangling of eponymous templates: int[] a, b, c, d; writeln(typeof(cartesianProduct(a, b)).mangleof.length); writeln(typeof(cartesianProduct(a, b, c)).mangleof.length); writeln(typeof(cartesianProduct(a, b, c, d)).mangleof.length); 534 4025 25003 I can't even get it to compile with 5 params, but it's increasing by a factor of 6 or 7 each time, so 5 will be hundred of KB, 6 will be MBs and 7 will be 10s of MB. This needs to be fixed. Simply compressing the names will not help, we need a better mangling scheme.
Jul 25 2013
parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Thursday, 25 July 2013 at 08:17:28 UTC, Peter Alexander wrote:
 Actually, it's probably caused by the exponential size of 
 template symbol names thanks to mangling of eponymous templates:
Sorry, that's a lie. Eponymous templates aren't the problem, the problem is that you are instantiating an exponential number of templates, which obviously can never scale.
Jul 25 2013