JSON.stringify: replace recursive traversal with bounded frames

Parent: #473 Follows: #556, #558, #1001, #1002

Measured problem

The clean real-GC ReleaseFast matrix at 8ca0d15b preserves every frozen checksum but leaves the two structure controls far behind system JavaScriptCore:

• representative_json_stringify_depth_4096: 1163.341 ms versus 111.120 ms (10.47x elapsed gap), checksum 83848800;
• representative_json_stringify_shallow_4096: 966.656 ms versus 104.796 ms (9.22x elapsed gap), checksum 63340200.

Those are seven fresh-process, order-balanced pairs with both medians above 50 ms. Raw evidence and exact binary/source/dependency hashes are in docs/.data/json-jit-pipeline-jsc-2026-10-01.json; the dated report is docs/.data/json-jit-pipeline-jsc-2026-10-01.md.

A separate five-second macOS sample capture of the exact deep runner recorded 3,005 main-thread samples. The call graph repeatedly cycles through four binary offsets; each appears about 1,564–1,569 times when recursive frames are counted. Source inspection identifies the corresponding semantic cycle as Stringifier.serializeProperty → serializeLoaded → serializeObject → serializeObjectEntry → serializeProperty for every object level. This mapping is an inference because the ReleaseFast binary does not retain function-level symbols. The sampler completed before the bounded wrapper stopped the runner during symbol-processing memory growth, so the capture is attribution only; all timing and correctness claims come from the completed matrix above.

Scope

• Replace recursive ordinary array/object traversal with an explicit, allocator-bounded serialization frame stack.
• Preserve the exact SerializeJSONProperty ordering: live Get, toJSON, replacer call, wrapper unboxing, cycle entry/leave, key snapshot, and output emission/rollback.
• Preserve active-ancestor cycle semantics without turning legal shared siblings into cycles.
• Preserve Proxy/accessor/host-exotic fallbacks, mutation between sibling callbacks, property order, indentation, undefined omission versus array null, BigInt throws, and the existing logical/native depth contract.
• Keep the completed output transfer and temporary-allocator ownership exact under moving GC, OOM, and no-GIL execution.
• Profile the shallow shared-sibling row separately from the deep chain so one improvement cannot hide a regression in the other.

Acceptance

• Focused tests cover deep objects, deep arrays, shallow shared siblings, aliases, cycles, getters, Proxy traps, toJSON, replacers, indentation, omission rollback, BigInt, and abrupt completion order.
• The 50,000-level deep witnesses still throw catchable RangeError in tree and required-VM modes; allocation-failure sweeps leave no partial state or leak.
• JSON test262, tree/required-VM agreement, real-GC moving collection, no-GIL, and TSan gates remain exact.
• Seven-pair exact-parent evidence shows stable lower CPU work on both depth-4096 and shallow-4096 rows, with base/variant/reviver/escaped controls and exact checksums.
• A fresh seven-pair direct-JSC matrix materially narrows both 10.47x/9.22x gaps without changing jobs, warmup, timed boundary, or output.

Guardrails

No source/workload recognition, reduced nesting, cached final JSON, omitted callback/Get work, global visited set, looser stack limit, changed checksum, arena-only shortcut, or benchmark-specific branch.

The complete frozen baseline and qualification record is now published in 0d2c6cf: https://github.com/zig-utils/zig-js/blob/main/docs/.data/json-jit-pipeline-2026-10-01.md

The direct system-JSC evidence is in d8813af: https://github.com/zig-utils/zig-js/blob/main/docs/.data/json-jit-pipeline-jsc-2026-10-01.md

Current structure-control gaps are 10.47x at depth 4096 and 9.22x at shallow 4096. A bounded macOS sample completed before the memory guard stopped symbol post-processing; stripped offsets repeatedly map by source inspection to the serializeProperty -> serializeLoaded -> serializeObject -> serializeObjectEntry recursion. Treat that as attribution only; the 84 complete order-balanced samples remain the timing source of truth.

Implementation landed on main in 1c83703.

Correctness gates against the real zig-gc checkout (0285ef801dd221a4ae8e88b31a09ae31627657a3):

• Debug unit filter JSON stringify: 15/15, 0 failed, 0 leaked
• TSan unit filter JSON stringify: 15/15, 0 failed, 0 leaked (includes shared no-GIL, moving collection, and OOM sweeps)
• test262 test/built-ins/JSON: 165 pass, 0 fail
• required-VM witness sweep: 165 agree, 0 diverge
• preserved deep/shared witness: tree OK true, VM OK true
• preserved 50,000-level limit witness: tree OK true, VM OK true

The dependency path was restored before commit. Diagnostic screens preserved the frozen depth/shallow checksums and reduced wall/cycles; I am now collecting direct-provenance seven-pair exact-parent evidence for 700736c8 -> 1c837038. The issue remains open until that evidence and the direct-JSC matrix are published.

The first two direct-provenance control rows are published in 292e2ba (raw JSON + dated Markdown, seven balanced pairs, exact checksums, no discarded samples):

