fast by construction

nine chapters have asked you to give things up. no mutation. no loops—recursion is the only way to repeat yourself. seven small overloads where another language writes one switch. a reasonable person reads all that and waits for the bill: elegance this thorough must cost something once the program actually runs.

the tax is negative. a pure, values-only language—failure handled for you, no mutation, not one named buffer—decodes json a hair faster than serde_json, the parser a rust team hand-tunes for exactly this job. the rest of the chapter answers two questions: how, and how do we keep it true.

the honest asterisks, up front. the margin is small. of the 25 interleaved pairs, 24 went to kanso; the medians were 0.89ms to serde's 0.93ms. this is one document on one machine—"faster than serde_json on this gauntlet," not "the fastest json parser alive." and the memory stays flat while it works: about 5.8mb whether you decode once or a hundred and fifty times, because each decode hands its scratch space back before the next one starts.

two other people's harnesses

the table runs every decoder through one harness so nobody gets a hometown advantage. still, it's worth watching the two rivals that matter run on their own turf, so you trust that the bar is real and not something we drew ourselves.

the easy bar is go's standard library—one of the most exercised json decoders in production anywhere. here it is on its own benchmark, same 188kb fixture:

go decoded 160 top-level values, mean over 150: 1.827406ms

about 1.83ms a decode. respectable, and not the one to beat. the hard bar is rust: serde_json, measured in its own harness on the very same bytes, comes in under a millisecond:

serde mean over 150 decodes: 863.687µs

863 microseconds in serde's own harness—the sub-millisecond wall. a tree-walking interpreter is never going to touch it, and we won't pretend otherwise. the compiled binary does, but only after we look honestly at that interpreter first.

the same program, two engines

one module, two ways to run it. start with the engine you've used all book—kanso run, the interpreter. and be fair to it: this clock times the whole pipeline. parse the source, type-check it, infer it, then tree-walk a four-hundred-line parser across 188kb of json, a hundred and fifty times over:

$ time kanso run bench/jsonbench
decoded 150 times, checksum 24000
kanso run bench/jsonbench  0.26s user 0.00s system 99% cpu 0.267 total

a quarter of a second for 150 full decodes, tree-walked. that's far closer to compiled speed than the folklore about interpreters would let you guess—and winning this race was never the interpreter's job anyway. its job is to answer in milliseconds on human-sized programs, carry no state between runs, and stand as the reference the compiler has to match to the bit. notice the checksum on that line: 24000. hold onto it.

now hand the exact same module to the compiler. nothing changes—no annotation, no rewritten fn, no buffer given a name. kanso build, then run the binary it produces:

$ kanso build bench/jsonbench --release
built ./jsonbench (llvm ir at jsonbench.ll)
$ time ./jsonbench
decoded 150 times, checksum 24000
./jsonbench  0.14s user 0.00s system 99% cpu 0.140 total

0.14 seconds for the same 150 decodes, and the same 24000 falls out the bottom. the fixture is read at runtime, so the optimizer can't cheat by folding the answer in at compile time; the matching checksum proves each of the 150 decodes really happened. that 24000 is not decoration. the interpreter printed it, the binary prints it, and every future run on every machine has to print it too—or something is broken. that agreement is the first of this chapter's three safety nets, and we'll build on it later.

wall-clock time is a blunt instrument, though: it counts process startup, and it can't interleave runs to cancel out heat and noise. the careful measurement is the interleaved best-of-25 from the table up top, where the binary lands at 0.81ms against serde's 0.83. the win didn't arrive in one heroic stroke—it came in a few measured steps, none of which touched the module you wrote in chapter 08. the biggest was teaching the compiler to inline a batch of one-line helpers directly in its own ir, where the linker had been quietly declining to: −10.7%. the compiler got better at the same program.

where the time goes

"zero-cost abstraction" is a promise nearly every compiled language makes and nearly none will show you the evidence for. here is the evidence—a cpu profile of that binary, caught mid-benchmark, sorted by what sat on top of the stack most often:

Sort by top of stack, same collapsed (when >= 5):
        d__value_for_3  (in jsonbench)        504
        k_truthy  (in jsonbench)        180
        k_b_push_mut  (in jsonbench)        179
        k_utf8_bad  (in jsonbench)        132
        _platform_memmove  (in libsystem_platform.dylib)        126
        d__str_char_4  (in jsonbench)        114
        d__obj_key_start_4  (in jsonbench)        106
        k_b_find2  (in jsonbench)        98
        k_b_put  (in jsonbench)        97

read it as a picture of where the afternoon went. the busiest thing in the whole program, by a wide margin, is d__value_for_3—and that is your function. it's the _value_for you wrote in chapter 08, the little group of overloads that peeks at the next byte and decides whether a value is a string, a number, an object, or an array. below it sit the rest of the parser's own functions and a few runtime primitives for shuffling bytes around.

now look at what's missing. there is no interpreter in this list. no dispatcher walking a table of function pointers. no tag-checking loop, no garbage collector. memmove—raw byte copying, the floor of any parser—has sunk to fifth. the overloads, the pattern matches, the railway you spent nine chapters learning: none of them appear, because by the time the compiler is done they aren't separate things in the program anymore.

