Stack Size

Last week Stu put up a post that included a mention of Ackermann's function. It looked very simple, and being inclined to avoid doing any real work, I thought I would write up a little program to exercise it. The program was very simple, but the results were a little disappointing, if not unexpected. Stu warned that the results quickly exceed the bounds of the native 32-bit arithmetic of your typical Pentium processor.

My immediate problem with the program was not the arithmetic, but the stack. Ackermann's function is recursive, which means it calls itself, and as simple minded as it is, it has calls to itself nested within calls to itself. Kind of like wheels within wheels. So the problem is that it runs out of stack space and crashes which means it doesn't deliver any results at all.

I have been using Microsoft's (boo! hiss!) Visual C++ (Version 6.0 last copyright 1998, a very good product) for quite a while so I whipped up the first version of the program there, and when it ran out of stack space I was able to find the command to increase it (/stack:number).

But stack space is the least of the problems with this program. The other problem is the ridiculously large numbers it produces. So now we are operating in the realm of fantasy, and Windows, as wonderful as it is, is not going to cut it. So off to Linux we go. Besides, I had installed the Eclipse software development program on my Linux box, and I needed to learn how to use it. This looks like a prime opportunity.

After a bunch of fiddling around with Eclipse and my program, I finally get it to compile and run. All is well. Now, how do you set the stack size for this program? Help is no help at all. A bunch of Googling turns up ulimit, a program you can run from a terminal window to set a bunch of different memory allocation limits. So I set ulimit to some gloriously large number like a billion and let my program run overnight. It did nothing. It did not run out of stack space, which is something, but it also failed to complete the computation of A(4,0). Bah.

So I'm playing around with ulimit this morning and I learn a few things. After the first time you set the stack size, you can only reduce it. You can enlarge it only the first time you run ulimit. ulimit works in units of 1KB, so the default setting of 8192 is equivalent to 8 megabytes. Anything above 4 million or so (2 to the 21st power, which translates to 4 gigabytes, the most memory that can be handled by a 32-bit processor) causes the stack size to be unlimited. 7 or below will keep my program from running. The shell (or CLI (Command Line Interpreter) if you prefer) immediately reports back killed.