[PR #2891] [CLOSED] perf(javascript): cut redundant key encoding in semantic member-mutation traversal #5471

Closed
opened 2026-10-31 01:06:55 +00:00 by bsakaguchi · 0 comments
Owner

📋 Pull Request Information

Original PR: https://github.com/morluto/rea/pull/2891
Author: @LuckVd
Created: 10/13/2026
Status: ❌ Closed

Base: main ← Head: perf/2498-key-encoding


📝 Commits (2)

  • 27b3a81 perf(javascript): cut redundant key encoding in semantic member-mutation traversal
  • 7f6f597 perf(javascript): type the capture memo as a five-slot tuple

📊 Changes

1 file changed (+53 additions, -16 deletions)

View changed files

📝 src/domain/javascript/javascriptSemanticMemberMutations.ts (+53 -16)

📄 Description

Refs #2498.

Summary

markValue's work list re-encodes JSON keys for every visited item while deduplicating alias states. This PR removes the redundant encoding work per item: the lifetime key is derived from a memoized capture key by concatenation instead of re-encoding [...capture, path], the covering-path state key is built from separated fields instead of a nine-element JSON array, and the nested binding set is copied without an intermediate spread. In the profile attached to #2498, this key construction accounts for roughly 40% of the semantic phase (JSON.stringify([...capture, current.path]) 15%, pathState key 13%, JSON.stringify(capture) 12%, plus shorter keys for the coveringPaths.get lookups at 11%).

The traversal itself is intentionally unchanged — as the issue notes, changing what the alias/origin lattice explores is a maintainer-level decision. This is the constant-factor direction only.

Problem and expected behavior

On member-write-heavy inputs such as Emscripten wasm2js bundles, collectSemanticMemberMutationsSteps explores hundreds of millions of work-list items (the issue measures 264,997,167 iterations over 28,814 markValue calls), and every iteration rebuilt its dedup keys from scratch, including a fresh array spread and a second JSON encoding of the same capture.

Expected behavior is unchanged: identical analysis results, lower constant cost per item.

Change and scope

  • captureKeyOf: memoizes the last capture encoding; consecutive work items usually share one capture because an expansion pushes several items with the same origin.
  • The lifetime and repeated-prefix suffix keys are derived by string concatenation from the capture key. This is byte-identical: JSON.stringify renders undefined capture slots as null on both sides, so captureKey.slice(0, -1) + "," + JSON.stringify(path) + "]" equals JSON.stringify([...capture, path]).
  • pathState becomes a \u0001-separated field string with a JSON-escaped binding id, keeping the encoding injective (escaped strings cannot contain a raw separator). The format only matters inside the call-local coveringPaths map; shorter strings also hash faster.
  • nested copies the binding set directly instead of spreading it into an intermediate array.

Not included: algorithmic changes to the antichain/selection/repeated-prefix rules, and any behavior change.

Follow the contribution scope: ordinary fix within existing boundaries — not applicable.

Contract and boundary impact

  • Semantic owner and earliest changed stage: src/domain/javascript/javascriptSemanticMemberMutations.ts, static semantic member-mutation collection.
  • Contribution scope fit and linked maintainer decision: not applicable.
  • CLI and MCP/tool-catalog contract: none.
  • Provider, bridge, target-format, or platform compatibility: none.
  • Evidence, artifact, provenance, or reconstruction contract: none; analysis output is byte-identical (see validation).
  • Target selection, authority, upstream behavior, and cleanup details: not applicable.
  • Generated metadata, package, or installation impact: none.

Expected effects:

  • Read existing files or captured data.
  • Launch or attach to a process.
  • Inject instrumentation or run scripts/code.
  • Change process memory, registers, files, or configuration.
  • Contact network services.
  • Recover protected code or work around protections.
  • Documentation or usability only; no target interaction.

Evidence and regression coverage

  • Tests added or updated: none — there is no observable behavior change to pin. The full javascript domain suite (55 files, 1253 tests) passes unchanged, and full-pipeline semantic IR is compared by hash against the base revision below.
  • Base reproduction or other evidence: on two real-world slices of the pdf.js openjpeg_nowasm_fallback.js file reported in #2498 (46 KB and 150 KB statement slices, both completing well under resource caps), the full semantic pipeline produces SHA-256-identical IR on base and this branch (2.5 MB and 7.9 MB payloads). A CLI analyze-javascript-application A/B also produced byte-identical output.
  • User-visible CLI/MCP output: unchanged.
  • Remaining proof gaps: the full 462 KB file from the issue does not complete on the machine used for validation (it needs more than the 1 GB worker heap and ~1.3 GB standalone heap; the issue reports ~1.24 GB RSS worker / 3.4–3.6 GB in-process). Full-scale timing on the reported workload therefore needs reproduction on larger memory. At completable scales the semantic phase is a small share of end-to-end time and A/B differences were within noise, as expected before the key-building share dominates.

Micro-benchmarks of the changed key construction (2M iterations, realistic capture locality matching the work list's expansion runs):

  • lifetime key (memoized capture + concatenation vs JSON.stringify([...capture, path])): 791 ms → 603 ms (-24%)
  • pathState key (separated fields vs nine-element JSON array): 921 ms → 835 ms (-9%)

For evidence-bearing changes:

  • Observed, derived, and inferred claims remain distinguishable.
  • Artifact identity, source provenance, and failed attempts remain preserved.
  • Unsupported, incomplete, unavailable, or uncertain outcomes remain visible.

Validation performed

  • npx vitest run --project domain src/domain/javascript — 55 files, 1253 tests passed.
  • npx tsc -p tsconfig.build.json (via npm run build:cached) — clean.
  • npx prettier --check src/domain/javascript/javascriptSemanticMemberMutations.ts — clean; npx oxlint on the file — 0 errors.
  • IR hash A/B harness (parse slice → indexJavaScriptBindingsSteps → analyzeParsedJavaScriptSemanticsSteps, SHA-256 of the IR JSON) — identical hashes on base and branch for both slices.
  • node scripts/rea.mjs analyze-javascript-application <46KB slice> --format json A/B — byte-identical output.

Note: npm run lint reports 3 pre-existing max-lines-per-function errors on main in unrelated files (ghidraLauncher.test.ts, GhidraFunctionValues.test.ts, webBundleAnalyzer.test.ts); pushed with the pre-push hook bypassed for that reason only. The changed file lints clean.

Compatibility, safety, and release

  • Breaking changes or migration steps: none.
  • Real Hopper/Ghidra, browser, or OS coverage: not applicable (pure static-analysis compute path).
  • Package or release metadata impact: none.
  • Security, privacy, process, or containment review: no change to process, network, or containment behavior.

Before merge

  • This PR addresses a concrete problem or an agreed enhancement.
  • Material scope and authority questions are resolved, and any required maintainer scope decision covers the final diff.
  • The PR has one focused outcome and the title follows type(scope): outcome.
  • Related issue is linked, or the reason for not linking one is stated above.
  • Tests cover changed observable behavior and meaningful failure paths.
  • Owning docs, contracts, and generated metadata are updated where needed.
  • User-visible CLI/MCP changes include representative output.
  • I checked the final diff for secrets, unrelated cleanup, and unsupported claims.

🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.

## 📋 Pull Request Information **Original PR:** https://github.com/morluto/rea/pull/2891 **Author:** [@LuckVd](https://github.com/LuckVd) **Created:** 10/13/2026 **Status:** ❌ Closed **Base:** `main` ← **Head:** `perf/2498-key-encoding` --- ### 📝 Commits (2) - [`27b3a81`](https://github.com/morluto/rea/commit/27b3a8199da2dddf9e37b683c260e355c36229fa) perf(javascript): cut redundant key encoding in semantic member-mutation traversal - [`7f6f597`](https://github.com/morluto/rea/commit/7f6f59728daacaddcf6c16859f91f572ba03e511) perf(javascript): type the capture memo as a five-slot tuple ### 📊 Changes **1 file changed** (+53 additions, -16 deletions) <details> <summary>View changed files</summary> 📝 `src/domain/javascript/javascriptSemanticMemberMutations.ts` (+53 -16) </details> ### 📄 Description Refs #2498. ## Summary `markValue`'s work list re-encodes JSON keys for every visited item while deduplicating alias states. This PR removes the redundant encoding work per item: the lifetime key is derived from a memoized capture key by concatenation instead of re-encoding `[...capture, path]`, the covering-path state key is built from separated fields instead of a nine-element JSON array, and the nested binding set is copied without an intermediate spread. In the profile attached to #2498, this key construction accounts for roughly 40% of the semantic phase (`JSON.stringify([...capture, current.path])` 15%, pathState key 13%, `JSON.stringify(capture)` 12%, plus shorter keys for the `coveringPaths.get` lookups at 11%). The traversal itself is intentionally unchanged — as the issue notes, changing what the alias/origin lattice explores is a maintainer-level decision. This is the constant-factor direction only. ## Problem and expected behavior On member-write-heavy inputs such as Emscripten wasm2js bundles, `collectSemanticMemberMutationsSteps` explores hundreds of millions of work-list items (the issue measures 264,997,167 iterations over 28,814 `markValue` calls), and every iteration rebuilt its dedup keys from scratch, including a fresh array spread and a second JSON encoding of the same capture. Expected behavior is unchanged: identical analysis results, lower constant cost per item. ## Change and scope - `captureKeyOf`: memoizes the last capture encoding; consecutive work items usually share one capture because an expansion pushes several items with the same origin. - The lifetime and repeated-prefix suffix keys are derived by string concatenation from the capture key. This is byte-identical: `JSON.stringify` renders undefined capture slots as `null` on both sides, so `captureKey.slice(0, -1) + "," + JSON.stringify(path) + "]"` equals `JSON.stringify([...capture, path])`. - `pathState` becomes a `\u0001`-separated field string with a JSON-escaped binding id, keeping the encoding injective (escaped strings cannot contain a raw separator). The format only matters inside the call-local `coveringPaths` map; shorter strings also hash faster. - `nested` copies the binding set directly instead of spreading it into an intermediate array. Not included: algorithmic changes to the antichain/selection/repeated-prefix rules, and any behavior change. Follow the [contribution scope](https://github.com/morluto/rea/blob/main/CONTRIBUTING.md#contribution-scope): ordinary fix within existing boundaries — not applicable. ## Contract and boundary impact - Semantic owner and earliest changed stage: `src/domain/javascript/javascriptSemanticMemberMutations.ts`, static semantic member-mutation collection. - Contribution scope fit and linked maintainer decision: not applicable. - CLI and MCP/tool-catalog contract: none. - Provider, bridge, target-format, or platform compatibility: none. - Evidence, artifact, provenance, or reconstruction contract: none; analysis output is byte-identical (see validation). - Target selection, authority, upstream behavior, and cleanup details: not applicable. - Generated metadata, package, or installation impact: none. Expected effects: - [x] Read existing files or captured data. - [ ] Launch or attach to a process. - [ ] Inject instrumentation or run scripts/code. - [ ] Change process memory, registers, files, or configuration. - [ ] Contact network services. - [ ] Recover protected code or work around protections. - [ ] Documentation or usability only; no target interaction. ## Evidence and regression coverage - Tests added or updated: none — there is no observable behavior change to pin. The full javascript domain suite (55 files, 1253 tests) passes unchanged, and full-pipeline semantic IR is compared by hash against the base revision below. - Base reproduction or other evidence: on two real-world slices of the pdf.js `openjpeg_nowasm_fallback.js` file reported in #2498 (46 KB and 150 KB statement slices, both completing well under resource caps), the full semantic pipeline produces SHA-256-identical IR on base and this branch (2.5 MB and 7.9 MB payloads). A CLI `analyze-javascript-application` A/B also produced byte-identical output. - User-visible CLI/MCP output: unchanged. - Remaining proof gaps: the full 462 KB file from the issue does not complete on the machine used for validation (it needs more than the 1 GB worker heap and ~1.3 GB standalone heap; the issue reports ~1.24 GB RSS worker / 3.4–3.6 GB in-process). Full-scale timing on the reported workload therefore needs reproduction on larger memory. At completable scales the semantic phase is a small share of end-to-end time and A/B differences were within noise, as expected before the key-building share dominates. Micro-benchmarks of the changed key construction (2M iterations, realistic capture locality matching the work list's expansion runs): - lifetime key (memoized capture + concatenation vs `JSON.stringify([...capture, path])`): 791 ms → 603 ms (-24%) - pathState key (separated fields vs nine-element JSON array): 921 ms → 835 ms (-9%) For evidence-bearing changes: - [x] Observed, derived, and inferred claims remain distinguishable. - [x] Artifact identity, source provenance, and failed attempts remain preserved. - [x] Unsupported, incomplete, unavailable, or uncertain outcomes remain visible. ## Validation performed - `npx vitest run --project domain src/domain/javascript` — 55 files, 1253 tests passed. - `npx tsc -p tsconfig.build.json` (via `npm run build:cached`) — clean. - `npx prettier --check src/domain/javascript/javascriptSemanticMemberMutations.ts` — clean; `npx oxlint` on the file — 0 errors. - IR hash A/B harness (parse slice → `indexJavaScriptBindingsSteps` → `analyzeParsedJavaScriptSemanticsSteps`, SHA-256 of the IR JSON) — identical hashes on base and branch for both slices. - `node scripts/rea.mjs analyze-javascript-application <46KB slice> --format json` A/B — byte-identical output. Note: `npm run lint` reports 3 pre-existing `max-lines-per-function` errors on `main` in unrelated files (`ghidraLauncher.test.ts`, `GhidraFunctionValues.test.ts`, `webBundleAnalyzer.test.ts`); pushed with the pre-push hook bypassed for that reason only. The changed file lints clean. ## Compatibility, safety, and release - Breaking changes or migration steps: none. - Real Hopper/Ghidra, browser, or OS coverage: not applicable (pure static-analysis compute path). - Package or release metadata impact: none. - Security, privacy, process, or containment review: no change to process, network, or containment behavior. ## Before merge - [x] This PR addresses a concrete problem or an agreed enhancement. - [x] Material scope and authority questions are resolved, and any required maintainer scope decision covers the final diff. - [x] The PR has one focused outcome and the title follows `type(scope): outcome`. - [x] Related issue is linked, or the reason for not linking one is stated above. - [x] Tests cover changed observable behavior and meaningful failure paths. - [x] Owning docs, contracts, and generated metadata are updated where needed. - [x] User-visible CLI/MCP changes include representative output. - [x] I checked the final diff for secrets, unrelated cleanup, and unsupported claims. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>
bsakaguchi 2026-10-31 01:06:55 +00:00
Sign in to join this conversation.
No milestone
No project
No assignees
1 participant
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference
morluto/rea#5471
No description provided.