Dense Arena Interning: The Engine of Compiler Performance | Systems Notes
Compilers spend a massive amount of time looking at names and structures. Every variable, function, and keyword in your source code is a string that needs to be identified, categorized, and resolved across multiple compiler phases.<br>The problem isn’t just matching strings or comparing type signatures—it’s doing it over and over again across the entire pipeline. The same variable name counter might be checked hundreds of times: initially in the lexer, again in the parser, repeatedly in the type checker, and throughout optimization passes.<br>I implemented a Dense Arena Interner to solve this by converting strings and structures into dense integers the moment they are created. We pay the hashing cost upfront during lexing or type construction. In exchange, every subsequent phase of the compiler gets to rely entirely on O(1) array indexing and single-instruction pointer comparisons.<br>Here’s the technical journey from repeated, expensive structural checks to hardware-level integer comparisons.<br>C3<br>compiler-v3
A compiler for a statically-typed, procedural language featuring explicit memory control and an LLVM backend.<br>CLLVMCOMPILERS
The Linear Bottleneck: O(N*L)<br>Imagine a Lexer scanning your code. It finds the characters f-u-n-c. It needs to know: “Is this a keyword like func or return, or is it a variable name?”<br>The naive approach is a linear scan using strcmp against a list of known keywords:<br>// Naive Lexer logic<br>const char* keywords[] = { "fn", "if", "else", "while", "return", ... };
for (int i = 0; i num_keywords; i++) {<br>if (strcmp(token_string, keywords[i]) == 0) {<br>return keyword_tokens[i];<br>} strcmp(s1, s2) is O(L) , where L is the string length. It must check every character until it finds a mismatch.<br>Linear Scan is O(N) , where N is the number of keywords.<br>Total Cost: O(N * L) per token.<br>If your language has 50 keywords and the average identifier is 8 characters, you’re doing roughly 400 character comparisons just to identify a single word. In a large project, this overhead becomes a massive anchor on performance.<br>The Hashing Improvement: O(L)<br>To improve this, we move to a Hash Map. Instead of checking every keyword, we compute a hash of the token and jump directly to the potential match. I use separate chaining with dynamic arrays for buckets. This ensures that even with collisions, performance remains stable. Hashing takes O(L) per lookup (with average-case O(1) bucket access).<br>// hash_map.c - Simplified insertion<br>bool hashmap_put(HashMap* map, void* key, void* value) {<br>// 1. Automatic Resizing (Load Factor > 0.75)<br>if (map->size >= (map->bucket_count * 3) / 4) {<br>hashmap_rehash(map, map->bucket_count * 2);
// 2. O(L) Hashing: We must visit every byte to compute the hash.<br>size_t index = hash_func(key) % map->bucket_count;<br>DynArray *bucket = &map->buckets[index];
// 3. O(1) average lookup in bucket chain<br>for (size_t i = 0; i bucket->count; i++) {<br>KeyValue *kv = dynarray_get(bucket, i);<br>if (cmp_func(kv->key, key) == 0) {<br>kv->value = value; // Update existing<br>return true;
// 4. Push new entry<br>return dynarray_push(bucket, (KeyValue){key, value});<br>} While O(L) is much better than O(N * L), we are still paying the hashing price every time we encounter that string in the Parser, Typechecker, or Optimizer. We need a way to phase-shift this cost away from all stages to just the Lexer.<br>For a symbol reused k times across later passes, the tradeoff is simple: without interning, repeated checks are O(k * L) ; with interning, you pay O(k * L) only in one phase and later passes become O(k) .<br>Interning shifts the cost to one phase, then reuses a canonical handle for nearly constant-time comparisons.<br>The Foundation: Stable Memory (The Arena)<br>To eliminate string comparisons entirely, we need to ensure that identical strings point to the exact same memory address . Standard malloc or realloc can move things around or scatter them, making pointer comparisons risky.<br>I use an Arena Allocator which manages memory in large contiguous blocks, providing two critical guarantees: O(1) allocation and Pointer Stability .<br>typedef struct ArenaBlock {<br>struct ArenaBlock *next; // Pointer to the next block in the chain<br>size_t capacity; // Total size of this block's data<br>size_t used; // Number of bytes currently allocated<br>uint8_t data[]; // The actual memory<br>} ArenaBlock;
typedef struct {<br>ArenaBlock *blocks; // Head of the block list<br>size_t block_size; // Default size for new blocks<br>} Arena; Allocation in an Arena is just “bumping” a pointer forward. Once a string is stored in an Arena block, its address never changes . This stability allows us to use the pointer itself as a unique ID.<br>void *arena_alloc(Arena *arena, size_t size) {<br>if (!arena) return NULL;<br>if (size == 0) return NULL; /* semantic choice */
const size_t align = alignof(max_align_t);
ArenaBlock *block = arena->blocks;<br>if (!block) return NULL;
/* align the *offset*, not just the size */<br>size_t...