Lab 16: Strings and Interning (Milestone 11)

Background

You will replace the placeholder string type with a real heap object, decide byte-vs-text, cache the hash, seed it, and then — only after a benchmark says so — add interning.

The order is the lab. ADR-007 requires a measurement before the optimization, and this is the one place in the curriculum where the temptation to skip that step is strongest, because interning is obviously a good idea.

Why This Lab Matters

It is the cleanest measure-first exercise you will get. The optimization is small, the benchmark is easy, and the answer is genuinely not obvious — which is exactly when the discipline matters.
The byte-vs-text decision moves a class of panics to the boundary. Lab 4 left it open on purpose; you close it here.
The hash seed is a security control, and it only coexists with determinism because of a decision made two labs ago.

Prerequisites

Lab 15 complete: the collector works and the corpus is green under --gc-stress.
Strings and Interning read.

Predict First

#"héllo" — 5 or 6? Which is Lua's answer?
for i=1,10000 do s = s .. "x" end — how many bytes are copied in total?
Interning makes s == "sports" O(1). What does it make s1 .. s2 cost?
If the intern table is a strong GC root, what never happens?
Two different strings with the same FNV hash land in the intern table. What must the lookup do?
Ember randomizes its hash seed per Engine. Why does that not break determinism?

Step 1: `EmberStr`, and the Byte Decision

#![allow(unused)]
fn main() {
pub struct EmberStr {
    bytes: Box<[u8]>,     // BYTES, not String. See ADR: byte strings.
    hash: u64,            // computed ONCE at creation; sound because immutable
}
}

Ember strings are byte strings, like Lua's. That closes the question Lab 4 flagged. Consequences to implement now:

#s is bytes.len().
string.sub, string.byte, string.char are byte-indexed.
as_str() returns Option<&str> — never unwrap, never lossy.
The only place UTF-8 is checked is the host boundary (Section 5), where a conversion failure becomes a clear marshaling error.

Write the divergence entries now, while the reasoning is fresh:

<!-- appendix/lua-differences.md -->
- **Strings are byte strings** (as in Lua). Ember has no Unicode-aware string operations:
  `#s` counts bytes, `string.upper` is ASCII-only. Lua 5.3+ ships a `utf8` library;
  Ember's is a challenge extension. See docs/limitations.md.

Step 2: Hashing, Seeded

#![allow(unused)]
fn main() {
fn hash_bytes(b: &[u8], seed: u64) -> u64 { /* FNV-1a, seeded */ }
}

The seed is created per Engine, from the host's entropy, and is never observable from a script. That is a real constraint on the API surface:

No string.hash function.
Table iteration order must not depend on it — which is free, because iteration is insertion-ordered.
No error message may include a hash or a bucket index.

Note: This is ADR-008 paying for ADR-007's threat model. Determinism was chosen for reproducibility and testability; it turns out to be what makes hash randomization affordable. Write that interaction down in docs/sandboxing.md — it is the kind of cross-subsystem consequence that is invisible unless someone records it.

Step 3: Benchmark Before Interning

Four benchmarks. Run them against the non-interning implementation and commit the numbers.

