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. 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. 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. Here’s the technical journey from repeated, expensive structural checks to hardware-level integer comparisons. A compiler for a statically-typed, procedural language featuring explicit memory control and an LLVM backend. CLLVMCOMPILERS The Linear Bottleneck: O(N*L) 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?” The naive approach is a linear scan using strcmp against a list of known keywords: // Naive Lexer logic const char* keywords[] = { "fn", "if", "else", "while", "return", ... };

for (int i = 0; i < num_keywords; i++) { if (strcmp(token_string, keywords[i]) == 0) { return keyword_tokens[i]; } } strcmp(s1, s2) is O(L), where L is the string length. It must check every character until it finds a mismatch. Linear Scan is O(N), where N is the number of keywords. Total Cost: O(N * L) per token. 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. The Hashing Improvement: O(L) 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). // hash_map.c - Simplified insertion bool hashmap_put(HashMap* map, void* key, void* value) { // 1. Automatic Resizing (Load Factor > 0.75) if (map->size >= (map->bucket_count * 3) / 4) { hashmap_rehash(map, map->bucket_count * 2); }

// 2. O(L) Hashing: We must visit every byte to compute the hash. size_t index = hash_func(key) % map->bucket_count; DynArray *bucket = &map->buckets[index];

// 3. O(1) average lookup in bucket chain for (size_t i = 0; i < bucket->count; i++) { KeyValue *kv = dynarray_get(bucket, i); if (cmp_func(kv->key, key) == 0) { kv->value = value; // Update existing return true; } } // 4. Push new entry return dynarray_push(bucket, (KeyValue){key, value}); } 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. For a symbol reused 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). Interning shifts the cost to one phase, then reuses a canonical handle for nearly constant-time comparisons. The Foundation: Stable Memory (The Arena) 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. I use an Arena Allocator which manages memory in large contiguous blocks, providing two critical guarantees: O(1) allocation and Pointer Stability.