take the hottest function as the case study. in the source, _value_for is seven overloads—seven tiny functions, one per kind of byte. you might picture running it as walking into a room and asking, one at a time, "are you a string? a number? an object?" until someone says yes. that is not what the machine does. the compiler knows all seven arms ahead of time, so it builds the equivalent of a telephone switchboard: take the byte, jump straight to the one arm that handles it, no working down a line. seven overloads in the source, one indexed jump in the machine.

the word for turning "one function that works for many types" into "a separate specialized copy for each concrete type actually used" is monomorphization. that's all it is—the compiler saw exactly which bytes flow through _value_for and stamped out the specialized switchboard, so dispatch, the "only switch" from chapter 03, costs nothing at runtime. you can watch it happen on a program small enough to hold in one hand.

fn kind 43
  "plus"

fn kind 45
  "minus"

fn kind 46
  "dot"

fn kind 101
  "exponent"

fn kind _
  "other"

main = print (kind 46)

dot

five overloads, each matching one byte literal, plus a catch-all _. build it and look at the emitted ir—the whole group is a single indexed branch:

  switch i64 %t3, label %arm4 [
    i64 43, label %arm0
    i64 45, label %arm1
    i64 46, label %arm2
    i64 101, label %arm3
  ]

the catch-all _ became the default label; each byte literal became one case. this is the exact shape the real json scanner is built from. here is _is_number_char from the benchmark module—its arms are the bytes 43 45 46 69 101, which are + - . E e—compiled the same way, one function deeper into a working parser:

  switch i64 %t4, label %arm6 [
    i64 43, label %arm0
    i64 45, label %arm1
    i64 46, label %arm2
    i64 69, label %arm3
    i64 101, label %arm4
  ]

overloads in the source, one jump in the machine, at any scale. it is the same thing every chapter has landed: kanso deletes things. commas, wrappers, exceptions, mocks—and now the runtime cost of its own abstractions.

one more symbol is worth a glance. k_b_push_mut, sitting third from the top, is list-append that extends the list in place instead of copying it—the parser's accumulator grows without ever cloning itself, which is a big part of why memmove fell so far down. that trick rests on a lineage of published papers, and the full story—how the language's guardrails let the compiler get away with it, and which papers we raided to get there—lives on the compiler page. this chapter hands you the receipt; that page opens up the machine.

a loop that isn't a loop

recursion is kanso's only way to repeat, so the compiler can't treat tail calls as a nicety it applies when it's in a good mood. a call in tail position—the last thing a function does before it returns—becomes a jump that reuses the current stack frame instead of stacking a new one on top. here is mutual recursion ten million frames deep:

fn even 0
  true

fn even n
  odd (n - 1)

main =
  verdict = even 10000000
  print "10000000 even? {verdict}"

fn odd 0
  false

fn odd n
  even (n - 1)

10000000 even? true

ten million alternating calls, no annotation asking for anything, and the stack never grows past a single frame. three milliseconds, done. the guarantee is right there in the ir—musttail, llvm's strongest promise: emit the jump, or refuse to compile the module at all.

  %t13 = musttail call tailcc %KValue @d_odd_1(i64 %t12)
  ...
  %t13 = musttail call tailcc %KValue @d_even_1(i64 %t12)

that distinction is the whole point. a plain tail-call hint is advisory: the backend may honor it, and on a bad day for register allocation it may not, and your ten-million-deep recursion overflows the stack in production while passing every test on your laptop. musttail deletes the bad day from the space of outcomes. a loop that isn't really a loop is not a shape kanso can ship by accident.

the ratchet

every number so far has a shelf life. the profile was one afternoon on one machine; the gauntlet drifts with the temperature of the room. a benchmark you run once and quote forever isn't evidence of much. the part of this chapter that outlives any single run is the part that turned these numbers into tests—things ci checks on every commit, that fail a build the exact way a wrong answer fails a build. that's the ratchet: it lets a win go forward and won't let it slide back.

the ratchet has teeth on three surfaces. the first you've already met: the interpreter and the compiled binary have to print the same bytes on every example in the suite, the whole json corpus included. that 24000 we held onto is one tooth—when the compiler rewrites the entire program and not a single output bit moves, the rewriting is trustworthy. the other two teeth are new.

costs are facts, not measurements

a deterministic language has deterministic costs. run any compiled binary with KANSO_COUNTERS=1 and, instead of how long it took, the runtime tells you what it did. take a program small enough to check by eye: build a thousand-element list one push at a time, then sum it.

import "std/list"

fn build 0 acc
  acc

fn build n acc
  build (n - 1) (push acc n)

pub play = print "sum {list/sum (build 1000 [])}"

