Did anyone ever run out of stack space on the 6502?

Question

Unlike its main rival the Z80, the 6502 had a size limit of 256 bytes for the hardware stack. That sounds like a very tight limit, but in my experience, it was never actually an issue; by the time you were trying to do anything complex enough to exceed it, you would run out of 64K RAM before running out of the 256-byte stack.

But my experience is not necessarily universal. So, did anyone ever run out of stack space on a 6502?

Obviously I'm not counting 'a coding bug caused infinite recursion'. I'm looking for answers like 'X computer algebra package ran on the Apple II, but it used algorithms that legitimately did some heavy recursion, so it could only solve equations up to complexity Y before running out of stack space even though there was still some RAM to spare'.

Answer 1

Unlike its main rival the Z80, the 6502 had a size limit of 256 bytes for the hardware stack.

The 6502 stack is mainly meant as a return stack and for register preservation - which usually isn't a lot on a CPU with just 3 registers. It lacks all features for stack relative addressing (*1). A limitation not really a hindrance as the 6502 was focused on embedded, an area where dynamic memory allocation and variable parameter passing is not common.

That sounds like a very tight limit, but in my experience, it was never actually an issue; by the time you were trying to do anything complex enough to exceed it, you would run out of 64K RAM before running out of the 256-byte stack.

For embedded, games and runtimes like BASIC that's certainly true. It can get tricky with ALGOL derivative languages trying to (mis-)use the machine stack for data storage. That's why most of those language runtimes, like Pascal, used a separate data stack.

But my experience is not necessarily universal. So, did anyone ever run out of stack space on a 6502?

Let's say it's hard, but possible. Two examples from the Apple II world:

Applesoft BASIC

While Applesoft itself uses only a few levels for subroutine calling, it does use the stack for bookkeeping of

• Temporary Variables (in expressions)
• FOR/NEXT Loops
• Subroutine Calling

Space requirements are, as the original Applesoft Manual (Blue Book) states in Appendix D - Space hints:

As a result, a few levels of nested FOR/NEXT and calculations can put up a heavy stack load - and when structured with GOSUB even more. This has been experienced notably by some programs walking matrices, doing complex calculations.

Already in a basic matrix multiplication, like shown in line 5 of this Rosetta Code snippet may eat up ¼ of the stack:

(Indentation added for readability)

FOR I = 1 TO M:                 | +16 bytes
  FOR J = 1 TO P:               | +16 bytes
    FOR K = 1 TO N:             | +16 bytes
      AB(I,J) =
        AB(I,J) +               | + 4 bytes
        (A(I,K) * B(K,J)):      | +12 bytes
NEXT K,J,I

That's 64 bytes at maximum depth. Add another 6 for each level of a subroutine it's in - which for that kind of stuff is extremely common, as it's needed over and over. And that's just a multiplication on the inside. Imagine some using more complex formula for 3D calculation in graphics or astronomical programs makes it easy to see how BASIC can end up reporting an "OUT OF MEMORY" error.

These numbers may as well be valid for other 6502 MS-BASIC derivatives.

ProDOS

ProDOS in turn may use up to a quarter (~64) of the stack during execution, thus stressing the available space even more. While ProDOS calls usually don't happen within calculations, it does need more stack during execution than bare-bones BASIC.

Conclusion:

Yes, it may happen with non-trivial BASIC programs.

---

*1 - Although that can be emulated to some degree by moving the stack pointer to X and using indexed addressing, but that quickly gets cumbersome when needing anything past the most basic byte fetch.

Answer 2

Most likely answer is, yes, someone has likely run out of stack space on a 6502 at some point.

On the other hand, modern C compilers don't use the hardware stack much, as they implement a software stack for passing parameters.

And depending on what you are doing, you can simply extend it or do a context switch, by moving the 256 byte stack area to elsewhere in memory temporarily, then use the stack as you wish and finally restore the stack area.

I know that this technique is used to make a bare-bones multi-tasking RTOS for a C64 with SDCC.

Answer 3

I did, arguably.

The Atari Lynx is a system with unified memory, a 4bpp frame buffer and a scaling blitter.

So for algorithmic drawing, a fairly obvious optimisation is to push pixels to the stack as whole bytes, then blit them to their proper destination at 50% scale. That saves you from both the 6502-specific deficiencies around arbitrary memory indexing and from having to use the processor for pixel-into-byte packing.

Blitter objects require a description block which is read first by the blitter. Therefore the cost increases with both the total number of pixels and the total number of individual blitter objects.

