From ecc350ca5c2eb50be8309c5f14f8bf0d87db9a02 Mon Sep 17 00:00:00 2001 From: Moon Flower Date: Mon, 12 Oct 2026 08:46:23 +0330 Subject: a --- docs/history/35-bench/notes.md | 82 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) create mode 100644 docs/history/35-bench/notes.md (limited to 'docs/history/35-bench') diff --git a/docs/history/35-bench/notes.md b/docs/history/35-bench/notes.md new file mode 100644 index 0000000..914bbba --- /dev/null +++ b/docs/history/35-bench/notes.md @@ -0,0 +1,82 @@ +# 35 — zc against C + +two programs, each written in zc and in C, timed without bootstrapping the compiler. the sieve is the integer loop, where o3 and the llvm backend should look good. the tree is the allocator and the call, where they should not. + +`bench/sieve.zc` and `bench/sieve.c` count primes below 100000. one word per flag, marks start at `i * i`, checksum 9592. zc has three kernels: a plain `fixed []int` (bounds-checked), the same function marked `o3`, and an `o3` loop through a raw `*int` with no per-index check. C has the same word loop, plus a byte-flag loop that is a different representation. `bench/trees.zc` and `bench/trees.c` build a full binary tree of depth 12 and walk it. checksum 8191, the node count. zc `new(node)` / `free`, the same marked `o3`, and one array used as an arena of pairs. C uses `malloc` / `free`, and the same arena shape. a node in zc is two pointers plus the 6-word buddy header, which rounds to 8 words (64 bytes). the C node is two pointers (16 bytes). + +the number is the slope between 1 repetition and N, so process startup falls out, and so does the time zc spends compiling the benchmark. five slopes, median, min and max. pinned to one cpu with `taskset`. the vms are built at `-O3`. C is `gcc` and `clang` at `-O3 -march=native`, then again with `-flto`, and gcc again with `-fprofile-generate` / `-fprofile-use`. LTO and PGO stayed inside the spread on both programs, so the tables below use the plain `-O3 -march=native` line for C and mention the others only where they differ. `ZYHOT=1` on the llvm vm, so every block is compiled, and each o3 region is compiled with llvm's O3 pipeline at install time. the arm64 jit is `qemu-aarch64` 8.2.2 running an aarch64 binary on this x86 host. that is emulation, not arm64 hardware. the microcore is not in the table: it does not lift o3. + +the machine: Linux 6.12.94+ x86_64, KVM, 4 vCPUs. `/proc/cpuinfo` says Intel Xeon, family 6 model 207; the hypervisor leaves the model name as "Intel(R) Xeon(R) Processor". gcc 13.3.0, clang 18.1.3, llvm 18.1.3. + +the llvm tree rows were retimed with about 3 seconds of kernel work (n = 220, 155 and 38419). the first calibration aimed at 0.8 seconds and undershot, because compiling the benchmark under `ZYHOT=1` takes about 9 seconds and a short slope drowns in that jitter. `bench/run.py` now grows N until the measured gap actually reaches the target. the other rows already had a tight spread at 0.8 seconds, except the llvm raw sieve, whose five samples still all sit between 1.4x and 1.7x the gcc sieve. + +## sieve + +milliseconds per count of the primes below 100000. + +| path | median | min | max | +| --- | ---: | ---: | ---: | +| gcc -O3 -march=native, word flags | 0.149 | 0.149 | 0.150 | +| clang -O3 -march=native, word flags | 0.157 | 0.157 | 0.173 | +| gcc -O3 -march=native -flto, byte flags | 0.081 | 0.080 | 0.081 | +| zc interpreter, plain, bounds-checked | 214.3 | 212.8 | 215.7 | +| zc interpreter, o3, bounds-checked | 22.92 | 22.91 | 22.93 | +| zc interpreter, o3, raw pointer | 14.36 | 14.26 | 15.84 | +| zc llvm, ZYHOT=1, o3 raw pointer | 0.219 | 0.209 | 0.256 | +| zc llvm, ZYHOT=1, o3 bounds-checked | 0.640 | 0.633 | 0.667 | +| zc arm64 jit, qemu-user, o3 raw pointer | 2.094 | 2.075 | 2.102 | + +gcc with `-flto` was 0.149, gcc with PGO was 0.149, clang with `-flto` was 0.158. + +on the same word algorithm, the llvm backend is about 1.5x the best C. that is the strength. the interpreter running the lifted blocks is about 65x slower than that llvm region (14.4 ms against 0.22 ms), and the plain bytecode is about 9x slower again than the lifted blocks (214 ms against 23 ms). the bounds check costs 1.6x on the interpreter and 2.9x once llvm has made the arithmetic cheap (0.64 ms against 0.22 ms). + +the arm64 column is qemu-user. 2.09 ms is 14x the native gcc number and only 6.9x faster than the native interpreter running the same lifted blocks. both of those comparisons are skewed: qemu is translating aarch64, and the interpreter is x86 host code. the ratio that is safe to read is jit against itself. it is not a measurement of arm64 hardware. + +the byte sieve is the same algorithm in 1 byte per flag. gcc runs it in 0.081 ms, 1.8x faster than the word sieve. zc cannot take that path on the fast tier: byte loads and stores are opcodes 612..617, and `lift_block` leaves the region on anything it does not recognize. + +## trees + +milliseconds per tree of depth 12, built and walked, then released. + +| path | median | min | max | +| --- | ---: | ---: | ---: | +| gcc -O3 -march=native, malloc | 0.092 | 0.091 | 0.092 | +| clang -O3 -march=native, malloc | 0.110 | 0.110 | 0.111 | +| gcc -O3 -march=native -flto, arena | 0.0144 | 0.0143 | 0.0144 | +| clang -O3 -march=native -flto, arena | 0.0308 | 0.0304 | 0.0311 | +| zc interpreter, plain new/free | 178.1 | 177.6 | 179.4 | +| zc interpreter, o3 new/free | 269.4 | 269.2 | 273.9 | +| zc interpreter, o3 arena | 2.108 | 2.102 | 2.164 | +| zc llvm, ZYHOT=1, plain new/free | 13.69 | 13.14 | 14.60 | +| zc llvm, ZYHOT=1, o3 new/free | 23.70 | 21.67 | 28.14 | +| zc llvm, ZYHOT=1, o3 arena | 0.282 | 0.269 | 0.291 | +| zc arm64 jit, qemu-user, plain new/free | 80.83 | 80.64 | 83.65 | +| zc arm64 jit, qemu-user, o3 arena | 1.667 | 1.624 | 1.691 | + +gcc malloc with `-flto` was 0.093, with PGO 0.092. clang malloc with `-flto` was 0.110. + +`new` / `free` on the llvm backend is about 150x gcc `malloc` (13.7 ms against 0.092 ms). the same backend walking an arena, with no allocator in the loop, is 0.28 ms, about 20x gcc's arena (0.014 ms) and about 50x faster than zc's own `new`. so most of the tree gap is the allocator, and what is left after the allocator is gone is the call. marking the tree `o3` makes it slower: 269 ms against 178 ms on the interpreter, 24 ms against 14 ms on llvm. `new` in o3 code is `new_raw`, and every return and every store of a child calls `fatten` and `own`, which are ordinary calls out of the region. + +`free` only quarantines. the timed loop does not call `gc` itself; the next `new` sweeps when an 8-word block will not fit. an earlier single slope that called `gc` on every tree was about twice as slow. forty iterations completed without `scrub`. the sweep still scans the whole data-stack area (`gc_roots` marks `DSLO`..`DSHI`), so a shape that leaves a pointer in an unused slot would pin the quarantined nodes. `scrub` only overwrites 1024 words below the stack pointer. + +under qemu the arena jit (1.67 ms) is barely faster than the interpreter's arena (2.11 ms). the body between calls is a handful of micro-ops, and every call returns to the driver. the sieve, whose inner loop never calls, is where the jit pays off. + +## what is missing, by impact + +1. the buddy allocator. `new_raw` in `src/rt.zc` adds a 6-word header and rounds up to a power of two, so a two-pointer node is 64 bytes. `free` quarantines instead of pushing the block back on its size-class list; the next failed allocation runs `gc`, which walks the whole heap. on llvm that is the difference between 13.7 ms and 0.28 ms, and against gcc `malloc` it is about 150x. fix: a bump allocator the program can opt into (the arena kernel is that, written by hand), and a free path that returns a block the program has already dropped to the free list without a full sweep. stamp the type in `new` so the header does not have to be repaired later. + +2. the call ABI. `lift_block` ends the block at a call (opcode 6, `T_CALL`). `run` spills the region, returns to the C driver, dispatches the callee, and re-enters at the return point. a depth-12 tree is 8191 calls to build and 8191 calls to walk, and the llvm arena is still 20x gcc's arena (0.28 ms against 0.014 ms). the same exit is why `o3` cannot speed the tree up. fix: when the callee is an o3 region, compile a native call to its entry with the arguments in registers, and only spill to the vm stack when the callee is ordinary bytecode. + +3. bounds checks on `fixed []T`. the o3 index path in `src/compiler.zc` compares the index with `outside` and, on the failure path, calls `oob`. in the lifted sieve that compare spills the index to the data stack and reloads it on the way back, on every in-bounds store. llvm pays 2.9x for it (0.64 ms against 0.22 ms). fix: keep the index in a register across the check, and drop the check when the loop bound was already compared against the length. a raw `*int` is the escape hatch that already exists; the checked form should not be this far from it. + +4. the lifted blocks are too small, and nothing vectorizes. the raw sieve's inner step is a compare block, an empty block, a store block and an add block, four dispatches per flag. that is the interpreter's 14 ms. llvm's O3 pipeline closes most of it (down to 0.22 ms) but does not match gcc, which fills and counts with `ymm` stores and `vpaddd` (0.15 ms, 1.5x faster). fix: merge an empty block into its successor and rotate the loop before codegen, so both `rexec` and llvm see one block per iteration. gcc's leftover advantage is the vectorizer; a region whose loops are single blocks gives llvm's vectorizer a chance at the fill and the count. + +5. `fatten` and `own` on the way out of o3. storing a fresh child emits a call to `own`, and because the value has pointer fields the compiler also calls `fatten` (`emitown`, and again on an o3 return). `fatten` stamps the type `new_raw` left blank and walks children that are already stamped. the o3 tree is about 1.5x slower than the plain one on the interpreter, and about 1.7x slower on llvm, for that. fix: pass the type into the allocation so the header is born stamped, and inline `p[-2] = owner` as a store in the region when memdebug is off. do not fatten a pointer that was allocated as that type a few instructions earlier. + +6. byte addressing is not on the fast path. opcodes 612..617 fall into the `leave_at` default in `lift_block`, so a byte sieve would run as bytecode even inside `o3`. the C byte sieve shows the prize is about 1.8x on this size, less than the gaps above, and it grows for a bigger limit where the word sieve stops fitting in cache. fix: lift `ld8` / `st8` / `ld16` / `st16` / `ld32` / `st32` the same way the word load and store are lifted, in the interpreter, the arm64 jit and the llvm region. + +7. the collector's roots, and quarantine. `gc_roots` marks every word from `DSLO` to `DSHI`, not just the live stack, so a pointer left above the stack pointer keeps a freed block quarantined forever. `scrub` clears 1024 words and is easy to forget; this tree happened to overwrite those slots before the sweep. fix: mark from the stack pointer to the top, and treat a block the program freed, whose pointer it has cleared, as immediately reusable. + +8. library and language gaps the two programs ran into. there is no arena and no packed array in `lib/std.zc`, so the fast tree is an index bump written out by hand and the fast sieve is a word per flag. a small arena and a packed byte buffer in the library would make those the ordinary spelling. `u`, `m` and `d` are still reserved as bare words, so the first draft of the tree would not compile with a parameter named `d` (`if (d > 0)` is read as a tag). fix: only treat those letters as tags after a dot. `new` inside `o3` does not zero its memory (`new_raw`); the leaves had to store null children or the walk would read garbage. fix: have the compiler emit those zero stores in the region, or zero pointer fields in `new_raw` when the type is known. + +the register file is part of the same ceiling. a region has seven variable registers (`RMAXV`). the bounds-checked sieve already uses all seven. a loop with one more live value stays in memory, and the arm64 jit gives up on a block that needs more temporary registers than it has. raising that, or spilling inside the region instead of abandoning it, matters once the calls and the checks above are cheap enough for register pressure to show. -- cgit v1.2.3