Storage & Garbage Collection

Abelson & Sussman · 1996 · SICP §5.3

Memory is a vector of pairs. Garbage collection reclaims unreachable storage. Stop-and-copy GC compacts live data by copying it to new space, then flipping.

Memory as vectors

At the lowest level, memory is a flat array of numbered slots. Lisp pairs become two parallel vectors: the-cars and the-cdrs. Index n across both vectors forms one pair. A pointer is just an index.

Scheme

; Memory as two parallel vectors: the-cars and the-cdrs.
; A cons cell at index i stores car in the-cars[i], cdr in the-cdrs[i].

(define memory-size 8)
(define the-cars (make-vector memory-size 'free))
(define the-cdrs (make-vector memory-size 'free))
(define free 0)

(define (my-cons car-val cdr-val)
  (let ((idx free))
    (set! free (+ free 1))
    (vector-set! the-cars idx car-val)
    (vector-set! the-cdrs idx cdr-val)
    idx))  ; return the pointer (index)

(define (my-car ptr) (vector-ref the-cars ptr))
(define (my-cdr ptr) (vector-ref the-cdrs ptr))

; Build the list (a b c)
(define p2 (my-cons 'c '()))
(define p1 (my-cons 'b p2))
(define p0 (my-cons 'a p1))

(display "list starts at index: ") (display p0) (newline)
(display "car[0]=") (display (my-car p0))
(display " car[1]=") (display (my-car p1))
(display " car[2]=") (display (my-car p2)) (newline)
(display "cdr[0]=") (display (my-cdr p0))
(display " cdr[1]=") (display (my-cdr p1))
(display " cdr[2]=") (display (my-cdr p2))

; Memory as two parallel vectors: the-cars and the-cdrs.
; A cons cell at index i stores car in the-cars[i], cdr in the-cdrs[i].

(define memory-size 8)
(define the-cars (make-vector memory-size 'free))
(define the-cdrs (make-vector memory-size 'free))
(define free 0)

(define (my-cons car-val cdr-val)
  (let ((idx free))
    (set! free (+ free 1))
    (vector-set! the-cars idx car-val)
    (vector-set! the-cdrs idx cdr-val)
    idx))  ; return the pointer (index)

(define (my-car ptr) (vector-ref the-cars ptr))
(define (my-cdr ptr) (vector-ref the-cdrs ptr))

; Build the list (a b c)
(define p2 (my-cons 'c '()))
(define p1 (my-cons 'b p2))
(define p0 (my-cons 'a p1))

(display "list starts at index: ") (display p0) (newline)
(display "car[0]=") (display (my-car p0))
(display " car[1]=") (display (my-car p1))
(display " car[2]=") (display (my-car p2)) (newline)
(display "cdr[0]=") (display (my-cdr p0))
(display " cdr[1]=") (display (my-cdr p1))
(display " cdr[2]=") (display (my-cdr p2))

Representing lists using vectors

A list is a chain of pairs where each cdr points to the next pair (or to the empty list). Walking the list means following cdr pointers through the vector. Linked lists work the same way in hardware: each “next” field is a memory address.

Scheme

; Walk a list stored in vector memory.

(define the-cars (make-vector 10 'free))
(define the-cdrs (make-vector 10 'free))
(define free 0)

(define (alloc! car-val cdr-val)
  (let ((i free))
    (set! free (+ free 1))
    (vector-set! the-cars i car-val)
    (vector-set! the-cdrs i cdr-val)
    i))

; Build (10 20 30 40)
(define p3 (alloc! 40 'nil))
(define p2 (alloc! 30 p3))
(define p1 (alloc! 20 p2))
(define p0 (alloc! 10 p1))

; Walk the list following cdr pointers
(define (walk ptr)
  (if (eq? ptr 'nil)
      (display "nil")
      (begin
        (display (vector-ref the-cars ptr))
        (display " -> ")
        (walk (vector-ref the-cdrs ptr)))))

(display "list: ") (walk p0) (newline)

; Show the raw memory layout
(display "index: ")
(let loop ((i 0))
  (if (< i free)
      (begin (display i) (display "  ") (loop (+ i 1)))))
(newline)
(display "cars:  ")
(let loop ((i 0))
  (if (< i free)
      (begin (display (vector-ref the-cars i)) (display " ") (loop (+ i 1)))))

Stop-and-copy garbage collector

When free memory runs out, the collector copies all reachable data from “from-space” to “to-space,” then flips. Dead data stays behind. The copy is contiguous, so fragmentation vanishes. Cost scales with live data, not total memory.

Scheme

; Stop-and-copy GC simulation.
; Two half-spaces of size 5. Copy live data, flip spaces.

(define SIZE 5)
(define from-cars (make-vector SIZE 'free))
(define from-cdrs (make-vector SIZE 'free))
(define to-cars   (make-vector SIZE 'free))
(define to-cdrs   (make-vector SIZE 'free))
(define free 0)
(define scan 0)

(define (alloc! car-val cdr-val)
  (let ((i free))
    (set! free (+ free 1))
    (vector-set! from-cars i car-val)
    (vector-set! from-cdrs i cdr-val)
    i))

; Allocate 5 cells, making some garbage
(define garbage1 (alloc! 'dead1 'nil))
(define live1    (alloc! 'alive1 'nil))
(define garbage2 (alloc! 'dead2 'nil))
(define live2    (alloc! 'alive2 live1))
(define garbage3 (alloc! 'dead3 'nil))

(display "Before GC — from-space full (") (display free) (display "/") (display SIZE) (display ")") (newline)

; Roots: only live2 is reachable (which points to live1)
; Copy root and everything it reaches
(set! free 0)
(set! scan 0)

(define (copy-cell old-idx)
  (let ((new-idx free))
    (set! free (+ free 1))
    (vector-set! to-cars new-idx (vector-ref from-cars old-idx))
    (vector-set! to-cdrs new-idx (vector-ref from-cdrs old-idx))
    ; Leave forwarding pointer
    (vector-set! from-cars old-idx 'forwarded)
    (vector-set! from-cdrs old-idx new-idx)
    new-idx))

; Copy root
(define new-root (copy-cell live2))
; Scan: process cdr of copied cell
(let ((cdr-val (vector-ref to-cdrs scan)))
  (if (number? cdr-val)
      (let ((new-cdr (copy-cell cdr-val)))
        (vector-set! to-cdrs scan new-cdr))))

(display "After GC — to-space has ") (display free) (display " live cells") (newline)
(display "to-cars: ")
(let loop ((i 0))
  (if (< i free)
      (begin (display (vector-ref to-cars i)) (display " ") (loop (+ i 1)))))
(newline)
(display "3 dead cells reclaimed")

; Stop-and-copy GC simulation.
; Two half-spaces of size 5. Copy live data, flip spaces.

(define SIZE 5)
(define from-cars (make-vector SIZE 'free))
(define from-cdrs (make-vector SIZE 'free))
(define to-cars   (make-vector SIZE 'free))
(define to-cdrs   (make-vector SIZE 'free))
(define free 0)
(define scan 0)

(define (alloc! car-val cdr-val)
  (let ((i free))
    (set! free (+ free 1))
    (vector-set! from-cars i car-val)
    (vector-set! from-cdrs i cdr-val)
    i))

; Allocate 5 cells, making some garbage
(define garbage1 (alloc! 'dead1 'nil))
(define live1    (alloc! 'alive1 'nil))
(define garbage2 (alloc! 'dead2 'nil))
(define live2    (alloc! 'alive2 live1))
(define garbage3 (alloc! 'dead3 'nil))

(display "Before GC — from-space full (") (display free) (display "/") (display SIZE) (display ")") (newline)

; Roots: only live2 is reachable (which points to live1)
; Copy root and everything it reaches
(set! free 0)
(set! scan 0)

(define (copy-cell old-idx)
  (let ((new-idx free))
    (set! free (+ free 1))
    (vector-set! to-cars new-idx (vector-ref from-cars old-idx))
    (vector-set! to-cdrs new-idx (vector-ref from-cdrs old-idx))
    ; Leave forwarding pointer
    (vector-set! from-cars old-idx 'forwarded)
    (vector-set! from-cdrs old-idx new-idx)
    new-idx))

; Copy root
(define new-root (copy-cell live2))
; Scan: process cdr of copied cell
(let ((cdr-val (vector-ref to-cdrs scan)))
  (if (number? cdr-val)
      (let ((new-cdr (copy-cell cdr-val)))
        (vector-set! to-cdrs scan new-cdr))))

(display "After GC — to-space has ") (display free) (display " live cells") (newline)
(display "to-cars: ")
(let loop ((i 0))
  (if (< i free)
      (begin (display (vector-ref to-cars i)) (display " ") (loop (+ i 1)))))
(newline)
(display "3 dead cells reclaimed")

Python

# Stop-and-copy GC simulation
SIZE = 5
from_cars = ['free'] * SIZE
from_cdrs = ['free'] * SIZE
to_cars = ['free'] * SIZE
to_cdrs = ['free'] * SIZE

# Allocate 5 cells
cells = [('dead1','nil'), ('alive1','nil'), ('dead2','nil'),
         ('alive2', 1),   ('dead3','nil')]
for i, (car, cdr) in enumerate(cells):
    from_cars[i] = car
    from_cdrs[i] = cdr

print(f"Before GC — from-space full (5/{SIZE})")

# Root is index 3 (alive2 -> alive1)
free = 0
forwarded = {}

def copy_cell(old_idx):
    global free
    if old_idx in forwarded:
        return forwarded[old_idx]
    new_idx = free
    free += 1
    to_cars[new_idx] = from_cars[old_idx]
    to_cdrs[new_idx] = from_cdrs[old_idx]
    forwarded[old_idx] = new_idx
    # Recursively copy cdr if it's a pointer
    if isinstance(to_cdrs[new_idx], int):
        to_cdrs[new_idx] = copy_cell(to_cdrs[new_idx])
    return new_idx

new_root = copy_cell(3)
print(f"After GC — to-space has {free} live cells")
print(f"to_cars: {to_cars[:free]}")
print(f"3 dead cells reclaimed")

# Stop-and-copy GC simulation
SIZE = 5
from_cars = ['free'] * SIZE
from_cdrs = ['free'] * SIZE
to_cars = ['free'] * SIZE
to_cdrs = ['free'] * SIZE

# Allocate 5 cells
cells = [('dead1','nil'), ('alive1','nil'), ('dead2','nil'),
         ('alive2', 1),   ('dead3','nil')]
for i, (car, cdr) in enumerate(cells):
    from_cars[i] = car
    from_cdrs[i] = cdr

print(f"Before GC — from-space full (5/{SIZE})")

# Root is index 3 (alive2 -> alive1)
free = 0
forwarded = {}

def copy_cell(old_idx):
    global free
    if old_idx in forwarded:
        return forwarded[old_idx]
    new_idx = free
    free += 1
    to_cars[new_idx] = from_cars[old_idx]
    to_cdrs[new_idx] = from_cdrs[old_idx]
    forwarded[old_idx] = new_idx
    # Recursively copy cdr if it's a pointer
    if isinstance(to_cdrs[new_idx], int):
        to_cdrs[new_idx] = copy_cell(to_cdrs[new_idx])
    return new_idx

new_root = copy_cell(3)
print(f"After GC — to-space has {free} live cells")
print(f"to_cars: {to_cars[:free]}")
print(f"3 dead cells reclaimed")

The broken-heart algorithm

When the collector copies a cell to new space, it leaves a broken heart (forwarding pointer) in old space. If it encounters the same cell again via another reference, it follows the forwarding pointer instead of copying twice. This handles shared structure and cycles.

Scheme

; Broken-heart forwarding: shared structure handled correctly.

(define from-cars (make-vector 6 'free))
(define from-cdrs (make-vector 6 'free))
(define to-cars   (make-vector 6 'free))
(define to-cdrs   (make-vector 6 'free))
(define free 0)
(define forwarding (make-vector 6 -1))

(define (alloc! car-val cdr-val)
  (let ((i free))
    (set! free (+ free 1))
    (vector-set! from-cars i car-val)
    (vector-set! from-cdrs i cdr-val)
    i))

; Shared structure: both cell 1 and cell 2 point to cell 0
(define shared (alloc! 'X 'nil))      ; index 0
(define a      (alloc! 'A shared))    ; index 1, cdr -> 0
(define b      (alloc! 'B shared))    ; index 2, cdr -> 0

(display "Before: a=(A . 0) b=(B . 0) — both share cell 0") (newline)

(set! free 0)

(define (relocate old)
  (if (eq? (vector-ref from-cars old) 'broken-heart)
      (begin
        (display "  broken heart at ") (display old)
        (display " -> forwarded to ") (display (vector-ref from-cdrs old)) (newline)
        (vector-ref from-cdrs old))
      (let ((new-idx free))
        (set! free (+ free 1))
        (vector-set! to-cars new-idx (vector-ref from-cars old))
        (vector-set! to-cdrs new-idx (vector-ref from-cdrs old))
        ; Leave broken heart
        (vector-set! from-cars old 'broken-heart)
        (vector-set! from-cdrs old new-idx)
        (display "  copied ") (display old) (display " -> ") (display new-idx) (newline)
        new-idx)))

(display "Copying a:") (newline)
(define new-a (relocate a))
(display "Copying shared (via a's cdr):") (newline)
(define new-shared-1 (relocate shared))
(vector-set! to-cdrs new-a new-shared-1)

(display "Copying b:") (newline)
(define new-b (relocate b))
(display "Copying shared again (via b's cdr):") (newline)
(define new-shared-2 (relocate shared))
(vector-set! to-cdrs new-b new-shared-2)

(newline)
(display "Shared cell copied only once. ")
(display "new-shared-1=") (display new-shared-1)
(display " new-shared-2=") (display new-shared-2)

; Broken-heart forwarding: shared structure handled correctly.

(define from-cars (make-vector 6 'free))
(define from-cdrs (make-vector 6 'free))
(define to-cars   (make-vector 6 'free))
(define to-cdrs   (make-vector 6 'free))
(define free 0)
(define forwarding (make-vector 6 -1))

(define (alloc! car-val cdr-val)
  (let ((i free))
    (set! free (+ free 1))
    (vector-set! from-cars i car-val)
    (vector-set! from-cdrs i cdr-val)
    i))

; Shared structure: both cell 1 and cell 2 point to cell 0
(define shared (alloc! 'X 'nil))      ; index 0
(define a      (alloc! 'A shared))    ; index 1, cdr -> 0
(define b      (alloc! 'B shared))    ; index 2, cdr -> 0

(display "Before: a=(A . 0) b=(B . 0) — both share cell 0") (newline)

(set! free 0)

(define (relocate old)
  (if (eq? (vector-ref from-cars old) 'broken-heart)
      (begin
        (display "  broken heart at ") (display old)
        (display " -> forwarded to ") (display (vector-ref from-cdrs old)) (newline)
        (vector-ref from-cdrs old))
      (let ((new-idx free))
        (set! free (+ free 1))
        (vector-set! to-cars new-idx (vector-ref from-cars old))
        (vector-set! to-cdrs new-idx (vector-ref from-cdrs old))
        ; Leave broken heart
        (vector-set! from-cars old 'broken-heart)
        (vector-set! from-cdrs old new-idx)
        (display "  copied ") (display old) (display " -> ") (display new-idx) (newline)
        new-idx)))

(display "Copying a:") (newline)
(define new-a (relocate a))
(display "Copying shared (via a's cdr):") (newline)
(define new-shared-1 (relocate shared))
(vector-set! to-cdrs new-a new-shared-1)

(display "Copying b:") (newline)
(define new-b (relocate b))
(display "Copying shared again (via b's cdr):") (newline)
(define new-shared-2 (relocate shared))
(vector-set! to-cdrs new-b new-shared-2)

(newline)
(display "Shared cell copied only once. ")
(display "new-shared-1=") (display new-shared-1)
(display " new-shared-2=") (display new-shared-2)

Free list vs compacting collection

An alternative to stop-and-copy is a free list: link all unused cells into a chain, allocate from the head. Simpler, but fragmentation accumulates. Stop-and-copy trades the cost of moving live data for contiguous allocation: every alloc is a pointer bump.

Scheme

; Free-list allocator: simple but fragmenting.

(define SIZE 8)
(define memory (make-vector SIZE 'free))

; Build free list: 0 -> 1 -> 2 -> ... -> 7 -> nil
(define free-list
  (let loop ((i (- SIZE 1)) (next 'nil))
    (if (< i 0) next
        (loop (- i 1) (cons i next)))))

(define (alloc-free-list! val)
  (if (null? free-list)
      (error "Out of memory!")
      (let ((idx (car free-list)))
        (set! free-list (cdr free-list))
        (vector-set! memory idx val)
        idx)))

(define (dealloc! idx)
  (vector-set! memory idx 'free)
  (set! free-list (cons idx free-list)))

(define a (alloc-free-list! 'A))
(define b (alloc-free-list! 'B))
(define c (alloc-free-list! 'C))
(display "Allocated A=") (display a)
(display " B=") (display b)
(display " C=") (display c) (newline)

; Free B — creates a hole
(dealloc! b)
(display "After freeing B, memory: ")
(let loop ((i 0))
  (if (< i SIZE)
      (begin (display (vector-ref memory i)) (display " ")
             (loop (+ i 1)))))
(newline)
(display "Free list head: ") (display (car free-list))
(display " (fragmented!)")

; Free-list allocator: simple but fragmenting.

(define SIZE 8)
(define memory (make-vector SIZE 'free))

; Build free list: 0 -> 1 -> 2 -> ... -> 7 -> nil
(define free-list
  (let loop ((i (- SIZE 1)) (next 'nil))
    (if (< i 0) next
        (loop (- i 1) (cons i next)))))

(define (alloc-free-list! val)
  (if (null? free-list)
      (error "Out of memory!")
      (let ((idx (car free-list)))
        (set! free-list (cdr free-list))
        (vector-set! memory idx val)
        idx)))

(define (dealloc! idx)
  (vector-set! memory idx 'free)
  (set! free-list (cons idx free-list)))

(define a (alloc-free-list! 'A))
(define b (alloc-free-list! 'B))
(define c (alloc-free-list! 'C))
(display "Allocated A=") (display a)
(display " B=") (display b)
(display " C=") (display c) (newline)

; Free B — creates a hole
(dealloc! b)
(display "After freeing B, memory: ")
(let loop ((i 0))
  (if (< i SIZE)
      (begin (display (vector-ref memory i)) (display " ")
             (loop (+ i 1)))))
(newline)
(display "Free list head: ") (display (car free-list))
(display " (fragmented!)")

Notation reference

Scheme / SICP	Python	Meaning
(cons a b)	(a, b) or [a, b]	Allocate a pair
(car p) / (cdr p)	p[0] / p[1]	First / second element of pair
(vector-ref v i)	v[i]	Read from vector/array
(vector-set! v i x)	v[i] = x	Write to vector/array
broken-heart	forwarding dict	Marker: cell already copied
from-space / to-space	from_* / to_*	Two memory half-spaces for GC

Translation notes

Python hides all of this behind the runtime. sys.getrefcount() exposes reference counts; gc.collect() triggers the cycle collector. CPython uses reference counting (immediate collection) plus a generational collector for cycles, not stop-and-copy. The SICP model is closer to what the JVM or Go runtime does with copying/compacting collectors. The vector representation of pairs maps directly to struct-of-arrays layouts in systems programming.

Neighbors