27

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'.

9
  • 26
    Since programmers of recursive programs knew that it could overflow, they could have used a "secondary stack" independent of the actual stack for parameters and reserve the actual stack for function calls. And recursion can be emulated with a custom stack too. I remember the "forest fire" filling algorithm on a pretty modern (well compared to 6502) HPUX workstation and our teacher requiring us to implement such a mechanism because else the stack exploded. Commented Jan 2, 2023 at 20:55
  • 8
    Lot's of applications (to just name one: the UCSD p-Code VM, which is stack-based) use their own stack instead of the hardware stack exactly to avoid running out of stack space.
    – dirkt
    Commented Jan 3, 2023 at 7:14
  • 2
    The Atari 2600 used a 6507 (a 6502 with fewer address lines) and only 128 bytes of RAM, which doubled up as zero page and stack space. Adding items to the stack would overwrite more main memory as you carried on. As it was easy to run out of RAM, it was also easy to run out of stack too!
    – Kaz
    Commented Jan 3, 2023 at 12:12
  • 2
    Didn’t flood fill use the stack? Commented Jan 3, 2023 at 19:03
  • 4
    Not really a good question. You might find someone with personal knowledge of running out of stack. But you won't find anyone who can tell you for certain that no-one ever did. Commented Jan 4, 2023 at 21:40

7 Answers 7

49

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:

enter image description here

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.

8
  • 6
    This... this here is a fantastic answer. I used virtually every tool and technique you list here back in the day, and I didn't know half of this. Marvelously-well-researched, impeccably-cited, and clearly written. I honestly didn't know the answer to OP's question, but having read this, I could now effectively CRAFT an example to illustrate an answer to it, in code. Hats off to you, @Raffzahn.
    – NerdyDeeds
    Commented Jan 3, 2023 at 9:13
  • 1
    Is there any indication that Applesoft BASIC actually used the hardware stack rather than some other software stack?
    – jcaron
    Commented Jan 3, 2023 at 11:57
  • 1
    @jcaron What more indication' would you need beside the shown original manual?
    – Raffzahn
    Commented Jan 3, 2023 at 16:14
  • 2
    A quick look through the source code seems to indicate it does indeed use the system stack github.com/cmosher01/Apple-II-Source/blob/master/src/system/…
    – jcaron
    Commented Jan 3, 2023 at 16:39
  • 1
    @jcaron Yes, it is as what we take fro granted today, can rarely be projected back. That's true for technology the same way as for any other part of life. With you citation you may want to notice the "most of those" right before, which refers to the ALGOL type languages which use a stack for data structures by default. Pascal is an ALGOL language, BASIC not (At least as far as original BASIC and most early BASICs go Some later did add the notion of procedures and local variables which do need a stack for data)
    – Raffzahn
    Commented Jan 3, 2023 at 16:57
17

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.

16

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.

8

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.

1
  • 2
    Actually, for cases where the system stack is big enough, the 6502's stack works pretty well, since after one performs a TSX, the abs,X addressing mode may be used to access any item on the stack directly by index. By contrast, when using a software-based stack with zp,y addressing, copying a byte from a location 3 bytes above top-of-stack to a location 8 above would require loading Y with 3, reading the byte, loading Y with 7, and then storing it.
    – supercat
    Commented Jan 5, 2023 at 17:41
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.

7

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.

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .