Status: Superseded by ADR-294 — its D1-D5 are D12-D16 there
Date: September 30, 2026
Target Version: Nikaia 0.0.283
Answers: open-decisions.md, How the ring after
the tree reads the checker’s types. The owner chose option (1), moving them
whole, and asked for this record and a measurement first.
Related: ADR-250 (the road: a module moves when everything it
reads is Nikaia or plain data), ADR-252 (the tree moved, and
how), ADR-100 (a ledger is a file, believed only against its
sources), ADR-024 D4, ADR-030 (? and $V)
The compiler holds two different things that are both called a type.
ast::Type: the Vec[Row] in a declaration,
with the span it was written at. It has been declared in Nikaia since
ADR-252 D1, in tools/ast.nika, like the rest of the tree.contracts::ty::Ty, in contracts/ty.rs
(1 925 lines). It is the written type with three additions:
Unknown, which means no claim. It is compatible with everything, so an
error is reported only where both sides are known and disagree.Var ($V, ADR-030), a name in a library’s signature that the receiver
binds at a call.Fn with sync and throws, Seq
with what one step may do and what the whole is (ADR-105, ADR-212), and
Pointed (ADR-147).It has no spans, because it is also what the ledger records. A ledger
is a file (ADR-100), so a Ty has a text form: Ty::parse reads it,
and Display writes it. Two types are the same when they are written the
same, and nothing is interned.
The ledger’s records are declared around it in contracts/mod.rs. They are
FnContract, TypeContract, Signature, FieldContract, VariantContract,
ConfigContract, Ledger, and the small enums Sync, Lock, Crosses,
Threads and Provenance.
ADR-250’s rule is that a module moves when everything it reads is Nikaia or
plain data. The tree moved, so fold, trust and the rest of the first ring
could move after it (ADR-252, 0.0.273–0.0.281; the self-hosted share went
from 2.4 % to 3.8 %).
Every module of the next ring reads Ty or a ledger record:
sync asks whether a callee is sync.throws asks what a callee may fail with.keeps asks what a parameter lends.Ty on 633 lines of check/mod.rs.So nothing more moves until these types are Nikaia, or until each module’s adapter flattens them into plain data. The second path is option (2) of the open decision. It builds an adapter per module that is deleted again once the types move, and the owner declined it.
| compiler | the checker’s type | across a unit boundary |
|---|---|---|
rustc |
hir::Ty for what was written; ty::Ty<'tcx>, interned in an arena, compared by pointer |
.rmeta, a binary encoding of the interned types |
| Go | go/ast for what was written; go/types, plain heap objects, compared by structure with identity rules (types.Identical) |
export data, a binary encoding |
| TypeScript | one Type object per type, created through caches so each is created once, with flags for the kind |
.d.ts, a text form, re-read by the same parser |
| Swift | canonical types, interned in the ASTContext |
.swiftinterface, a text form |
| Zig | InternPool: every type and every comptime value is a u32 index into one pool |
the pool is what incremental compilation keeps between updates |
Nikaia is closest to TypeScript today. Types are plain trees and the boundary is text. Go and TypeScript are also the two that moved (or are moving) their compiler to another language. Go 1.5 did it by mechanical translation, so the shape of the types did not change during the move. The move and the redesign were kept apart.
Zig’s InternPool was not a micro-optimisation. It followed from four
properties of Zig, each stated in its design talks and in the self-hosted
compiler’s history:
For each of the four, Nikaia’s situation today is different. Each difference could close, so each is a condition to watch, not a permanent answer:
rustc follows the front end. docs/subprocess-cost.md measured the
whole rustc compile of json.rs at 1.72 billion instructions. If the
front end is a few percent of a build, halving it is invisible to the
person waiting. This changes if Nikaia gets a back end of its own.@typeInfo and no function that returns a
type. This changes if build-time evaluation ever computes types.If the measurement comes out differently from Zig’s answer, this is why. If it comes out the same, Zig’s reasons were not the only ones.
Ty, Shape, the ledger records of §1.1 and their small enums are declared
in Nikaia. They go in a tool module beside ast.nika, lowered by nikaia
lower-std and re-exported from contracts, so every reader keeps its path.
This is ADR-252 D1’s route, used a second time.
ledger.nika, which already reads the file’s lines.fits, bind, substitute, qualify, …) move,
and with them the next ring.The shape is decided before (b) and not during it. Interning later would touch the checker’s 633 lines a second time. Deciding first is what keeps the move and the redesign apart, which is the lesson of Go 1.5 in §1.3.
Interning (a u32 handle into a pool, as Zig and rustc do) is chosen
only if both of these hold on the corpus’s largest programs:
Ty are at least 15 % of the front
end’s instructions, net of what interning would add (a hash and a lookup
for every type built).It is also chosen if the measured growth with program size carries (1) past 15 % at the size of the compiler itself, 75 000 lines, even though it holds today at neither.
Otherwise Ty moves as it is, a plain tree with a text form (D1), and §4
records the numbers that would reopen this decision.
These numbers are this record’s guess, committed in a separate commit before the first measurement ran, so that the result cannot be shaped to fit them.
json, the largest example (by instructions).Ty, counted inclusively and
including the allocations under them, is 3–12 % of the front end’s
instructions on the larger programs. Best guess: about 6 %.std.contracts, 2 997 lines, and the sysroot) is at least 40 % of the
front end.== comparisons by at least five to one, and
fits is called more often than ==. Interning’s cheap equality therefore
removes little: fits has Unknown’s rules and stays a walk either way.Ty values,
and at least 20 times as many are built or cloned. So interning would
save memory, but the memory is small either way.Ty share is roughly flat with program size. It does not
grow, because the checker’s work per line does not depend on how many
lines came before.The weakest of these is P6. The corpus spans only 15 to 1 197 lines, and a size effect that starts later would not show in it.
The corpus. Every .nika file in examples/, tests/samples/,
benches/ and crates/nikaia/tests/fixtures/, each lowered on its own. Then
nikaia lower-std, which checks the eleven tool modules and text.nika.
tests/errors/ is left out, because a program refused early measures the
refusal.
The build. The release profile with line tables
(CARGO_PROFILE_RELEASE_DEBUG=1), because that is the compiler people run.
Two instruments, never mixed.
valgrind --tool=callgrind on the unmodified
compiler: instructions per function, inclusive. The count is the same on
every run, so two compilers can be compared, which a timing on a shared
virtual machine cannot do.==, fits, distinct values) come from a
separate census build whose Clone, PartialEq and Drop for Ty are
written out with a counter. That build’s timings are never quoted.The known sources of error, and what is done about each:
| # | error | direction | correction |
|---|---|---|---|
| E1 | No real users’ programs. The corpus is examples, tests and the compiler’s own tools, written by the people who wrote the compiler, and skewed toward what the compiler already does well. | unknown | Reported per program, never only as a total. Growth is fitted across sizes, and the rule (D3) is applied at an extrapolated size, not only a measured one. Where this changes the answer, the record says so; the conclusion is stated with the size range it was measured on. |
| E2 | The lowering cache. A second run reuses the lowering and measures nothing. | lower | --no-cache on every run. |
| E3 | Fixed cost hides the per-line cost. On small programs the run is mostly reading std.contracts. |
lower | An empty program is measured, and each program is reported as a total and as the part above that baseline. |
| E4 | Wall-clock on a shared machine is noise. | either | Decisions rest on instruction counts. Wall-clock is reported only as a median of repeated runs, with its spread, to say what the counts feel like. |
| E5 | Instructions are not time. Zig’s argument (§1.4) is cache misses, which an instruction count does not see: a pointer-chasing clone costs more than its instructions. | lower | Callgrind’s cache simulation (--cache-sim=yes) is run too, and misses under the Ty functions are reported beside their instructions. |
| E6 | Inlining hides clones. A derived clone or drop the optimiser inlines into its caller is counted as the caller’s. |
lower | The census build puts #[inline(never)] on the written-out functions. Its total instructions are compared with the unmodified build’s, and the difference bounds what inlining hid. |
| E7 | What interning removes is less than what Ty costs. Building a type still happens: it becomes a hash and a lookup. |
higher | The number of types built is counted (census) and charged at a hash’s cost, and the net is what D3 reads. |
| E8 | The counting build is slower and different. | either | Counts only, never costs, from that build (above). |
| E9 | The test suite’s own programs are not in the corpus. About 1 800 tests write a program inline in Rust. | unknown | Acknowledged. They are small (mostly under 20 lines), so they would add programs rather than size, and E3’s baseline would dominate them. |
| E10 | One run of a deterministic count can still depend on the environment (hash seeds, the path length, the sysroot’s location). | small | Two runs of the same program are compared; a difference over 0.5 % is reported. |
Everything is in benches/ty-census/, so that anyone can run it again on a
later compiler and compare the numbers:
run.sh runs one lowering per corpus program under callgrind, and
nikaia lower-std once. With --cache-sim it adds the cache simulation;
with --count it runs the census build instead.attribute.py charges a profile’s cost to Ty. It sums the inclusive cost
of every call from outside the set of clone, drop and == functions into
that set, so a clone inside a clone is not counted twice. narrow is the
functions whose own type is Ty. broad adds every container of one
(Vec<Ty>, Box<Ty>, (String, Ty), the ledger’s records). The build
uses v0 mangling, which keeps generic arguments in symbol names and changes
no code.report.py writes one row per program.census.py rewrites a scratch copy into the census build.scale.py copies one program k times (E1, below).The machine is the shared four-core virtual machine of
docs/subprocess-cost.md, with valgrind 3.22.
The prediction in D4 is left as it was written. What follows is set against it.
A real edit to examples/json (one string literal changed), in a project
whose dependencies are already built, as a person editing it would run it.
Instructions per process, on the compiler before §4.4’s fixes, which
change json’s front end by 0.1 %:
| process | Ir | share |
|---|---|---|
rustc on the crate, incremental |
780.7 M | 42.5 % |
| the linker | 580.6 M | 31.6 % |
the front end (nikaia build) |
198.8 M | 10.8 % |
cargo |
196.1 M | 10.7 % |
nikaia again, as the build’s rustc wrapper |
67.8 M | 3.7 % |
the rest (rustc --version, cc) |
14.3 M | 0.8 % |
| total | 1 838.3 M |
With incremental compilation off (CARGO_INCREMENTAL=0), rustc on the
crate is 2 464.6 M, and the front end is 5.7 % of the build.
P1 was wrong. The front end is 5.7–10.8 % of a build, not under 5 %, and
both of the compiler’s processes together are 7.7–14.5 %. P1 was read off a
September figure for a whole rustc compile of a standalone json.rs. That
is not what a person editing a project waits for: incremental rustc and
already-built dependencies make the back end smaller and the front end’s
share larger. D3’s second condition holds for the case that matters most,
an edit.
The wrapper’s 67.8 M is a finding of its own. On a cache hit it still reads
std.contracts (§4.6).
Ty costs (D3’s first condition)Callgrind on the release compiler. The table is after the two fixes of §4.4;
lower-std is shown both before and after them. “std.contracts read” is
Ledger::parse, inclusive. Four programs are left out: two are refused on
purpose (foreign-runtime/crossing and smuggled), and two need a
dependency that --input does not read (3.3 of #93).
| program | lines | Ir | std.contracts read |
Ty narrow |
Ty broad |
|---|---|---|---|---|---|
fn main() {} |
2 | 91.3 M | 88.3 % | 1.40 % | 6.87 % |
hello_world |
3 | 103.3 M | 89.3 % | 1.25 % | 6.03 % |
calc |
112 | 128.4 M | 71.6 % | 1.15 % | 5.29 % |
config |
87 | 145.7 M | 63.3 % | 1.22 % | 4.72 % |
tally |
68 | 152.0 M | 60.5 % | 1.08 % | 4.67 % |
k-nucleotide |
184 | 176.3 M | 52.2 % | 1.80 % | 4.81 % |
n-body |
192 | 177.5 M | 51.9 % | 3.46 % | 6.61 % |
access-log |
151 | 182.1 M | 50.6 % | 2.08 % | 4.93 % |
1brc |
184 | 185.1 M | 49.7 % | 1.91 % | 4.88 % |
http |
232 | 198.8 M | 47.0 % | 1.65 % | 4.34 % |
json |
229 | 236.6 M | 39.0 % | 1.31 % | 3.50 % |
benches/jumps |
190 | 236.1 M | 39.0 % | 1.12 % | 3.44 % |
lower-std, before §4.4 |
3 603 | 3 893.0 M | 14.6 % | 13.85 % | 16.16 % |
lower-std, after |
3 603 | 1 649.7 M | 34.6 % | 2.51 % | 4.55 % |
P2 held for the examples and failed for the compiler’s own modules. On
the examples, Ty is 3.4–6.6 % broad and 1.1–3.5 % narrow, lower than the
best guess of 6 %. On lower-std it was 16 %, above D3’s 15 %, which is
exactly the answer the rule would have acted on.
It was not Ty. §4.4 found two walks whose cost grows faster than the
program. With them fixed, the output unchanged and Ty unchanged, lower-std
falls by 58 % and Ty falls to 4.6 %. D3’s first condition does not hold
anywhere in the corpus, before netting out what interning would add (E7).
P3 held. Reading std.contracts is 47–89 % of every program under 100
lines, and still 39 % of json.
The first attempt was the error E1 warned about. A least-squares fit
across the 21 programs gives total instructions ∝ lines^0.60 and Ty ∝
lines^1.04. Extrapolated, Ty would be 15.7 % at 10 000 lines and 37.9 % at
75 000, and D3 would say intern. The fit was rejected for three reasons:
The one large point disagrees with it: lower-std, 1 945 lines of code, is
4.4 % where the fit says about 7.5 %.
What replaced it holds the kind of code fixed and changes only size.
scale.py copies one program k times, and the Ty share (broad) is measured
for each k:
| program (lines of code) | k = 1 | 2 | 4 | 8 | 16 | 32 |
|---|---|---|---|---|---|---|
1brc (91 → 871) |
4.97 % | 5.03 % | 5.21 % | 5.06 % | 4.36 % | |
access-log (87 → 837) |
5.03 % | 5.07 % | 5.20 % | 5.08 % | 4.29 % | |
k-nucleotide (92 → 842) |
4.90 % | 4.58 % | 3.97 % | 3.55 % | 3.05 % | |
n-body, before §4.4 (128 → 1 868) |
7.07 % | 8.14 % | 9.59 % | 11.33 % | 13.34 % | |
n-body, after (128 → 3 724) |
6.42 % | 7.56 % | 6.98 % | 5.57 % |
P6 holds once the walk is fixed, and was false before it. n-body’s
growth was the second walk of §4.4, not Ty. What this overstates is the
number of distinct types: every copy holds the same ones.
Both were found by asking where the Ty share came from. Both are fixed in
this version. Both change no output: nikaia lower-std rewrites no file, and
the test suite passes.
Comparable copied its cycle guard at every enum. An enum’s payloads
were each asked with &mut seen.clone(), so a type reached through two
payloads was walked twice, and one reached through a chain of enums was
walked once per path. The syntax tree is such a chain. Every payload list
was also cloned before it was walked. A struct’s fields already shared the
guard, so the enum now does the same: a type in seen is either being
asked one level up (and answers yes, as before) or has already answered yes
(a no stops the walk). The payloads are borrowed. lower-std: 3 893 M →
1 650 M.struct. self.bodies[i].vx = … looks for a function field of that name
in every declared struct, and fields_of cloned each one’s field list
(check/mod.rs, ADR-230 D1’s check). That is (assignments × structs)
clones. The check now borrows. Asking every struct is still quadratic, but
it is a map lookup and a short scan. n-body × 16: 1 329 M → 1 225 M,
and its Ty share stops growing.This is the lesson of the measurement, and it is the answer to E1’s worry from the other side. A share attributed to a type is not a property of the type’s representation. Interning would have made both walks cheaper per step and left their step counts alone. It would have hidden a quadratic behind a smaller constant.
Counts (the census build, before §4.4):
| program | top-level clones | == |
fits |
distinct types cloned |
|---|---|---|---|---|
fn main() {} |
1 100 | 0 | 0 | 95 |
hello_world |
1 129 | 18 | 6 | 96 |
json |
5 630 | 801 | 546 | 106 |
n-body |
15 920 | 660 | 402 | 100 |
lower-std |
996 496 | 3 086 | 3 994 | 182 |
== by at least 6.8 to 1 in every
program, and by 323 to 1 in lower-std. But fits is called less often
than == in most programs (json 546 against 801), so that half was wrong.
Almost every == compares a type with no arguments (compared nodes equal
top-level comparisons within 1.3 %), so interning’s cheap equality removes
almost nothing.json) to 5 475 (lower-std) clones per distinct type. The smallest
programs clone only 12 times per type.Cache misses (E5), with --cache-sim, after §4.4’s first fix:
| program | Ty broad, instructions |
first-level read misses | last-level read misses |
|---|---|---|---|
json |
3.49 % | 19.2 % | 0.18 % |
n-body |
7.20 % | 23.9 % | 0.20 % |
lower-std |
4.58 % | 17.1 % | 0.22 % |
This is Zig’s argument, visible here too. Per instruction, code over Ty
misses the first-level cache three to five times as often as the compiler’s
average, because it follows pointers. It does not decide anything at this
size, because almost nothing misses the last level: the whole run fits in
cache. Charging a first-level miss 10 cycles and a last-level miss 100 moves
Ty’s share from 3.49 % to 3.7 % (json), 7.2 % to 7.5 % (n-body), and
4.6 % to 4.8 % (lower-std). Zig’s workload (hundreds of thousands of lines in
one process, with comptime values in the same pool) is where a working set
stops fitting, and that is where its answer pays. The last-level miss share is the
number that would say ours has stopped fitting, and report.py prints it.
The other errors of D5:
json)
are close to callgrind’s non-inlined calls (5 936), so inlining hid few
clones. Drops cannot be checked that way. Doubling every drop would add
under a point to any row.Three more errors, found by making the measurement:
--no-cache (E2’s correction)
also reached the build’s rustc wrapper, which then lowered the program a
second time (193.6 M). Counting that would have doubled the front end’s
share of a build. A person’s build hits the cache there, so §4.1 counts the
wrapper at its cache-hit cost.lower-std checks
the tool modules beside the 1 197-line tree. It is the only input here
whose shape resembles the compiler this road ends with, and it was the only
one where the answer flipped. A decision read only from the examples would
have been right for the wrong reason.TyThese are measured, not decided, and go to #122:
std.contracts is the largest single cost of every run: 80.6 M
instructions, 35–89 % of the front end. The build’s wrapper pays it again
on a cache hit. It is parsed from text on every run, and nothing is kept
between runs.n-body × 32, resolving a
symbol (a DashMap with SipHash, from lasso) takes 572 M of 2 918 M,
a fifth of the run, more than every Ty clone
together. The compiler already interns names, and an intern is only as
cheap as its lookup.Ty share is mostly Program::of (2.3 M in four calls) and a
BTreeMap<String, FnContract> consumed into another (1.9 M). That is work
that grows with std.contracts, not with the program.D3 answers: Ty moves as it is, a plain tree with a text form (P7 held).
The first condition fails everywhere in the corpus (at most 6.6 % broad after
§4.4). The second holds for an edit. Growth held within one program is flat
up to 3 724 lines of code.
The range this was measured on: units of up to 3 724 lines of code, runs of up to 1.65 billion instructions, programs written by the compiler’s authors, and no program with dependencies. Outside it, the answer is a guess, and it is reopened when any of these is seen:
Ty broad at or above 15 % in any report.py row, or rising by more
than a point per doubling in a scale.py series, after the growth has been
checked for a walk like §4.4’s.Ty at or above 5 %: the working set has
stopped fitting, which is Zig’s condition.The record, the measurement (§3–§4), and §4.4’s two fixes (0.0.283).
Step (b)’s first half, and the writing half of (c) (0.0.285):
tools/ty.nika declares Ty and Shape, the words a sequence carries, and
Ty::text, which is what a diagnostic prints and a ledger stores. The
compiler’s contracts::ty re-exports them, and what was impl Ty is the
trait TyOps beside it, since a crate cannot write an inherent impl for
another crate’s type. Display is five lines of Rust in nikaia-std that
call text, because the language has no Display to write it in. Three
things changed shape on the way, each in the language’s terms:
throws is a reserved word, so the field is can_throw, as ast::Code
already spells it.Fn’s result is a Ty?, which ADR-246 lowers to Box<Option<Ty>> where
the Rust had Option<Box<Ty>>. The readers follow.Shape has no Default (ADR-252 D4.4). Shape::none() names the same
value, and missing hands back owned words.The reading half of (c) (0.0.286): Ty::parse and split_args are
tools/ty.nika’s. The Rust parser was kept long enough to run both over
every type the two shipped ledgers write, the text of each read back, and
ninety-odd edge cases (ref mut, &[T], fn(a]) -> b, Seq[i64] sync
pauses, non-ASCII names): 989 inputs, identical.
What it costs, measured as §3 measures: this language has no slice of a
String, so every piece of a type’s text is a copy where the Rust sliced in
place. Reading std.contracts went from 90.96 M instructions to 95.46 M
after the obvious savings (one view marker read per type, no list of
characters where no bracket closes the text), which is 5.0 % of an empty
program and 2.3 % of json. Recorded rather than hidden: it is the first
measured price of a module moving, and a slice of text would give it back.
The ledger’s small records (0.0.289): Provenance, Sync, Lock,
Crosses, Threads, Touch, State, Held, Count, Class and the
field, variant and config entries are ty.nika’s, with the methods that say
them. Two things the Rust derived and the language does not give are written
where they are used, each as the value or the order the derive meant:
Default (Sync::No, Lock::No, Threads::Undecided, Crosses::Undecided,
Count::Atomic, and hand-written Defaults on the compiler’s own records),
and Ord, which only three places needed (a set of touches kept by kind,
parameter and access; classes sorted by members and Count::rank; join and
or as a match). The language question of an order on a declared type
stays where ADR-204 §4 left it. No ledger byte changes.
Signature, FnContract and TypeContract (0.0.290). Two fields
change name, because their words are reserved: FnContract.throws is
fails_with and FnContract.sync is sync_claim, and the ledger file keeps
its keys (throws = …, sync = …). A Default becomes empty(), the
constructor the Nikaia declares.
Ledger and Notes (0.0.291), which ends (b). The tables are
collections::BTreeMap and BTreeSet, so the file stays ordered. What the
compiler does with a ledger stays Rust behind LedgerOps until (c) and (d)
move it; the orphan rule that made TyOps makes every caller import it.
Reading a ledger back (0.0.292), which is (c): tools/ledger.nika
reads the file whole, with the records ty.nika declares beside it, and
Ledger::parse is one call. The reader is where the text lives, so it also
took what (b) left behind its *Ops traits: a touch, a view’s state, a
sharing class, a variant and a signature read back, and unspell. It was
measured before it shipped, because §4.6 found reading std’s ledger to be
most of an empty program: as first written it cost a third more than the
Rust, and as shipped it costs less (93.1 M instructions for an empty
program, from 95.7 M). The difference was the lowering and not the reader:
a list of a text’s characters is asked for at its size now, for every
Nikaia module.
What the checker asks of a type (0.0.295), which is (d): fits,
erase, parameterise, as_a_view, is_seen, unseen, is_a_view and
is_unknown are Ty’s methods in ty.nika, and bind, substitute,
qualify and renamed its functions. The compiler calls them as it did,
because a type’s own method is found before an extension trait’s. What stays
Rust is what cannot be Nikaia yet or is not worth it: the constructors from a
name (Ty::named takes anything that becomes text), base, which hands back a
slice of the name, and from_ast, which reads this compiler’s tree.
fits is asked at every argument, assignment and return, so it was measured:
an empty program, 1brc, n-body and k-nucleotide each lower within 0.2 %
of the instructions the Rust took (93.1 M, 186.8 M, 178.5 M, 177.1 M). The move
found a checker defect on the way: an element of a ref Array[T] was ?, so
a method on it was one nothing describes and the function around it became a
future; it is the item now.
All of D2 is built.
§4.6’s first finding, answered (0.0.296): reading std.contracts was
mostly reading it again. Seven places parsed STD for themselves, so an empty
program read it seven times; every reader now borrows the one parse, and an
empty program lowers in 22.8 M instructions, from 93.4 M. The other two
findings stay in #122.
The one parse, made cheaper (0.0.297): the reader is three grammars in
tools/ledger.nika that slice views out of the text instead of walking it as
Vec[char], and the costs that were the parser library’s were removed there
(winnow-grammar: a memo for the whitespace skip, first-byte guards on
alternatives, errors a hand-written rule builds only for the diagnosing
pass). Reading std.contracts is 5.9 M of an empty program’s 17.4 M, from
11.4 M of 22.8 M.