• base: candidate/parent wall 1.091x, instructions 1.0523x, cycles 1.0771x (stable)
• variant: wall 1.133x, instructions 1.0283x, cycles 1.0062x, but wall/cycle RSD is diagnostic

This is a real control regression, so #1019 remains open. Attribution to the source path is concrete: the ordinary-object leaf attempt emits primitive members before discovering a later nested object, rolls the output back, then serializes through the general frame path. The representative base row repeats that pattern 198,000 times. The next change will preflight small ordinary-object values into stack-local storage before output, eliminating tentative emission while retaining the callback-free primitive-leaf path and exact cycle/OOM ordering.

Follow-up optimization landed directly on main in b6ae214.

The three-file change keeps the explicit-frame semantics from 1c83703 while:

• inlining the first eight continuation frames and removing full-frame copies on pop;
• fusing one bounded level of proven callback-free primitive-leaf children;
• reusing immutable stable-key vectors across identical Shapes only after each Object revalidates its accessor, attribute, and delete/re-add metadata;
• retaining the general rooted frame path for one-link chains, Proxies, accessors, exotics, callbacks, replacers, cycles, and deeper descendants.

Correctness on the pinned real collector 0285ef801dd221a4ae8e88b31a09ae31627657a3:

• Debug JSON stringify: 15/15 passed, 0 failed, 0 leaked
• TSan JSON stringify: 15/15 passed, 0 failed, 0 leaked/races
• test262 test/built-ins/JSON: 165 pass, 0 fail
• required-VM witness: 165 agree, 0 diverge

Single-pair diagnostic screens against exact parent 700736c preserve every frozen checksum and show:

• base: ~4.5% lower wall, ~4.4% lower cycles, ~2.5% fewer instructions
• anti-specialization variant: ~8.6% lower wall, ~5.0% lower cycles, ~4.6% fewer instructions
• depth-4096: ~8.1% lower wall, ~7.2% lower cycles, with a disclosed ~6.8% instruction increase
• shallow-4096: ~22.8% lower wall, ~23.1% lower cycles/instructions

These are screens, not publication evidence. The issue remains open while I build direct-provenance final binaries and collect the required seven balanced pairs plus a fresh direct-JSC matrix.

Final exact-parent follow-up evidence is now on main in three four-file commits:

• af83650 — base + anti-specialization variant
• 6bfee98 — reviver/source + escaped-string controls
• 0ae48ca — depth-4096 + shallow-4096 controls

All six rows use direct binaries for the exact parent 292e2ba -> b6ae214, seven order-balanced pairs, 14 samples per row, exact frozen checksums, real zig-gc 0285ef8, and no discarded samples.

Stable CPU-work changes (candidate/parent):

• base: instructions 0.9177x, cycles 0.9158x
• variant: instructions 0.9373x, cycles 0.9137x
• reviver/source: instructions 0.9944x, cycles 0.9935x
• escaped strings: instructions 0.9998x, cycles 0.9964x
• depth-4096: instructions 0.9110x, cycles 0.9598x
• shallow-4096: instructions 0.7741x, cycles 0.7817x

Two fresh direct-JSC attempts were deliberately not committed. The first depth row had 8.46% RSD and a 1.347 s median versus 1.063 s in the exact-parent run from the same binary; the second had 21.03% depth RSD, 48.03% reviver RSD, and 24.22% escaped-string RSD while unrelated Home/Stacks jobs were consuming CPU. Both generated artifacts were untracked and removed. The issue remains open until a clean direct-JSC matrix establishes both gap reductions.

Preserved the first same-window baseline/candidate/JSC triplet matrix on main in d165a68 instead of retrying away an unfavorable result. The 126-sample report is explicitly rejected as acceptance evidence: the representative gap narrows 4.00x -> 3.81x, but depth-4096 widens 10.38x -> 11.43x with 41.42% candidate RSD; shallow narrows 9.06x -> 7.10x with 39.98% candidate RSD. No sample was discarded.\n\nReport: https://github.com/zig-utils/zig-js/blob/main/docs/.data/json-jit-pipeline-jsc-gap-reduction-2026-10-02.md\nRaw: https://github.com/zig-utils/zig-js/blob/main/docs/.data/json-jit-pipeline-jsc-gap-reduction-2026-10-02.json\n\nThe failure is now driving a general runtime fix: repeated deep calls rebuild and copy the same geometric continuation buffer. A three-run balanced screen of an interpreter-local, reentrancy-safe reusable buffer preserves checksums and moves depth to ~0.890x the original recursive baseline (and ~0.976x the prior explicit-frame candidate), while shallow is ~0.788x / ~0.991x. This is diagnostic only; correctness/TSan and seven-pair evidence remain pending.

