perf(string): the UTF-16 index cache holds 4 entries, so 5 interleaved non-ASCII strings fall back to O(n²) — a 1,224× cliff at exactly K=5

[proggeramlug]

Summary

The UTF-16 index that makes non-ASCII string indexing linear lives in a four-entry thread-local cache keyed by string identity (CACHE_ENTRIES = 4, crates/perry-runtime/src/string/char_ops/utf16_index.rs). A program that interleaves indexed access across five or more non-ASCII strings evicts the entry it is about to need on every access, rebuilds the index from scratch each time, and falls straight back to the O(n²) behaviour #10055/#10656/#10685 were filed to remove.

It is a step function, not a gradual degradation: 1,224× at exactly K=5.

Measurement

Perry 0.5.1596 with #10656 and #10685 applied, macOS arm64. substring(i, i+8) at increasing i, interleaved round-robin across K strings of 120,000 chars each, normalised to nanoseconds per slice so the K values are comparable. The only difference between the two columns is a single leading é:

K	ASCII control	non-ASCII	Node (non-ASCII)
1	67 ns	67 ns	67 ns
4	33 ns	50 ns	17 ns
5	27 ns	81,525 ns	13 ns
8	25 ns	80,972 ns	17 ns
12	39 ns	81,228 ns	11 ns

The ASCII control is flat across the whole range — ASCII never consults the cache — which isolates the cause to eviction rather than to "more strings" or memory pressure. Node is flat too.

Why this matters

The two fixes that just landed (#10656, #10685) wired the last accessors to the index, which removes the pathology for one hot string at a time. This is the same pathology reached by a different route, and five concurrent strings is not an exotic shape:

• i18n / locale bundles — several message catalogues, all non-ASCII by definition;
• any multi-file tool scanning more than four sources with accented text;
• template or markdown rendering across several documents;
• CSV/JSON processing over several non-ASCII columns or records.

tsc escapes it only because one 1.87 MB string dominates its scanning.

Suggested fix

Move the index into the string — lazily allocated on first indexed access, freed with the string — instead of a global four-slot cache. That removes:

• the eviction cliff entirely (no fixed capacity to exceed);
• the thread-local access and RefCell borrow on every non-ASCII indexed read;
• the four-entry identity probe.

Cost is roughly 6% of the string's bytes (one Position per CHECKPOINT_BYTES = 128), and only for non-ASCII strings that are actually indexed — against 100% for a materialised UTF-16 side buffer.

Raising CACHE_ENTRIES is not a fix: it moves the cliff to K+1 rather than removing it.

Reproduction

function mk(n, seed) { const s = seed + "a".repeat(n - seed.length); return "é" + s.slice(1); }
function interleave(k, n) {
  const strs = []; for (let i = 0; i < k; i++) strs.push(mk(n, "s" + i));
  const t0 = Date.now();
  for (let i = 0; i + 8 < n; i += 8) for (let j = 0; j < k; j++) strs[j].substring(i, i + 8);
  return Date.now() - t0;
}
console.log("K=4", interleave(4, 120000), "ms");   // fast
console.log("K=5", interleave(5, 120000), "ms");   // ~1,200x slower

Related: #10055, #10067, #10656, #10685.

[proggeramlug]

Tried the sparse run table in the real index — it makes this cliff WORSE. Reverted.

I implemented the run-table design (sync points at run boundaries instead of a fixed 128-byte stride, with affine spans resolving by arithmetic) directly in char_ops/utf16_index.rs, keeping the existing lazy incremental build. It is correct — 159 tests pass, including a new exhaustive check of every index across six shapes (pure ASCII, sparse, dense, astral, alternating, exactly-at-threshold) in forward, backward and shuffled order — and steady-state scaling stays linear.

But it regresses the cliff it was meant to remove:

K interleaved non-ASCII strings	fixed stride (today)	run table
1	67 ns	67 ns
4	50 ns	50 ns
5	81,525 ns	100,287 ns
8	80,972 ns	100,307 ns
12	81,228 ns	100,018 ns

+23% worse at K>=5. The ASCII control stays flat (25-39 ns) in both.

Why the prototype's numbers did not transfer

The prototype measured the run table as a pure function over a prebuilt table. That is the steady-state query cost, and there it genuinely wins (backward 152 -> 7 ns, random 166 -> 10 ns). But K>=5 is not steady state: every access is a cold rebuild, and rebuild cost is what dominates there. The run-table build does strictly more per-byte bookkeeping than placing a checkpoint every 128 bytes — tracking run open/close, pending-ASCII gap length against the coalescing threshold, and the affine flag — so multiplying that by "rebuild on every single access" makes the pathological case worse, not better.

So the two designs trade against each other exactly opposite to how I assumed: the run table is better at querying and worse at building, and this cliff is a pure-building workload.

What this means for the fix

It sharpens the case for the per-string index rather than weakening it. The cliff is caused by rebuilding, so the fix has to be not rebuilding — i.e. an index owned by the string and freed with it, which has no eviction and therefore no K-th-string wall at any table shape. Changing the table's shape while keeping a shared 4-entry cache cannot help, and here actively hurts.

The ingest-fused variant the prototype measured (build the table during the scan compute_utf16_len already performs) remains attractive for the same reason: it removes the rebuild entirely rather than making it cheaper.

Reverted; not pushed. The measurement stands as evidence for scoping the real fix.

[proggeramlug]

Fixed in #10664 — the cliff is gone, flat at every K

Capacity was the defect, so there is no capacity. UTF16_INDEX_CACHE becomes an owner-keyed map and entries live until their string dies, reclaimed by prune_dead_utf16_indexes — the collector hook that already existed, so this reuses the lifetime machinery rather than inventing ownership.

K interleaved non-ASCII strings	before	after
1	67 ns	67 ns
4	50 ns	67 ns
5	81,525 ns	67 ns
8	80,972 ns	67 ns
12	81,228 ns	67 ns

1,217× at K≥5, and flat — there is no K-th-string wall left to move, because there is no capacity to exceed. The ASCII control stays at 25–39 ns in both, isolating the cause to the index rather than to string count.

The failed attempt is the reason this shape was chosen

Per my comment above, I first tried changing the table's shape — sparse run-boundary syncs with affine spans, which the prototype measured at 108× less index memory. It made this cliff 23% worse (81,525 → 100,287 ns), because K≥5 is a pure rebuilding workload and a run table builds more slowly than it queries. That is what established the fix had to be stop rebuilding, not rebuild more cleverly.

Cost, stated honestly

Entries are now unbounded between collections by construction. Measured on tsc --noEmit demo.ts, peak RSS is 606.7 MB with the change against 613.4 MB without — slightly lower, not higher — so it does not cost anything measurable on that workload, but the change in character is real and worth knowing.

Verification

158 string:: tests pass single-threaded. The old cache_eviction_is_bounded_and_short_strings_do_not_evict_sources asserted len() <= CACHE_ENTRIES, now false by design, so it is replaced by indexes_survive_any_number_of_interleaved_strings: 16 strings — four times the old capacity — asserting every index survives, still answers correctly on a second pass, and is reclaimed by the prune hook. It retains that test's capacity-independent invariant, that a one-character string from char_at must not disturb its source's index.

scan_utf16_index_roots_mut now drains, lets the visitor rewrite the owner identities, and reinserts, since the map keys are exactly what the collector relocates.

One gc:: test fails identically with and without this change (same panic site), verified by running it alone against both trees — pre-existing and unrelated.