Stacks, exceptions and crashes -- oh my!

This topic seems to surface about twice a year, and I figured it might be a good idea to do some educational work to shed a bit of light on the topic of stacks. There are several different "stack problems" that can plague an application, and understanding what problems can arise will help you code better.

The way work gets done in applications is by the CPU allocating space somewhere for your data to live, and then executing instructions that work on that data. The convention for this process is to use "stacks", so that you can have data local to just one method which doesn't affect data local to another method. For a bit more information about the basics of stacks, check out this Wikipedia article on the subject. For the purposes of this discussion, I assume that you know what a stack is, and what a stack frame is (basically, the stack is comprised of stack frames -- that's a key concept).

There are really two different problems related to stacks that you can run into: 1) You have too much data to fit into a stack frame, and 2) Your stack as a whole has grown too large.

Problem #1 stems from the fact that it's very difficult to work around processor limitations (such as some imposed by PPC) on how much local data you can address. That's not to say it's impossible to do, but it is hard. And 32k of local stack data is a huge amount of data (we're talking over 8000 local variables at four bytes a piece). So in REALbasic, when you compile for PPC, we make this into a compile time error. We can do this because the size of an individual stack frame is known at compile time, so we can simply check to see if the method is "too large", and if it is, throw an error.

Problem #2 can only be determined at runtime, because it involves dynamic choices of what method is being called. As methods are called, their stack frames are added to the stack. And if there is "too much" data on the stack (where "too much" is determined by the OS), then you get a crash. REALbasic attempts to alleviate this problem as best it can by doing stack overflow checking. The way this checking works is that the compiler inserts a call into the framework at the start of every method, and that call will check to see if we're close to overflowing the stack. To perform that check, the method basically says "how much stack is being used now? If I add some constant value to it, will I overflow the stack? If so, throw an exception!" We add a constant value to the current stack size to ensure there is enough room to throw the stack overflow exception (otherwise we'd just crash). This solution works nicely to combat against recursive methods causing crashes in your applications, but it isn't perfect.

So what's the problem with this approach? Well, what happens if the next method we call requires a larger stack frame than our constant value in the stack checker? Ka-boom! The stack checker ensures there's enough space left for the exception code to run, but by the time the stack checker is actually called, the frame has already been setup. So if the last stack frame was checking to make sure at least 1k was left on the stack, and the current stack frame grabs 2k of stack space.... there's no way to capture that. Well, not quite -- there are a few things which could be done. We could keep track of the largest stack frame size, and pass that into the stack frame checking method. Then it could ensure we have enough space for the largest stack frame plus the space required for an exception to be thrown. This solution is also very difficult to do, because it means we have to do a lot more tracking and backpatch all of the places we call the stack frame checker. The other solution is to pick a much higher "we're about to overflow the stack" constant in the stack frame checker. Of course, that's not really a solution, just raising the limit (at which point in time, someone else will hit the new limit and the problem starts over). There are other solutions as well, but they typically fall into these two categories of "very hard to do" and "not really solving the problem."

The things that go on the stack include local variables, parameters, and temporaries. Out of this list, temporaries are the ones you don't see, and are generally the cause of all your stack-related troubles. The compiler generates temporaries for things like datatype conversions (amongst other things), and because the compiler doesn't have an optimizer, it does not reuse the temporaries. So what can you do to alleviate the situation? Write better code. I know that sounds quite harsh, but it's true. If you follow these tenets, you will never run into a problem:

1) Make your methods concise. If you can hit PageDown in your code editor more than once or twice, your method isn't concise (or you're on a PDA/tiny monitor!). There's no "magic number" as to how many lines of code is considered "too many", but the shorter your methods are (within reason), the more maintainable and readable your code will be.

2) Use matching datatypes. If you are making an array of integers, don't pass in a bunch of doubles! That needlessly uses temporaries which end up adding to your total stack frame size. If only there was some way for the compiler to tell you when you were implicitly converting between datatypes... (hint: check out the Analyze Project feature in a future release of REALbasic)

That's it! Just do those two things, and you probably will never wonder about random crashes related to running out of stack space in your application. And out of those two things, #1 is by far the most important.

Hopefully you have a better understanding of what sort of stack-related problems can arise in your application, and how to ensure that it never happens to you. :-)