Symbol Table Layouts and the Cost of Leaving a Scope

The resolver described in Resolving Identifier Uses Against a Stack of Lexical Scopes needs two operations on its environment: insert a name, and look a name up from the innermost scope outward. A hash map per scope satisfies both. What it does not satisfy is the third operation the compiler actually performs constantly — discarding an entire scope — and the cost of that operation is what separates a toy resolver from a symbol table that survives a real program.

The operation nobody counts

Entering and leaving scopes is not rare. A function body, every block inside it, every for loop header that declares its own induction variable, every pattern match arm with bindings, every lambda, every catch clause introduces a scope. A large translation unit contains thousands of them, and the compiler visits each twice.

With one dictionary per frame, leaving a scope means dropping the dictionary. If the frame was allocated per scope, that is a deallocation; if the frame was a plain object in a garbage-collected host language, it is nothing at all. The design looks free, and in a memory-managed implementation it nearly is.

The costs sit elsewhere. Each frame is a separate hash table with its own bucket array, so a program with deep nesting holds many small tables, each sized for a handful of entries, each with a fixed overhead of a header and a bucket array. A table sized for 8 entries still occupies a few hundred bytes. Ten thousand scopes of that shape is megabytes of mostly empty buckets, and the lookups that walk outward touch a different cache line per frame.

The alternative inverts the trade: one global table for the whole compilation unit, with each entry tagged by the scope it belongs to, plus a per-scope list of the names inserted into it. Lookup becomes a single hash probe plus a check that the found entry is visible; scope exit becomes a walk over that scope’s name list, removing entries. The removal walk is the cost that the per-frame design avoided, and it is why the two designs are genuinely different rather than a matter of taste.

Shadow stacks: one table, versioned entries

The cleanest version of the single-table design does not remove entries at all. Each slot in the table holds a stack of bindings for that name, and each binding records the scope depth at which it was pushed. Entering a scope that declares x pushes a new binding for x; leaving the scope pops it.

Lookup hashes the name once, finds the entry, and reads the top of that entry’s stack. If every scope pops exactly what it pushed, the top is always the innermost visible declaration and no scan is needed; the depth recorded with each binding is then a consistency check rather than part of lookup, and a mismatch means a push or pop was missed. A scan down the stack is needed only in designs that deliberately keep bindings past scope exit, which is what a compiler does when it retains the table for a later query or caches one per function body instead of rebuilding on each pass.

The advantage is that the hash is computed once per use and the table’s bucket array never changes size during the walk. Insert and pop are both O(1). Memory is proportional to the number of live bindings, not to the number of scopes: a frame with no declarations costs a stack entry for the depth, nothing more. The bucket array is sized for the total number of distinct names in the unit, which is a number the compiler can estimate from the source and which grows slowly.

The disadvantage is that removing a binding requires knowing its name. That is fine when the scope exit is driven by the same code that pushed the bindings, but it complicates any design that wants to free a scope’s storage wholesale. It also means a stale binding can be observed if the pop is skipped, so the pop must be unconditional and ordered — including on the error path, where a resolver that returns early on a malformed declaration leaks the frame and silently changes the meaning of every later lookup in the unit.

Sizing, hashing, and the constant factors

Symbol tables are usually small. A single function has tens of names; a large source file has hundreds to low thousands of distinct identifiers in scope at any point. At those sizes the difference between a good and a mediocre hash function is smaller than the difference between one memory access and two, and the difference between an open-addressed table and a chained one is dominated by allocation behaviour rather than by probe counts.

Open addressing — linear probing over a single array, with a load factor kept below roughly 0.7 — has one allocation, stores entries contiguously, and needs no per-entry pointer. Chaining needs an allocation per collision but tolerates deletion without tombstones. For a symbol table that is built once and read many times, open addressing wins on cache behaviour: a probe sequence touches consecutive slots in one array.

Deletion is the wrinkle. Open addressing with linear probing cannot simply clear a slot, because clearing it breaks the probe chain for any key that was displaced past it. The usual fix is a tombstone marker, which accumulates and degrades probe length unless the table is rebuilt. A shadow stack sidesteps the problem: entries are never deleted, only pushed and popped, so the array stays dense and tombstone-free.

String interning changes the arithmetic more than either layout choice. If every identifier is interned to a single canonical pointer, a name comparison is a pointer comparison and the hash can be computed once at intern time and stored with the interned string. Without interning, every lookup hashes the characters of the name and compares byte strings on a hit. For a compilation unit with tens of thousands of identifier occurrences, the hashing work is measurable but not dominant; the pointer-chasing through frames usually is.

Names that are not in the lexical table

A symbol table built purely from lexical scope is incomplete, because languages carry names that are not declared in the program text.

Predeclared names — built-in types, true, false, the standard library’s top-level bindings — must be resolvable without a declaration. The usual implementation seeds the outermost frame with them, which costs one frame construction and makes the resolver uniform: everything is a lookup. A language with hundreds of built-in types pays for that seeding in every compilation, so implementations instead check the predeclared table only after the lexical walk fails, turning a hit into an extra lookup and a miss into the same cost as before.

Members of an object are not lexical at all. A field access resolves against the type of the receiver, which the resolver does not yet know. Those lookups are deferred to the type checker, which needs a second kind of table keyed by type identity rather than by name alone. The split matters for the layout: lexical tables are keyed by string, member tables are keyed by (type, name), and mixing them produces a table whose hash function has to combine two components and whose entries have a different lifetime.

Labels, struct tags, and type names are the other common case. In C, struct s and a variable named s coexist, and the tag lives in its own namespace. That separation is not an implementation convenience; it is specified behaviour, and a symbol table that stores both in one map cannot represent a legal program. The mechanism for splitting them is covered in Separate Namespaces and Overload Sets in a Symbol Table.

Lifetime and the shape of the interface

The interface a symbol table presents shapes what the resolver can express, and the common mistake is to expose only insert and lookup. Adding enter_scope and leave_scope makes the stack discipline explicit and lets the table enforce it — refusing a lookup on a scope that has been left, or asserting balance at the end of the walk. A table with only insert and lookup forces the resolver to maintain the discipline itself, and resolvers with early returns do not.

Some compilers need to keep tables past the resolution pass. Debuggers and language servers want the symbol table at every point in the file, not just at the point the checker stopped. That requirement rules out mutation in place: the structure must be persistent, so that a snapshot taken at an arbitrary node remains valid after the walk continues. Persistent maps with structural sharing give O(log n) lookup instead of O(1), and the constant is large enough that such tables are built lazily, on demand, rather than for every compilation.

The opposite requirement appears in incremental compilation. Rechecking a single function after an edit requires the tables for its enclosing scopes to be reconstructible without rewalking the whole file, which pushes the design toward storing each scope’s declarations in the syntax tree and rebuilding a small stack on demand.

What goes wrong at scale

Two failure patterns recur. The first is unbounded growth of the global table when scopes are entered and left millions of times, as happens in machine-generated code: with a shadow stack the table grows to the number of distinct names, which is fine, but with a per-frame design the allocator sees millions of small tables and the cost moves into allocation and garbage collection.

The second is a lookup that silently succeeds when it should fail. A resolver that leaves popped bindings in the table, or that reuses one frame for sibling scopes, resolves names against declarations that are out of scope. The program then compiles and misbehaves at run time. This class of bug is invisible in tests that only check whether valid programs are accepted, which is why the balanced-scope assertion and a table that refuses post-exit lookups earn their keep.