154. Strings and interning in Rust

The same string twice

In the TypeScript VM, heap.copyString('hi') returns the same object every time it sees hi (chapter 52). That is why a === b is a correct string comparison there. drip-rs keeps the idea and changes the handle. A string value is a StrRef, adapted from src/object.rs:

pub struct StrRef {
    pub handle: Gc<ObjString>,
    pub hash: u32,
}

pub struct ObjString {
    pub chars: Box<str>,
    pub hash: u32,
}

The hash is stored twice: in the object, and in every handle to it. Chapter 149 showed that the handle’s 4 extra bytes are free, because a Value is 16 bytes either way. This chapter is about what they buy.

chars is a Box<str>, not a String. An interned string never grows, so it doesn’t need a capacity field. On rustc 1.97 here, Box<str> is 16 bytes and String is 24.

A table that never sees the heap

Look at the table’s methods in src/table.rs:

pub fn get(&self, key: StrRef)
    -> Option<Value>
pub fn set(&mut self, key: StrRef,
    value: Value) -> bool
pub fn delete(&mut self, key: StrRef)
    -> bool

None of them takes the heap. The hash comes from the key, and two keys are equal exactly when their handles are, because strings are interned. That matters because tables live inside heap objects: every instance has fields: Table, every class methods: Table. Suppose, as a design experiment, that set had to read the strings arena to hash a key:

let strings = &self.heap.strings;
self.heap[instance].fields
    .set(strings, name, value);

rustc 1.97 (trimmed):

error[E0502]: cannot borrow `self.heap`
  as mutable because it is also
  borrowed as immutable
21 | let strings = &self.heap.strings;
   |     ------------------ immutable
   |                borrow occurs here
