Strings and Interning

Three concepts: immutability, hashing, and interning.

This chapter is the curriculum's cleanest example of the measure-first discipline. Interning is an obviously good idea that costs an allocation and a hash on every string creation, and whether it pays depends entirely on what your programs do. ADR-007 requires the benchmark before the optimization, and Lab 16 enforces it.

It also settles the question Lab 4 deliberately left open: are Ember's strings text or bytes?

Concept 1: Immutability and Identity

1. Concept

An Ember string is an immutable sequence of bytes on the heap. s:upper() returns a new string; nothing mutates one in place.

2. Problem

Strings are shared aggressively: they are constants in every chunk, keys in every table, and values copied freely between stack slots. If any holder could mutate one, every other holder would see it — and a table key that changed would be permanently unfindable, because its hash bucket no longer matches its contents.

3. Mental model

An immutable string is a value that happens to live on the heap. Copying a Value::Str copies a handle; because nothing can change what the handle points at, the copy is indistinguishable from a deep copy. Immutability is what lets a reference behave like a value.

4. Implementation

#![allow(unused)]
fn main() {
// src/strings.rs
pub struct EmberStr {
    bytes: Box<[u8]>,      // NOT String — see Concept 1's decision below
    hash: u64,             // computed ONCE, at creation
}

impl EmberStr {
    pub fn as_bytes(&self) -> &[u8] { &self.bytes }
    pub fn hash(&self) -> u64 { self.hash }
    /// Fallible: a host asking for `&str` gets an error on non-UTF-8 rather
    /// than a panic or a lossy conversion.
    pub fn as_str(&self) -> Option<&str> { std::str::from_utf8(&self.bytes).ok() }
}
}

The hash is cached. A string is hashed once, at creation, and every table lookup reuses it. That is the single largest win available in the string subsystem and it costs eight bytes per string — and it is only sound because the string is immutable.

5. Alternatives — and the byte-vs-text decision

6. Decision

A: Ember strings are byte strings, exactly like Lua's. This resolves the question Lab 4 flagged as undecided.

Three reasons, and the third is the one that decides it:

1. Lua compatibility. #s, string.sub, string.byte, and the pattern library are all byte-oriented. Choosing B means diverging from all of them, or maintaining a second index.
2. Binary data is a real use case. A host passing a protobuf blob, a hash digest, or a compressed payload through a script should not have it rejected or mangled.
3. B moves a class of errors from the boundary to the middle. With B, string.sub(s, 1, 2) on a multi-byte character either panics, silently produces invalid UTF-8, or errors — three bad options, deep inside the runtime. With A, the only place UTF-8 matters is the host boundary, where as_str() returns Option and the marshaling layer can produce a clear error. Push validation to the edge; keep the core representation dumb.

The cost is honest and goes in docs/limitations.md: Ember has no Unicode-aware string operations. #s counts bytes, string.upper is ASCII-only, and there is no string.len_in_characters. Lua 5.3+ ships a small utf8 library for exactly this gap; Ember's is a challenge extension.

7. Tradeoffs

8. Production concerns

• .. in a loop is quadratic. for i = 1, n do s = s .. x end allocates and copies a progressively longer string every iteration: O(n²) bytes copied. This is the classic Lua performance bug, and the answer is table.concat, which Lab 21 provides. Lua 5.4 also mitigates it in the VM: OP_CONCAT takes a register range and concatenates a whole run at once, so a..b..c..d is one allocation rather than three. Ember's CONCAT is binary; the multi-operand version is a challenge, and the benchmark is a .. chain.
• String length is attacker-controlled. ("x"):rep(1e9) is a one-line memory bomb. The memory budget in Section 5 is what stops it, and rep/concat/format must each check before allocating, not after.
• Never unwrap() a UTF-8 conversion. as_str() returns Option for a reason; the fuzzer will find the path that ignores it.

9. References

rg -n 'TString|LUAI_MAXSHORTLEN|luaS_newlstr|luaS_hash|luaS_hashlongstr' lstring.c lobject.h

