Notes for the Kalai maintainers. Both toolchains were built and run on one machine
(kalai 9a2066b9, rustc 1.83.0, icu4x a1123ac, Apple Silicon). Everything below is a
number produced there or a pointer into the source.
^:refon a parameter already emits&Tand works. What is missing is the&at call sites, and any analysis to decide where the annotation goes. Smallest change with the largest effect.- Making
:anya shared pointer instead of an owning box measures 2.05× on the transpiledsql_builderand brings the clone to parity with Temper. - The container boundary is untouched.
From<BValue> for Vectorstill copies its payload: 157,990 ns on 50k elements. - There is no
bit-and,bit-ororbit-shift-*anywhere, which blocks any trie, hash, codec or parser. - Two rules in
pass/rust/b_function_call.cljare dead and emit Rust that does not compile. Nothing checks the rule sets for this class of problem. - 65% of a transpiler run is JVM boot and namespace loading. AOT is 1.8× with byte-identical output.
Four lines of Clojure shaped like CodePointTrie::get, called once per code point:
(defn trie-get ^{:t :int} [^{:t {:mvector [:int]}} data ^{:t :int} cp]
(let [^{:t :int} i1 (quot cp (int 2048))
^{:t :int} b1 (nth data i1)
...]
(nth data i3)))
(defn scan ^{:t :int} [^{:t {:mvector [:int]}} data ^{:t :int} n]
;; while (< @i n) -> (reset! acc (+ @acc (trie-get data @i)))
...)The emitted body is good — native i32 arithmetic, a concrete Vec<i32>, no boxing, and
.clone() on an i32 is free. The loop does not compile:
error[E0382]: use of moved value: `data`
16 | acc = (acc + trie_get(data, i));
| ^^^^ value moved here, in previous iteration of loop
Adding ^:ref to the parameters fixes it with no compiler change:
| Annotation | Emitted signature | cargo build |
|---|---|---|
| none | data: Vec<i32> |
E0382, moved value |
^:ref on both functions |
data: &Vec<i32> |
compiles |
^:ref on the callee only |
data: &Vec<i32> |
E0308, expected &Vec<i32> |
The passing variant was checked against a hand-written restatement of the same walk at
n ∈ {1, 31, 32, 500, 2047}; outputs match. param-str in pass/rust/e_string.clj already
does the work:
(let [{:keys [mut ref]} (meta param)]
... (str (when ref "&") (when mut "mut ") (type-str param)))The third row is the gap. ^:ref reaches the signature, and the call site still emits
trie_get(data, i) with no &. There is no table of function signatures anywhere in the
passes, so an invoke rule has no way to know its callee wants a borrow.
Two pieces, in order:
- Call-site insertion. Collect
defnparameter annotations into a table; insert&when the callee wants a reference and the argument is owned. This makes hand-written^:refusable on real programs. Roughly a day. Cross-namespace calls are unmeasured. - Inference. Mark a parameter
^:refwhen the body only reads it. Multi-day, and it interacts with^:mut.
Limit. Tested on one shape:
:mvectorof:int. Behaviour with:anypayloads, maps, and parameters that are also^:mutis unmeasured.
pub type BValue = Box<dyn Value> becomes an Arc newtype. A newtype rather than a bare
Arc because Arc is not #[fundamental], so the impl From<BValue> for <foreign type>
blocks stop being legal under the orphan rule.
#[derive(Clone)]
pub struct BValue(pub std::sync::Arc<dyn Value>);Transpiled sql_builder, five queries, Criterion. 2.05× geometric mean, 1.65–2.56×
across cases, 95% CI ±0.10% to 0.35% of each point estimate, program output byte-identical.
| Case | before | after | |
|---|---|---|---|
| SELECT + WHERE (=) | 3,369.6 | 2,045.0 | 1.65× |
| SELECT + nested AND / < / = | 5,582.5 | 2,606.1 | 2.14× |
| aliases + nested WHERE | 8,827.8 | 3,443.2 | 2.56× |
| INSERT with 3 value rows | 7,045.3 | 3,123.0 | 2.25× |
| parameterized SELECT | 3,453.1 | 1,922.4 | 1.79× |
(ns per iteration.)
The semantic change: two BValues produced by cloning now share one value. Kalai builds a
value and then treats it as immutable, and the mutating operations it emits are on the
owning container, so no clone can observe another being modified. Worth agreeing to
explicitly before the code.
One rule to write down before it lands: reference counting cannot collect cycles.
Persistent structures are acyclic, so the only exposure is atom, and that is better
stated than discovered as a leak.
The clone itself drops from ~826,000 ns to 3.79 ns on 50,000 elements. Temper's equivalent measures 3.753 ns, so the two representations are now the same speed.
Clones arrive in bulk because the parameter is by value and the argument is a BValue.
From a one-line Clojure function:
// sql_builder/rust/src/sql_builder/core.rs
pub fn select_str(select: std::vec::Vec<kalai::BValue>) -> String {
return select.clone().iter().clone()
.map(|kalai_elem| cast_to_str(kalai_elem.clone()))
...
}
// and the caller pays again: select_str(std::vec::Vec::from(select))
// where that From impl is x.clone().0Downcasting is 157,990 ns on the same collection, four orders of magnitude above the clone beside it:
impl From<BValue> for Vector {
fn from(v: BValue) -> Vector {
if let Some(vector) = v.as_any().downcast_ref::<Vector>() {
vector.clone() // Vector(pub Vec<BValue>) — O(n)Copy-on-write (Arc<Vec<T>> + make_mut) is the cheapest fix. Its cost depends on
granularity:
| Build 10,000 elements | time | |
|---|---|---|
plain Vec |
5.85 µs | |
COW, make_mut hoisted per block |
6.07 µs | +3.9% |
COW, make_mut per push |
47.5 µs | 8.1× |
RwLock, guard held once |
8.27 µs | +41% |
Kalai emits block-structured collection literals, so the cheap form is what the codegen already produces.
Check before committing to it. One long-lived alias costs a single copy: 1.84 µs unique, 3.00 µs with a clone held throughout. Re-sharing between every mutation costs 923.6 µs. Whether
atomcodegen produces the re-share pattern is unmeasured, and it is the one thing that would spoil this route.
Related: :vector maps to rpds::Vector and shares; :mvector maps to std::vec::Vec and
copies O(n). ^:mut already carries the bit needed to choose between them at the point of
use.
Kalai has arithmetic and comparisons only. Tries, hashes, codecs and parsers all need shifts
and masks. Before writing rules, check what tools.analyzer actually emits — see below for
why.
pass/rust/b_function_call.clj:189-193 maps clojure.core/double and clojure.core/float
to x.is_type("Double"), treating coercions as type predicates. They sit among nine genuine
predicates (string?, vector?, map?, …), which is why they are easy to read past.
Running them shows the rules never fire at all. tools.analyzer inlines both coercions, so
what arrives is (r/invoke clojure.lang.RT/doubleCast ?x) and the (u/var #'double)
pattern does not match. The invoke falls through to the generic path and the backend emits
clojure.lang._rt/double_cast(x), which is not valid Rust.
pass/java/b_function_call.clj:126-130 has the identical dead rules; there the fallthrough
happens to produce valid Java.
Generalizing is the useful part. There are 56 s/rewrite blocks in the tree and about 38
invoke rules in each of the Rust and Java function-call passes. A script that extracts rule
heads of the form (u/var #'foo) and checks whether tools.analyzer ever emits that shape
would find every instance of this mechanically. About a day, finds bugs, changes no
behaviour.
Meander compiles a clause that can never fire without complaint, and so does core.match.
The precedent worth copying is Cranelift's ISLE, a term-rewriting DSL for instruction
lowering that ships an overlap checker: two rules overlap if some input could fire either,
and no two overlapping rules may share a priority. Turning it on there found rules that were
fully shadowed. Rule order in Kalai's passes is already an implicit priority, so that framing
fits better than the textbook pattern-matrix one.
A pass that propagates what a test implies into its branch: after (if (string? x) ...),
x is :string in the consequent, and ab_cast can skip emitting String::from(x) when
the narrowed type already matches. Users write this by hand today — every branch of
cast-to-str restates its cast — and the TODO lists "users need to specify a lot of typing
and casting" as known pain. An ergonomics fix that happens to remove a copy per branch.
Failure mode is "didn't narrow", which is the status quo.
Transpiling examples/ to Rust and Java |
ms |
|---|---|
| JVM boot + bare Clojure | 840 |
| loading Kalai's namespaces | 2,310 |
| all pass execution combined | 156 |
helper-fn-impl-strs |
280 |
AOT compilation is 1.8× on the whole run and 3.7× on namespace load, with byte-identical output. It is a build-config change, and it pins the Clojure version at build time. Eleven files is not evidence that this scales; measure on a large input before relying on it.
Nothing here has to be built. Kalai depends on meander and tools.analyzer.jvm; both ship
machinery for problems the docs record as open, and the pipeline requires neither.
s/rewrite (56 call sites), s/bottom-up (11), s/choice (6), s/match (2). Two of the
unused ones are immediately relevant.
s/trace logs each application, which is the affordance currently served by eight scattered
u/spy and cprint calls. And s/fix / s/innermost normalise to a fixpoint, which is
what c_condense.clj hand-rolls: its three operator rules exist to flatten (+ (+ a b) c)
and collapse to one rule under innermost.
strategy/epsilon.cljc:1124-1177 defines linear?, variable-preserving?, collapsing?
and duplicating? — the standard vocabulary for termination and confluence of a rewrite
system. There is no call site anywhere in the library's source or tests.
duplicating? is the one that matters: it is the property that makes a bottom-up rewrite
blow up, and b_function_call.clj:158-160 has a duplicating rule — the update case
mentions ?x and ?k twice each on the right. Wiring the four predicates into a dev-time
report over each pass's rule list is an afternoon.
clojure.tools.analyzer.passes/schedule takes passes annotated
{:walk :pre|:post|:any|:none, :after #{...}, :before #{...}, :affects #{...}}, computes the
transitive order, and in its own words returns a function "trying to compose together as many
passes as possible to reduce the number of full tree traversals."
deps.edn pins tools.analyzer.jvm; the source requires .jvm, .jvm.utils, .ast and
.passes.jvm.emit-form, never .passes. Meanwhile a_annotate_ast.clj:429-448 hand-orders
five full-AST prewalks including a deliberate duplicate:
(map #(ast/prewalk % normalize-t-in-ast))
(map #(ast/prewalk % propagate-types-from-bindings-to-locals))
;; TODO: this is here for a circular depedency,
;; between normalization and propagation,
;; but it doesn't solve [x 1, y x, z y] ...
(map #(ast/prewalk % normalize-t-in-ast))docs/Design.md spends about a hundred lines on three propagation directions — initial value
to binding, binding to initial value, binding to locals — and does not settle their order.
There is no right order. Types flowing down from a binding are an inherited attribute;
types flowing up from an initial value are a synthesized one; and
[v [], v2 v, v3 v2, v4 v3] is a dependency graph rather than a sequence. Demand-driven
evaluation with memoisation and cycle detection dissolves the class: declare the dependencies
and never write a pass order.
The design doc sketches this without naming it — "If we follow this binding info recursively
within the nested environment info ... our recursive navigation will subsume/replace the work
done in binding-to-local propagation entirely." Reference attribute grammars (JastAdd,
Silver) are the literature. In practice it is not a rewrite of a_annotate_ast.clj, it is a
change of interface for the handful of type queries it answers: from "a pass that has run" to
"a memoised function you call on a node".
pass/rust/c_condense.clj and pass/java/c_condense.clj are 27 lines each and differ only
in the ns line and the r/ versus j/ prefix. The TODO already names the fix: "make
shared passes apply for all target languages... a block is just a block, why bother with
r/block, j/block."
provider/data is 102 MB against 45 MB for all components including fixtures. Half of the
77k-line utils/ tree is zero-copy machinery: yoke, zerovec, zerotrie, databake.
The hot path is self.trie.get(ch) on a borrowed slice, walked as array indexes with
bit-packed values. Clone elision does not reach that; the data plane has to bypass the
transpiler.
The encouraging part is that the layout vocabulary is closed. Across the 165k-line component tree:
450 CodePointInversionList 269 CodePointTrie 174 ZeroVec 158 VarZeroVec
96 ZeroMap 49 LiteMap 40 PotentialUtf8
20 ZeroTrieSimpleAscii 5 ZeroMap2d 4 TinyStr16 ...
Twelve names, six that matter, top four at 83%. That set changes when someone invents a new
kind of table, not when Unicode adds a script. So it is roughly six more rows in the type
table at e_string.clj:63-81, which already holds about twenty. The test for whether
per-target code is acceptable: does it grow when the library grows? Per-API wrappers do.
A fixed vocabulary of layouts does not.
What the data plane needs is a byte buffer and one primitive, read a u32 at offset i, available natively in every target. For a declared schema on top, FlatBuffers or Cap'n Proto match the access pattern.
The argument that does not depend on speed: ICU4J and ICU4X ship different data formats today, which is duplicated work inside one organization. One declared layout means one blob for every target, which removes work rather than adding something to maintain. That also suggests translating logic from ICU4J, where the semantics are closest to Kalai's input language, while targeting ICU4X's data layout.
Kill criterion. If native data plus transpiled logic cannot get inside ~20% of ICU4X on one real kernel, profiled properly, the transpiler route does not reach "a small percentage of hand-written." That measurement has not been run and it should come before any of the ICU-specific work.
Two teams with opposite starting bets converged on the same Rust representation and the same open problems.
| Kalai | Temper | |
|---|---|---|
| apex / list type | Arc-wrapped :any |
List<T> = Arc<Vec<T>> |
| clone on that type | 3.791 ns | 3.753 ns |
would prefer Rc |
blocked: lazy_static needs Sync |
blocked: threading story unsettled |
| borrows | annotation only, no analysis | ~20 lines, closure capture only |
| read-only / builder split | no | yes, but the builder holds a lock |
| rules | ~200 meander rules | 3,816 lines of Kotlin |
| generated output | checked into the repo | golden strings in tests |
Where Temper is ahead is narrow: it splits the read-only type from the builder type, and it
decides clones from the type rather than the syntax. Its builder is Arc<RwLock<Vec<T>>>,
which costs it — on a build-then-share-then-read workload, 113.20 µs against 5.67 µs for
plain Arc<Vec> and 11.19 µs for an owning Vec. A builder does not need to be shared, so
it should not carry a lock.
Where Kalai is ahead is not narrow. Meander rules express in a few lines what costs Temper
hundreds of hand-written when clauses, and checking generated output into the repo turns a
codegen change into a reviewable diff of real Rust.
- Arena plus
i32handles. Attractive on paper: a handle isCopyso the move error cannot arise, cycles stop mattering, andlazy_static!is already emitted. Untested, and it would have to land as a Rust-backend lowering rather than a source change, since handles into arrays are worse than object references on the JVM. Only worth reaching for if^:refresists. - Columnar data formats (Arrow, Vortex, Lance, Nimble, BtrBlocks). Analytics lineage, access patterns three orders of magnitude coarser, and decode-on-access is wrong for a trie walk. Arrow's ~13 language bindings were the only real draw, and none of the newer formats has them.
- Transducers in the pipeline. The passes thread a single tree through whole-tree rewriters, so there is no sequence to fuse. A perfect fusion saves ~3% of a run.
- Optimizing the passes at all. 156 ms of 4,800. JFR shows no hotspot.
- Datalog-based borrow inference. Rust's own borrow checker is one (polonius, Souffle
plus
datafrog), so the shape is right, but it is a far larger machine than the read-only-parameter case needs. helper-fn-impl-strs. 280 ms and 37% of pipeline work, carrying its own;; TODO: can we remove this?. It string-replacesString::from("RUST-FROM-FN-i32")back intoi32::from, which makes it the most fragile thing in the repo.
- Syntax-directed clone insertion —
wrap-value-enum - The hand-ordered prewalks and the circular-dependency TODO
- The propagation-ordering discussion
- Meander's unused rewrite-system predicates (@
74de6b1) - The pass scheduler you already depend on
- ISLE's overlap checker, written up by its author
- Temper's list type (@
18c0cf03) - Temper's type-directed clone suppression
- Temper's escape analysis, ~20 lines
- Type-directed clone insertion (replace the
literal?test withis-copy?plus "never clone a call result"): −3.8% geomean, against a predicted 10–20%. Once elements are refcounted, the clone it removes isVec::with_capacityplus n increments. Correct, and not where the time goes. - The 50,000-element clone ratio scales linearly with the 50,000, so its size is a property of the harness. The end-to-end figure is the one to quote.
- Golden-string tests do not show that emitted Rust compiles. An early version of the clone-insertion change passed every new golden and emitted code that panicked. Kalai has no test category that compiles emitted Rust; adding one is about half a day, and both items in §1 need it.
- Criterion A/B: re-record the comparison point rather than reusing a stored baseline, and keep a case in each run that cannot have changed. A stored baseline here had drifted 6% while another in the same directory had not.
Built and run under mise (rust@1.83.0, java@temurin-21, clojure@1.12.5,
gradle@8.10.2) on Apple Silicon. Kalai's committed Rust output compiles and runs, and its
Java output agrees byte-for-byte on all five SQL examples. End-to-end figures are Criterion;
the cross-project clone comparison is a small Rust program linking both runtimes. Everything
in §1 is reproducible from the four-line probe.
Produced by Claude (Anthropic) for Emmanuel Oga, August–September 2026. Corrections welcome.