# ROUND ANLEGEWEG -- the fast path of the allocation Branch `anlegeweg`, worktree `/root/firn-anlegeweg`, forked from `main` (`4af14c3ed`). 04.09.2026. The assignment came out of round TEMPO2, which had measured the one number everything else hangs off: ``` allocate one object in the heap ...... 161 ns call an empty Firn function .......... 3 ns read one column of the syntax tree ... 7 ns look up a name ....................... 25 ns ``` and named the consequence: *"161 ns down to 10 to 20 ns would be a factor of 2 to 3 on the WHOLE machine on its own."* What this round delivers: ``` 1. THE NUMBER IS TAKEN APART. Five ablation steps, each one measured on its own. It was never the collecting; it was three dozen FUNCTION CALLS on the way, and a size class that the runtime recomputed on every call although the CALL SITE has known it all along. 2. THE FAST PATH IS BUILT, AND IT IS INLINED AT THE CALL SITE -- in BOTH compilers (firnc0 in Rust, firnc1 in Firn). allocate 24 octets ....... 153.9 ns -> 54.9 ns 2.80 x allocate 56 octets ....... 190.4 ns -> 74.5 ns 2.55 x one JS environment ....... 566.9 ns -> 210.9 ns 2.69 x with 8192 objects alive .. 179.1 ns -> 84.7 ns 2.11 x 3. AND THE FINDING THIS ROUND DID NOT GO LOOKING FOR, WHICH TURNED OUT TO BE WORTH MORE THAN THE ONE IT DID: an address that is NOT in the heap used to cost the collector a walk over the whole chunk list -- 279 ns. And that is the commonest case there is, because the CONSERVATIVE stack scan hands every word of the stack to `__gc_mark`. __gc_mark on a real pointer ...... 29 ns -> 27 ns __gc_mark on a non-pointer ....... 279 ns -> 5 ns gc_soak throughput ............... 1.30 x gc_soak longest pause ........... 27.5 ms -> 10.0 ms 4. AN HONEST ANSWER TO "A FACTOR OF 2 TO 3 ON THE WHOLE MACHINE": NO. Measured end to end: twelve JS benches, geometric mean ...... 1.225 x page build xoffi.ai .................... 740.8 -> 727.2 ms image on all five pages ................ BIT-IDENTICAL Why the allocation got 2.8 times faster and JavaScript only 1.2 times, and what that means for the road map, is section 10 -- with the numbers that carry the decision. ``` --- ## 0. The measuring bench ``` Host AMD EPYC 7571, 20 cores visible, LXC container foreign load during the measurements, which is why every number that matters is BEFORE against AFTER in the same session, interleaved, best of three Compiler firnc0 (Rust) and firnc1 (self-hosted), default build level `dev-fast` -- the one Certus is built with Firn worktree /root/firn-anlegeweg, from 4af14c3ed Certus /root/certus-tempo2, vendor/firn/baum at a58d17dd5; the same two patches applied there for the A/B Benches tools/anlegeweg/mikro.fi (the elementary operations) tools/anlegeweg/reject.fi (the cost of a non-pointer) tools/gc_soak/run.sh (endurance, heap, pauses) tools/tempo2/jsbench.py (twelve JS benches) tools/tempo2/messen.py (page build, five pages) tools/tempo2/mikro_main.fi (the same items inside Certus) ``` **The numbers are RAW**, exactly as in TEMPO2: the idle loop is not subtracted, so they are directly comparable with that report. What the loop itself costs stands in item 0 (2.7 ns). --- # PART 1 -- WHAT THE 154 NANOSECONDS WERE MADE OF ## 1. The elementary operations, one by one `tools/anlegeweg/mikro.fi`, five million rounds per item, best of three: ``` before after 0 idle (the loop alone) 2.706 ns 2.686 ns 1 call an empty function 3.340 ns 3.247 ns 2 __gc_ld64 (call + load) 3.048 ns 3.044 ns 3 read a word directly 2.680 ns 2.712 ns 4 __gc_st64 (call + store) 4.762 ns 4.725 ns 5 write a word directly 0.669 ns 0.670 ns 6 __gc_class_for(24) 5.222 ns 3.444 ns 6b __gc_class_for(200) 25.529 ns 3.093 ns 7 __gc_classes_bytes(0) 3.046 ns 3.353 ns 8 __gc_diag_inc 7.213 ns 7.450 ns 9 null 24 octets through __gc_st64 14.227 ns 14.384 ns 10 null the same 24 octets directly 4.502 ns 4.362 ns 11 __gc_now_ns() 395.519 ns 391.212 ns 12 ALLOCATE 24 octets 153.879 ns 54.900 ns 2.80 x 13 ALLOCATE 56 octets 190.384 ns 74.527 ns 2.55 x 14 four objects (one environment) 566.880 ns 210.928 ns 2.69 x 15 allocate with 8192 alive 179.064 ns 84.693 ns 2.11 x 16 __gc_alloc_raw(1, 24) directly 142.329 ns 63.017 ns 2.26 x ``` Three of these lines are the whole diagnosis: * **line 2 against line 3**: `__gc_ld64` is a FUNCTION. Every single word access inside the collector was a call. On its own that is 0.4 ns in a loop with plenty of room for overlap -- in a chain of thirty dependent ones it is not. * **line 6b**: the size class was a LOOP that CALLED `__gc_classes_bytes` once per round. For 200 octets that is six calls: 25.5 ns for a question whose answer is four comparisons. * **line 11**: `__gc_now_ns()` is a real system call, 395 ns. It is read only when there is collector work at all -- but that is worth knowing before anyone puts it anywhere else. ## 2. The ablation: five steps, each one measured The same bench, but `lib/gc/gc.fi` changed one step at a time and the compiler rebuilt each time (`tools/anlegeweg/` plus the ablation script). Item 12, with the collector running and with the collection limit lifted: ``` step with GC unfettered 0 the state before this round 144.4 ns 146.4 ns A size class as a binary search, no call per round 140.5 ns 131.3 ns B the word accesses inside the allocation path as plain memory ops instead of __gc_ld64 / __gc_st64 calls 103.7 ns 96.7 ns C diagnostic counter and the nulling loop likewise 106.9 ns 99.5 ns D the FAST PATH: one function that asks the ordinary case in one go and then does the whole allocation itself 68.2 ns 65.1 ns E D plus a BUMP REGION for fresh chunks 80.6 ns 53.6 ns ``` **Read the table like this.** The 154 ns were, in round figures: | item | ns | |---|---| | the size class through a loop with a call per round | 4 (24 octets), 22 (200 octets) | | roughly thirty `__gc_ld64`/`__gc_st64` CALLS on the way | 37 | | the long path itself: phase checks, `__gc_alloc_in`/`_out`, `__gc_get_block`, `S_BLOCKGROESSE`, the call overhead of all of it | 36 | | the allocation proper: unhook a block, null the payload, write the header, keep three counters | ~46 | | LOWERING the allocation: error union, `catch`, the null check at the call site | ~9 | Not one of these items is the collector. Step D is measured with the collector on and off and the difference is 3 ns -- **it was never the marking and never the sweeping.** ## 3. What was measured and then THROWN AWAY: the bump region A bump region is what the literature puts first, and it is what a TLAB in HotSpot, an `mcache` span in Go and the nursery in SBCL all are: a fresh chunk is not hung into the free list block by block but noted as one contiguous region, and allocating is "load the cursor, add, compare against the bound, write it back". Its blocks come straight from `mmap`, so they are already zero and **the nulling of the payload falls away entirely**. It was built (step E) and it was measured, interleaved, best of five: ``` free list only with bump region allocate 24 octets, GC on 74.6 ns 81.1 ns E/D 1.087 allocate 56 octets, GC on 102.0 ns 107.1 ns E/D 1.050 four objects, GC on 266.8 ns 268.3 ns E/D 1.006 allocate with 8192 alive 104.1 ns 103.9 ns E/D 0.998 allocate 24 octets, GC OFF 65.1 ns 53.6 ns E/D 0.823 chunks created over the run 1613 2448 heap 1310720 1835008 ``` **Verdict: dropped.** The bump region wins exactly where nothing is ever collected -- and that is not a case a real program is ever in. As soon as the collector runs, every allocation comes out of a RECYCLED block, the free list is the source, the bump region is empty and unused, and the only thing left of it is a heap 40 % bigger (7 chunks instead of 5) and 50 % more chunks created. The number stands here so that nobody spends a second round on it. *(What WOULD pay off is a sweep that hands its dead blocks back as contiguous regions instead of as a linked list -- Immix does that. That is its own round; it changes the sweep, not the allocation.)* --- # PART 2 -- THE FAST PATH, AND WHERE IT STANDS ## 4. In the runtime: `__gc_alloc_fast` `lib/gc/gc.fi` gets one function that asks the ordinary case in one go. Every one of the five conditions is the same one the long path checks; not one of them is skipped: ``` S_INIT == 1 ready (0 = gc_init() missing, 2 = in a finalizer) S_MULTI == 0 one thread -- otherwise safepoint, lock, per thread free lists: all of it untouched S_PHASE == 0 no cycle running -- otherwise the object has to become grey and go onto the mark stack S_SINCE < S_LIMIT the allocation limit, the trigger of the cycle class < CLASSES the size has a size class free list of that class not empty ``` After that: unhook the block, null the payload, write the header (type id, the current white, serial number), keep the three counters. All of it with plain memory accesses, and the address arithmetic with `+%` -- these are addresses inside the state block and inside a chunk, an overflow is impossible there by construction, and the check on every single one of them was a measurable part of what made the path slow. `__gc_class_for` and `__gc_classes_bytes` became binary searches out of the same table (`6b`: 25.5 ns -> 3.1 ns). `__gc_klasse_bytes` gives class and block size back in ONE call. ## 5. At the call site: the compiler folds it into constants That is the point of the round. The runtime has to work out at every call what the CALL SITE has known all along -- which size class the object belongs to and how big its block is. So the fast path now stands AT the call site, in both compilers (`compiler/src/gc_lower.rs`, `lib/firnc1/lower.fi`), with `class` and `step` folded into constants and the nulling of the payload unrolled. What the code generator makes of `gc Cell { a: i, b: 0, c: 0 }` (24 octets, class 0, block 48) at the DEFAULT build level: ```asm lea rax, [rip + .L__gc_state] mov r9, qword ptr [r8+8] ; S_INIT cmp r9, 1 jne slow mov r10, qword ptr [r8+1992] ; S_MULTI cmp r10, 0 jne slow mov r10, qword ptr [r8+320] ; S_PHASE cmp r10, 0 jne slow mov r10, qword ptr [r8+96] ; S_LIMIT lea r11, [r8+88] ; S_SINCE mov rdx, qword ptr [r11] cmp rdx, r10 jae slow lea r10, [r8+168] ; S_FREE + 0*8 mov rdi, qword ptr [r10] cmp rdi, 0 je slow lea rsi, [rdi+16] ; the payload mov r14, qword ptr [rsi] ; unhook mov qword ptr [r10], r14 mov qword ptr [rsi], 0 ; null, unrolled mov qword ptr [rsi+8], 0 mov qword ptr [rsi+16], 0 lea r10, [r8+104] ; S_SERIES mov r14, qword ptr [r10] lea r15, [r14+1] mov qword ptr [r10], r15 mov dword ptr [rdi], 1 ; the type id, a constant mov r14d, dword ptr [r8+360] ; the current white mov dword ptr [rdi+4], r14d mov qword ptr [rdi+8], r15 ; the serial number lea r10, [rdx+48] ; S_SINCE += 48 mov qword ptr [r11], r10 ... ; S_TOTAL, S_D_ALLOK ``` **41 instructions, no call, every offset a constant.** Before this round the same source line was one `call __gc_alloc_raw`, and behind it some 140 instructions plus three dozen further calls. The state block offsets are now a CONTRACT between three files. They are not written down twice on trust: the test `gc::tests::offsets_match_the_runtime` reads them back out of the embedded runtime text (`include_str!`) and turns red the moment one of them moves. **Code size is not an argument here, and that was checked and not guessed:** Certus has 105 `gc C{ }` sites in all of `lib/`, the Firn tree 96. A hundred sites of forty instructions is 20 KiB. ## 6. Why it is not 10 to 20 ns 54.9 ns for 41 instructions is 2.7 cycles per instruction. The same program at `--opt-level=release-safe` needs **33.0 ns** for the same line. The remaining gap is therefore not the allocator any more; it is the code generator at the default level -- locals live in memory, an address with two uses becomes a `lea` of its own instead of an addressing mode. That is a finding for a round about the code generator, and it is a number and not an opinion: 54.9 against 33.0. --- # PART 3 -- TAGGED IMMEDIATES, AND WHAT CAME OUT OF LOOKING ## 7. The claim in `lib/js/val.fi`, checked The head of `lib/js/val.fi` says, about why Certus has no tagged word: > *"A packed small integer would be harmless in the other direction > (`__gc_mark` finds no block for it), but the pointer case is fatal."* **About correctness the sentence is right.** `__gc_mark` calls `__gc_block_of`, that finds no block for a value which is not in the heap, and the value is ignored. Checked, and it holds. **About the price the sentence is wrong, and badly.** `__gc_block_of` WALKS THE CHUNK LIST. Its one entry cache hits for a real pointer almost always; for something that is not in the heap it NEVER hits, so every such value costs a full walk over every chunk of the heap. `tools/anlegeweg/reject.fi`, on a heap of 9.7 MiB (200,000 live objects, some 37 chunks): ``` before after __gc_mark on a real pointer 29 ns 27 ns __gc_mark on an immediate 279 ns 5 ns __gc_block_of on an immediate 276 ns 3 ns ``` ## 8. And that is not a corner case, it is the common one The collector scans the stack CONSERVATIVELY (SPEC 3.5.3). It hands EVERY word of the stack and every saved register to `__gc_mark`, and the fewest of them are pointers. Every one of those words was paying for a walk over the whole chunk list. The remedy is four instructions: the state block keeps the LOWEST and the HIGHEST address the heap has ever occupied, and `__gc_block_of` and `__gc_chunk_of` refuse everything outside them at once. The pair is only ever widened, never narrowed -- a chunk handed back to the operating system leaves the bounds where they are. The answer stays CORRECT (an address inside the bounds is still looked for properly), it is only a little less sharp; narrowing it would need a walk of the list at exactly the moment that is meant to become cheap. What it is worth, on the collector's own endurance run (`tools/gc_soak/run.sh`, mode 0, 90 s budget, changing object sizes): ``` before after rounds in 90 s 558 976 727 744 1.302 x octets through the allocator 1.9 GiB 2.3 GiB collections 490 637 heap / live, median 2.61 x 2.56 x longest pause 27.54 ms 9.98 ms 2.76 x RSS maximum 42 940 KiB 43 316 KiB verdict bounded bounded ``` **A third more throughput and the worst pause cut to a third** -- out of a finding that came from a question about tagged immediates. ## 9. What tagged immediates would still be worth: measured, and it is little The rejection makes them SAFE and CHEAP for the collector. But before 31,500 lines of `lib/js` get rewritten, the question is what is at the end of it. Two measurements say: not much. **First**, `realm_num` in Certus already keeps a cache for the small integers 0..1024 -- a number out of that range costs a heap object, one inside it costs a lookup. The same bench with numbers inside and outside that window (`jsrun` after this round, 200,000 rounds): ``` arith, inside the cache 235 598 op/s arith, outside 202 800 op/s 1.16 x counter, inside the cache 270 679 op/s counter, outside 248 116 op/s 1.09 x ``` **Second**, the reason: one round of `while (i < N) { s = i & 1023; i = i + 1; }` costs **3.7 microseconds** in this interpreter. TEMPO2 measured 264 to 1266 ns per node of the syntax tree. Against that, a number -- 104 ns to allocate, 37 ns to fetch from the cache, about 2 ns as an immediate -- is a few per cent, not a factor. **Conclusion, against the road map of TEMPO2:** item 2 (immediates) and item 3 (bytecode) should swap places. As long as one loop round costs 3.7 microseconds, immediates are polishing. The tree walk is the thing. --- # PART 4 -- THE RESULT ## 10. (a) The allocation path ``` Firn, tools/anlegeweg/mikro.fi, default build level allocate 24 octets 153.9 ns -> 54.9 ns 2.80 x allocate 56 octets 190.4 ns -> 74.5 ns 2.55 x four objects (one env) 566.9 ns -> 210.9 ns 2.69 x with 8192 alive 179.1 ns -> 84.7 ns 2.11 x __gc_alloc_raw directly 142.3 ns -> 63.0 ns 2.26 x Certus, tools/tempo2/mikro_main.fi (the same items TEMPO2 measured) allocate a number 165 ns -> 104 ns 1.59 x allocate an environment 635 ns -> 245 ns 2.59 x fetch a number from the cache 39 ns -> 37 ns look up a name 24 ns -> 26 ns call an empty function 4 ns -> 4 ns ``` `realm_num` gains less than the raw allocation because most of what it does is not allocating: three floating point comparisons, `math_bits`, a `u64`/`f64` round trip with checked casts, and two levels of error union. ## 11. (b) The twelve JS benches `tools/tempo2/jsbench.py`, N = 200,000, best of four runs before and two after per version, Certus against Certus: ``` Bank before +fast path x +rejection x leere_schleife 418 567 448 218 1.071 431 032 1.030 arith 189 981 207 102 1.090 198 030 1.042 funktionsaufruf 106 947 123 514 1.155 145 251 1.358 eigenschaft_lesen 474 867 505 182 1.064 502 800 1.059 eigenschaft_schreiben 324 283 343 953 1.061 356 449 1.099 methodenaufruf 137 241 152 199 1.109 169 465 1.235 feld_index 198 427 205 209 1.034 216 384 1.090 prototypkette 148 299 163 387 1.102 185 074 1.248 zeichenketten 249 368 261 821 1.050 277 175 1.112 objekt_anlegen 107 635 124 515 1.157 141 479 1.314 closure 102 071 118 331 1.159 143 588 1.407 fibonacci 46 825 51 672 1.104 91 627 1.957 ------------------------------------------------------------------------ geometric mean 1.095 1.225 ``` The fast rejection is worth more than the fast path here, and the reason is the same in both cases: `fibonacci` and `closure` build the deepest stacks, and it is the CONSERVATIVE STACK SCAN that pays for every word. ## 12. (c) The page build `tools/tempo2/messen.py`, growth per copy, 412 x 915, three runs: ``` page before after image xoffi.ai 740.8 ms 727.2 ms same SHA-256 xoffi.ai/100 373.3 ms 369.0 ms same SHA-256 news.ycombinator 224.4 ms 177.4 ms same SHA-256 de.wikipedia 69.3 ms 63.7 ms same SHA-256 example.com 4.4 ms 4.7 ms same SHA-256 ``` Per phase on xoffi.ai: sheets 74.8 -> 60.2 ms, cascade 84.8 -> 77.6 ms, HTML 90.9 -> 90.3, flow 43.4 -> 42.7, **rastering 499.0 -> 506.3**. The page build is 62 % rastering and rastering barely allocates; that is why the 2.8 x on the allocation is worth 2 % here and no more. The distance to Chromium on xoffi.ai stays at the 6.2 x of TEMPO2. **Every image is bit-identical to the version before the round.** That is the acceptance, not the timing. ## 13. The frozen numbers ``` Firn, bash test.sh see section 14 tools/gc_soak/run.sh PASSED, bounded, counter-check GROWS throughput 1.302 x, longest pause 27.54 -> 9.98 ms, heap/live 2.61 -> 2.56 Certus, tools/layout/run.sh --fast own cases 1087 / 1087 boxes in 146 cases (limit 1087) against Chromium 1087 / 1087, deviation 0.00 % (limit 1087) paint order 5171 / 5171 probe points (limit 5171) LAYOUT OK Certus, tools/js/run.sh --fast test262 parser 3051 (TEMPO2: 3051 -- IDENTICAL) test262 engine 2693 (TEMPO2: 2693 -- IDENTICAL) Certus, tools/tempo2/messen.py the SHA-256 of the image on all five pages: unchanged ``` **One red one, and it is not this round's.** `tools/js/soak.sh` in the `--fast` shape (20,000 rounds) demands that the deliberately leaking counter-check grows by at least 4596 KiB. It is flaky, and it is flaky BEFORE the change as well -- four runs, interleaved: ``` before 4864 KiB PASS before 3336 KiB FAIL after 3332 KiB FAIL after 3332 KiB FAIL ``` With the full 40,000 rounds both sides pass comfortably (before 14400 KiB, after 12892 KiB). The threshold sits on top of an RSS sample that is taken after the run has already grown; at 20,000 rounds the run is short enough that the first sample lands past the growth. It belongs fixed, and it belongs fixed in a round of its own, because it is a measurement and not a collector. --- ## 14. What lies in this branch ``` lib/gc/gc.fi __gc_alloc_fast (the fast path), the size classes as binary searches, __gc_klasse_bytes, and the fast rejection (S_HEAPLO / S_HEAPHI) in __gc_block_of and __gc_chunk_of compiler/src/gc.rs the state block offsets as a contract, class_for, and the two tests that keep them honest compiler/src/gc_lower.rs alloc_fast: the fast path AT the call site lib/firnc1/gc.fi the same offsets and the same table for the self-hosted compiler lib/firnc1/lower.fi gc_alloc_fast: the same FIR lib/firnc1/gctext.fi regenerated (tools/gen_gctext.sh) bin/gctext.fi likewise tools/anlegeweg/mikro.fi NEW -- the elementary operations in nanoseconds tools/anlegeweg/reject.fi NEW -- what a non-pointer costs the collector tools/anlegeweg/mikro.sh NEW -- three runs, best value per line docs/RUNDE-ANLEGEWEG.md this report ``` ## 15. The work list after this round ``` 1. THE CODE GENERATOR at the default build level. Measured in this round: the same allocation is 54.9 ns at `dev-fast` and 33.0 ns at `release-safe`. Locals in memory, an address with two uses becoming a `lea` instead of an addressing mode. WIRKUNG: on everything. 2. BYTECODE instead of the tree walk (TEMPO2 item 3). One round of a JS loop costs 3.7 microseconds. Measured in this round: numbers as immediates would be worth 1.09 to 1.16 x against that. Bytecode first, immediates after -- the other way round than TEMPO2 had it. 3. THE SWEEP hands its dead blocks back as a linked list. Handing them back as CONTIGUOUS REGIONS (Immix) would make the bump allocation of section 3 pay off after all -- it failed here only because the free list is the source in the steady state. 4. tools/js/soak.sh --fast: the threshold of the counter-check hangs on an RSS sample. Flaky before this round as well (section 13). ```