ReviewOS

zig-utils/zig-js

JSON: make stringify replacer deduplication linear

#519
Closed chris opened this 8 days ago ·
8 days ago

Parent: #473 Related: #493

Defect

JSON.stringify(value, replacerArray) preserves first occurrence order by scanning the complete accepted PropertyList for every string/number wrapper entry. A unique user-controlled replacer array therefore performs Θ(n²) byte comparisons before serialization.

A production ReleaseFast growth witness using unique keys measured 2k → 4k → 8k → 16k entries at 0.03s → 0.21s → 1.15s → 5.11s user time while producing the correct output.

Implementation

  • Keep the ordered PropertyList required by ECMA-262.
  • Add invocation-local content membership so duplicates are rejected without rescanning prior entries.
  • Preserve coercion/getter order, String/Number wrapper behavior, encoded property keys, first-occurrence order, OOM propagation, and no-GIL isolation.

Acceptance

  • Tests cover unique keys, duplicates, encoded keys, numbers, wrappers with observable coercion, ignored values, and throwing accessors/coercions.
  • A deterministic growth row demonstrates near-linear membership work rather than quadratic scanning.
  • Focused normal + TSan, full unit, and JSON.stringify test262 pass with zero regressions.
  • Exact-parent evidence records CPU and memory impact with matching output/checksum identity.
8 days ago

Implemented and measured on main:\n\n- benchmark total pipeline\n- isolated membership benchmark\n- linear ordered membership index\n- release temporary membership buckets\n- exact-parent evidence\n\nThe isolated 16,384-key membership workload improved from 177.012 ms to 6.683 ms (0.038x) and from 3.60 billion to 120.9 million instructions (0.0336x). The complete stringify pipeline used 0.8661x the instructions; its wall-time sample was too noisy for a stable claim.\n\nExact follow-up evidence caught arena-retained hash buckets. Moving those invocation-local buckets to the realm allocator and deinitializing them reduced median peak RSS from 45,465,600 to 34,258,944 bytes with effectively unchanged runtime (0.999x). Energy was below useful counter resolution and cache-miss attribution was unavailable, so no claims are made for either.\n\nSemantics are covered for duplicate strings and wrappers, encoded-NUL keys, ignored plain objects, and throwing getters/coercions. Focused normal and TSan tests pass, the complete unit suite is 1545 pass / 1 expected skip / 0 failures or leaks, and the ReleaseFast JSON.stringify test262 subtree remains 66/66 (0 flips).

8 days ago

Adjacent stringify optimization #557 is complete in a7da43f4, with evidence 6dbe188f. Replacer/property ordering remains exact, the bounded-OOM callback witness passes, and Test262 JSON.stringify remains 66/66.

Sign in to comment on this issue.