typedef struct ArenaBlock { struct ArenaBlock *next; // Pointer to the next block in the chain size_t capacity; // Total size of this block's data size_t used; // Number of bytes currently allocated uint8_t data[]; // The actual memory } ArenaBlock;

typedef struct { ArenaBlock *blocks; // Head of the block list size_t block_size; // Default size for new blocks } 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. void *arena_alloc(Arena *arena, size_t size) { if (!arena) return NULL; if (size == 0) return NULL; /* semantic choice */

const size_t align = alignof(max_align_t);

ArenaBlock *block = arena->blocks; if (!block) return NULL;

/* align the *offset*, not just the size */ size_t offset = align_up(block->used, align);

/* If not enough room in current block, allocate a new one */ if (offset + size > block->capacity) { size_t new_capacity = arena->block_size; while (new_capacity < size) new_capacity *= 2;

ArenaBlock *new_block = malloc(sizeof(ArenaBlock) + new_capacity); if (!new_block) return NULL;

new_block->next = arena->blocks; new_block->capacity = new_capacity; new_block->used = 0; arena->blocks = new_block;

block = new_block; offset = 0; }

void *ptr = (void*)(block->data + offset); block->used = offset + align_up(size, align); /* bump after alignment */ return ptr; } However, there is a catch: the “Un-freeable” Nature of Arenas. Arena allocators are perfect for batch compilers because you usually just drop the entire memory block at the end of compilation. But if this compiler is ever adapted to run as a long-lived Language Server Protocol (LSP) daemon, memory could balloon since arenas cannot free individual interned strings as files change.

Core Abstractions: Slice and InternResult Before looking at the interner itself, we need to define the two core data structures used to pass data around. Slice: A lightweight reference to a string or object. It doesn’t own its memory; it just points to a start and a length. This allows the Lexer to point directly into the source file buffer without copying. typedef struct { const char *ptr; size_t len; } Slice; InternResult: This is the canonical handle returned by the interner. key points to an arena-allocated Slice, and that slice points to the canonical byte sequence. You may create many temporary slices while lexing, but if two slices have the same bytes and length, they resolve to the same interned record. Entry stores the Dense ID and optional metadata (for example, token type). typedef struct { void *key; // Arena-allocated Slice* (points to canonical bytes) Entry *entry; // Metadata (Dense ID and metadata) } InternResult; The Dense Arena Interner: Buying O(1) Lookups Interning deduplicates data—whether that’s a string identifier or a complex type struct—so that only one “canonical” copy exists. The Dense part of this implementation refers to how we identify these objects. Instead of just using pointers, we assign every unique item a contiguous, zero-indexed integer (0, 1, 2…). The DenseArenaInterner uses the Hash Map to find existing entries and the Arena to store new ones. typedef struct { Arena *arena; // Where canonical data lives HashMap *hashmap; // Maps raw data -> InternResult* int dense_index_count; // Counter for the Dense ID (0, 1, 2...) } DenseArenaInterner; When we intern an item, we check the Hash Map. If it’s already there, we return the existing InternResult. If not, we copy it into the Arena exactly once and increment our dense_index_count. This ensures that if we’ve seen 500 unique objects, they are mapped to the integers 0 through 499. // dense_arena_interner.c - Simplified interning loop InternResult* intern(DenseArenaInterner *interner, Slice *slice, void *meta) { // 1.

O(L) Hash + O(1) Map Lookup InternResult *found = hashmap_get( interner->hashmap, slice, interner->hash_func, interner->cmp_func ); if (found) return found;

// 2. Create stable, arena-owned key and canonical bytes Slice *key_slice = arena_alloc(interner->arena, sizeof(Slice)); void *canonical_data = interner->copy_func(interner->arena, slice->ptr, slice->len); key_slice->ptr = canonical_data; key_slice->len = slice->len;

// 3. Assign the next Dense ID InternResult *res = arena_alloc(interner->arena, sizeof(InternResult)); Entry *ent = arena_alloc(interner->arena, sizeof(Entry)); ent->meta = meta; ent->dense_index = interner->dense_index_count; res->key = key_slice; res->entry = ent;

// 4. Update the map for future O(1) lookups hashmap_put( interner->hashmap, key_slice, res, interner->hash_func, interner->cmp_func );

interner->dense_index_count++; return res; } Lexer Integration: The Memory Win The lexer maintains two separate interners: one for Keywords and one for Identifiers. Startup: Bootstrapping Keywords. When the compiler starts, we pre-populate the keyword table. This ensures every keyword is already “canonical” and inside the hash map before we scan a single line of code. //

lexer.c - Initialization logic static const struct { const char *word; TokenType type; } KEYWORDS[] = { {"fn", TOK_FN}, {"if", TOK_IF}, {"return", TOK_RETURN}, ... };

for (size_t i = 0; KEYWORDS[i].word; i++) { Slice s = { .ptr = KEYWORDS[i].word, .len = strlen(KEYWORDS[i].word) }; // Store the TokenType as metadata directly in the Entry intern(lexer->keywords, &s, (void*)(uintptr_t)KEYWORDS[i].type); } Runtime: The O(L) Check. Now, when the Lexer scans a word, it uses intern_peek—a function that checks the keyword map without allocating new memory. // lexer.c - Identifier scanning static void *lexer_lex_identifier(Lexer *lexer, ...) { Slice slice = lexer_make_slice_from_ptrs(start, end);

// 1. Keyword check (O(L) hashing + O(1) pointer lookup) InternResult *kw = intern_peek(lexer->keywords, &slice); if (kw) { // It's a keyword! Pull the TokenType from the metadata. *out_type = (TokenType)(uintptr_t)kw->entry->meta; return kw; }

// 2. Not a keyword? Intern it into the general identifier table. *out_type = TOK_IDENTIFIER; return intern(lexer->identifiers, &slice, NULL); } What did we gain in the lexer? Crucially, we didn’t gain speed. Both a standard hash map and an interner are O(L) operations for the lexer. The win here is twofold: Memory deduplication: If return appears 500 times, we store it once instead of 500 times. Dense Indexing Generation: By assigning each identifier a contiguous Dense ID, we enable the later compiler phases—specifically the Scoping and Type Checking systems—to use these IDs for O(1) flat-array lookups. The lexer pays the O(L) “toll” to generate these IDs, but it is the rest of the compiler that cashes in on the performance.