• Lua's lstring.c and the TString definition in lobject.h.
• Lua 5.4 Reference Manual §6.4 (the string library) and §6.5 (the utf8 library) — note that Unicode is a library, not a core concern, which is the same decision Ember makes.
• The bstr crate's documentation, for a well-argued treatment of byte strings in Rust and why String is not always the right answer.

Concept 2: Hashing

1–3. Concept, problem, mental model

A string's hash is computed once, at creation, and carried with it. Every table lookup, every equality comparison, every constant-pool dedup reuses it.

The alternative — hashing at every lookup — costs O(length) on every table access, which for article.semantic_score in a loop is the dominant cost of field access.

4. Implementation

#![allow(unused)]
fn main() {
fn hash_bytes(b: &[u8], seed: u64) -> u64 {
    // FNV-1a: 12 lines, decent distribution, fast on short keys. It is NOT
    // collision-resistant, which is exactly why `seed` exists — see below.
    let mut h = 0xcbf29ce484222325 ^ seed;
    for &c in b { h ^= c as u64; h = h.wrapping_mul(0x100000001b3); }
    h
}
}

And here is the part that is a security decision, not a performance one.

Rust's default HashMap hasher is SipHash-1-3 with a randomly seeded key, chosen specifically to resist hash-collision denial-of-service: an attacker who can control table keys and predict your hash function can force every key into one bucket, turning O(1) lookups into O(n) and a table build into O(n²). This is the vulnerability class that hit PHP, Python, Ruby, Java, and others in 2011 (CVE-2011-4815 and siblings).

Ember's core hash is FNV, which is not collision-resistant. Two consequences, and both must be stated:

1. The seed must be per-Engine and unpredictable to a script, so an attacker cannot precompute colliding keys offline. Ember derives it from the host at Engine::new().
2. Per-engine randomization conflicts with determinism — and this is a real tension, not a footnote. Ember resolves it by making the seed affect only bucket placement, never iteration order, because iteration is insertion-ordered. That is the payoff for ADR-008 that nobody expects: because order does not depend on the hash, the hash can be randomized for security without costing reproducibility. Write that in docs/gc.md… no — write it in docs/sandboxing.md, because it is a threat-model property.

Warning: If you ever "optimize" by making iteration follow bucket order, you lose determinism and you make the hash seed observable to a script — which hands an attacker an oracle for discovering the seed. Two properties, one change, both lost. This is why the ADR exists.

5–7. Alternatives, decision, tradeoffs

Lua's approach is worth knowing: short strings (≤ LUAI_MAXSHORTLEN, 40 bytes) are hashed in full; long strings are hashed lazily and by sampling a subset of bytes. Both are performance choices that trade collision quality for speed, and both assume the strings are not adversarial.

Decision: seeded FNV-1a, with the threat model written down. Section 7 benchmarks SipHash against it, and the decision to keep FNV must survive that benchmark and the threat model — not just the benchmark.

Concept 3: Interning

1. Concept

Interning means keeping exactly one heap object per distinct string content. Two equal strings are then the same object, so equality is a handle comparison rather than a byte comparison.

2. Problem

if article.topic == "sports" then ... end

Without interning, that is a byte-by-byte comparison on every evaluation. With interning, it is handle_a == handle_b — one integer compare. Table lookups get the same benefit: the probe compares handles rather than contents.

3. Mental model

An intern table is a set of all live strings, keyed by content. Creating a string looks it up first; if it is there, you get the existing handle. The identity of a string becomes its meaning.

4. Implementation

#![allow(unused)]
fn main() {
pub struct Strings {
    /// content-hash → handle. WEAK: an entry here must not keep a string alive.
    table: HashMap<InternKey, GcRef<EmberStr>>,
    seed: u64,
}

impl Heap {
    pub fn intern(&mut self, bytes: &[u8]) -> Result<GcRef<EmberStr>> {
        let h = hash_bytes(bytes, self.strings.seed);
        if let Some(&existing) = self.strings.lookup(h, bytes, &self.slots) {
            return Ok(existing);                        // ← the whole point
        }
        let r = self.alloc_str(EmberStr::new(bytes.into(), h))?;
        self.strings.table.insert(InternKey { hash: h, handle: r }, r);
        Ok(r)
    }
}
}