#![allow(unused)]
fn main() {
// benches/strings.rs
fn field_access(c: &mut Criterion) {      // t.name in a loop: hashing a short key
fn string_eq(c: &mut Criterion) {         // s == "literal" in a loop
fn concat_build(c: &mut Criterion) {      // building strings with `..` — interning's WORST case
fn many_distinct(c: &mut Criterion) {     // a million distinct strings — worst for memory
}

cargo bench --bench strings 2>&1 | tee docs/learning/strings-no-intern.txt
git add docs/learning/strings-no-intern.txt && git commit -m "lab-16: string baseline, no interning"

Write down your prediction now, in docs/learning/13-strings.md: which two will improve with interning, which two will regress, and by roughly how much?

Step 4: Interning

#![allow(unused)]
fn main() {
pub fn intern(&mut self, bytes: &[u8]) -> Result<GcRef<EmberStr>> {
    let h = hash_bytes(bytes, self.strings.seed);
    // A hash match is NOT an equality match. Compare the bytes.
    if let Some(&existing) = self.strings.lookup(h, bytes, &self.slots) { return Ok(existing); }
    let r = self.alloc_str(EmberStr::new(bytes.into(), h))?;
    self.strings.insert(h, r);
    Ok(r)
}
}

Two things this changes elsewhere, and both are easy to miss:

String equality becomes handle comparison. Update raw_eq — and keep the byte-comparison path behind a debug_assert that asserts the two agree. If interning is ever incomplete (a path that allocates a string without interning it), handle equality silently returns false for equal strings. That assertion catches it.
The intern table becomes root set 6, and it is weak. The sweep phase must remove entries whose object was not marked:

#![allow(unused)]
fn main() {
// in sweep, before clearing marks:
self.strings.retain(|_, &mut handle| self.marks[handle.index as usize]);
}

Forget that and no interned string is ever collected — a leak with no cycle in it, which is the kind the collector will never help you find.

Step 5: Benchmark Again, and Decide

cargo bench --bench strings 2>&1 | tee docs/learning/strings-interned.txt

Fill this in with your numbers:

Benchmark	No interning	Interned	Δ
`field_access`
`string_eq`
`concat_build`
`many_distinct`

Then decide, and record the decision either way:

If field_access and string_eq improved more than concat_build and many_distinct regressed → keep it.
If the regressions dominate → revert, and write ADR-007 as "we measured; interning did not pay for our workload". A reverted optimization with a measurement is worth more than a kept one without.
If the regressions are concentrated in concat_build and many_distinct → you have just derived Lua's short-string cutoff from first principles. Implement it (intern strings ≤ 40 bytes) and benchmark a third time.

That third outcome is the likely one, and arriving at it by measurement rather than by being told is the point of the whole lab.

Step 6: The `..` Trap

local s = ""
for i = 1, 10000 do s = s .. "x" end     -- ~50,000,000 bytes copied. O(n²).

Two mitigations, and Ember gets the first now and the second as a challenge:

table.concat (Lab 21) — accumulate into a table, join once. This is what Lua programmers are taught to do and it is the real answer.
A multi-operand CONCAT — Lua 5.4's 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 is binary.

Measure the quadratic behavior so it is not abstract:

$ for n in 1000 2000 4000 8000; do
    /usr/bin/time -f "$n: %e s" ember run -e "local s='' for i=1,$n do s=s..'x' end return #s"
  done

Four data points, each doubling n. If the time roughly quadruples, you have measured O(n²) on your own machine, which is more persuasive than any explanation.

The Trace

$ ember run --trace-strings -e 'local a="sports" local b="spo".."rts" return a == b'

Without interning:

str alloc  #1  "sports"    hash=0x8f3a…  (constant pool)
str alloc  #2  "spo"       hash=0x21b4…
str alloc  #3  "rts"       hash=0x9c07…
str alloc  #4  "sports"    hash=0x8f3a…  ← a SECOND object with the same content
eq         #1 vs #4        6-byte compare → true
true

With interning:

str intern #1  "sports"    hash=0x8f3a…  MISS → alloc
str intern #2  "spo"       hash=0x21b4…  MISS → alloc
str intern #3  "rts"       hash=0x9c07…  MISS → alloc
str intern     "sports"    hash=0x8f3a…  HIT  → reuse #1     ← no allocation
eq         #1 vs #1        handle compare → true             ← no byte compare
true

Two objects became one, and a six-byte comparison became an integer compare. That is the whole mechanism, visible.

And the weak-table check, which is the part that leaks if you get it wrong:

$ ember run --trace-gc --stats -e '
local t = {}
for i = 1, 100000 do t[i] = "unique-" .. i end
t = nil
collectgarbage()
return 1'

gc: sweep      freed=100001  intern-table entries removed=100000
--- heap census ---
  EmberStr    4      ← only the literals remain

If intern-table entries removed is 0, your intern table is strong and you have a leak.

Expected Output

$ ember run -e 'return #"héllo"'
6
$ ember run -e 'return "a" .. 1 .. true'
<argv>:1:19: error: attempt to concatenate a boolean value

   1 │ return "a" .. 1 .. true
     │                    ^^^^
$ ember run --stats -e 'local s="" for i=1,1000 do s=s.."x" end return #s'
1000
--- stats ---
allocations: 1002        ← O(n) allocations, O(n²) bytes copied

Debugging Steps

`s1 == s2` is false for equal strings

A path allocates a string without interning it. The debug_assert from Step 4 names it.

Memory grows without bound in a long-running loop over distinct strings

The intern table is strong. Add the retain in sweep.

`--gc-stress` fails only in string-heavy tests

A newly interned string is reachable only from the (weak) intern table until it is stored. It needs the same rooting as any other fresh allocation — a weak table does not root.

Two different strings compare equal

The intern lookup compares hashes and not bytes. This is a correctness catastrophe; add the byte comparison and a test with a deliberate collision.

`#"héllo"` is 5

You used String and chars().count(). Ember counts bytes.

The concat benchmark regressed 10× after interning

Expected, and it is the data. Every intermediate s .. "x" is now hashed and probed. This is what motivates the short-string cutoff.

Experiment

CLAIM. Lua's short-string cutoff exists because identifiers and data have different lifetimes and comparison rates — and the crossover is measurable.

METHOD. Implement interning with a length cutoff N. Run field_access, string_eq, concat_build, and many_distinct at N = 0 (no interning), 8, 16, 40, 128, and ∞ (intern everything).

PREDICTION. Where is the crossover? Is Lua's 40 close to your optimum?

RESULT. Plot or tabulate it in docs/learning/13-strings.md. Then write ADR-007 with the number and the curve. An ADR that shows the sensitivity of a constant is far more useful than one that just states it — the next person will know whether 40 was load-bearing or arbitrary.

Test

#![allow(unused)]
fn main() {
#[test]
fn strings_are_byte_strings() {
    assert_eq!(run("return #'héllo'"), "6");                 // bytes, not chars
    assert_eq!(run("return #'\\xff\\x00\\xfe'"), "3");        // arbitrary bytes are fine
}

#[test]
fn equal_content_means_equal_handles_when_interned() {
    assert_eq!(run("local a='sports' local b='spo'..'rts' return tostring(a==b)"), "true");
    // White-box: the handles must be identical, not merely equal by content.
    let (a, b) = intern_two("sports", "sports");
    assert_eq!(a.index(), b.index());
}

#[test]
fn a_hash_collision_does_not_merge_two_strings() {
    // Two byte sequences forced to the same hash bucket must remain distinct.
    let (s1, s2) = colliding_pair();          // constructed for the test's seed
    assert_ne!(intern(s1).index(), intern(s2).index());
    assert_eq!(run(&format!("return tostring({s1:?} == {s2:?})")), "false");
}

#[test]
fn the_intern_table_is_weak() {
    let mut vm = Vm::new();
    vm.run_str("local t={} for i=1,10000 do t[i]='u-'..i end t=nil").unwrap();
    let before = vm.strings.len();
    vm.collect();
    assert!(vm.strings.len() < before / 2,
            "intern table did not shrink: {} → {}", before, vm.strings.len());
}

#[test]
fn the_hash_seed_is_not_observable() {
    // Two engines with different seeds must produce IDENTICAL output for any
    // program in the corpus. This is the property that lets us randomize.
    for case in corpus() {
        let a = Engine::with_seed(1).run(&case.src);
        let b = Engine::with_seed(0xdeadbeef).run(&case.src);
        assert_eq!(a, b, "{} output depends on the hash seed", case.name);
    }
}

#[test]
fn huge_string_allocation_hits_the_memory_limit_not_the_allocator() {
    let e = run_with_memory_limit("return ('x'):rep(1000000000)", 4 << 20).unwrap_err();
    assert_eq!(e.kind, ErrorKind::Limit);   // checked BEFORE allocating
}
}

Challenge Extensions

The utf8 library. utf8.char, utf8.codepoint, utf8.len, utf8.offset, and the utf8.charpattern. Lua's answer to Unicode-as-a-library, and it makes the byte-string decision comfortable rather than merely defensible.
Multi-operand CONCAT. Take a register range, allocate once. Benchmark a..b..c..d..e.
Rope strings. Represent a concatenation lazily as a tree, flatten on demand. Turns the O(n²) loop into O(n). Then measure how much it costs everything else — this is a real tradeoff, and most language runtimes have decided against it.
SipHash comparison. Swap FNV for SipHash-1-3 and measure. Then decide — and remember the decision must survive the threat model, not just the benchmark.
Small-string optimization. Store strings ≤ 15 bytes inline in the heap object rather than in a separate allocation. Measure allocation count on the corpus.

Deliverables

EmberStr with byte storage and a cached hash; as_str() returns Option.
The byte-string decision documented in appendix/lua-differences.md and docs/limitations.md.
A per-Engine hash seed, unobservable from scripts, with the two-engine test.
Baseline benchmarks committed before interning exists.
Interning with a byte comparison in the lookup and a debug_assert that handle equality agrees with content equality.
The intern table is weak and swept; the shrink test passes.
Post-interning benchmarks, the comparison table filled in, and a decision recorded either way in ADR-007.
The O(n²) .. measurement, with four doubling data points.
string.rep/concat check the memory budget before allocating.
--trace-strings showing intern hits and misses.
docs/learning/13-strings.md written, including your pre-benchmark prediction and how wrong it was.

Validation / Self-check

Why is caching a string's hash sound? What property makes it so?
Give the three reasons Ember uses byte strings, and the class of error the third one relocates.
What must an intern lookup compare, beyond the hash? What is the failure mode of skipping it?
Why must the intern table be weak, and where in the collector does that happen?
Why is the hash seed a security control, and what three API constraints does it impose?
How do insertion-ordered tables make seed randomization compatible with determinism?
Report your four benchmark deltas. Which two regressed, and what does that imply?
What is the short-string cutoff for, and what did your curve say the crossover was?
Why is s = s .. "x" in a loop O(n²), and what are the two mitigations?

Next: Lab 17 — Multiple Returns and Varargs.

Open-Source Engineer & Contributor