Bug 10693 – cartesianProduct with over 7 ranges causes segfault at compile time
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P2
Component
phobos
Product
D
Version
D2
Platform
All
OS
All
Creation time
2013-07-21T21:50:00Z
Last change time
2014-07-14T22:27:17Z
Keywords
pull
Assigned to
nobody
Creator
ttanjo
Comments
Comment #0 by ttanjo — 2013-07-21T21:50:45Z
The following code causes segfault at compile time on dmd v2.064-devel-477e42a on Linux 64bit.
--
// foo.d
import std.algorithm;
void main(string[] args)
{
int[] a, b, c, d, e, f, g;
foreach(_; cartesianProduct(a, b, c, d, e, f, g))
{
}
}
--
Output:
$ dmd foo.d
segmentation fault: 11
Comment #1 by ttanjo — 2013-07-21T21:54:18Z
Oh sorry, it causes on Mac OS X 64bit, not Linux 64bit.
Comment #2 by ttanjo — 2013-07-21T22:10:33Z
When I use cartesianProduct with 6 ranges, it compiles without errors but its compiling takes too long time (about 5 minutes in my system).
--
$ time dmd foo.d
dmd foo.d 302.94s user 2.27s system 99% cpu 5:05.71 total
--
Comment #3 by hsteoh — 2013-07-24T21:21:02Z
This is likely because there are a lot of recursive templates involved in the implementation of cartesianProduct, and DMD is running out of memory. Probably the implementation has to be redesigned to use less templates.
Comment #4 by peter.alexander.au — 2013-07-25T01:25:10Z
This is caused by symbol sizes:
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
It's growing exponentially per parameter.
Comment #5 by hsteoh — 2013-08-10T13:31:47Z
Looks like cartesianProduct of >2 arguments needs to be reimplemented, as it's using an exponential number of templates, which is completely non-scalable.
Latest git HEAD no longer segfaults at compile-time (new cartesianProduct implementation no longer uses exponential number of templates); but now a new problem is exposed: an empty cartesianProduct triggers a range error at runtime. Looks like a missing .empty check somewhere...
Comment #9 by github-bugzilla — 2014-07-14T21:06:52Z