Repository navigation
perf: no rope/cons-string representation makes accumulator concatenation quadratic (514x Node at n=16000; 17.9% of iso_miss) #8394
Description
Activity
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.mdKey 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:
- Add a reader-inventory lint/ratchet and flat-only/rooted reader APIs; migrate crates/perry-runtime/src/string with no cons producer.
- Migrate runtime consumer clusters, stdlib FFI, and codegen inline byte readers until only audited flat primitives can perform payload arithmetic.
- Land the inert GC type, constructor, iterative flatten/cache, tracing tests, and static write-barrier sabotage test; still no production producer.
- Pilot direct js_string_concat behind an A/B knob and measure time + instructions + RSS.
- 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.
- 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.
No rope / cons-string representation: accumulator concatenation is quadratic
grep -riE '\brope\b|cons_?str' crates/perry-runtime/srcreturns zero hits. Everystring 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.13xNode, the widest remaining gap) spends 17.9% of self time in
js_string_concat_chain,driven by one line:
concat_chainitself is already well optimized — #7912 fuses the chain and sizes thescratch 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
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:
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 indexedread is the standard fix and is what V8/JSC do:
+on two strings allocates an O(1) cons node instead of copying.lengthis O(1) from the stored totalThe 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 callfirst. 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.