perf(string): substring/slice walks from byte 0 on non-ASCII strings — O(n²) tokenizing, 97% of native tsc's remaining runtime

[proggeramlug]

Summary

slice_range::copy_utf16_range resolves its start boundary with a walk from byte 0 on every call:

let first = advance(bytes, Boundary::default(), start as usize);

So substring / slice / substr on a string containing at least one non-ASCII character is O(start) per call, and slicing at increasing offsets — which is what every tokenizer does — is O(n²).

This is the third instance of the #10055 pathology. #10067 fixed charCodeAt and bracket indexing; #10656 fixed codePointAt; this is the remaining one.

Measurement

Perry 0.5.1596 (with #10656 already fixed), macOS arm64, vs Node v26.5.1. Many small substring(i, i+8) calls at increasing i, over a string whose only non-ASCII content is a single leading é:

n	ASCII	one non-ASCII char	Node
20,000	0 ms	33 ms	0 ms
40,000	0 ms	102 ms	0 ms
80,000	0 ms	404 ms	0 ms
160,000	0 ms	1,662 ms	0 ms

Time quadruples per doubling of n. The ASCII control is flat, so this is the fast-path loss, not the copy itself.

Why it matters

After #10656 landed, a natively compiled tsc --noEmit on a two-line file spent ~97% of its remaining runtime in copy_utf16_range (sample, 50,627 of ~51,700 leaf samples; the next symbol is 162). TypeScript's scanner extracts every token with substring, and lib.dom.d.ts carries 45 non-ASCII characters in 1.87 MB — enough to disable the ASCII fast path for the whole file.

Fix

The machinery already exists. char_ops::utf16_index keeps a per-string cursor plus sparse checkpoints every 128 bytes; unit_at uses it. Exposing the same seek as a boundary lookup lets copy_utf16_range start from a nearby known position instead of byte 0.

Measured with that change:

	before	after	Node
substring scan, n=160,000	1,662 ms	1 ms	0 ms
tsc --noEmit demo.ts	85.04 s user	7.76 s user	0.80 s

11x on real tsc, and 85x cumulative against the original 658.31 s.

Correctness is unchanged, including the cases a bad boundary would corrupt rather than merely slow: hashing every substring of a string containing astral characters (all i,j pairs, including ones that split a surrogate pair) gives 1234090636 on both Perry and Node, split-pair slices still yield ["\ud83d","\ude00","😀"], and a random-access-order slice hash matches. 156 existing string:: tests pass.

Note on the class, not just the instance

Three of four UTF-16-indexed accessors have now been found on the same walk, one at a time, each after it became someone's bottleneck. The index was correct throughout — the accessors simply were not wired to it, and nothing structural prevented that.

Two follow-ups worth considering:

• Audit every remaining UTF-16-indexed entry point against the index, rather than waiting for the next profile.
• CACHE_ENTRIES = 4. The index cache is keyed by string identity with four slots. tsc is fine because one large string dominates, but a program interleaving slices of five or more non-ASCII strings would thrash it and fall back to quadratic. Worth a test before this class is called closed.

Reproduction

let s = "é" + "a".repeat(160000).slice(1);
const t0 = Date.now();
for (let i = 0; i + 8 < s.length; i += 8) s.substring(i, i + 8);
console.log(Date.now() - t0);   // Perry ~1662 ms, Node ~0 ms

Related: #10055, #10067, #10656.

[proggeramlug]

Fixed in #10664 (ready for review, verified locally), alongside #10656 — both are the same pathology in different accessors.

Index::seek is factored out of unit_at so it and the new boundary_at share one implementation and one cursor, rather than being two parallel copies that can drift — which is how these two accessors were missed after #10067.

	before	after	node
substring scan, n=160,000	1,662 ms	1 ms	0 ms
tsc --noEmit demo.ts	85.04 s user	7.76 s user	0.80 s

11× on real tsc, 85× cumulative from the original 658.31 s. The profile predicted 5–15 s from its ~97% attribution and it landed at 7.8 s.

Correctness verified against node including split surrogate pairs (all-substring hash 1234090636, split-pair slices ["\ud83d","\ude00","😀"], random-access-order hashes match). 158 string:: tests pass.