fast by construction

the earlier chapters 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.

none of it costs speed here. 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 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. it also helps to see the two main rivals on their own benchmarks, so you can check the bar against numbers we did not produce.

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 interpreter, kanso run --interp. and be fair to it: this clock times the whole pipeline. parse the source, type-check it, infer it, then tree-walk the json parser across 188kb of json, a hundred and fifty times over:

$ time kanso run bench/jsonbench --interp
decoded 150 times, checksum 24000
kanso run bench/jsonbench --interp  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 13. 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 value_for, which chapter 13 read: 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 eight arms, one per kind of first byte. you might picture running it as asking each arm in turn whether it matches until one says yes. the machine does something else. the compiler knows all eight arms ahead of time, so it emits one indexed jump: take the byte, go straight to the arm that handles it.

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"

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, and each byte literal became one case. the real decoder compiles the same way. here is value_for in a release build of the benchmark today: its six byte arms are 34 91 102 110 116 123, which are " [ f n t {, the none arm is the case for 256, a value no byte can have, and the arm for everything else is the default:

  switch i64 %x0r, label %arm7 [
    i64 34, label %arm0
    i64 91, label %arm1
    i64 102, label %arm2
    i64 110, label %arm3
    i64 116, label %arm4
    i64 123, label %arm5
    i64 256, label %arm6
  ]

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 cannot treat tail calls as an optional optimization. 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)

fn odd? 0
  false

fn odd? n
  even? (n - 1)

verdict = even? 10000000

print "10000000 even? {verdict}"

10000000 even? true

ten million alternating calls, no annotation asking for anything, and the stack never grows past a single frame. built with kanso build pingpong.kso --release, the binary takes about three milliseconds. 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)

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 makes the call a jump or makes the compile fail, so a tail call kanso emits always runs in constant stack.

and now it can be said as a contract rather than a description: a call in tail position consumes no stack, in every engine, and a program may lean on that the way a scheme program does. the accumulator rewrite the appendix shows for simple counting shapes is a different thing — an optimization the compiler is free to widen or narrow between releases. the promise is tail position, and nothing wider.

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 a program with KANSO_COUNTERS=1, under kanso run or kanso play or as a binary built with kanso build --counters, 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)

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

allocs=7
alloc_bytes=28960
arena_blocks=1
arena_peak_bytes=1048576
cohort_frees=0
cohort_kept=0
perm_allocs=2
beat_iters=0
evac_allocs=3
evac_bytes=80
survive_slots=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
ryu_short=0
utf8_bytes=0
find2_calls=0
number_spans=0
append_fast=0
append_grow=0
append_rendered=0
utf8_zerocopy=0
carry_dedup=0
bytes_malloc=3
bytes_freed=2
perm_live_bytes=16400
perm_peak_bytes=16400
str_scans=0
str_scan_bytes=0
seek_resumes=0
seek_steps=0
buf_reuse=0
held_peak_bytes=0
view_allocs=0
view_frees=0
ten_blocks=0
ten_frees=0
ten_handups=0
chain_finds=0
sh_str=64
sh_rec=0
sh_buf=112
sh_map=0
sh_bytes=0
spare_peak_bytes=0
sum 500500

a thousand pushes cost seven allocations, exactly. run it again, on a different chip, on a loaded cpu or with a cold cache, and every one of those integers comes back the same. they have no error bars: they are as reproducible as the program's printed output, because the list's growth policy is fixed and it extends its one owner in place until it has to double.

the same instrument, pointed at the gauntlet, gives the first lines of the file ci keeps for it:

two of those integers tell the memory story. arena_blocks is 2 across all hundred and fifty decodes: each decode hands its scratch space back before the next begins, so the count does not grow with the number of decodes. beat_iters is 150, one for each decode. none of these numbers moves between runs, so ci keeps them in a file and diffs it like program output:

allocs=1125014
alloc_bytes=152572448
arena_blocks=2
arena_peak_bytes=2097152
cohort_frees=1
cohort_kept=0
perm_allocs=4
beat_iters=150

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. 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 from the earlier chapters cost nothing at run time, and the goldens are what keep that true from one commit to the next. the appendices that follow are for looking things up.

exercises

1. build samples/fast/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 (47 < c and 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.