allocs=12
alloc_bytes=43936
arena_blocks=1
arena_peak_bytes=1048576
cohort_frees=0
cohort_kept=0
perm_allocs=1
beat_iters=1000
evac_allocs=0
evac_bytes=0
put_mut_fast=0
put_mut_grow=0
push_mut_fast=0
push_mut_slow=1000
thunk_allocs=0
thunk_forces=0
thunk_evals=0
thunk_frees=0
thunk_escaped=0
thunk_live_exit=0
el_parses=0
ryu_renders=0
utf8_bytes=0
find2_calls=0
append_fast=0
append_grow=0
utf8_zerocopy=0
carry_dedup=0
bytes_malloc=0
bytes_freed=0
str_scans=0
str_scan_bytes=0
buf_reuse=0
held_peak_bytes=0
view_allocs=0
view_frees=0
sh_str=64
sh_rec=0
sh_buf=0
sh_map=0
sh_bytes=0
sum 500500

a thousand pushes cost twelve allocations. not "about twelve." not "twelve on my laptop." twelve—run it again, run it on a different chip, a loaded cpu, a cold cache, and every one of those integers comes back identical. these aren't measurements with error bars. they're facts about the program, as reproducible as its printed output, because the list's growth policy is fixed and it extends its one owner in place until it has to double.

now point the same instrument at the gauntlet:

allocs=8341214
alloc_bytes=489854112
arena_blocks=4
perm_allocs=8
beat_iters=151
decoded 150 times, checksum 24000

two of those integers tell the memory story cleanly. arena_blocks=4 across a hundred and fifty decodes is the flat-memory guarantee written as a constant: one decode touches four blocks of scratch space, a hundred and fifty decodes touch the same four, because each decode hands its arena back before the next begins. beat_iters=151 is one rewind per decode plus one for the program itself, on the record. and because none of these five numbers ever move, ci writes them down and diffs against the file:

allocs=8341214
alloc_bytes=489854112
arena_blocks=4
perm_allocs=8
beat_iters=151

a regression in the compiler's folding now shows up as a changed integer in a diff—the same way a broken behavior shows up as a failed assertion. if a future edit to push loses the in-place reuse, allocs jumps, the golden fails, and it fails on every machine, before anyone has to file a "feels slower lately." no clocks, no flaky thresholds, no "it was fine on ci but slow on mine." that −10.7% inlining win from a few pages back stopped being an anecdote the day alloc_bytes became a committed integer.

and the shape of the code

counters pin what the program does when it runs. they can't see the shape of the code the compiler emitted—and some of this chapter's best guarantees live in that shape. that the scanner is a jump table and not a chain of comparisons. that every tail call is a real musttail and not an advisory hint one register-allocation change could quietly drop. a benchmark won't catch the day a jump table decays into an if-ladder, because the program still gives the right answer, just slower on inputs the benchmark never tries. a check on the emitted code will.

the emitted .ll is plain text, so the check is a plain grep committed as a golden. the tail-call guarantee for the ten-million-frame program is exactly two musttail calls—one per direction of the recursion:

$ grep -c "musttail call" pingpong.ll
2

the day someone changes codegen and a tail call comes out as a plain call, that count drops and the check fails—loudly, at build time, long before a stack overflow reaches a user. the dispatch shape is pinned the same way. the scanner's decision has to stay a switch over its byte literals:

$ grep -A5 "switch i64 %t3" classify.ll
  switch i64 %t3, label %arm4 [
    i64 43, label %arm0
    i64 45, label %arm1
    i64 46, label %arm2
    i64 101, label %arm3
  ]

turn that literal dispatch back into a cascade of comparisons and the switch line stops matching and the golden fails. the property stops being a sentence in a book and becomes a wall the codegen has to keep clearing. three surfaces, three sets of teeth: behavior goldens prove the answer is right, cost goldens prove the work stayed bounded, structural goldens prove the fast shape held.

you can now read a kanso binary's cost the way you read its output—as a fact, not a feeling. you can prove a tail call is real, prove a dispatch group stayed a jump table, prove an allocation count didn't creep, each one a golden that ci diffs on every commit. the abstractions you spent nine chapters learning to write cost nothing at runtime, and now you hold the receipts that keep it that way. that is the book's last claim, and every earlier chapter was walking toward it: kanso deletes the clutter from your source, and then the compiler deletes your source's abstractions from the machine. what runs is only the decisions.

exercises

1. build samples/ch10/counters.kso, then change the loop count from 1000 to 2000 and rebuild. run it under KANSO_COUNTERS=1 and write down the new allocs and alloc_bytes. from your two data points, work out the list's growth policy: does doubling the element count double the allocation count, or add a fixed few?
2. write your own two-overload tail-recursive function—say, a countdown that prints as it goes—build it, and grep the .ll for musttail call. now rewrite one arm so its recursive call is not the last thing it does—wrap the call in a bit of arithmetic—rebuild, and grep again. say what happened to the count, and what that predicts about the stack at ten million frames.
3. take the classify.kso dispatch group and add five more byte-literal arms. rebuild and check that the emitted switch grew to match—one label per literal, one default. then swap one literal arm for a guard that ranges over bytes (_both (47 < c) (c < 58)) and see whether that arm stays inside the switch or moves out of it.
4. the cost golden in bench/cost_golden.txt is committed. break it on purpose: edit one integer, run the counters, and diff the two. then describe what a real regression would have to change in the program to produce that same diff—and why a wall-clock benchmark would have waved it through.