22 | self.heap[instance].fields.set(...
   | ^^^^^^^^^ mutable borrow occurs here

heap[instance] borrows the whole heap mutably (chapter 153), and the strings arena is part of it. Carrying the hash in the handle removes the need, so SetProperty is one line: self.heap[instance].fields.set(name, value).

The interner

Interning is the one place that has to compare characters. Adapted from src/gc.rs:

pub fn intern(&mut self, chars: &str)
    -> StrRef {
    let hash = hash_string(chars);
    match self.interned.find_string(
        &self.strings, chars, hash)
    {
        Some(s) => s,
        None => self.add_string(
            chars.into(), hash),
    }
}

interned is a Table whose keys are every live string. find_string probes it by hash, and only on a matching hash compares the text, reading it from the strings arena it was handed. Borrowing self.interned and self.strings at once is fine here. Inside the heap’s own method, rustc can see they are different fields. add_string allocates the ObjString and adds it to the table with the value Nil, as TypeScript’s copyString does with null. clox and the TypeScript heap protect the new string as a temporary root while they do this. drip-rs needn’t, because the heap never collects on its own (chapter 145).

The VM also has intern_owned(String). It takes a string it has just built, such as the result of +, and keeps that allocation: into_boxed_str only reallocates to drop spare capacity, and concat reserves exactly the joined length^[2]. intern has to copy, because it was only lent a &str.

The hash is FNV-1a^[1], as in TypeScript:

pub fn hash_string(s: &str) -> u32 {
    let mut hash: u32 = 2_166_136_261;
    for byte in s.bytes() {
        hash ^= u32::from(byte);
        hash = hash
            .wrapping_mul(16_777_619);
    }
    hash
}

wrapping_mul is TypeScript’s Math.imul: a multiply that keeps the low 32 bits. One difference: drip-rs hashes UTF-8 bytes and TypeScript UTF-16 code units, so they agree only on ASCII. Nothing a program can print depends on a hash.

Two columns, with tombstones

The table itself is the TypeScript one from chapters 51 to 53, struct of arrays and all:

pub struct Table {
    count: usize, // live + tombstones
    keys: Vec<Option<StrRef>>,
    values: Vec<Value>,
}
const TOMBSTONE: Value = Value::Bool(true);

None replaces TypeScript’s null key. An empty slot is (None, Nil) and a deleted one (None, true), exactly the TypeScript encoding. The probe loop becomes a match with guards:

match keys[index] {
    None if values[index] == Value::Nil => {
        return tombstone.unwrap_or(index);
    }
    None => {
        tombstone.get_or_insert(index);
    }
    Some(k) if k == key => return index,
    Some(_) => {}
}
index = (index + 1) & mask;

tombstone is an Option<usize> where TypeScript used -1. get_or_insert keeps the first tombstone passed, so set reuses it. The keys below really do collide: by FNV-1a, y, a, len and key all have hash & 7 == 4.

Why keep two columns in Rust? TypeScript’s reason was to avoid an allocation per entry, and a Rust Vec of pairs wouldn’t allocate per entry anyway. But a pair would also pad. Measured with rustc 1.97 here, Option<StrRef> is 12 bytes and Value 16, while the pair (Option<StrRef>, Value) is 32. The two columns use 28 bytes a slot, and the probe loop mostly reads only the denser keys.

Your turn

#[derive(Clone, Copy, Debug, PartialEq)]
struct StrRef {
    id: u32,
    hash: u32,
}

// FNV-1a, as in drip-rs.
fn fnv(s: &str) -> u32 {
    let mut h: u32 = 2_166_136_261;
    for b in s.bytes() {
        h ^= u32::from(b);
        h = h.wrapping_mul(16_777_619);
    }
    h
}

const CAP: usize = 256; // a power of 2

struct Interner {
    // The text of string `id`.
    strings: Vec<Box<str>>,
    // Open addressing: CAP slots.
    keys: Vec<Option<StrRef>>,
}

impl Interner {
    fn new() -> Self {
        Interner {
            strings: Vec::new(),
            keys: vec![None; CAP],
        }
    }

    fn str(&self, s: StrRef) -> &str {
        &self.strings[s.id as usize]
    }

    // The handle for these characters,
    // made if need be.
    fn intern(
        &mut self,
        chars: &str,
    ) -> StrRef {
        todo!()
    }
}

#[derive(Clone, Copy, Debug, PartialEq)]
struct StrRef {
    id: u32,
    hash: u32,
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum Value {
    Nil,
    Bool(bool),
    Num(f64),
}

const TOMBSTONE: Value =
    Value::Bool(true);

// Fixed at 8 slots: no growing here.
struct Table {
    keys: Vec<Option<StrRef>>,
    vals: Vec<Value>,
}

impl Table {
    fn new() -> Self {
        Table {
            keys: vec![None; 8],
            vals: vec![Value::Nil; 8],
        }
    }

    fn slot(&self, k: StrRef) -> usize {
        find(&self.keys, &self.vals, k)
    }

    fn get(&self, k: StrRef)
        -> Option<Value> {
        let i = self.slot(k);
        let v = self.vals[i];
        self.keys[i].map(|_| v)
    }

    fn set(
        &mut self,
        k: StrRef,
        v: Value,
    ) {
        let i = self.slot(k);
        self.keys[i] = Some(k);
        self.vals[i] = v;
    }

    fn delete(&mut self, k: StrRef) {
        let i = self.slot(k);
        if self.keys[i].is_some() {
            self.keys[i] = None;
            self.vals[i] = TOMBSTONE;
        }
    }
}

// The slot holding `key`, or else where
// it should go: the first tombstone
// passed, or the empty slot that ended
// the probe.
fn find(
    keys: &[Option<StrRef>],
    vals: &[Value],
    key: StrRef,
) -> usize {
    todo!()
}

What you learned

• A StrRef is a string handle plus the string’s hash, and costs nothing extra inside a 16-byte Value.
• Because keys carry their hash and are interned, the table never needs the heap. That is what lets tables live inside heap objects without borrow conflicts.
• The string interner is the heap’s interned table. intern hashes, probes, compares characters only on a hash match, and allocates only if the string is new.
• drip-rs’s table is the TypeScript one: two columns, (None, Nil) empty, (None, true) a tombstone, linear probing by & mask.