Two details that are easy to get wrong:

1. The intern table must be weak, or no string is ever collected. It is root set 6, and Ember treats it as weak: the sweep phase removes entries whose object was not marked. A strong intern table is a defensible choice — Lua's is strong, and Lua collects interned strings via a dedicated pass — but it must be a choice.
2. The lookup compares bytes, not just hashes. A hash match is not an equality match. Skipping the byte comparison makes two colliding strings the same object, which is a silent, catastrophic correctness bug.

5. Alternatives

Lua's C is the interesting one and the reasoning is worth copying: short strings are usually identifiers and table keys — created many times, compared constantly, and cheap to hash. Long strings are usually data — created once, rarely compared, and expensive to hash. Interning the first and not the second is a distinction based on how programs actually behave.

6. Decision

ADR-007: implement A first. Benchmark. Then implement C or D only if the benchmark justified it, and record the delta either way.

This is the discipline, not the answer. The measurement you need, from Lab 16:

If concat_build and many_distinct regress more than field_access and string_eq improve, then option C's short-string cutoff is exactly the fix, and you will have discovered why Lua has one rather than being told.

7. Tradeoffs

8. Production concerns

• Interning is an unbounded cache. A script that generates a million distinct strings puts a million entries in the intern table. Weak entries plus sweeping bound it by the live set — which is the right bound, and it is only correct if the sweep actually removes them. Test it: create a million strings, drop them, collect, and assert the intern table shrank.
• Interning changes --gc-stress behavior. A newly interned string is reachable from the intern table (weakly) and from nothing else until it is stored. It is subject to the allocation hazard like any other object; a weak table does not root it.
• The seed must not leak. With interning, s1 == s2 is a handle comparison, so a script cannot observe the hash — good. But if any API exposes a hash or an iteration order derived from it, the seed becomes discoverable. Keep hashes out of the script-visible surface entirely.

9. References

• Lua's lstring.c: luaS_newlstr (the intern lookup), luaS_createlngstrobj, and LUAI_MAXSHORTLEN in luaconf.h. Note luaS_hashlongstr's lazy hashing.
• Java's String.intern() and the long history of its interaction with the permanent generation — a cautionary tale about strong intern tables.
• Rustc's Symbol and SymbolIndex in rustc_span — interning in a compiler, where every identifier is a u32.
• The 2011 hash-collision DoS disclosures (Klink & Wälde, 28C3) — the primary source for why hash seeding exists.

Things to Notice

• Immutability is what makes a heap reference behave like a value, and it is what makes hash caching sound. Two properties from one decision.
• Byte strings push UTF-8 validation to the host boundary, where an Option can express failure, instead of into the middle of the runtime where only a panic can.
• .. in a loop is O(n²) in every language that does this, and every one of them ships a join/concat for it.
• The hash seed is a security control, and it only coexists with determinism because iteration order does not depend on it. ADR-008 pays for ADR-007's threat model — an interaction nobody planned.
• A hash match is not an equality match. The byte comparison in the intern lookup is not optional.
• Lua interns short strings and not long ones, because identifiers and data behave differently. That distinction is an observation about programs, not about strings.
• ADR-007 is about the method, not the answer. Benchmark, then decide, then record — including when the answer is "do nothing".

Validation / Self-check

1. Why does immutability make caching a string's hash sound?
2. Give the three reasons Ember chose byte strings, and name the class of error the third one moves to the boundary.
3. What is the O(n²) string bug, and what are the two mitigations (library and VM)?
4. Why is choosing a faster hash a security decision? What does the seed protect against?
5. How do insertion-ordered tables make a randomized hash seed compatible with determinism?
6. What two things must an intern lookup compare, and what breaks if you skip the second?
7. Why must the intern table be weak? What is the alternative, and who does it?
8. Why does Lua intern short strings but not long ones? What observation about programs is that based on?
9. Name the four benchmarks ADR-007 requires and say which two would motivate a length cutoff.

Next: Multiple Returns and Varargs.