www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 5845] New: [CTFE] "stack overflow" with ref ulong argument + CTFE benchmark

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

           Summary: [CTFE] "stack overflow" with ref ulong argument + CTFE
                    benchmark
           Product: D
           Version: D2
          Platform: x86
        OS/Version: Windows
            Status: NEW
          Keywords: rejects-valid
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc


--- Comment #0 from bearophile_hugs eml.cc 2011-04-14 18:14:14 PDT ---
This program generates a "stack overflow" with DMD2 2.052, but it compiles and
runs correctly with DMD1 v1.026.

The problem appears to be here:
uint solve(int niv, int dx, ref ulong diag45, ref ulong diag135, ref ulong
cols) {
Removing the ref avoids the problem:
uint solve(int niv, int dx, ulong diag45, ulong diag135, ulong cols) {

Additionally: this program (with enum result=nqueen(10);) can also be used as
one benchmark for CTFE speed (if run at runtime it allocates no heap memory).



import std.c.stdio: printf;

bool test(int k, int j, ulong diag45, ulong diag135, ulong cols) {
    return ((cols    & (1UL << j)) +
            (diag135 & (1UL << (j + k))) +
            (diag45  & (1UL << (32 + j - k))) ) == 0;
}

void mark(int k, int j, ref ulong diag45, ref ulong diag135, ref ulong cols) {
    cols    ^= (1UL << j);
    diag135 ^= (1UL << (j + k));
    diag45  ^= (1UL << (32 + j - k));
}

//uint solve(int niv, int dx, ulong diag45, ulong diag135, ulong cols) { // OK
uint solve(int niv, int dx, ref ulong diag45, ref ulong diag135, ref ulong
cols) { // stack overflow
    uint solutions_found;

    if (niv) {
        for (int i = 0; i < dx; i++)
            if (test(niv, i, diag45, diag135, cols)) {
                mark(niv, i, diag45, diag135, cols);
                solutions_found += solve(niv - 1, dx, diag45, diag135, cols);
                mark(niv, i, diag45, diag135, cols);
            }
    } else {
        for (int i = 0; i < dx; i++)
            solutions_found += test(0, i, diag45, diag135, cols);
    }

    return solutions_found;
}

ulong nqueen(int n) {
    ulong diag45  = 0; // / diagonal bitboard
    ulong diag135 = 0; // \ diagonal bitboard
    ulong cols    = 0; // column bitboard

    return solve(n - 1, n, diag45, diag135, cols);
}

const ulong result = nqueen(8);

void main() {
    // NQUEENS: 1, 0, 0, 2, 10, 4, 40, 92, 352, 724,
    //          2_680, 14_200, 73_712, 365_596
    printf("%lld\n", result);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Apr 14 2011
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5845


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |clugdbug yahoo.com.au
            Summary|[CTFE] "stack overflow"     |Regression(2.041) [CTFE]
                   |with ref ulong argument +   |"stack overflow" with
                   |CTFE benchmark              |recursive ref argument


--- Comment #1 from Don <clugdbug yahoo.com.au> 2011-05-17 14:04:11 PDT ---
This is not useful as a benchmark.
Reduced test case:

void test5845(ulong cols) {}

uint solve(bool niv, ref ulong cols) {
    if (niv)
        solve(false, cols);
    else
        test5845(cols);
    return 65;
}

ulong nqueen(int n) {
    ulong cols    = 0;
    return solve(true, cols);
}

static assert(nqueen(2) == 65);

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 17 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5845



--- Comment #2 from bearophile_hugs eml.cc 2011-05-17 16:03:23 PDT ---
(In reply to comment #1)

 This is not useful as a benchmark.


Do you want to tell me why?

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 17 2011
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5845



--- Comment #3 from Don <clugdbug yahoo.com.au> 2011-05-18 01:31:35 PDT ---
(In reply to comment #2)

 (In reply to comment #1)

 This is not useful as a benchmark.


 
 Do you want to tell me why?


Because a simpler benchmark that tests exactly the same things is:
int foo(int n) {
  for (int i=0; i< n; ++i) {}
  return 0;
}
static assert(foo(10000));
Your code is longer but it tests NOTHING else.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 18 2011
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=5845


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED


--- Comment #4 from Don <clugdbug yahoo.com.au> 2011-05-18 21:22:25 PDT ---
D1 fix:
https://github.com/D-Programming-Language/dmd/commit/669cafeb9fecc98d5f4689f379f638a9661f0b35

D2 (a couple of related commits are also involved in this fix):
https://github.com/D-Programming-Language/dmd/commit/0c8750880ad31e0715546daa68be4d69f4af88c0

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 18 2011