Data-oriented design in a compiler's source: Krabby's interning and storage
I spent some time reading the source of Krabby, an experimental high-performance Rust compiler. It's explicitly a playground for compiler architecture — a roadmap for people who want to know how to design a fast compiler for a language as complex as Rust. The README says the goal is to show how to design a fast compiler; the source shows it. Three design decisions stood out to me as textbook data-oriented thinking: how identifiers are interned, how literal blobs are stored, and how tokens are laid out.
1. Identifier interning: one buffer, u32 offsets
Krabby's LocalIdentInterner keeps all identifier text in
a single String, and references each identifier by a
u32 offset into that buffer:
pub struct LocalIdentInterner {
ids: HashTable<IdentID>, // hash -> ID
offs: Vec<u32>, // ID -> byte offset into data
data: String, // all identifiers, concatenated
hasher: DefaultHashBuilder,
}
An identifier is stored exactly once. Lookup hashes the input,
finds an IdentID in the table, then slices the one
buffer to compare. The key move is that the data is one
contiguous allocation — good cache locality — and the offsets
are fixed-size integers, so walking them is cheap.
The ID type itself is worth noticing:
#[repr(transparent)] pub struct IdentID(pub NonZero<u32>);
NonZero<u32> means the zero value is a sentinel
"no ID" — an Option<IdentID> costs nothing extra.
This is the same trick rustc uses for its own interned IDs. Small
type, big payoff across a whole compiler.
2. Blob storage: IDs that encode their own address
Literals (string contents, numbers as text) are "blobs". Krabby deliberately does not deduplicate them — dedup costs more than it saves for literal data. Instead, the storage layout is clever:
//! IDs are split into the high 20 bits, specifying the index of the //! responsible chunk in the global list, and a low 12 bits, indicating //! the index of the blob in the responsible chunk.
So a BlobID is a single u32 that encodes
where the blob lives: chunk number in the top 20 bits, offset
within the 4096-slot chunk in the bottom 12 bits. Looking up a blob is
two arithmetic operations, no table walk.
The chunking also solves a concurrency problem: each worker thread allocates into its own chunk, so threads don't contend on a shared allocator. When a chunk fills up, a new one is appended to a global list. The comment in the source even sketches a future lock-free version using atomic tagged pointers.
3. Tokens: Copy, compact, interned
A token is two words:
pub struct Token {
pub kind: TokenKind,
pub pos: u32, // byte position in source
}
Strings never appear inline. An identifier token carries an
IdentID (a u32), a doc comment carries a BlobID
(a u32). The whole thing is Copy — no ownership, no
allocation, no indirection. A vector of tokens is a flat array that
the prefetcher can chew through.
Why this matters
Nicholas Nethercote's recent rustc performance work is the same lesson from the other direction. He's spent years shrinking AST expression nodes from 104 bytes down to 64 — small enough to fit in a cache line — and it keeps paying off in wall-time reductions. Krabby starts from that principle instead of arriving at it after a decade of profiling.
None of these three techniques is new. Interning, arena allocation, and compact tokens are well-trodden compiler ground. What Krabby does is apply them consistently from day one, with documentation explaining the why (cache locality, contention, address arithmetic). For someone studying how to build a fast compiler — which is literally the project's stated purpose — that documentation is as valuable as the code.
One caveat worth noting: Krabby is experimental and its license is the Keypunch Public License, not a common FOSS license. Read the license before borrowing ideas wholesale. But reading for understanding is free.
Filed after reading the Krabby source (git.sr.ht/~bal-e/krabby, latest commits July 2026). Quotes are from the actual source comments.