[PR #2962] [MERGED] perf(javascript): defer ambiguity expansion in version comparisons #5519

New issue

Closed

opened 2026-10-31 01:07:16 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-31 01:07:16 +00:00

Owner

📋 Pull Request Information

Original PR: https://github.com/morluto/rea/pull/2962
Author: @Shenrui-Ma
Created: 10/13/2026
Status: ✅ Merged
Merged: 10/13/2026
Merged by: @morluto

Base: main ← Head: perf/defer-version-match-candidates

📝 Commits (1)

5f6ebb0 perf(javascript): avoid quadratic temporary matching state

📊 Changes

3 files changed (+314 additions, -27 deletions)

View changed files

📝 src/domain/javascript/javascriptApplicationVersionKeys.ts (+35 -27)
➕ src/domain/javascript/javascriptApplicationVersionMatching.test.ts (+181 -0)
➕ tests/acceptance/applications/applicationVersionMatchingCli.test.ts (+98 -0)

📄 Description

Summary

Reduce temporary candidate allocation when comparing application versions with repeated module bodies. No separate issue; the CLI reproduction is included below.

Problem and expected behavior

With 3,000 identical factory bodies in a retained bundle, the source-digest tier allocates nine million candidate pairs, all discarded after later identity matches resolve the modules.

Change and scope

Retain ambiguous groups through the existing matching passes, then expand candidates only between their still-unmatched nodes. Preserve tier order without re-matching residual groups. Append to key buckets instead of copying growing arrays. Genuine ambiguity remains uncapped and can still require quadratic output.

Contract and boundary impact

Owner: JavaScript version matcher, grouping and candidate expansion.
Scope: existing comparison; advance maintainer decision not applicable.
CLI/MCP contracts and provider interfaces: unchanged.
Evidence, artifacts, provenance, and reconstruction: preserved.
Authority/cleanup: comparison of captured data only.
Generated metadata, packaging, and installation: no changes.

Expected effects:

Read existing files or captured data.

Evidence and regression coverage

Behavior tests pass on base and patch, covering late matching, residual ambiguity, cross-tier candidate union, and input ordering.

The production analyzer supplies inputs from two synthetic versions with identical bundles and different package versions. Complete CLI output matched before and after; a separate stdio MCP check also matched.

Combined results for both optimizations with 3,000 retained factories on Apple M5 Pro (macOS arm64, Node 24.18.0): medians of four fresh-process runs per revision, in alternating order.

Metric	Before	After
Wall time	3.330 s	2.295 s
CPU time	4.27 s	3.01 s
Peak process RSS	1,046.0 MiB	556.5 MiB

Measurements cover the comparison CLI, excluding input preparation, with compile caching disabled and filesystem caches uncontrolled. Unique, unmatched, and genuinely ambiguous controls had similar timings and overlapping RSS ranges.

Observations and derivations remain distinguishable.
Artifact identity, provenance, and failed attempts remain preserved.
Incomplete and uncertain outcomes remain visible.

Validation performed

Focused matching, CLI, and MCP tests passed, including Node 22/24/26 checks.
npm run check passed with warnings.
The full local suite on the benchmark base had 10 failing cases; all reproduced without the patch with matching error signatures.

Benchmark reproduction and recorded runs

Use two checkouts of bd2c202dd, differing only by this patch. Build each with the pinned Node/npm toolchain: npm ci, then npm run build:cached.

Set the checkout paths below. This macOS runner generates inputs with the baseline analyzer, checks complete output hashes, and retains inputs, output, and timings in the printed directory.

REA_BASE=/absolute/path/to/unmodified-base
REA_PATCH=/absolute/path/to/checkout-with-patch
python3 - "$REA_BASE" "$REA_PATCH" 3000 4 <<'PY'
import collections
import hashlib
import json
import os
from pathlib import Path
import re
import shutil
import statistics
import subprocess
import sys
import tempfile

if sys.platform != "darwin":
    raise SystemExit("This runner uses macOS /usr/bin/time -l and its byte RSS units.")
base, patched = map(lambda value: Path(value).resolve(), sys.argv[1:3])
count = int(sys.argv[3]) if len(sys.argv) > 3 else 3000
repeats = int(sys.argv[4]) if len(sys.argv) > 4 else 4
assert base != patched and count > 1 and repeats > 0
node = shutil.which("node")
assert node is not None
root = Path(tempfile.mkdtemp(prefix="rea-version-comparison-"))
env = dict(os.environ, NODE_DISABLE_COMPILE_CACHE="1")
env.pop("NODE_COMPILE_CACHE", None)
bundle = "globalThis.webpackChunkfixture.push([[1],{" + ",".join(
    f"{index}:function(){{}}" for index in range(count)
) + "}]);\n"
evidence = []
for version in [1, 2]:
    app = root / str(version)
    app.mkdir()
    (app / "chunk.js").write_text(bundle)
    (app / "package.json").write_text(json.dumps(
        {"name": "fixture", "version": f"{version}.0.0"}, indent=2
    ) + "\n")
    output = root / f"analysis-{version}.json"
    with output.open("w") as stdout, (root / f"analysis-{version}.stderr").open("w") as stderr:
        subprocess.run([node, str(base / "scripts/rea.mjs"),
                        "analyze-javascript-application", str(app), "--json"],
                       cwd=base, env=env, stdout=stdout, stderr=stderr, check=True)
    record = json.loads(output.read_text())
    graph = record["normalized_result"]["graph"]
    groups = collections.Counter(
        observation["properties"]["source_sha256"]
        for item in graph["nodes"] if item["kind"] == "javascript-module"
        for observation in item["observations"]
        if "source_sha256" in observation["properties"]
    )
    assert graph["coverage"]["status"] == "complete" and max(groups.values()) == count
    evidence.append(record)
input_file = root / "input.json"
input_file.write_text(json.dumps(dict(zip(["left", "right"], evidence))))
rows, expected = [], None
print("node:", subprocess.check_output([node, "--version"], text=True).strip())
print("evidence:", root)
print("round,variant,wall_s,cpu_s,peak_rss_bytes")
for iteration in range(repeats):
    order = [("base", base), ("patch", patched)]
    for label, repo in order if iteration % 2 == 0 else reversed(order):
        output, timing = root / f"{iteration}-{label}.json", root / f"{iteration}-{label}.time"
        with output.open("w") as stdout, timing.open("w") as stderr:
            subprocess.run(["/usr/bin/time", "-l", node, str(repo / "scripts/rea.mjs"),
                            "compare-application-versions", str(input_file), "--json"],
                           cwd=repo, env=env, stdout=stdout, stderr=stderr, check=True)
        data = output.read_bytes()
        result = json.loads(data)["normalized_result"]
        assert result["matching"]["ambiguous"] == 0
        assert result["matching"]["exact_node_identity"] >= count
        digest = hashlib.sha256(data).hexdigest()
        expected = expected or digest
        assert digest == expected, "Complete CLI output differs"
        text = timing.read_text()
        times = re.search(r"([\d.]+) real\s+([\d.]+) user\s+([\d.]+) sys", text)
        rss = re.search(r"(\d+)\s+maximum resident set size", text)
        assert times and rss
        row = [iteration, label, float(times[1]), float(times[2]) + float(times[3]), int(rss[1])]
        rows.append(row)
        print(",".join(map(str, row)), flush=True)
for label in ["base", "patch"]:
    selected = [row for row in rows if row[1] == label]
    print(label, "medians:", [statistics.median(row[index] for row in selected) for index in [2, 3, 4]])
(root / "runs.json").write_text(json.dumps(rows, indent=2) + "\n")
print("All complete CLI outputs have SHA-256", expected)
PY

Original observations behind the table:

round,revision,wall_s,cpu_s,peak_process_rss_bytes
0,baseline,3.21,4.16,1099841536
0,patched,2.29,2.98,581025792
1,patched,2.31,3.06,591986688
1,baseline,3.32,4.27,1101004800
2,baseline,3.34,4.27,1093828608
2,patched,2.28,2.97,581140480
3,patched,2.30,3.04,585875456
3,baseline,3.39,4.31,1091715072

Run the regression tests in the patched checkout:

npm run test:focused -- src/domain/javascript/javascriptApplicationVersionMatching.test.ts tests/acceptance/applications/applicationVersionMatchingCli.test.ts

Compatibility, safety, and release

No breaking changes, migration, or new dependencies. Performance measurements cover the synthetic workload above; production-wide performance is unmeasured.

Before merge

Concrete problem and focused conventional title.
Scope and authority resolved.
Reason for no linked issue stated.
Matching and ambiguity semantics covered.
No contract/documentation/metadata updates needed.
Representative public output verified.
Final diff and validation review complete.

_{🔄 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/2962 **Author:** [@Shenrui-Ma](https://github.com/Shenrui-Ma) **Created:** 10/13/2026 **Status:** ✅ Merged **Merged:** 10/13/2026 **Merged by:** [@morluto](https://github.com/morluto) **Base:** `main` ← **Head:** `perf/defer-version-match-candidates` --- ### 📝 Commits (1) - [`5f6ebb0`](https://github.com/morluto/rea/commit/5f6ebb07d0bfb7e52535cede7301f860aaa578f1) perf(javascript): avoid quadratic temporary matching state ### 📊 Changes **3 files changed** (+314 additions, -27 deletions) <details> <summary>View changed files</summary> 📝 `src/domain/javascript/javascriptApplicationVersionKeys.ts` (+35 -27) ➕ `src/domain/javascript/javascriptApplicationVersionMatching.test.ts` (+181 -0) ➕ `tests/acceptance/applications/applicationVersionMatchingCli.test.ts` (+98 -0) </details> ### 📄 Description ## Summary Reduce temporary candidate allocation when comparing application versions with repeated module bodies. No separate issue; the CLI reproduction is included below. ## Problem and expected behavior With 3,000 identical factory bodies in a retained bundle, the source-digest tier allocates nine million candidate pairs, all discarded after later identity matches resolve the modules. ## Change and scope Retain ambiguous groups through the existing matching passes, then expand candidates only between their still-unmatched nodes. Preserve tier order without re-matching residual groups. Append to key buckets instead of copying growing arrays. Genuine ambiguity remains uncapped and can still require quadratic output. ## Contract and boundary impact - Owner: JavaScript version matcher, grouping and candidate expansion. - Scope: existing comparison; advance maintainer decision not applicable. - CLI/MCP contracts and provider interfaces: unchanged. - Evidence, artifacts, provenance, and reconstruction: preserved. - Authority/cleanup: comparison of captured data only. - Generated metadata, packaging, and installation: no changes. Expected effects: - [x] Read existing files or captured data. ## Evidence and regression coverage Behavior tests pass on base and patch, covering late matching, residual ambiguity, cross-tier candidate union, and input ordering. The production analyzer supplies inputs from two synthetic versions with identical bundles and different package versions. Complete CLI output matched before and after; a separate stdio MCP check also matched. Combined results for both optimizations with 3,000 retained factories on Apple M5 Pro (macOS arm64, Node 24.18.0): medians of four fresh-process runs per revision, in alternating order. | Metric | Before | After | | --- | ---: | ---: | | Wall time | 3.330 s | 2.295 s | | CPU time | 4.27 s | 3.01 s | | Peak process RSS | 1,046.0 MiB | 556.5 MiB | Measurements cover the comparison CLI, excluding input preparation, with compile caching disabled and filesystem caches uncontrolled. Unique, unmatched, and genuinely ambiguous controls had similar timings and overlapping RSS ranges. - [x] Observations and derivations remain distinguishable. - [x] Artifact identity, provenance, and failed attempts remain preserved. - [x] Incomplete and uncertain outcomes remain visible. ## Validation performed - Focused matching, CLI, and MCP tests passed, including Node 22/24/26 checks. - `npm run check` passed with warnings. - The full local suite on the benchmark base had 10 failing cases; all reproduced without the patch with matching error signatures. <details> <summary>Benchmark reproduction and recorded runs</summary> Use two checkouts of [bd2c202dd](https://github.com/morluto/rea/commit/bd2c202dd930548194cdbc55c27a797f22279db9), differing only by this patch. Build each with the pinned Node/npm toolchain: `npm ci`, then `npm run build:cached`. Set the checkout paths below. This macOS runner generates inputs with the baseline analyzer, checks complete output hashes, and retains inputs, output, and timings in the printed directory. ```sh REA_BASE=/absolute/path/to/unmodified-base REA_PATCH=/absolute/path/to/checkout-with-patch python3 - "$REA_BASE" "$REA_PATCH" 3000 4 <<'PY' import collections import hashlib import json import os from pathlib import Path import re import shutil import statistics import subprocess import sys import tempfile if sys.platform != "darwin": raise SystemExit("This runner uses macOS /usr/bin/time -l and its byte RSS units.") base, patched = map(lambda value: Path(value).resolve(), sys.argv[1:3]) count = int(sys.argv[3]) if len(sys.argv) > 3 else 3000 repeats = int(sys.argv[4]) if len(sys.argv) > 4 else 4 assert base != patched and count > 1 and repeats > 0 node = shutil.which("node") assert node is not None root = Path(tempfile.mkdtemp(prefix="rea-version-comparison-")) env = dict(os.environ, NODE_DISABLE_COMPILE_CACHE="1") env.pop("NODE_COMPILE_CACHE", None) bundle = "globalThis.webpackChunkfixture.push([[1],{" + ",".join( f"{index}:function(){{}}" for index in range(count) ) + "}]);\n" evidence = [] for version in [1, 2]: app = root / str(version) app.mkdir() (app / "chunk.js").write_text(bundle) (app / "package.json").write_text(json.dumps( {"name": "fixture", "version": f"{version}.0.0"}, indent=2 ) + "\n") output = root / f"analysis-{version}.json" with output.open("w") as stdout, (root / f"analysis-{version}.stderr").open("w") as stderr: subprocess.run([node, str(base / "scripts/rea.mjs"), "analyze-javascript-application", str(app), "--json"], cwd=base, env=env, stdout=stdout, stderr=stderr, check=True) record = json.loads(output.read_text()) graph = record["normalized_result"]["graph"] groups = collections.Counter( observation["properties"]["source_sha256"] for item in graph["nodes"] if item["kind"] == "javascript-module" for observation in item["observations"] if "source_sha256" in observation["properties"] ) assert graph["coverage"]["status"] == "complete" and max(groups.values()) == count evidence.append(record) input_file = root / "input.json" input_file.write_text(json.dumps(dict(zip(["left", "right"], evidence)))) rows, expected = [], None print("node:", subprocess.check_output([node, "--version"], text=True).strip()) print("evidence:", root) print("round,variant,wall_s,cpu_s,peak_rss_bytes") for iteration in range(repeats): order = [("base", base), ("patch", patched)] for label, repo in order if iteration % 2 == 0 else reversed(order): output, timing = root / f"{iteration}-{label}.json", root / f"{iteration}-{label}.time" with output.open("w") as stdout, timing.open("w") as stderr: subprocess.run(["/usr/bin/time", "-l", node, str(repo / "scripts/rea.mjs"), "compare-application-versions", str(input_file), "--json"], cwd=repo, env=env, stdout=stdout, stderr=stderr, check=True) data = output.read_bytes() result = json.loads(data)["normalized_result"] assert result["matching"]["ambiguous"] == 0 assert result["matching"]["exact_node_identity"] >= count digest = hashlib.sha256(data).hexdigest() expected = expected or digest assert digest == expected, "Complete CLI output differs" text = timing.read_text() times = re.search(r"([\d.]+) real\s+([\d.]+) user\s+([\d.]+) sys", text) rss = re.search(r"(\d+)\s+maximum resident set size", text) assert times and rss row = [iteration, label, float(times[1]), float(times[2]) + float(times[3]), int(rss[1])] rows.append(row) print(",".join(map(str, row)), flush=True) for label in ["base", "patch"]: selected = [row for row in rows if row[1] == label] print(label, "medians:", [statistics.median(row[index] for row in selected) for index in [2, 3, 4]]) (root / "runs.json").write_text(json.dumps(rows, indent=2) + "\n") print("All complete CLI outputs have SHA-256", expected) PY ``` Original observations behind the table: ```csv round,revision,wall_s,cpu_s,peak_process_rss_bytes 0,baseline,3.21,4.16,1099841536 0,patched,2.29,2.98,581025792 1,patched,2.31,3.06,591986688 1,baseline,3.32,4.27,1101004800 2,baseline,3.34,4.27,1093828608 2,patched,2.28,2.97,581140480 3,patched,2.30,3.04,585875456 3,baseline,3.39,4.31,1091715072 ``` Run the regression tests in the patched checkout: ```sh npm run test:focused -- src/domain/javascript/javascriptApplicationVersionMatching.test.ts tests/acceptance/applications/applicationVersionMatchingCli.test.ts ``` </details> ## Compatibility, safety, and release No breaking changes, migration, or new dependencies. Performance measurements cover the synthetic workload above; production-wide performance is unmeasured. ## Before merge - [x] Concrete problem and focused conventional title. - [x] Scope and authority resolved. - [x] Reason for no linked issue stated. - [x] Matching and ambiguity semantics covered. - [x] No contract/documentation/metadata updates needed. - [x] Representative public output verified. - [x] Final diff and validation review complete. --- <sub>🔄 This issue represents a GitHub Pull Request. It cannot be merged through Gitea due to API limitations.</sub>

bsakaguchi

2026-10-31 01:07:16 +00:00