www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Stack Space & Ackermann

reply Era Scarecrow <rtcvb32 yahoo.com> writes:
  Well re-watched a video regarding the Ackermann function which 
is a heavily recursive code which may or may not ever give a 
result in our lifetimes. However relying on the power of memoize 
I quickly find that when the program dies (from 5 minutes or so) 
nearly instantly (and only using 9Mb of memory).

long ack(long m, long n) {
     long ans;

     if (m == 0) ans = n + 1;
     else if (n==0) ans = ack(m-1, 1);
//    else ans = ack(m-1, ack(m, n-1)); // original
     else ans = memoize!ack(m-1, memoize!ack(m, n-1));

     return ans;
}

  This is only due to the limited stackframe space. Doing a search 
I find that the amount of stack space is decided on when the EXE 
is being compiled and in the EXE header but I'm not sure which 
one needs to be update (supposedly it's either 250k or 1Mb is the 
default), although neither help in this case, nor do the other 
binary tools as they don't recognize the binary format of D's exe 
output files)

  Alternatively if there's a way to tell the compiler a hint 
(either in D or in the compiling/linking flags) or the specific 
offset of which 32bit entry is the stack reserved space, I could 
continue my little unimportant side experiments.

  Suggestions? Comments?
Jan 04 2017
next sibling parent reply rikki cattermole <rikki cattermole.co.nz> writes:
On 05/01/2017 5:50 PM, Era Scarecrow wrote:

  Well re-watched a video regarding the Ackermann function which is a
 heavily recursive code which may or may not ever give a result in our
 lifetimes. However relying on the power of memoize I quickly find that
 when the program dies (from 5 minutes or so) nearly instantly (and only
 using 9Mb of memory).

 long ack(long m, long n) {
     long ans;

     if (m == 0) ans = n + 1;
     else if (n==0) ans = ack(m-1, 1);
 //    else ans = ack(m-1, ack(m, n-1)); // original
     else ans = memoize!ack(m-1, memoize!ack(m, n-1));

     return ans;
 }

  This is only due to the limited stackframe space. Doing a search I find
 that the amount of stack space is decided on when the EXE is being
 compiled and in the EXE header but I'm not sure which one needs to be
 update (supposedly it's either 250k or 1Mb is the default), although
 neither help in this case, nor do the other binary tools as they don't
 recognize the binary format of D's exe output files)

  Alternatively if there's a way to tell the compiler a hint (either in D
 or in the compiling/linking flags) or the specific offset of which 32bit
 entry is the stack reserved space, I could continue my little
 unimportant side experiments.

  Suggestions? Comments?


Well, you could create a fiber[0].

Fibers allow you to set the stack size at runtime.
Jan 04 2017
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Thursday, 5 January 2017 at 04:53:23 UTC, rikki cattermole 
wrote:

 Well, you could create a fiber[0].

 Fibers allow you to set the stack size at runtime.




  Well that certainly does seem to do the trick. Unfortunately I 
didn't get the next output because I ran out of memory to 
allocate/reallocate over 2Gb :P

  I suppose with a 64bit compiling the program might run a bit 
longer and succeed further (with 24Gigs of ram), however the 
sheer amount of memory required will make this little exercise 
more or less a waste of time.

  Still that was an interesting way around the (stackframe) 
problem, one I'll keep I mind (should i need it again).

void m() {
     foreach(i; iota(6))
         foreach(j; iota(6)) {
             writefln("Ackerman (%d,%d) is : %d", i,j,ack(i,j));
     }
}

int main(string[] args) {
     Fiber composed = new Fiber(&m, 2<<28); //512MB
     composed.call();

     return 0;
}

results:

Ackerman (3,5) is : 253
Ackerman (4,0) is : 13
Ackerman (4,1) is : 65533

core.exception.OutOfMemoryError src\core\exception.d(693): Memory 
allocation failed
Jan 04 2017
parent reply rikki cattermole <rikki cattermole.co.nz> writes:
On 05/01/2017 7:03 PM, Era Scarecrow wrote:

 On Thursday, 5 January 2017 at 04:53:23 UTC, rikki cattermole wrote:

 Well, you could create a fiber[0].

 Fibers allow you to set the stack size at runtime.




  Well that certainly does seem to do the trick. Unfortunately I didn't
 get the next output because I ran out of memory to allocate/reallocate
 over 2Gb :P

  I suppose with a 64bit compiling the program might run a bit longer and
 succeed further (with 24Gigs of ram), however the sheer amount of memory
 required will make this little exercise more or less a waste of time.

  Still that was an interesting way around the (stackframe) problem, one
 I'll keep I mind (should i need it again).

 void m() {
     foreach(i; iota(6))
         foreach(j; iota(6)) {
             writefln("Ackerman (%d,%d) is : %d", i,j,ack(i,j));
     }
 }

 int main(string[] args) {
     Fiber composed = new Fiber(&m, 2<<28); //512MB
     composed.call();

     return 0;
 }

 results:

 Ackerman (3,5) is : 253
 Ackerman (4,0) is : 13
 Ackerman (4,1) is : 65533

 core.exception.OutOfMemoryError src\core\exception.d(693): Memory
 allocation failed


You're using more memory then need to:

foreach(i; 0 .. 6)

No need for iota.
Jan 04 2017
parent Era Scarecrow <rtcvb32 yahoo.com> writes:
On Thursday, 5 January 2017 at 06:20:28 UTC, rikki cattermole 
wrote:

 foreach(i; 0 .. 6)

 No need for iota.


  I thought that particular slice/range was depreciated. Still the 