Runtime follow-up landed directly on main in b617e7c. The three-file change retains one explicit-frame backing buffer for an Interpreter lifetime, so repeated deep calls no longer rebuild/copy a geometric ArrayList. Reentrant stringify callbacks lease a separate fallback; each no-GIL worker owns a distinct Interpreter/cache.\n\nCurrent qualification against real zig-gc 0285ef8:\n- focused JSON stringify: 16/16 passed, 0 failed/leaked\n- strengthened deep-spill no-GIL witness: passed\n- same witness under TSan, no suppressions: passed\n- three-run balanced diagnostic, exact checksums: depth-4096 median ~0.890x original recursive baseline / ~0.976x prior explicit-frame candidate; shallow-4096 ~0.788x / ~0.991x\n\nThe diagnostic is not publication evidence. JSON test262, required-VM, exact-parent seven-pair evidence, and a fresh same-window JSC triplet matrix remain before closure.

Pushed 9692d3f6 directly to main as rejected exact-parent evidence.

• seven order-balanced pairs are preserved with no discarded samples;
• six candidate samples measured 320.822–344.676 ms;
• the seventh overlapped an external Home Zig build and measured 853.280 ms at 60.46% boundary occupancy;
• candidate wall-time RSD is therefore 49.20%, so the report is explicitly diagnostic-only and does not satisfy the acceptance gate;
• offline docs-link gate: 368 files, all links resolve.

Raw evidence and the generated report are linked from docs/benchmarks.md. Collection will resume with fresh filenames once the external build/test stream is quiet.

The clean direct exact-parent batch is now published on main in ef98ab7e, 5f756db6, and 4099e91d.

Exact comparison: d165a68d → b617e7cf, direct immutable builds, seven order-balanced pairs per row, no discarded samples, exact frozen checksums.

Stable retired-instruction ratios:

• depth-4096: 0.9988x candidate/parent (parent RSD 0.034%, candidate RSD 0.024%);
• shallow-4096: 0.9994x (parent RSD 0.006%, candidate RSD 0.003%);
• base/variant/reviver/escaped controls: 0.9995x / 0.9999x / 0.9972x / 1.0002x.

The depth parent wall-time RSD is 9.60%, so the documentation explicitly limits the claim to stable CPU work rather than a broad elapsed-time speedup. All six raw schema-4 artifacts and generated reports are indexed in docs/benchmarks.md; the offline link gate passes 374 files.

Correctness gates already completed on the same candidate:

• JSON test262: 165 pass, 0 fail;
• forced tree/required-VM sweep: 165 agree, 0 diverge;
• 50,000-level object and array witnesses: catchable RangeError in both forced tree and required-VM modes;
• focused semantics, moving-GC/OOM coverage, no-GIL witness, and unsuppressed TSan witness pass.

The remaining acceptance item is the fresh seven-pair direct-JSC triplet proving that both original structure gaps narrow on a clean host.

Pushed c6082df7 directly to main with the complete second 126-sample triplet, explicitly marked rejected.

The medians moved both target gaps in the right direction (depth 10.52x → 10.09x; shallow 9.16x → 8.90x), but the distribution is not acceptance-grade:

• shallow baseline/candidate/JSC RSD: 30.01% / 28.52% / 41.56%;
• escaped-string baseline/candidate/JSC RSD: 52.03% / 42.49% / 30.10%;
• shallow candidate/baseline paired ratios span 0.51x–1.46x.

No sample was discarded. The raw artifact, generated report, and rejection rationale are linked from docs/benchmarks.md; the docs-link gate passes 375 files. I am rerunning only after a sustained-idle check, with collector chatter redirected away from the UI path.

The scheduler-contamination follow-up is now implemented under #1021 in e0e5550, 4550396, ff8d3b0, and 388a01f. The live guard rejects an actually contaminated host before sample 1 and leaves no artifacts. The clean seven-triplet rerun remains pending until unrelated command-bearing Bun work releases the host; no noisy replacement evidence will be published.

Pushed 9453de45 directly to main to close the explicit-frame allocation-failure proof gap.

The new exhaustive checkAllAllocationFailures witness covers:

• lazy frame-cache allocation;
• cached frame-buffer spill growth;
• reentrant stringify fallback growth while the outer cache is leased;
• unwind releasing the lease and emptying retained logical length;
• successful retry reusing the retained cache without stale frames.

Focused module gate: 2 passed, 0 failed, 238 MB bounded peak. This is test-only and flips 0 test262 cases. The final direct-JSC matrix and Home-driven repository gate remain the open acceptance items.

Final direct-JSC acceptance remains blocked by the repository tool gate tracked in #1021, but its upstream compiler failure now has a concrete root cause and fix shape: home-lang/home#834 comment. This is a Home diagnostic-list invariant bug, not resource pressure (fresh reproduction: exit 134 at a 138 MB bounded peak). No consumer-side workaround has been introduced.

The Home-driven repository gate is now clear on the current toolchain: benchmark-comparison-test passes all 19 validators, including the algorithmic-growth stage fixed by 9d435e3 / #1044.

The remaining direct-JSC acceptance run is still correctly blocked by host state. A fresh collector preflight on current main rejected before sample 1 and wrote neither artifact; it found active Stacks/ts-cloud Bun services, Home compiler/tests, a ReportCrash daemon, and unrelated Bun test jobs. No timing collection was started.