www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Exception caused by calling a pure function repeatedly

reply "ixid" <nuaccount gmail.com> writes:
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?
May 29 2012
next sibling parent "ixid" <nuaccount gmail.com> writes:
It seems to leak memory with each iteration of the loop taking 
another 100-200K until it crashes when going over 11 MB.
May 29 2012
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
May 29 2012
next sibling parent reply "ixid" <nuaccount gmail.com> writes:
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.
May 30 2012
next sibling parent reply "ixid" <nuaccount gmail.com> writes:
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?
May 30 2012
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
May 30 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
May 30 2012
prev sibling parent reply "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
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.
May 30 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
May 30 2012
prev sibling parent "ixid" <nuaccount gmail.com> writes:
This is specifically a fixed-length array issue?


No, fixed and dynamic overflow, though I think one takes one more 
iteration than the other possibly to cause it.
May 30 2012
prev sibling parent reply sclytrack <sclytrack iq87.fr> writes:
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?
May 30 2012
parent "ixid" <nuaccount gmail.com> writes:
If you mean should multiple threads access it at the same time I 
think it's safe as the inum used by each thread will never be the 
same.
May 30 2012