few k that are lost in the iota doesn't seem to make a difference 
when i run the code again.
Jan 04 2017
prev sibling parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Jan 05, 2017 at 04:50:19AM +0000, Era Scarecrow via Digitalmars-d-learn
wrote:

 Well re-watched a video regarding the Ackermann function which is a
 heavily recursive code which may or may not ever give a result in our
 lifetimes.  However relying on the power of memoize I quickly find
 that when the program dies (from 5 minutes or so) nearly instantly
 (and only using 9Mb of memory).
 
 long ack(long m, long n) {
     long ans;
 
     if (m == 0) ans = n + 1;
     else if (n==0) ans = ack(m-1, 1);
 //    else ans = ack(m-1, ack(m, n-1)); // original
     else ans = memoize!ack(m-1, memoize!ack(m, n-1));
 
     return ans;
 }
 
 This is only due to the limited stackframe space.


[...]

For heavily-recursive functions like this one, you *really* want to be
revising the algorithm so that it *doesn't* recurse on the runtime
stack.  Keep in mind that the Ackermann function was originally
conceived specifically to prove that a certain elementary class of
recursive functions (called "primitive recursive" functions) cannot
perform certain computations. Very roughly speaking, primitive recursive
functions are "well-behaved" with regard to recursion depth; so the
Ackermann function was basically *designed* to have very bad
(unrestricted) recursion depth such that no primitive recursive function
could possibly catch up to it. Translated to practical terms, this means
that your runtime stack is pretty much guaranteed to overflow except for
the most trivial values of the function.

The other problem with your code, as written, is that it will quickly
and easily overflow any fixed-width integer such as long here. For
example, ack(4,1) == 65533, but ack(4,2) is a value that requires 65536
bits to represent (i.e., an integer that's 1 KB in size), and ack(4,3)
is a value that requires ack(4,2) bits to represent, i.e., the number of
bits required is a number so huge that it itself requires 1KB to
represent. This far exceeds any memory capacity of any computer system
in existence today, and we haven't even gotten to ack(4,4) yet.

You might at least be able to get to ack(4,2) if you use BigInt instead
of long (though be prepared for incredibly huge running times before the
answer ever appears!), but even BigInt won't help you once you get to
ack(4,3) and beyond.  And don't even think about ack(5,n) for any value
of n greater than 0, because those values are so ridiculously huge you
need special notation just to be able to write them down at all.

Because of this, your code as written most definitely does *not* compute
the Ackermann function except for the smallest arguments, because once
ack(m, n-1) overflows long, it can only return the answer module
long.max, which will be much smaller than the actual value, so the
nested recursion ack(m-1, ack(n, m-1)) actually will compute a value far
smaller than what the real Ackermann function would (and it would run
much faster than the real Ackermann function).

Not to mention, the recursive definition of the Ackermann function is
really bad for actually computing its values in a computer, because it
makes a huge number of recursive calls just to compute something as
simple as + and * (essentially what ack(1,n) and ack(2,n) do). In a
practical implementation you'd probably want to special case these
arguments to use faster, non-recursive code paths.  Using memoize
alleviates the problem somewhat, but it could be improved more.

Nonetheless, even if you optimize said code paths, you still won't be
able to get any sane results for m>4 or anything beyond the first few
values for m=4. The Ackermann function is *supposed* to be
computationally intractible -- that's what it was designed for. :-P


T

-- 
Do not reason with the unreasonable; you lose by definition.
Jan 04 2017
parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Thursday, 5 January 2017 at 07:30:02 UTC, H. S. Teoh wrote:

 Nonetheless, even if you optimize said code paths, you still 
 won't be able to get any sane results for m>4 or anything 
 beyond the first few values for m=4. The Ackermann function is 
 *supposed* to be computationally intractible -- that's what it 
 was designed for. :-P


  Yeah I know. The function as written is as it was shown on the 
video and explained, and is badly formed. Memoize did give me 
real quick results up to 4,1; But it's obvious getting anything 
better is impossible as things stand.

  Still it did bring up how to handle needing larger stack spaces, 
which I've wondered about with wanting to make large structures 
on the stack so I wouldn't have to rely on actually allocating 
anything and not having to clean it up afterwards. Simpler, 
cleaner & faster memory management in my mind.
Jan 05 2017
parent "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Thu, Jan 05, 2017 at 08:11:58AM +0000, Era Scarecrow via Digitalmars-d-learn
wrote:

 On Thursday, 5 January 2017 at 07:30:02 UTC, H. S. Teoh wrote:

 Nonetheless, even if you optimize said code paths, you still won't
 be able to get any sane results for m>4 or anything beyond the first
 few values for m=4. The Ackermann function is *supposed* to be
 computationally intractible -- that's what it was designed for. :-P


 
  Yeah I know. The function as written is as it was shown on the video
  and explained, and is badly formed. Memoize did give me real quick
  results up to 4,1; But it's obvious getting anything better is
  impossible as things stand.
 
  Still it did bring up how to handle needing larger stack spaces,
  which I've wondered about with wanting to make large structures on
  the stack so I wouldn't have to rely on actually allocating anything
  and not having to clean it up afterwards. Simpler, cleaner & faster
  memory management in my mind.


Actually, the runtime stack is really intended more for control flow
(e.g., to store function return addresses and arguments, local
variables, etc.) than for allocating large structures.  In the old days
Linux used to allocate only 4KB for the stack, though these days I'd
imagine it has been raised. (Well, in the *real* old days of Apple II,
the runtime stack was hardware-limited to 256 bytes. But those were
different times. :-P)  For large data structures you really should be
looking to heap allocation.

It is possible to have stack-like behaviour of heap-allocated data, such
as C++'s RAII idiom.  I haven't really tried that in D in a large scale
yet, but I'd imagine you should be able to do that in D quite easily as
well.


T

-- 
In a world without fences, who needs Windows and Gates? -- Christian Surchi
Jan 06 2017