ReviewOS

zig-utils/zig-js

JSON: make reviver source lookup linear in parsed width

#517
Closed chris opened this 9 days ago ·
9 days ago

Parent: #473 Related: #493

Defect

JSON.parse(text, reviver) records primitive source metadata in one flat list. Every InternalizeJSONProperty callback scans that full list backward to find (holder, key, unchanged value), so a flat array/object with n primitives performs Θ(n²) metadata comparisons before invoking the required callbacks.

A production ReleaseFast growth witness on a flat numeric array measured 16k → 32k → 64k elements at 0.23s → 0.76s → 2.98s (approximately 4x at the larger doubling). Results and context.source checksums remained correct.

Implementation

  • Replace the global reverse scan with invocation-local source metadata indexed first by parsed holder and then by property key.
  • Keep only the last primitive source for duplicate object keys, matching JSON overwrite semantics.
  • Retain the unchanged-value check so reviver-visible mutations suppress context.source exactly as required.
  • Do not attach metadata to shared engine objects or introduce process-global state.

Acceptance

  • Deterministic tests cover arrays, numeric-key object ordering, duplicate keys, escaped keys, -0/0, NaN-inapplicability, and reviver mutation.
  • A growth witness demonstrates near-linear source lookup work/time rather than quadratic scanning.
  • Focused normal + TSan gates and JSON.parse test262 pass with zero regressions.
  • Exact-parent evidence records representative/adversarial impact without unsupported wall-time claims.
9 days ago

Implementation audit refinement: ECMA-262 §25.5.2.4 passes the original child parse record down only when SameValue(parseRecord.[[Value]], currentValue) holds. A holder/key index is therefore insufficient: an earlier reviver callback can move a parsed object into a later sibling, and object-attached metadata would incorrectly follow it.

The implementation will instead retain an invocation-local JSON Parse Record tree: array children stay position-aligned, object children are keyed after duplicate-key overwrite, and each recursive call receives only the record selected by its parent. This both removes the global Θ(n²) scan and preserves mutation semantics. The value check will use SameValue (including +0/-0 distinction), not ===.

9 days ago

Completed and landed directly on main.

The implementation now carries the ECMA-262 JSON Parse Record hierarchy: array records remain position-aligned, object records are keyed after duplicate overwrite, and child records propagate only through SameValue at the original tree position. This also corrects +0/-0 mutation, moved-object source leakage, numeric-key order, escaped keys, duplicates, and callable replacement traversal. No-reviver parsing allocates no parse records.

Growth witness (16k/32k/64k flat primitives, ReleaseFast user time): 0.21/0.73/2.94s before → 0.05/0.05/0.10s after. Seven-pair exact-parent medians: wall 238.862 → 44.800 ms (0.188x), instructions 0.1248x, cycles 0.1890x, peak RSS 46.3 → 37.2 MB. Identities/checksums matched with no discards; cache counters are unavailable, so no cache claim is made.

Verification: focused normal + TSan; full unit 1,545 passed / 1 expected skip / 0 failed or leaked; ReleaseFast JSON.parse test262 77/77, flips 0 and regressions 0.

Sign in to comment on this issue.