perf: no rope/cons-string representation makes accumulator concatenation quadratic (514x Node at n=16000; 17.9% of iso_miss)

[proggeramlug]

No rope / cons-string representation: accumulator concatenation is quadratic

grep -riE '\brope\b|cons_?str' crates/perry-runtime/src returns zero hits. Every
string concatenation materializes bytes eagerly, so the standard accumulate-in-a-loop
pattern is O(n^2) where V8's cons-strings make it O(n) amortized.

This is the largest single cost in the worst benchmark row. iso_miss (Perry 2.13x
Node, the widest remaining gap) spends 17.9% of self time in js_string_concat_chain,
driven by one line:

seen = seen + "[" + names[i] + "]";   // iso_miss.ts:205, per name per env frame

concat_chain itself is already well optimized — #7912 fuses the chain and sizes the
scratch to the real arity, and its comment cites this exact line. The remaining cost is
not call overhead, it is copying the accumulated prefix on every append.

Measured

function build(n: number): number {
  let s = "";
  for (let i = 0; i < n; i++) s = s + "[" + "abc" + "]";
  return s.length;
}

n	Perry	Node 26.5.1
2000	11 ms	1 ms
4000	63 ms	0 ms
8000	459 ms	1 ms
16000	1888 ms	1 ms

Perry's time grows ~4-7x per doubling (quadratic); Node is flat.

This is not Node deferring the work. Forcing full materialization by reading every
997th code unit out of the result:

n	Perry	Node
2000	10 ms	1 ms
16000	2057 ms	4 ms

Node still finishes in 4 ms, so its cons-string plus a single flatten is genuinely linear.
At n=16000 Perry is 514x slower on the same work.

Suggested direction

A cons-string node (left, right, total length) with lazy flattening on first indexed
read is the standard fix and is what V8/JSC do:

• + on two strings allocates an O(1) cons node instead of copying
• .length is O(1) from the stored total
• the first operation needing contiguous bytes flattens once, O(n)

The parts that already exist and would need to participate: js_string_concat_chain
(crates/perry-runtime/src/string/concat.rs), js_string_equals, js_string_compare,
and js_get_string_pointer_unified — anything reading raw bytes needs a flatten call
first. The GC also needs to trace the two child edges of a cons node.

This is a real architectural change rather than a local optimization, which is why I am
filing it rather than attempting it: it touches the string representation everywhere. But
it is the single biggest remaining item on the worst row, and accumulator concatenation is
one of the most common patterns in real JavaScript.

[proggeramlug]

I completed the blast-radius survey and am choosing a staged implementation rather than a producer-first rope patch.

The reason is concrete: excluding tests, 174 runtime files (356 sites) and 54 stdlib files (82 sites) perform explicit StringHeader payload pointer arithmetic. There are also 192 shared borrowed-byte-helper calls, 170 one-line extern-C APIs with StringHeader parameters, and generated inline payload reads. A cons returned only from direct a+b can still reach any of those consumers, so missing one is silent data corruption.

The design is committed here:
https://github.com/proggeramlug/perry/blob/c102929914978d679879f142de40218b717d4d17/ROPE-DESIGN.md

Key decisions:

• Keep STRING_TAG for all heap strings; use a distinct traced GC_TYPE_CONS_STRING behind it.
• Preserve the 20-byte StringHeader prefix so .length remains the offset-0 O(1) load.
• Trace left, right, and the cached flat result. Cache publication is an old-to-young store and needs a verified write barrier.
• Flatten iteratively through rooted one-/two-/N-operand adapters. A generic borrowed string_data pointer must not begin allocating behind callers' backs.
• Carry exact WTF-8 boundary metadata. A high-surrogate/low-surrogate join changes two 3-byte sequences into one 4-byte scalar, so simply summing byte lengths and OR-ing flags is incorrect.
• Guard the generated charCodeAt and literal-equality payload reads; heap-string .length stays inline.

Proposed landing order:

1. Add a reader-inventory lint/ratchet and flat-only/rooted reader APIs; migrate crates/perry-runtime/src/string with no cons producer.
2. Migrate runtime consumer clusters, stdlib FFI, and codegen inline byte readers until only audited flat primitives can perform payload arithmetic.
3. Land the inert GC type, constructor, iterative flatten/cache, tracing tests, and static write-barrier sabotage test; still no production producer.
4. Pilot direct js_string_concat behind an A/B knob and measure time + instructions + RSS.
5. Preserve perf(runtime): concat a chain of heap strings without transient roots (iso_miss -16%) #7912's existing concat-chain fusion, but retain the accumulated prefix and fuse only the suffix before making one cons node. This is the stage expected to fix rope.ts, rope2.ts, and iso_miss.
6. Tune thresholds and enable only if compute improves without an RSS regression, then remove the knob.

The first safe slice is therefore the reader inventory/enforcement plus central rooted flat-view APIs, not the cons producer. Production strings remain flat throughout that slice, so its allowlist can ratchet down without creating a wrong-answer window.