ADR 0033: Freeing at last use, in front of the collector

Status: accepted, 2026-10-13

Problem

Native code allocated everything on the conservative collector of ADR 0006 and collected only after max(256 MB, 4x live) of allocation (ADR 0008, speed first). Most benchmarks never reached a collection, so their peak memory was simply everything they had ever allocated: simd peaked at 273 MB against 40 MB in C++, app at 137 MB against 24 MB, churn at 268 MB for a program that keeps almost nothing. The goal for 0.8.2 was memory near C++ without giving up any speed.

Options

1. Lower the collection threshold. Cheap to build. Measured on two allocation-bound programs that keep old versions of a map or a tree alive (about 100 MB live): a 64 MB minimum made them 8% and 21% slower and saved nothing, because 4x live dominates; a factor of 2 instead of 4 cut their peaks from 370 MB and 330 MB to 254 MB and 208 MB and made them 36% and 52% slower. Rejected: the collector’s cost is tied to the live set, not to the garbage.
2. Full Perceus (Reinking, Xie, de Moura, Leijen, PLDI 2021): a reference count in every heap block, dup and drop inserted from the typed IR, reuse of dropped cells, borrowed parameters, no collector. This is what the design notes promised. It doesn’t fit SSPUR’s native representation as it is:
   • A Str is a (len, ptr) slice that may point into the middle of another string (split, words, trim, take all return slices), and list versions share one buffer (push grows in place, take and drop are views). Counting them means finding the block header from an interior pointer on every dup, which is a page-table lookup.
   • Every helper in the C runtime (about 3,000 lines) and every piece of code the 15 generator modules emit (maps, heaps, sets, show, compare, hash, encode, closures, views, GPU transfers, parallel workers, FFI) would need an ownership convention, and every one of them is a place to get a count wrong. A missed dup is a use after free.
   • Atomic counts would be needed for values shared with par tasks, threads and channels. The parts of Perceus that pay off here are its static ones: ownership, drop at last use, borrowed parameters and reuse of a dropped block by the next allocation of its size. The runtime count is the part that costs speed and correctness risk.
3. Static ownership in front of the collector (chosen). The compiler frees a block when it can prove the block has exactly one owner and that owner just made its last use. The count of every block it frees is known to be 1 at compile time, so no count is stored and no dup is ever emitted. Everything it can’t prove stays on the collector, which is unchanged and still the backstop, so a missed opportunity costs memory, never safety.

Decision

What gets freed

Only list buffers and string blocks, the blocks that dominate peak memory, and only shallowly: freeing a list buffer leaves its elements to the collector, unless the list provably owns them (below).

A trap, a raise, an early return or a self tail call skips the drops of that path, which leaves the blocks to the collector. Nothing is freed inside sys and bare code, __own reuse functions, parallel workers or vectorized loops.

Reuse

A freed small block goes onto a per-size-class LIFO list, and the allocator takes from it when its bump cursor runs out, so a block freed in one iteration is the one the next iteration gets, still in cache. The check sits after the bump test, so code that only allocates pays nothing. A freed large block (over 32 KB) that holds no pointers stays mapped in a cache of up to 64 MB and is handed back to the next allocation of the same page count, which saves the page faults of re-touching fresh memory (40 rounds of two 8 MB lists in simd). A request the cache can’t serve releases it. Pointer blocks are zeroed when freed, so stale words in a reused block can’t keep garbage alive through the conservative scan.

The runtime’s own temporaries are freed too: sort buffers, sort_by key pairs, counts hash tables, the old buffer when a string builder grows, and the scratch list split used to throw away.

The collector

Unchanged: same heap, same conservative scan, same pacing. Each collection first moves the free lists into the page free bits, so a freed block is never marked or handed out twice. SSPUR_GC_MIN_MB and SSPUR_GC_FACTOR change the pacing for anyone who wants to trade speed for memory; the defaults stay at 256 MB and 4x.

Threads

Frees do nothing while any par task, thread or parallel pipeline is running (ss_live or par_busy), so no count is ever shared between threads and nothing needs to be atomic. Values that cross threads escape anyway.

Cycles

