• H. S. Teoh (26/27) Jul 24 2013 implementation of cartesianProduct using too many template expansions
• Peter Alexander (15/22) Jul 25 2013 Actually, it's probably caused by the exponential size of
• Peter Alexander (4/6) Jul 25 2013 Sorry, that's a lie. Eponymous templates aren't the problem, the

"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."

"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.

"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.