Constant Pools and Encoding

Three concepts: the constant pool, instruction encoding, and the line table.

These are the "how big is it and where does it live" decisions. They look like implementation detail and they are not: the constant pool decides what a literal is at run time, the encoding decides whether there is a decode step at all, and the line table is — surprisingly — often as big as the code it annotates.

Concept 1: The Constant Pool

1. Concept

A constant pool is a per-chunk array of the literal values a function needs. Instructions refer to constants by index rather than carrying them inline.

   local greeting = "hello"
   local n = 3.14159

   constants:                       code:
     [0] "hello"                      LOAD_CONST 0
     [1] 3.14159                      SET_LOCAL  0
                                      LOAD_CONST 1
                                      SET_LOCAL  1

2. Problem

An instruction is a fixed, small size. A string literal is not. A f64 does not fit in an operand field. And the same literal often appears many times — "score" in a policy file might appear thirty times, and thirty copies of a string is thirty allocations and thirty hash computations.

3. Mental model

The pool is the chunk's literal table: everything the code needs that is not an instruction. An index into it is a cheap, fixed-size handle for an arbitrarily large value. It is exactly the same idea as a symbol table, a .rodata section, or the JVM's constant_pool — and the JVM's is called that for a reason.

4. Implementation

#![allow(unused)]
fn main() {
impl Chunk {
    /// Add a constant, deduplicating. Returns its index.
    pub fn add_constant(&mut self, v: Value) -> Result<u16> {
        if let Some(&i) = self.const_index.get(&ConstKey::of(v)) { return Ok(i); }
        if self.constants.len() >= u16::MAX as usize {
            return Err(compile_error("too many constants in one function"));
        }
        let i = self.constants.len() as u16;
        self.constants.push(v);
        self.const_index.insert(ConstKey::of(v), i);
        Ok(i)
    }
}

/// A hashable, exactly-comparable key for constant deduplication.
///
/// Float constants CANNOT be keyed by `PartialEq`:
///   * NaN != NaN, so a NaN literal would be added on every occurrence;
///   * 0.0 == -0.0, so they would COLLAPSE into one constant — and they are not
///     interchangeable, because 1/0.0 is +inf and 1/-0.0 is -inf.
/// Keying by the bit pattern fixes both, and it is the reason this type exists
/// rather than a plain `HashMap<Value, u16>`.
#[derive(PartialEq, Eq, Hash)]
enum ConstKey { Nil, Bool(bool), Int(i64), FloatBits(u64), Str(GcRef<EmberStr>) }
}

What may be a constant, and what may not:

That table is a real rule with a real failure mode: putting {} in the constant pool means every evaluation of a table literal returns the same table, and a policy that builds a fresh table per article silently shares one. It is the kind of bug that passes every unit test and fails in production under concurrency.

5. Alternatives

6. Decision

A, with B for integers that fit in i32.

The hybrid is worth naming as a decision rather than an accident. LOAD_INT covers the overwhelming majority of numeric literals in real code with no pool slot and no indirection; the pool covers everything else. Lua 5.4 made the same move when it added OP_LOADI.

Option C is tempting for string dedup across a whole program, and Section 4's string interning achieves the same benefit at the value level instead — which is better, because it also covers strings computed at run time.

7. Tradeoffs

8. Production concerns

• The u16 cap is a real compile error, not a wrap. A generated file with 70,000 distinct string literals must fail with "too many constants in one function", pointing at the offending literal. Lua handles overflow with an EXTRAARG instruction that supplies extra operand bits; Ember refuses. Test it with a generated file.
• Constants are shared and must be immutable. If Value::Str ever becomes mutable, the pool becomes a source of spooky action at a distance. This is one of the load-bearing reasons Ember's strings are immutable — and it is worth stating, because "strings are immutable" usually gets justified only by hashing.
• -0.0 and NaN. The ConstKey comment above is not pedantry. Verify: lua -e 'print(1/0.0, 1/-0.0)' prints inf and -inf. A pool that collapses them changes program behavior.
• Do not let the pool hold GC references the collector does not know about. Interned string constants are heap objects; chunk.constants is therefore a GC root. Miss it and a chunk's strings get collected while the chunk is still live. That is a Lab 15 bug, and it is listed here because this is where it is created.

9. References

luac -l -l /tmp/t.lua | sed -n '/constants/,/locals/p'
python3 -c "print(compile('x=\"a\"+\"a\"', 't', 'exec').co_consts)"
javap -v YourClass.class | sed -n '/Constant pool/,/^{/p'

