52. String interning

Two strings, one object

Chapter 51 left a loose thread. The table compares keys with k === key, and OP_EQUAL in chapter 49 was a === b. For objects, === asks “the same object?”, not “the same characters?” (chapter 4). Yet:

let a = "ab";
let b = "a" + "b";
print a == b; // true

a is a literal, made by the compiler. b is built at runtime by OP_ADD. Chapter 50 said every concatenation allocates a new object. So how can they be the same object?

They can because chapter 50 told a small lie. copyString doesn’t always allocate.

Interning

Here is the real copyString, in vm/heap.ts:

copyString(chars: string): ObjString {
  const hash = hashString(chars);
  const interned =
    this.strings.findString(chars, hash);
  if (interned) return interned;
  const s = this.allocate<ObjString>({
    type: 'string', chars, hash,
    isMarked: false, next: null,
  });
  this.push(s);
  this.strings.set(s, null);
  this.pop();
  return s;
}

heap.strings is a Table from chapter 51, used as a set: the keys are every string the VM has made, and the values are all null. Before making a string, copyString asks the set for one with the same characters. Only if there is none does it allocate, and then the new string goes into the set, so the next request finds it. (The push and pop keep s on the stack, safe from the collector, while it is being added.)

Every string in the VM is made by copyString: literals, names, concatenations. So there is never more than one object with the same characters.

let a = "hi";
let b = "h" + "i";
let c = a;
print a == b;

Finding a string by its characters

There is a catch. Table.find compares keys by identity, but that’s exactly what you can’t do yet: you are holding characters, not an object. So the table has a second lookup, the only place in the whole VM that compares a string’s characters:

findString(chars: string, hash: number) {
  if (this.count === 0) return null;
  const mask = this.keys.length - 1;
  let index = hash & mask;
  for (;;) {
    const k = this.keys[index];
    if (k === null) {
      if (this.values[index] === null) {
        return null;
      }
    } else if (k.hash === hash &&
        k.chars === chars) {
      return k;
    }
    index = (index + 1) & mask;
  }
}

The probing is the same as chapter 51’s. The difference is the test. k.hash === hash is a cheap number comparison that rules out almost every wrong string. Only when the hashes match are the characters compared, and that will nearly always be the right string. A tombstone (key null, value not null) is stepped over, as before.

let a = "ab";
let b = "a" + "b";
print a == b;

let s = "";
for (let i = 0; i < 3; i = i + 1) {
  s = s + "na";
}
print s;
print s == "nanana";
print "na" + "na" == "nana";

What it costs, what it buys

Interning moves work around. It doesn’t remove it.

Making a string costs more. Every new string, including every concatenation, is hashed in full and looked up before it exists. A loop that builds a long string piece by piece pays that on every step.

Using a string costs less. == on strings is one comparison, however long they are. Every global variable lookup (chapter 53), field access and method call looks a name up in a table, and those compare keys with === too. Programs make a string once and compare or look it up many times, so this is usually a good trade. It also saves memory: a thousand copies of "name" are one object.

The intern table has one more duty. If it kept every string alive, no string could ever be freed. So it holds strings weakly: during a collection, removeWhite turns every entry whose string nothing else reached into a tombstone, just before the sweep frees it (chapter 58).

Your turn

class Interner {
  constructor() {
    this.table = new Map();
    this.made = 0;
  }
  intern(chars) {
    this.made++;
    return { chars };
  }
}

const TOMB = true;

function findString(ks, vs, chars, h) {
  return null;
}

What you learned

• Interning keeps one object per distinct string, so equal strings are identical and == is a single ===.
• copyString hashes the characters and asks the intern table first. It allocates only for a string it has never seen.
• findString is the one place characters are compared, and only after the hashes match.
• The trade: every new string pays a hash and a lookup, so every later comparison and name lookup is a pointer check.
• The intern table holds strings weakly: unreachable strings leave it before they are freed.

That’s Day 13. Next, the VM puts its tables to work: global variables, found by name.