One would therefore ideally write the whole output once and blit it once. Even given that doing so is not realistic for other reasons, being stuck below 256 bytes total is the actual bottleneck.

Therefore I was forced to code around the limited stack.

---

As a more obvious example: all small-C compilers for the 6502 that I am aware of maintain a software 16-bit stack because the hardware one is too much of a hazard.

Answer 4

The 6502 instruction set is not very well-suited for using the hardware stack for tasks other than subroutines calls and short-term storage. Subroutine calls nested 128 deep are pretty rare even today, assuming non-recursive algorithms. The hardware stack is usually sufficient for the call stack.

A program that needs more complex stack operations usually implements a stack. The 6502 offers a number of ways. A small stack can be implemented in zero page. Zero page indexed addressing makes for fast access to stack elements. X is often used as the index for this stack. The same thing can be done off zero page, with a code size and speed penalty. You can have many stacks if you have space for them. You just have to keep track of all the stack pointers. For a bigger stack, the virtual stack pointer can be kept in a 16-bit address in zero page and manipulated quickly that way. Zero-page indirect addressing can be used to access the elements.

Software-implemented stacks on the 6502 are a lot more flexible to work with than the hardware stack, and not slower, in practice. While there are exceptions, high-level languages on the 6502 usually implement their own stack for data, and use the hardware stack just for subroutine calls.

Answer 5

It probably wasn't common for programs to use anywhere close to 256 bytes of storage as an actual stack which is accessed primarily via push/pop/jsr/rts. On the other hand, it was common for systems to use some of the storage in the $0100-$01FF range for purposes other than the stack, and programs which only left a few bytes for the stack could easily overflow it. On the Atari 2600, RAM was sufficiently tight that many programs only had 4 or maybe 6 bytes available for use as an actual stack.

Additionally, Microsoft's BASIC interpreter, and likely many others, makes use of the stack to keep track of things like temporary computations, nested FOR loops, etc. and it's not hard to write a BASIC program that would cause a Microsoft interpreter to overflow the stack.

Addendum

While I don't know the particular rationale for the design decision to use an 8-bit register to place the stack in the range 0x100-1FF, I suspect that much of it centered around a few things:

1. Placing the stack within zero page would reduce the amount of zero-page addressing space available for other purposes.

2. Systems with more than 512 bytes of RAM might want to have all of the RAM that wasn't used for zero page or the stack be contiguous (implying the stack should go as low as possible in page 1).

3. Systems with 512 bytes or less of RAM might want to have all of the RAM that isn't used as stack and doesn't exploit zero-page addressing be contiguous (implying the stack should go as high as possible in page 1).

4. Using an 8-bit stack pointer to put the stack in the range $0100-$01FF was easier than any other means of trying to cater to all three criteria.

Note that the decision to use an 8-bit stack pointer doesn't imply a particular desire to allow programs to use a full 256 bytes of stack, but rather a convenient means of allowing programs to use whatever size stack they want without adversely affecting the amount of contiguous RAM available for other purposes.

Answer 6

In Total Replay, we rely heavily on the stack page to hold actual code, so the usable stack is far smaller than 256 bytes. As such, we've run out of stack quite often and had to work around it, by making routines load second stages dynamically, for example.

Answer 7

Final Fantasy is a curious example. It has a spell called WARP which takes you one step closer to the entrance of the dungeon (or out of the dungeon if you're at the entrance). To implement this, the game uses the system stack to keep track of where you are in the dungeon.

The game has two kinds of staircases, which we call teleports and warps. A teleport pushes your current location onto the stack and a warp pops it, equivalent to using the WARP spell. It follows, then, if you follow a long enough series of teleports, you will overflow the system stack. There are in fact a few places where this is possible: Castle Coneria, the Ice Cave, and the Castle of Ordeal.

So what happens when you overflow the stack? Nothing. The player won't even notice. It will mean that the bottom of the stack is overwritten and so the player can no longer exit the dungeon using a series of warps, but this is not actually a problem in practice since there are no warp staircases in the areas where this is possible and you probably won't have the WARP spell yet.

But the programmer did add a safeguard, so if you're about to underflow the stack (by overflowing it and then executing WARP), the game will see the stack pointer is too close to the bottom of the stack and kick you out to the world map. This is easily testable by going up and down the stairs repeatedly in Castle Coneria, since both ends of the staircase are teleports. Executing the WARP spell should take you to whichever room you were previously in, but if you go up and down the right number times, then executing a single warp will take you back to the world map.