Object Pooling

A shoot-’em-up can have dozens of bullets on screen, each living for a second or two. A modern program might create an object for every shot and throw it away when the shot leaves the screen. An 8-bit game written in machine code had no memory allocator to ask, unless its programmer wrote one, so it did something simpler: it set aside room for a fixed number of bullets when the game was written, and reused those slots for ever. Firing claims a free slot; a bullet that hits something or leaves the screen hands its slot back. Nothing is ever created or destroyed.

Today that is called object pooling, and it is still taught. A 2022 Wireframe tutorial for the Game Boy recycles three coins instead of removing them when the player collects them: “This is a well-known technique called ‘object pooling’ and it means we never need to dynamically allocate or deallocate memory.”

An early example: Space War in BYTE

In October 1977 BYTE printed David Kruglinski’s “How to Implement Space War”, which put the game on an Altair-class 8080 microcomputer with 8K of memory, drawing on an oscilloscope screen. Its data is a short list of fixed “object blocks”: “ship 1, ship 2, torpedo 1, torpedo 2, score 1 and score 2”. Each ship owns one torpedo. The fire routine “claims one torpedo belonging to the firing ship if it is not claimed”, and the torpedo’s own routine releases it when it “hits edge of screen” or “gets too close to the sun”. It is a pool of one per player: while a ship’s torpedo is in flight, that ship has nothing left to fire.

Why pool

Robert Nystrom’s Game Programming Patterns sums up the aim as to “improve performance and memory use by reusing objects from a fixed pool instead of allocating and freeing them individually”. Two problems go away:

• Allocation cost. Asking a general-purpose allocator for memory, and giving it back, takes time that varies. A pool hands out a slot in a few instructions.
• Fragmentation. In Nystrom’s words, “Fragmentation means the free space in our heap is broken into smaller pieces of memory instead of one large open block.” A game that runs for hours can find a large request failing even though enough memory is free in total. A pool’s memory is reserved once and never moves.

The cost is a fixed maximum. When every slot is in use, something has to give. Nystrom lists the choices: size the pool so it never overflows, refuse the new object (“the user won’t notice if the next explosion isn’t quite as impressive”), replace an existing one (for sounds, “find the quietest sound already playing”), or grow the pool at run time.

The active-flag pool

The simplest pool keeps a flag per slot:

1. Start: every slot is marked free.
2. Spawn: scan for the first free slot, fill it in and mark it in use.
3. Update: each frame, visit every slot and process the ones in use.
4. Release: mark the slot free. Its data stays where it is, ignored, until the slot is reused.

On the 6502 the natural layout is one array per field, sometimes called a structure of arrays. The slot number goes in Y, and bullet_x,y, bullet_y,y and the rest all index directly. Here is a 16-slot bullet pool in ca65 syntax, five bytes per bullet:

NUM_BULLETS = 16

.segment "BSS"
; One array per field (a "structure of arrays"): the slot number in Y
; indexes every field directly with absolute,Y addressing.
bullet_x:        .res NUM_BULLETS
bullet_y:        .res NUM_BULLETS
bullet_vx:       .res NUM_BULLETS    ; signed
bullet_vy:       .res NUM_BULLETS    ; signed
bullet_active:   .res NUM_BULLETS    ; 0 = free, 1 = in use

.segment "CODE"
; Spawn a bullet at A = x, X = y.
; Returns carry clear and the slot in Y, or carry set if the pool is full.
spawn_bullet:
    pha                     ; keep x while A does the search
    ldy #0
@find_free:
    lda bullet_active,y
    beq @found              ; first free slot
    iny
    cpy #NUM_BULLETS
    bne @find_free
    pla                     ; pool full: tidy the stack
    sec
    rts
@found:
    pla
    sta bullet_x,y
    txa
    sta bullet_y,y
    lda #1
    sta bullet_active,y
    clc                     ; success: caller sets bullet_vx,y and bullet_vy,y
    rts

; Move every active bullet once a frame.
update_bullets:
    ldy #0
