 |
MimIR
MimIR is my Intermediate Representation
|
|
MimIR
MimIR is my Intermediate Representation
|
A note on the cost of reimplementing MimIR in OCaml, Scala, or Haskell.
All sizeof/offset figures were measured against build-release (-march=native -O3 -DNDEBUG -std=gnu++23 -DFE_ABSL, gcc). Timing figures appear in exactly two places — Patricia::Set measured against OCaml's patricia-tree and the container note under absl::flat_hash_* — and are marked as measurements; everything else in this document is an estimate and is marked as one. Code is referenced by file and symbol name rather than line number, so the references do not rot.
This document answers a recurring question: Why not use an academically more acclaimed language?
The short answer is that MimIR's core data structure is a mutable, hash-consed, cyclic graph of hand-packed 72-byte nodes, and none of those languages has an idiomatic form of that structure.
Slowdown and memory growth relative to the current C++ implementation, for a faithful reimplementation of the same architecture. Treat these as ±50%; the ordering is far more robust than the magnitudes.
| Language | Imperative subset | Idiomatic | Memory |
|---|---|---|---|
| OCaml (flambda) | 2.5–3.5× | 5–10× | 2.5–3.5× |
| Scala/JVM | 2.5–3.5× steady state 3–10× on short CLI runs | 5–12× | 3.5–5× |
| Haskell (GHC) | 3.5–6× | 8–20×, wide error bars | 3.5–5× |
The imperative subset column assumes mutable records, IORefs, and mutable hash tables throughout — i.e. writing C++ with a garbage collector. That concedes the entire premise of switching: you pay the full syntactic and tooling cost and collect none of the benefit. The idiomatic column is the honest comparison, and it is much worse.
Exactly one of these numbers has an anchor under it. Patricia::Set has been run head-to-head against a real OCaml implementation of the same structure, and on the operation MimIR actually leans on — merge, in the free_vars inner loop — it came out 2.6–8.6×, inside the OCaml row above. Other operations on that structure range far wider, up to 46×. One structure is not a port, so the table stays an estimate; it is simply no longer an unsupported one.
World::unify (include/mim/world.h) probes the sea of nodes on every Def construction. This is the hot path of the whole compiler.
absl::flat_hash_set is a SwissTable: one control byte per slot holding 7 hash bits, probed 16-at-a-time with SSE2/NEON, payload stored inline in a flat array. A lookup is typically one cache miss. GIDHash (include/mim/util/gid.h) makes it cheaper still — the hash is the already-computed dense u32 gid, so hashing costs nothing.
What the alternatives offer:
Call it 2–4× on the hash-cons probe alone.
One measurement isolates that container, same language and same workload: building fe::Patricia's node pools out of std::unordered_set — separate chaining over heap-allocated nodes, structurally what OCaml's Hashtbl is — instead of absl::flat_hash_set costs 1.8–3.1× at 65,536 elements, on construction, merge and diff alike. Nothing else differs between the two builds, so that factor is the table and only the table. One case regressed — sparse intersect, whose result is small enough that pool traffic barely registers, came out 1.1× slower — which is the expected shape: the win is proportional to how much of the work is probing. It lands at the bottom of the 2–4× estimated above, which is the honest reading: take the low end.
Also lost: fe::Vector = absl::InlinedVector<T, N> (submodules/fe/include/fe/vector.h), which keeps small op-vectors in the object with zero heap traffic. None of the three has an equivalent, so every temporary DefVec becomes a heap allocation.
Def::vars_ and Def::muts_ are sets of Var*/Def*, hash-consed by fe::Patricia (submodules/fe/include/fe/patricia.h) so that equal sets are pointer-equal. A set is a single uintptr_t with two tag bits:
Null | Uniq (D* inline) | Arr (arena FAM, ≤ N entries) | Br (branch)
An untagged word is the D* it holds, which is why every Def must be at least 4-byte aligned.
Consequences:
In OCaml a 4-constructor variant with payloads is 3 boxed blocks plus 1 immediate; in Haskell the same plus a thunk per constructor; on the JVM four classes and a megamorphic call site. Pointer tagging is reachable only via Obj.magic or Unsafe, at which point you have left the language.
Patricia::Arr is a C99 flexible array member (size_t hash; uint32_t size; Entry entries[];) placement-newed into arr_arena_ — not even portable C++. Elsewhere it becomes a record plus a separate array object: two allocations, an extra hop per element access, and on the JVM a second 16-byte header.
This is also the one structure where a functional formulation does not lose: a Patricia tree is persistent by construction, and MimIR's is the Okasaki and Gill formulation an ML programmer would write. What C++ buys here is the representation, not the algorithm — the tag bits, the flexible array member, and the arena the nodes are bump-allocated into.
That last claim is testable, because the structure exists in OCaml. patricia-tree (Lemerre and Lesbre) is the same Okasaki-Gill Patricia tree, and its MakeHashconsedSet functor hash-conses it so that equal sets are physically equal — the same guarantee fe::Patricia provides. It is a careful implementation by people who care about this structure, which is what makes it worth measuring against.
Both sides run the identical workload: the same splitmix64 stream and the same Fisher-Yates shuffle, so the id sets are bit-identical, and an element is a pointer to a heap object carrying the id on both sides. Four set sizes (16 to 65,536) over dense and sparse ids, steady state. The C++ side is built -DFE_ABSL throughout — the configuration MimIR actually ships, and the one the container note above is about.
Ordered by how much MimIR leans on each, since that matters more than the headline number:
| Operation | Where MimIR uses it | vs MakeHashconsedSet |
|---|---|---|
| merge | the free_vars inner loop — by far the dominant call | 2.6–8.6× faster |
| insert/erase | free_vars (user registration, FV(λx.e) = FV(e) \ {x}), Nest | 2.2–46× faster |
| has_intersection | Def::has_free_vars_in | 3.5–23× faster |
| iteration | walking local_muts() | 8.3–29× faster |
| contains | scattered | 1.8–16× faster |
| intersect/diff/subset_of | not on any hot path | 2.1–19× faster |
| bulk create | never called | (12–173×, and irrelevant) |
| peak RSS at n=65,536 | 3.8–6.1× smaller |
The honest headline is therefore the 2.6–8.6× on merge, not the eye-catching create figure: Def::free_vars unions its operands' free-var sets in a loop, and that single call dominates every other use of the structure. It also sits squarely inside the 5–10× the ballpark table estimates for idiomatic OCaml, which is mild corroboration that the table is not wild.
The gap tracks the representation, exactly as the section above predicts. Arr packing up to N=8 entries into one contiguous node flattens the bottom three levels of the trie — that is where the iteration and lookup numbers come from, since patricia-tree carries one leaf per element all the way down. Entry caching the id beside the D* removes a pointer chase per comparison. Uniq means a singleton allocates nothing at all.
Where the OCaml gap comes from is the load-bearing part. It is not the trie. patricia-tree's own non-hash-consed MakeSet builds 5.8–48× faster than its hash-consed one, so almost the whole gap sits in the hash-cons layer rather than in the Okasaki-Gill algorithm the two implementations share. That layer is Weak.Make: every node creation is a weak-hashtable merge, and the GC must scan those buckets.
A port does not get to opt out of it. Hash-consing is what makes Def::vars_ comparable in O(1), and World::unify is the same bet at the scale of the whole sea of nodes — so a set library without physical equality is not implementing the same thing, which is why the table above is against MakeHashconsedSet. The weak table is therefore not an unlucky choice by that library; it is what hash-consing costs when dead nodes have to be reclaimed by a garbage collector. MimIR's arena declines to reclaim them and rewinds the bump pointer instead — Speculative construction with arena rollback, turning up as a measurement rather than an argument.
The one caveat that genuinely weakens the numbers: they are pessimistic for OCaml against the ballpark table above, which assumes flambda. The switch measured was ocaml-base-compiler.5.4.0 without it.
The scope is one structure against one library. It says nothing about Haskell or Scala, nothing about the 72-byte Def layout, and nothing about a full port — it is one anchor under one row of one table.
sizeof(Def) is 72 bytes — measured against build-release (-march=native -O3 -DNDEBUG -std=gnu++23 -DFE_ABSL). The only slack is the u32 next to dbg_, which the Debug-only curr_op_ occupies — so a Debug build is 72 bytes too:
| off | field | bytes |
|---|---|---|
| 0 | normalizer_ / axm_ / var_ / binder_ / world_ (union) | 8 |
| 8 | flags_ | 8 |
| 16 | curry_, trip_ | 1 + 1 |
| 18 | node_ | 1 |
| 19 | mut_:1 external_:1 annex_:1 dirty_:1 dep_:4 | 1 |
| 20 | mark_ | 4 |
| 24 | gid_ | 4 |
| 28 | num_ops_ | 4 |
| 32 | hash_ | 8 |
| 40 | vars_ | 8 |
| 48 | muts_ | 8 |
| 56 | dbg_ | 4 |
| 60 | curr_op_ (Debug only) | 4 |
| 64 | type_ | 8 |
| total | 72 |
Three deliberate optimizations produce that number, and none of them survives a port:
World::allocate (include/mim/world.h):
So every subclass is layout-identical — App, Lam, Sigma add methods, never data — and one bump-pointer allocation covers header and operands. op(i) indexes off this + 1: no second object, no header, no indirection.
In OCaml every field is a tagged word and bitfields do not exist; on the JVM sub-word fields cannot be packed at all, and the object header alone is 12–16 bytes before a single field. A faithful port lands around 120–140 bytes per node plus a separate operand array with its own header — roughly 2–2.5× on the node before any allocator or GC effect.
One place where the gap narrows, in fairness. Dispatching by switch on a 1-byte tag is precisely what an ML pattern match compiles to. By dropping virtual dispatch, MimIR has converged on the functional languages' dispatch strategy rather than C++'s, so this particular optimization is roughly neutral in a port — OCaml and Haskell would get it for free and more legibly. The saving is the vptr, not the dispatch.
This one has no counterpart anywhere — World::unify:
The node is constructed speculatively — normalizer run, hash computed, free vars computed — then probed against the sea, and on a hit it is un-allocated and the gid counter rolled back. In a normalizing hash-consed IR the hit rate is high by construction, so the common path costs zero net allocation and produces zero garbage.
Patricia::leaf/arr/br do the same for set nodes: construct into the arena, probe the pool, and rewind on a hit. One arena per node kind is what keeps that rollback LIFO.
In fairness, a generational nursery handles short-lived garbage well — copying cost is proportional to survivors, so the dead speculative Def is nearly free to collect. The cost is the compounding: high nursery churn forces frequent minor collections, and each must scan a remembered set that is enormous here, because MimIR constantly mutates old-generation Defs — set(), the users set in muts_, and mark_ sweeps in free_vars(). Every one of those is an old→young pointer write paying caml_modify or card-marking. High churn × large remembered set is the bad quadrant.
RWPhase's world-swap is the same trick at macro scale: drop the whole old World and its arenas in O(1), with no tracing. A GC has to prove the old world is dead by walking it.
An immutable graph cannot have back-edges, and MimIR's IR is cyclic by construction — mutables reference themselves for recursion, and muts_ doubles as the users set. Idiomatic functional style has two answers, both bad here:
And since the store is persistent, every rewrite path-copies it. RWPhase currently drops an arena in O(1); idiomatically it allocates a new HAMT spine per touched node.
The sea of nodes is a mutable global table. The pure alternatives are a State World monad threaded through every constructor — so Def construction returns a new world and the HAMT insert cost lands on every node — or unsafePerformIO over a global IORef, which is what actual Haskell hash-consing does and is not idiomatic.
vars_, muts_, mark_, dirty_, and tid_ are mutable memo fields on nominally-immutable Defs. Idiomatically they become separate memo maps keyed by id — another lookup per access — and the invalidation currently free from dirty_ has to be threaded explicitly.
Laziness and hash-consing are directly opposed: hash-consing requires forcing at construction, so Def ends up !-annotated throughout. You would be writing strict Haskell with lazy Haskell's tooling and space-leak failure modes.
Every serious compiler written in these languages breaks idiom at exactly the point where MimIR is most demanding:
The pattern is a revealed preference: as soon as a real compiler in these languages needs what MimIR needs, it either abandons idiom or abandons the design.
The ADT-plus-exhaustive-matching payoff is largest for a tree-shaped, closed-ADT, non-hash-consed IR. MimIR is a graph-shaped, open-node-set, hash-consed IR whose node set is extensible at runtime by dlopen'd plugins, with terms and types in one graph because dependent types make a closed ADT impossible in the first place. match d with App (f, a) -> ... buys almost nothing over if (auto app = d->isa<App>()) when the node set is open anyway. Those are nearly opposite design points: you would pay the full idiomatic tax on a design that collects almost none of the idiomatic dividend.
MimIR's current performance problems are not constant-factor problems. RWPhase rebuilds the entire world per phase, PhaseMan iterates to fixpoint, free vars are re-derived via mark_ sweeps. Those are algorithmic, and a 2× language penalty is noise beside traversing the world N times. This is not an argument that the language does not matter — the penalty is multiplicative on top of the algorithmic cost, not an alternative explanation for it. The sharper point is that a tracing GC removes entire classes of fix from the toolbox: when you profile and decide to stop allocating, the fixes you reach for are rollback-on-hit, in-place mutation, and arena-scoped scratch — exactly the three things OCaml, Haskell, and Scala cannot express.
At the idiomatic end the question is arguably ill-posed. Nobody would write MimIR's IR that way; they would write a different IR — tree-structured Core with a Map-based store — and then the comparison is about IR design, not language throughput. A persistent world does buy real things: free structural sharing across phases, trivially correct speculative rewriting, RWPhase as a no-op. MimIR obtains those from arena-drop and world-swap instead, at a fraction of the cost.
Everything above is recoverable: Bigarray plus Obj.magic in OCaml, MutableByteArray# plus manual offset arithmetic in IO for Haskell, sun.misc.Unsafe or Panama MemorySegment on the JVM. That lands somewhere around 1.3–1.5×.
But look at what you would be writing: manual offset arithmetic into a byte array, hand-rolled pointer tagging, an unsafe-cast class hierarchy, a mutable splay tree in IO. That is strictly worse ergonomics than the current C++, and you have given up ADTs, exhaustive matching, and type safety — the entire reason to switch.
MimIR's core is not idiomatic C++ either. It is written in the systems-programming subset: flexible array members, placement new, tag bits, intrusive CRTP, arena rollback, hand-packed layout. Those languages do not have a worse version of that subset; they do not have it at all.
Rust is the only language on the list that offers the same systems-programming subset, so it deserves a separate answer.
The honest reason is historic. MimIR descends from Thorin, which was C++ from the outset, years before Rust 1.0 was a plausible choice for a compiler framework — and the surrounding ecosystem (LLVM, and the C++ literacy of everyone in a compilers group) pointed the same way. That is a perfectly good reason for how we got here. The interesting question is whether the technical case would justify moving, and it does not: the gain is close to zero and the losses are concrete.
Estimate: 1.0–1.3×, i.e. within noise of the C++ — but only via a design that gives up most of what makes the current implementation tight.
A mutable, cyclic, aliased graph is the one area Rust is known to be awkward at, and the standard advice for graphs in Rust is exactly the workaround: stop using pointers and use arena indices. That advice is not folklore; it is what Rust compilers actually do. rustc interns types into arenas and threads &'tcx references and rustc_index::IndexVec indices everywhere. Cranelift indexes everything through cranelift-entity. egg hash-conses e-nodes behind u32 ids and a union-find. None of them builds a pointer-linked mutable graph.
Index-based arena Rust is a legitimate design and would perform fine — an index is a bounds-checked load, not a hash lookup, so unlike the OCaml/Haskell case there is no asymptotic loss. But it is a different implementation, and each of MimIR's five load-bearing structures pays something:
The Rc<RefCell<Def>> design that a newcomer would reach for first is the one option that is clearly worse: refcount cycles leak by construction — and in a sea of nodes with muts_ holding back-edges there is no spanning tree to make Weak, so there is no principled place to break them — plus a runtime borrow check on every access, whose failure mode is a panic rather than a compile error.
Not nothing, and worth stating plainly:
This is the decisive practical point, because plugins are core architecture, not a peripheral feature.
MimIR loads dlopen'd modules exporting mim_get_plugin, which register normalizers as raw function pointers stored inside the Def union. Rust has no stable ABI. Every plugin would have to be compiled with the exact same rustc version as libmim, or the entire interface reduced to extern "C" shims with #[repr(C)] types on both sides — losing the very type safety that motivated the move. C++ already has friction here (absl containers must not appear in types that cross the dlopen boundary), but "keep `absl` out of the interface" is a much smaller constraint than "no stable ABI exists".
Roughly performance parity, in exchange for an unsafe core that reimplements the flexible array member and the tagged pointer by hand, a rollback pattern the borrow checker is specifically designed to reject, and a materially worse plugin ABI story — against real wins in build tooling, future parallelism, and unsafe-checking.
For a new project with these requirements the choice would be genuinely close, and the thread-safety argument might well decide it. For an existing, working, tuned implementation, that is not a trade that pays for itself.
MimIR's IR is a mutable, hash-consed, cyclic graph of hand-packed 72-byte nodes with zero padding and no vtable pointer. That is not a data structure those languages have an idiomatic form of — and every compiler written in them that needed one wrote imperative code to get it.
Rust is the only entry on the list that offers the same subset, and there the answer is parity rather than a win — see What about Rust? above. The reason MimIR is in C++ is historic; the reason it stays there is that nothing on offer would pay for the move.
1.18.0