A freed block can’t be part of a cycle: list buffers are freed shallowly, and the only deep case is a list of strings, which contain no pointers. Closures that capture themselves, var cells, effect handlers and generators (lowered to closures), actors, channels and in-place maps never get freed early; they all escape and stay on the collector, which handles cycles as before.

Modes

SSPUR_GC_STATS=1 now also prints how many blocks were freed at last use and how many were left for the collector when the program finished.

SSPUR_CFLAGS adds flags to every native build and to its cache key, so SSPUR_CFLAGS="-fsanitize=address,undefined" with DYLD_INSERT_LIBRARIES set to clang’s ASan runtime builds and runs native code under the sanitizers.

Verification

• cargo test --release with SSPUR_FILL_MS=5000 SSPUR_STRICT_NATIVE=1: 274 passed, 0 failed. tests/programs/drops.ssp is new: 27 tests aimed at the analysis (aliases, views, slices, closures, records, shadowing, early return, catch, list patterns, nested lists, var updates and push chains, deep lists with an escaping element, consumed keys in persistent and in-place maps, temporaries in interpolation, the Unicode fallback of the one-pass word count), which pass in the interpreter, natively, under SSPUR_MEM=check, and under SSPUR_GC_STRESS at 4 KB and 64 KB.
• The 199-program corpus: 199/199 identical, 270/270 functions native, also under SSPUR_MEM=check.
• sspur fuzz --gen 200 with seeds 2026 and 99: 0 findings each, also under SSPUR_MEM=check.
• AddressSanitizer and UndefinedBehaviorSanitizer (-fsanitize=address,undefined -fno-sanitize-recover=undefined): the suite programs, the benchmarks and the corpus give the same output as without sanitizers, with SSPUR_MEM=check (every freed block poisoned) and with reuse on. They found one old bug: the allocator’s fast path did arithmetic on a null cursor.
• Blocks left for the collector at exit: 0 for compute_big, churn, parallel and gpu. The others keep what is really shared or what the result points into: typical its tree nodes and records (sums are never freed early), strings_big the lowered text and the sorted list the printed result points into, app the generated CSV (the parsed sales hold slices of it) and the map, simd its two F64 inputs (read inside a lambda by dot and saxpy, so not borrowed). The collector releases them with the rest of the heap when native code returns.

Result

Apple M1 Pro, 2026-10-13, best of 5 alternating runs, wall time of the whole process, peak RSS (wait4). 0.8.1 is a build of the previous release; SSPUR_MEM=gc is this build with the frees turned off.

No benchmark got slower; simd and churn got faster because freed memory is reused instead of faulted in fresh. Peak memory is at C++’s level on simd and below it on typical, close on strings_big (29 against 23 MB, of which about 6 MB is SSPUR’s process), and still 1.7x on app and 3.3x on gpu:

• app holds the whole 10 MB CSV while 400,000 parsed sales (19 MB of records) hold slices of it; C++ copies the fields.
• gpu keeps about 52 MB of device buffers and Metal’s 14 MB, and builds each 4M-element input as a 32 MB host list before uploading it; the C++ version runs on the CPU.
• compute_big is at parity with C++ (1.01x), as 0.8.1 is when measured the same day; this change doesn’t touch scalar code, and in-process its four functions take 1.01s against C++’s 1.05s.

Two fixes outside the ownership analysis also show in SSPUR_MEM=gc: text.lower.words.counts (method calls without parentheses) now takes ADR 0008’s one-pass path instead of building the 2M-word list, and a string builder’s growth moved to a cold function, which made interpolation-heavy code about 7% faster.

On the two GC-bound programs used in option 1 (persistent maps and trees with old versions kept, no frees possible), 0.8.2 is 1% to 2% slower than 0.8.1; the hot code is identical, and the conservative scan finds slightly different stale words.

Not done

• Runtime reference counts (option 2). The workloads that still peak above C++ do so because of values that really are shared, or because of what the program keeps alive, not because of garbage the analysis missed.
• Freeing through records, tuples, sum values and maps. A record holding a list hands the list to the collector.
• Reusing a dropped cell directly for the next constructor of the same shape (Perceus reuse tokens). ADR 0008’s __own functions already do this for trees; for lists and strings the size-class free list gives the same effect one allocation later.
• Streaming dev_f32((0..n).map(f)) straight into the device buffer, which would remove gpu’s remaining transient host lists (done later, below).

