Jamming the cartridge
Michael A. Carr-Robb-John, Monolith Productions
In 1993 I was finishing off Desert Strike; I was doing the conversion from the 16-bit Mega Drive / Genesis to its humble little brother, the 8-bit Master System. The game was exceeding the desired cartridge size by about 12K, and going to the next size cartridge was out of the question. Today, 12K sounds incredibly small, but back then it was a major deal. During development, I had budgeted and planned all the sound and graphic resources and they were within their limits. The only section I hadn't been so strict on was the code. In those days, games were written in assembly language -- in this specific case, Z80 assembly -- so I had only one option left. I spent a week going through and finding redundant code and rewriting things to use a smaller memory footprint (usually at the cost of being more processor-intensive.)
By the time I had finished, the game fit onto a cartridge with just 98 bytes! The game was burned onto ROM and tested for a few days by the chaps in QA before being submitted to Sega for certification. Unfortunately it didn't pass on the first time, and the required fixes pretty quickly used up those 98 bytes. I think when we did publish, there were only 6 bytes free!
The Dalton Allocator
Jonathan Adamczewski, Insomniac Games
Toward the end of one project, we discovered that after playing through the game for many hours, movies would not trigger when they were supposed to. Fragmentation within one of our memory allocation heaps had made it impossible to reliably allocate the large blocks of memory that were needed for full-screen movie playback.
We needed to find a way to be sure that we could always get the memory we needed. However, it was too late in the project and too risky to consider defragmentation of the heap, we didn't have enough spare memory available to set aside exclusively for movie playback, and taking space away from other systems at that stage was impractical.
It was clear that when movies were playing, there were many other systems sitting idle, so we gave some consideration to "borrowing" memory from them. However, these other potential sources were either too small, or else also suffered from the same kind of fragmentation problems that we were already seeing. There was plenty of free space available for the GPU, but for various reasons we could not use that for the movie-playback buffers. So we needed another source of space.
While looking into another problem, a particular pattern of memory allocations within our main game-asset heap stood out: When the game started up, a number of assets were loaded from disk, and once in memory were never modified. Some of those assets were very large. None of them were needed while a movie was playing.
This gave us an idea: What if we were to copy the contents of one of the larger asset files to somewhere else in memory? The GPU's memory would work just fine as a place to temporarily stash the asset, and then we could temporarily reuse the space in the asset heap for movie playback, copying the asset data back from GPU memory when the movie finished.
So that's what we did. We chose the largest set of animation clips used for one of the game's heroes (named Dalton). The animation system was switched off, animation clips copied into the GPU's memory space, and the memory handed to the movie-playback system. At the end of the movie, the animation data was copied back to where it belonged, the animation system restarted, and the game proceeded as if nothing horrible had happened. The implementation ended up being fairly straightforward, though the process does span a number of frames to ensure that all the systems involved are safely synchronized with each other through each step of the process.
The memory for the movie system has since been described as coming from "the Dalton Allocator" after the character whose animation clip memory was usurped.
(I've since discovered that there's some history of this kind of thing at the studio -- of both stashing random things in GPU memory, and failing to set aside enough space earlier in the project...)