Having solved Project Euler 300 I wanted to explore which of the strictly superior fold set were redundant but started getting an exception thrown after a few iterations.

I've changed the offending part to try to make it as impact-free as possible (my code is not pretty :)), it's now pure and the return is only used with writeln to track the progress of the function yet it still causes an exception after 4 or 5 iterations.

http://pastebin.com/j6REskhd

The offending function is 'solve', which I've repeatedly called to make the exception as simple as possible along with const data and limited use of the return data. I've tried making it pure/const as well as adding delete on the main data and also removing pure and calling the garbage collector. This is the stack trace crash assembler command:

7C90E8E5  push        ebx

Does this mean there is a stack overflow? Any ideas what on earth is going on?

It seems to leak memory with each iteration of the loop taking another 100-200K until it crashes when going over 11 MB.

On 05/29/2012 07:33 PM, ixid wrote:
> Having solved Project Euler 300 I wanted to explore which of the
> strictly superior fold set were redundant but started getting an
> exception thrown after a few iterations.
>
> I've changed the offending part to try to make it as impact-free as
> possible (my code is not pretty :)), it's now pure and the return is
> only used with writeln to track the progress of the function yet it
> still causes an exception after 4 or 5 iterations.
>
> http://pastebin.com/j6REskhd
>
> The offending function is 'solve', which I've repeatedly called to make
> the exception as simple as possible along with const data and limited
> use of the return data. I've tried making it pure/const as well as
> adding delete on the main data and also removing pure and calling the
> garbage collector. This is the stack trace crash assembler command:
>
> 7C90E8E5 push ebx
>
> Does this mean there is a stack overflow? Any ideas what on earth is
> going on?

I haven't even run your program but I think your guess is correct: You are probably running out of stack space. The reason must be the fact that you pass fixed-length arrays by value.

LEN being 15, especially 'bits' is a very large array:

pure int[] solve(const bool[] redundancy, const ushort[LEN - 1][] matrixes, const int[2^^LEN] bits, const int[] numbers)

Fixed-length arrays are value types and are copied on the stack. Try passing 'bits' as 'const ref' instead of just 'const'.

Ali

-- 
D Programming Language Tutorial: http://ddili.org/ders/d.en/index.html

Thank you, that seems to fix it. I'd assumed that const arguments were optimized as ref any way for some reason so hadn't though to try that, hence my confusion about how more and more data was being created.

Then again I see how that's a silly though as I'm then expecting const to be immutable. What happens to ref const in a multi-threaded environment? Is it locked by the const ref function until it has finished or can other threads modify it?

On Wednesday, 30 May 2012 at 13:47:32 UTC, ixid wrote:
> Thank you, that seems to fix it. I'd assumed that const arguments were optimized as ref any way for some reason so hadn't though to try that, hence my confusion about how more and more data was being created.

1) Time ago I have asked for -w/-wi to produce a warning when you pass around a large value array. It's useful to avoid problems like yours.
2) Some time ago DMD used to print "stack overflow", now it doesn't. Such simple error message is quite useful (it's a regression, in Bugzilla).

Bye,
bearophile

On 05/30/2012 06:49 AM, ixid wrote:

> What happens to ref const in a multi-threaded
> environment? Is it locked by the const ref function until it has
> finished or can other threads modify it?

Yes, other threads can modify it but it would have to be marked as 'shared' to begin with. Otherwise only one thread could access it.

Then, it is still your responsibility to lock the data; but the best approach is to use message passing concurrency. I have a chapter on that:

  http://ddili.org/ders/d.en/concurrency.html

Ali

On 05/30/2012 04:33 AM, ixid wrote:
> Having solved Project Euler 300 I wanted to explore which of the
> strictly superior fold set were redundant but started getting an
> exception thrown after a few iterations.
>
> I've changed the offending part to try to make it as impact-free as
> possible (my code is not pretty :)), it's now pure and the return is
> only used with writeln to track the progress of the function yet it
> still causes an exception after 4 or 5 iterations.
>
> http://pastebin.com/j6REskhd
>
> The offending function is 'solve', which I've repeatedly called to make
> the exception as simple as possible along with const data and limited
> use of the return data. I've tried making it pure/const as well as
> adding delete on the main data and also removing pure and calling the
> garbage collector. This is the stack trace crash assembler command:
>
> 7C90E8E5 push ebx
>
> Does this mean there is a stack overflow? Any ideas what on earth is
> going on?

    superior.length = matrixes.length;
    foreach(inum, i;matrixes.parallel)
    {
	//.....
            superior[inum] = true;
    }

    Should "superior" be shared?

On Wednesday, 30 May 2012 at 06:06:10 UTC, Ali Çehreli wrote:
> pure int[] solve(const bool[] redundancy, const ushort[LEN - 1][] matrixes, const int[2^^LEN] bits, const int[] numbers)
>
> Fixed-length arrays are value types and are copied on the stack. Try passing 'bits' as 'const ref' instead of just 'const'.

This is specifically a fixed-length array issue?

I ask because I have a function in code I've written,

    final pure nothrow const(CoDetResult) reputation(immutable size_t users, immutable size_t objects, const Rating!(UserID, ObjectID, Reputation)[] ratings)

... which repeatedly gets passed vectors of length 4,000,000 or more, and memory usage stays at a constant level.

I didn't even realize it was possible to specify a fixed length for an array in a function declaration.

On 30.05.2012 20:40, Joseph Rushton Wakeling wrote:
> On Wednesday, 30 May 2012 at 06:06:10 UTC, Ali Çehreli wrote:
>> pure int[] solve(const bool[] redundancy, const ushort[LEN - 1][]
>> matrixes, const int[2^^LEN] bits, const int[] numbers)
>>
>> Fixed-length arrays are value types and are copied on the stack. Try
>> passing 'bits' as 'const ref' instead of just 'const'.
>
> This is specifically a fixed-length array issue?
>
> I ask because I have a function in code I've written,
>
> final pure nothrow const(CoDetResult) reputation(immutable size_t users,
> immutable size_t objects, const Rating!(UserID, ObjectID, Reputation)[]
> ratings)
>
> ... which repeatedly gets passed vectors of length 4,000,000 or more,
> and memory usage stays at a constant level.
>
> I didn't even realize it was possible to specify a fixed length for an
> array in a function declaration.

Fixed-sized array are value types. That is if you specify size in function declaration it becomes whole another type != that of dynamic array. However fixed array is easily "convertible" to dynamic slice via arr[] syntax.

-- 
Dmitry Olshansky