@next:
    lda bullet_active,y
    beq @skip
    clc
    lda bullet_x,y
    adc bullet_vx,y
    sta bullet_x,y
    clc
    lda bullet_y,y
    adc bullet_vy,y
    sta bullet_y,y
    ; off-screen check and collisions go here; to release the slot:
    ;   lda #0
    ;   sta bullet_active,y
@skip:
    iny
    cpy #NUM_BULLETS
    bne @next
    rts

The cost is easy to predict. Counted in the sim65 6502 simulator from the cc65 suite, update_bullets takes 237 cycles with all 16 slots empty, about 14 cycles per empty slot, and 701 cycles with all 16 bullets moving, before any collision checks. A 6502 running at about 1 MHz has roughly 20,000 cycles in a 50 Hz frame, so even a full pool leaves most of the frame for everything else.

A flag byte is not the only way to mark a free slot. A C64 routine on the Codebase64 wiki keeps eight character-based bullets in two tables, row and column, and uses a row of $FF to mean “bullet not active”, which saves the separate array.

The free-list pool

The active-flag pool’s weakness is spawning: the scan for a free slot takes longer as the pool fills. A free list makes spawning take the same time however full the pool is. Keep a stack of free slot numbers: spawning pops one, releasing pushes it back. Nystrom’s version stores the list inside the unused objects themselves, borrowing “the data for the unused particles”; on the 6502 a separate small array is simpler.

.segment "BSS"
free_list:    .res NUM_BULLETS
free_count:   .res 1

.segment "CODE"
; Fill the stack with every slot number. Works for up to 128 slots.
init_pool:
    ldy #NUM_BULLETS - 1
@fill:
    tya
    sta free_list,y         ; free_list[i] = i (any order works)
    dey
    bpl @fill
    lda #NUM_BULLETS
    sta free_count          ; every slot is free
    rts

; Returns carry clear and a slot number in A, or carry set if the pool is full.
alloc_bullet:
    ldy free_count
    beq @full
    dey
    sty free_count
    lda free_list,y
    clc
    rts
@full:
    sec
    rts

; A = slot number to release. Release each slot once only.
free_bullet:
    ldy free_count
    sta free_list,y
    iny
    sty free_count
    rts

The update loop still has to know which slots are in use, so a free list usually sits alongside an active flag rather than replacing it. Nothing stops a slot being released twice, which would put the same number on the stack twice and hand one slot to two bullets; the code that releases a bullet has to be sure it was in use. For a pool of a dozen or so bullets, the scan in the active-flag version is cheap enough that many programs never needed this.

Compaction

A third arrangement keeps all the active objects packed at the start of the arrays, with a count of how many there are. Spawning writes to the slot at the count and adds one. Releasing copies the last active object into the released slot and subtracts one. The update loop then visits only the active objects and never tests a flag. One care point: if the loop releases the object it is looking at, the object copied into that slot has not been processed yet, so the loop must look at the same slot again instead of moving on.

Sprites on the NES

The NES’s sprite memory, OAM, holds 64 sprites of 4 bytes each, and a game usually builds the next frame’s sprite list in a 256-byte page of RAM and copies it across with one write to $4014. That copy cannot be shortened: the NESdev Wiki describes it as writing the PPU’s OAM data port “256 times”, so all 64 entries are sent every time. A compacted object list still helps, because the game only builds entries for the objects in use. The rest of the page has to be filled with sprites moved off the bottom of the screen; NESdev’s advice is to “hide a sprite by moving it down offscreen, by writing any values between #$EF-#$FF” as its Y position.

When to pool

Modern engines

Pooling did not disappear with plentiful memory. Unity added a ready-made ObjectPool<T> to its scripting library in version 2021.1, describing object pooling as “a way to optimize your projects and lower the burden that is placed on the CPU when having to rapidly create and destroy new objects”.

See also

• Memory Management
• Game Loop
• Ring Buffer
• Sprite Multiplexing
• Nintendo Entertainment System
• Shoot ’em up