The compiler's salsa architecture

What is tracked, at what granularity, and what that means a recompile does.

This is the map. salsa-patterns.md is the rulebook -- why things are shaped this way and the mistakes that are easy to make. The phase narrative is in compiler-guide.md.

Every number here is generated, not remembered. A hand-written inventory of 127 tracked functions rots within a session; the one that used to live in the compiler guide listed fifteen and was six queries and one signature out of date when it was found. Regenerate with:

cargo run --release -p datalove-bench --example query_census

which compiles the system library plus a local module and prints what ran for a cold compile, two unchanged recompiles, an edit to your own module and an edit to the bottom of the system library, then every query that kept a memo and how many it kept. The figures below are that output for 26 modules.

The counts in the next table are a source scan rather than a database one, so they come from a different command -- and they had drifted to 60 here and 59 in salsa-patterns.md before this was written down:

python3 -c 'import pathlib,re
k={"interned":0,"input":0,"struct":0,"fn":0}
for p in pathlib.Path("crates").rglob("*.rs"):
    L=p.read_text().splitlines()
    for i,l in enumerate(L):
        m=re.match(r"\s*#\[salsa::(interned|input|tracked)",l)
        if not m: continue
        j=i+1
        while j<len(L) and re.match(r"\s*#\[",L[j]): j+=1
        st=re.match(r"\s*(pub\S*\s+)?struct\b",L[j])
        k[m.group(1) if m.group(1)!="tracked" else ("struct" if st else "fn")]+=1
print(k)'

The databases

The compiler's is datalove-datafun-compiler/src/lib.rs:

#[salsa::db]
#[derive(Default, Clone)]
pub struct Database { storage: salsa::Storage<Self> }

It implements DbClone, so a clone shares Arc<Zalsa> -- the memo state -- and gets its own thread-local. That is what the rayon paths hand to workers. Database::recording(recorder) returns one that reports every query it runs, and clones report to the same recorder, so work farmed out to rayon is visible.

bcts, datalove-datalit and the datalove facade each declare a plain salsa database of their own. Compiler work uses the datafun one, re-exported as datalove_datafun::Database.

What there is

The two structs with a tracked field, and why

A tracked struct's identity is a hash of its untracked fields. A #[tracked] field is read through an edge of its own, so it can change while the identity stays put -- and every read of one is a dependency edge salsa must walk when it validates a memo. That is the whole trade, and it is measured both ways in salsa-patterns.md. Only these two earn it:

ExprFun, TypeFunction and ExprFunctionCall used to be on this list and are not: expressions, signatures and call sites are read whole by consumers that are keyed per module, so the fine grain cost edges and bought nothing. Untracking them was worth 2.6x, 12% and 12% of a 512-module edit. Expressions and call sites have since stopped being salsa structs at all: they live in a per-body arena, and an ExprFun is a handle into it. StmtFun was on it too, its signature and body tracked apart so that name resolution could read one without the other; it is plain data now, and the parse firewall is module_items, a query that leaves the bodies out. See plan-plain-ast.md.

The call site one needed a fixture with calls in it to see. The synthetic world in recompile_profile is arithmetic and has none, so it reported the change as free; the effect only appears once the program actually calls functions. That is worth remembering before concluding that a change to the AST does nothing -- check that the fixture contains the thing being changed.

The queries, by granularity

Granularity is the number of memos a query keeps, and it is the thing to know about a query, because it says what the query is allowed to depend on. The compile_scaling_tests suite holds exactly that: a query must not depend on anything finer-grained than its key.

One memo: keyed on the graph or the world

These re-run whenever anything they read moves, which is most edits. They may look at each module; they must not look at each function.

A handful of memos: keyed on a phase's arguments

One memo per module: the per-module passes

These are where the work is, and they are what an edit is supposed to re-run exactly one of. They may look at their own module's functions; they must not look at the rest of the world -- which is what reachable_func_ids is for.

parse, lex, bracer, parse_module_full, parse_module_ast, resolve_module_names, resolve_module_imports, module_import_demands, typecheck_module, analyze_module, module_const_kinds, lower_module_functions, module_shape_inputs, shape_closed_module, merge_lowered, module_has_comptime_calls, ctfe_module_units, lower_module, module_code_units, reachable_func_ids.

Some keep more than one memo per module -- lower_module_functions keeps one for the first lowering and one per batch of functions waiting on a const, and reachable_func_ids keeps one per module per graph shape it has seen.

resolve_module_imports belongs here and only recently did. It was keyed on gathered maps of every module's exports and function ASTs, whose identity is a hash of the lot, so a signature edit anywhere gave it a new key for every module in the world. It asks resolve_module_exports of the modules its own module requires instead, so what reaches it is the dependency graph rather than the world. The section below on what the suites do not hold says why nothing caught that.

What a recompile does

Measured on the system library plus one local module, 26 modules:

The two edits costing the same is the point and not a coincidence: what an edit pays for is the per-module work for the module that changed plus the graph-keyed passes, and which module changed does not enter into it.

The 19 are: the edited module's parse/lex/bracer chain, its typecheck_module, analyze_module, lower_module_functions, module_shape_inputs, lower_module and so on -- one each -- plus the graph-keyed passes that must re-run because one of their inputs moved. Nothing runs per unchanged module.

It was 28 while the rider interfaces were built inside parse_module_graph, which re-ran on every edit. That meant the rider's own source was re-lexed and re-parsed each time -- the second parse, lex_chunk, bracer and source_map in the count -- and it built the rider's Source with Source::new on each pass, so a compile leaked an input per rider, inputs never being collected. rider_interfaces is keyed on an interned RiderSources now, so it happens once per distinct rider source.

An edit costs the same whatever the world size. Seventeen queries at 8 modules and seventeen at 64 in the synthetic fixture; the 28 above is larger only because the system library has riders and consts. What still grows with the world is the validation walk -- salsa checking each memo is still good -- which is inherent while the graph-keyed passes ask about every module.

The invariants, and where they are held

What none of them hold

• Aggregates are invisible to the memo-size tests, interned or tracked. Widening ReachableFuncIds to the whole world was tried against them and passes, because an interned value is one dependency however much it aggregates. The same held for AllModuleExports, a tracked struct whose identity hashed every module's exports: it sat in resolve_module_imports' key and cost eleven of twenty-five modules a full re-typecheck on any signature edit, and every memo-size test passed throughout. What sees this is asking how far downstream an edit travelled, which is what import_memo_tests does and what nothing did before.
• Dependency-edge counts are not measured directly, so the #[tracked] decisions rest on the memo-size proxy. Re-adding #[tracked] to ExprFun::expr, when expressions were tracked structs, cost 2.6x at 512 modules and passed everything.
• Durability is not observable through salsa events; see durability_tests' own header.
• Wall-clock anything. The suite says what runs and what a run depends on. It does not say what a run costs. Profile before believing a change is free.