• The JVM Specification §4.4, "The Constant Pool" — the most elaborate version of this idea, with typed entries and symbolic references.
• Lua's lcode.c: addk, luaK_stringK, luaK_intK, and note nilK's trick for storing nil in a table that cannot hold nil keys.
• CPython's co_consts, and try compile('x = 1000; y = 1000', ...) versus 'x = 1; y = 1' to see where small-int caching interacts with constant folding.

Concept 2: Instruction Encoding

1. Concept

Encoding is how an instruction is represented in memory: how wide it is, where the opcode ends and the operands begin, and whether there is a decode step.

2. Problem

An interpreter fetches an instruction on every step of every program. If decoding costs three shifts and three masks, you pay that on every instruction forever. If instructions are variable-width, you cannot index into the code array — which breaks absolute jump targets, breaks ip += 1, and makes the disassembler a parser.

3. Mental model

Encoding trades memory against decode work. A wide, uniform encoding is bigger and free to decode. A packed encoding is smaller and costs arithmetic on every fetch. A variable-width encoding is smallest and makes random access impossible.

4. Implementation

Ember uses a Rust enum, and therefore has no decode step at all:

#![allow(unused)]
fn main() {
let op = self.chunk().code[ip];    // one load; the discriminant IS the opcode
match op {
    Op::GetLocal(s) => ...,        // `s` is already an u8; the compiler extracted it
    ...
}
}

size_of::<Op>() == 8: one byte of discriminant, padding, and up to 6 bytes of operands (SetList(u16, u32) is the widest). Rust lays this out; you do not.

Compare with Lua, which packs everything into a u32:

   Lua 5.4 iABC:   |  C:8  |  B:8 |k|  A:8  | Op:7 |
   Lua 5.4 iABx:   |      Bx:17     |  A:8  | Op:7 |
   Lua 5.4 iAsBx:  |     sBx:17     |  A:8  | Op:7 |   (signed, biased)

   GETARG_B(i)  ==  (i >> 24) & 0xFF        ← a shift and a mask, per operand, per fetch

Four bytes instead of eight, at the cost of extraction arithmetic and of operand fields so narrow that Lua needs EXTRAARG instructions and a ~200-local limit. The narrow fields are not a coincidence of the encoding; they are a consequence of it.

5. Alternatives

Option D deserves a note. The JVM and Wasm accept variable-length encoding because they optimize for transfer size — these formats travel over networks — and because both are usually compiled before execution rather than interpreted directly. The JVM's tableswitch even needs alignment padding in the middle of the instruction stream, which tells you how far that priority goes.

6. Decision

A, and §7 may measure B.

The reasoning is the curriculum's stated priority order. A typed enum means the disassembler is a match, the validator is a match, the VM is a match, and none of them can extract an operand incorrectly because there is no extraction. That eliminates an entire bug class — one that is genuinely painful, because a mis-extracted operand produces plausible-looking wrong behavior.

The cost is 2× the code memory versus Lua. For a 10,000-instruction chunk that is 80 KB instead of 40 KB, which is not a number that should drive a design decision at this stage. Measure it in Section 7 — specifically, measure whether the larger code array costs instruction-cache misses in a tight loop, because that, not the raw bytes, is where a wide encoding could actually hurt.

7. Tradeoffs

8. Production concerns

• Serialization is a separate format. Op in memory is not a file format. If Section 5 caches compiled chunks, you write an encoder and a decoder, and that format should be packed and versioned. Conflating the two is how you end up unable to change your in-memory representation.
• size_of::<Op>() must be asserted. Adding a variant with a u64 operand silently doubles every chunk. const _: () = assert!(size_of::<Op>() == 8); makes it a compile error.
• A packed encoding needs its own validator rules. Ember validates semantic ranges (constant index, jump target). A packed VM must also validate that the opcode field names a real opcode — a class of check Ember gets from the type system for free. Note that when comparing.

9. References

• lopcodes.h in Lua: the iABC/iABx/iAsBx layouts, the GETARG_* macros, and the comment block explaining MAXARG_Bx and OFFSET_sBx. Fifteen minutes, and encoding tradeoffs become concrete.
• The WebAssembly binary format specification on LEB128, and the rationale document on why a compact wire format mattered more than decode speed.
• CPython 3.11's _PyCode_CODE layout, where inline cache entries live between instructions — an encoding decision made to serve specialization.

Concept 3: The Line Table

1. Concept

The line table maps each instruction back to the source it came from, so a runtime error can point at a line and a traceback can name one.

2. Problem

There is no other way to do it. By the time the VM is running, the AST is gone — so the association between instruction 47 and policy.ember:12:17 must have been recorded at compile time or it does not exist. This is Claim 11 arriving at its final layer.

3. Mental model