Follow-up: app (fused folds)

The first idea for app was to copy small string slices into their own blocks when they are stored into a record, as the C++ version copies its fields, so the 10 MB CSV would have one owner and be freed at its last use. Measuring where the peak sat showed that it wouldn’t lower it: the peak is at the end of text.split("\n").map(parse), when the CSV, the 400,000 line slices (6 MB) and the 400,000 parsed sales (19 MB) are all alive, and the CSV has to stay alive while the lines are parsed whatever the sales hold. Copies would have added about 13 MB of small strings to that peak.

What the program doesn’t need is the list of sales: fold(empty_map(), add) reads each sale once. So xs.map(f).fold(init, g) and xs.filter(p).fold(init, g) now compile to one loop when:

• g is a top-level function or a lambda with no effects at all (no fail, no div) that captures no local, so nothing it does can be seen except its result and its traps;
• f is a top-level function or a lambda that assigns no captured variable and takes no &mut, so g and the initial value can’t see what it changes;
• the initial value is a literal, a name, empty_map(), or a list, tuple or plain record of those, which can’t trap.

The unfused order runs f on every element before g runs once, and that is only visible when g traps (an f that logs, raises or traps does so in the same order either way). The fused loop sets a handler around g; if g traps, it keeps the trap, stops folding, runs f on the rest of the elements (so a raise or trap in f wins, as it would have), and then reports the kept trap. tests/programs/pipelines.ssp and a CLI test compare every case with the interpreter: g trapping alone, g trapping before a trap or raise in f, a contract of a function g calls, an f that logs, and the filter form.

Interleaving f and g one element at a time made report 10% slower than the two loops (the parser’s and the map’s code and allocations evict each other), so the loop runs f on a block of up to 64 elements into a buffer on the stack, then folds the block. That is 3% faster than before.

The handler needs a setjmp, which on macOS also saves the signal mask with a system call (0.34 microseconds against 4 ns). Native code never changes the signal mask, so on macOS every setjmp and longjmp in generated code, including the entry of every call from the interpreter, now uses _setjmp and _longjmp.

The CSV is still left for the collector (the split lines point into it, so report doesn’t borrow its argument); it no longer matters for the peak, which is now the CSV and the line list while the fold runs.

Follow-up: gpu (uploads without host lists)

gpu peaked at 178 MB against C++’s 54 MB (the C++ version runs on the CPU). Measured piece by piece:

• Each 4M-element input was built as a 32 MB host list of F64 before dev_f32 converted it into the device buffer, and y.to_list.sum built another 32 MB list to sum it. The lists were freed at their last use, but the collector’s heap still reached 64 MB.
• The launch queue (ADR 0023) keeps a mask of flagged threads for each queued launch, 512 KB for 4M threads, and cleared each new mask before its first use, which made all of it resident: 100 queued saxpy launches held 51 MB of masks.

Three changes, none of which changes a result:

• dev_f32((a..b).map(f)), and the same for dev_f64, dev_i32, dev_u32 and dev_int, allocate the device buffer and write each f(i) into it, with the conversion the list path does. An element out of range for I32 or U32 is remembered and reported after the last f, which is where the unfused upload would have found it, so a trap in a later f still wins.
• d.to_list.sum sums the converted elements of the buffer in order, as the list’s sum does, without the list.
• A new Metal buffer is zero-filled, so a new mask is no longer cleared; it stays mostly untouched and out of memory.

These are peaks of sspur run, which then built the program on every run. Since ADR 0034 a plain sspur run reuses the built program, and gpu peaks at 92 MB, the figure bench/native/README.md gives; sspur run --no-cache still peaks at 97 MB (both measured again on 2026-10-16, three runs each).

What remains is what a GPU program keeps: 52 MB of device buffers (the C++ version keeps the same data in about 50 MB of vectors), 18 MB of host copies of the buffers that kernels write, which let the queue rerun a launch exactly on the CPU when a thread flags a trap or a subnormal (ADR 0020), and about 14 MB for Metal itself. Dropping the copies would need the kernels to prove they can’t flag, which they can’t for F32 arithmetic in general.