www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 10693] New: cartesianProduct with over 7 ranges causes segfault at compile time

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10693

           Summary: cartesianProduct with over 7 ranges causes segfault at
                    compile time
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: ttanjo gmail.com


--- Comment #0 from Tomoya Tanjo <ttanjo gmail.com> 2013-07-21 21:50:45 PDT ---
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

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 21 2013
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10693



--- Comment #1 from Tomoya Tanjo <ttanjo gmail.com> 2013-07-21 21:54:18 PDT ---
Oh sorry, it causes on Mac OS X 64bit, not Linux 64bit.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 21 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10693



--- Comment #2 from Tomoya Tanjo <ttanjo gmail.com> 2013-07-21 22:10:33 PDT ---
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
--

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 21 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10693



--- Comment #3 from hsteoh quickfur.ath.cx 2013-07-24 21:21:02 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 24 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10693


Peter Alexander <peter.alexander.au gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au gmail.co
                   |                            |m


--- Comment #4 from Peter Alexander <peter.alexander.au gmail.com> 2013-07-25
01:25:10 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jul 25 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10693



--- Comment #5 from hsteoh quickfur.ath.cx 2013-08-10 13:31:47 PDT ---
Looks like cartesianProduct of >2 arguments needs to be reimplemented, as it's
using an exponential number of templates, which is completely non-scalable.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 10 2013
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=10693



--- Comment #6 from hsteoh quickfur.ath.cx 2013-08-10 13:32:20 PDT ---
See also issue #10779

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Aug 10 2013