Debug information is a parallel array: one entry per instruction, carried alongside the code and never read during execution. Its size is a real cost and its accuracy is a real feature.

4. Implementation

#![allow(unused)]
fn main() {
pub struct Chunk {
    pub code:  Vec<Op>,
    pub lines: Vec<Span>,     // INVARIANT: code.len() == lines.len()
    // ...
}

impl Chunk {
    fn emit(&mut self, op: Op, span: Span) -> usize {
        self.code.push(op);
        self.lines.push(span);
        debug_assert_eq!(self.code.len(), self.lines.len());
        self.code.len() - 1
    }
}
}

Emitting the op and the span in one function is the whole trick. If any code path pushes to code without pushing to lines, every subsequent error message points at the wrong source and nothing tells you. Make code private and emit the only way in.

5–7. Alternatives, decision, tradeoffs

Here is the fact people are not ready for: Vec<Span> is 8 bytes per instruction, and Op is 8 bytes per instruction. The debug information is exactly as large as the code.

Decision: A now, B as a measured optimization in Section 7.

A is one line of code and it makes error messages exact. B is Lua's design: a signed byte per instruction holding the delta from the previous line, plus an absolute checkpoint array for when the delta does not fit. It typically reaches about one byte per instruction — an 8× reduction — at the cost of a small scan on lookup, which is free because lookups only happen when something has already gone wrong.

Deferring is correct here for a reason worth naming: the optimization is invisible to every other subsystem. Nothing outside Chunk knows how lines is stored, so switching from A to B is a self-contained change you can make the day a benchmark asks for it. Optimizations with that property are exactly the ones to defer; optimizations that change an interface are not.

8. Production concerns

• Ember stores a Span, not a line number. That is a deliberate upgrade over Lua and CPython ≤3.10, both of which store lines only — and it is why Ember's runtime errors can put a caret under article.boost rather than highlighting the whole line. CPython came to the same conclusion in PEP 657 (Python 3.11), which added column information specifically so that a.b.c.d could show which access was None. Read PEP 657's before-and-after examples; they are the best available argument for this chapter.
• Debug info must be strippable. local_names and lines should be droppable without changing semantics. Test it: run the corpus with debug info stripped and assert the outputs are identical and only the error messages degrade.
• Untrusted debug info must not be trusted. A chunk loaded from a cache with a corrupt lines array must not be able to index out of bounds. Validator rule 1 (code.len() == lines.len()) exists for that, and it is why the check is in the validator and not only in a debug_assert.
• The line table is not a GC root, but local_names holds Strings and constants holds interned string handles. Know which of your side tables the collector must trace. That distinction costs an hour in Lab 15 if you have not thought about it.

9. References

• PEP 626 (precise line numbers) and PEP 657 (fine-grained error locations) — the second one is a short, well-argued case for storing spans instead of lines, by a language that had done it the other way for thirty years.
• Lua's lundump.c/ldebug.c: lineinfo, abslineinfo, and luaG_getfuncline. Option B, in about forty lines.
• DWARF's line-number program, if you want to see how far this idea can be pushed: a whole bytecode VM whose only job is to compress the address-to-line mapping.

Things to Notice

• Deduplicating float constants by PartialEq is a bug, twice over: NaN never matches itself, and 0.0 collapses with -0.0. Key by bits.
• Tables and closures cannot be constants, and the reason — each evaluation must produce a fresh object — is the same reason {} is not a literal in the way 1 is.
• The constant pool is a GC root. It holds interned strings.
• A typed enum removes a whole bug class (operand extraction) and costs memory. That is the curriculum's priority order applied to a concrete decision.
• Lua's narrow operand fields are a consequence of its encoding, not an independent choice. Every "why is Lua limited to 200 locals?" answer ends at the 8-bit A field.
• Your debug information is as big as your code, and that is normal, and Lua and CPython both compress it. Defer the compression because it is invisible from outside Chunk — that property, not the size, is what makes deferring correct.

Validation / Self-check

1. Why can a string literal not be an inline operand, and what replaces it?
2. Why must constant deduplication key on float bits? Give the two distinct bugs.
3. Which values may be constants and which may not? What is the failure mode of getting {} wrong?
4. What is size_of::<Op>() in Ember, why, and what is Lua's equivalent number?
5. Give the four encoding strategies and one production system for each. Why did the JVM and Wasm choose variable-length?
6. What is the decode step in Ember's VM? Why does that eliminate a bug class?
7. What is the invariant on lines, and what single design choice enforces it?
8. How big is Ember's line table relative to its code? What do Lua and CPython do instead, and why is deferring that change the right call here specifically?
9. Why does Ember store a Span rather than a line number, and which language recently made the same change?

Next: Code Generation.