perf(string): `codePointAt` is still O(n) per call on non-ASCII strings — #10067 fixed charCodeAt and bracket scans but missed it; costs natively compiled tsc 658 s vs node's 0.4 s

[proggeramlug]

Summary

String.prototype.codePointAt is O(n) per call on any string containing at least one non-ASCII character, so a linear scan over such a string is O(n²). On the same string, charCodeAt and bracket indexing are O(1).

This is the pathology #10055 reported. #10067 ("make Unicode indexed scans linear") fixed charCodeAt and bracket scans and left codePointAt on the old path.

It is not a micro-issue: it is the reason a natively compiled tsc takes 658 s on a two-line file that Node checks in 0.395 s.

Minimal reproduction

let s = "a".repeat(n);
s = s.slice(0, n - 1) + "é";     // ONE non-ASCII character, anywhere
let acc = 0;
for (let i = 0; i < s.length; i++) acc += s.codePointAt(i);

Perry 0.5.1593, macOS arm64, against Node v26.5.1:

n	codePointAt ASCII	codePointAt non-ASCII	charCodeAt non-ASCII	Node (any)
5,000	0 ms	8 ms	0 ms	0 ms
10,000	0 ms	32 ms	0 ms	0 ms
20,000	1 ms	128 ms	0 ms	0 ms
40,000	1 ms	518 ms	1 ms	1 ms

Time quadruples for each doubling of n — a clean O(n²). Position of the non-ASCII character does not matter (start, middle or end all behave identically), so the index lookup walks from the start of the string on every call.

The accessors disagree on the same string

200,000 indexed reads of typescript@5.9.3's lib.dom.d.ts (1,874,815 chars, 45 of them non-ASCII), against an ASCII-stripped copy of the same file:

accessor	ASCII-stripped	as shipped (non-ASCII)
charCodeAt	1 ms	2 ms
codePointAt	1 ms	13,049 ms
s[i]	2 ms	3 ms

Node is 0-2 ms in all six cells. So the data is fine and the string representation is fine — only this one accessor is on the slow path.

Why it matters: tsc

tsc --noEmit demo.ts on a two-line file, compiled natively with Perry:

perry-built tsc : 658.31 s user   (12 m 47 s wall)
node tsc.js     :   0.80 s user   ( 0.395 s wall)

sample on the linked binary (built with --report-size so it symbolizes), 60 s at 1 ms, leaf histogram:

js_string_code_point_at                                     36451    (~85%)
perry_runtime::string::slice_range::copy_utf16_range         5174    (~12%)
js_array_get_f64                                               35
...everything else < 20 samples

~97% of the process is these two symbols. copy_utf16_range under codePointAt is the per-call UTF-16 materialization that makes it linear. TypeScript's scanner calls codePointAt per character, and lib.dom.d.ts — the largest file it loads — contains 45 non-ASCII characters, which is enough to put the entire scan on the quadratic path.

Confirmed on both 0.5.1579 (663 s) and 0.5.1593 (658 s), so this is current-main behaviour, not a stale toolchain.

Blast radius

Any program that scans text with codePointAt falls off this cliff the moment its input contains one accented character, curly quote, em dash or emoji — parsers, tokenizers, lexers, markdown and template engines, CSV/JSON scanners, syntax highlighters. The input does not have to be "a Unicode workload"; one character in a megabyte is enough.

Suggested fix

Give codePointAt the same treatment #10067 gave charCodeAt and bracket indexing in crates/perry-runtime/src/string/char_ops.rs — it needs the same UTF-16 index mapping rather than re-deriving the prefix per call. codePointAt additionally has to combine a surrogate pair, but that is an O(1) step once the index lookup is O(1).

Worth checking the other accessors on that path at the same time (at, charAt, codePointAt via iterator/spread) so the next one is not found the same way.

Reproduction

npm install typescript@5.9.3
echo 'import "typescript/lib/_tsc.js";' > tsc-entry.ts
# package.json: {"perry":{"compilePackages":["typescript"],"allow":{"compilePackages":["typescript"]}}}
perry compile tsc-entry.ts -o tsc-perry
time ./tsc-perry --noEmit demo.ts     # demo.ts = any 2-line file with a type error

Related: #10055 (the same pathology, for charCodeAt), #10067 (the fix that missed this accessor).

[proggeramlug]

Fixed in #10664 (branch fix/10656-codepointat-linear, ready for review, verified locally).

codePointAt now routes through utf16_unit_at — the same lazy index #10067 gave charCodeAt — and applies the spec algorithm over code units, so no bespoke decoding is needed and the bounded WTF-8 stepping #6085 requires is preserved.

	before	after	node
200k reads, non-ASCII lib.dom.d.ts	13,049 ms	2 ms	1 ms
n=40,000 scan, one \u00e9	518 ms	1 ms	0 ms
tsc --noEmit demo.ts	658.31 s user	85.04 s user	0.80 s

7.7× on real tsc, and the predicted-vs-measured check held: the profile attributed ~97% to this function and its callee, which predicted 20–90 s, and the measurement landed at 85 s.

Values are byte-identical to node, including the astral/surrogate cases ("a\u{1F600}b" → 97, 128512, 56832, 98).