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
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. [0] http://dlang.org/phobos/core_thread.html#.Fiber.this
Jan 04
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.

 [0] http://dlang.org/phobos/core_thread.html#.Fiber.this
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
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.

 [0] http://dlang.org/phobos/core_thread.html#.Fiber.this
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
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
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
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
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