morluto/rea

Fork 0

mirror of https://github.com/morluto/rea.git synced 2026-11-05 06:45:22 +00:00

[PR #1434] [MERGED] perf(javascript): index change-graph nodes once per comparison #2884

New issue

Closed

opened 2026-10-17 21:11:23 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-17 21:11:23 +00:00

Owner

📋 Pull Request Information

Original PR: https://github.com/morluto/rea/pull/1434
Author: @keemsisi
Created: 10/10/2026
Status: ✅ Merged
Merged: 10/10/2026
Merged by: @N0zoM1z0

Base: main ← Head: perf/change-graph-node-lookup

📝 Commits (1)

ac87752 perf(javascript): index change-graph nodes once per comparison

📊 Changes

2 files changed (+124 additions, -8 deletions)

View changed files

➕ src/domain/javascript/javascriptApplicationChangeGraph.test.ts (+107 -0)
📝 src/domain/javascript/javascriptApplicationChangeGraph.ts (+17 -8)

📄 Description

Summary

When comparing two versions of a JavaScript application, the change graph resolves the left and right node of every changed_from edge with Array.prototype.find over the full node list of each graph. The cost of that step therefore grows as changed items × nodes. This change indexes both graphs' nodes by node_id once per change graph and looks each node up directly. Output is byte-identical. The gain is small at typical sizes and grows with size: 1.10–1.13× end to end at 8,000–16,000 changed modules, and no slowdown in any measured configuration.

No issue is linked: this is a focused performance fix, and the measurements below describe the problem and the result.

Problem and expected behavior

Trigger: compareJavaScriptApplicationVersions on two application graphs where many matched modules changed.

In src/domain/javascript/javascriptApplicationChangeGraph.ts, changedFromEdge runs once per comparison item, and its comparisonEvidence did:

const right = input.right.nodes.find(({ node_id: id }) => id === item.right_node_id);
const left = input.left.nodes.find(({ node_id: id }) => id === item.left_node_id);

That is two linear scans per changed item, which is quadratic in the number of changed modules.

Expected: each node lookup is constant time. Evidence selection stays the same (the right-hand observation evidence, falling back to the left), with the same output.

Change and scope

buildJavaScriptApplicationChangeGraph builds leftById and rightById maps once and passes them to changedFromEdge.
comparisonEvidence receives the already-resolved left and right nodes (ApplicationNode | undefined) instead of scanning. A missing node is still undefined, so the existing ?? fallback is unchanged.
Node IDs are unique within a validated graph (checkGraphInvariants rejects duplicates), so a map lookup returns the same node that find returned.

Not included: no change to schemas, graph validation, evidence selection, edge construction, or result contracts. The public and owned schema split from #1370 is untouched.

Contract and boundary impact

Semantic owner and earliest changed stage: domain, src/domain/javascript/javascriptApplicationChangeGraph.ts.
CLI and MCP/tool-catalog contract: none; inputs and results are unchanged.
Provider, bridge, target-format, or platform compatibility: none.
Evidence, artifact, provenance, or reconstruction contract: none. Comparison output, including changed_from edge evidence, is byte-identical.
Process execution, authorization, cleanup, or containment impact: none.
Generated metadata (docs/public/product-catalog.json), package, or installation impact: none.

Evidence and regression coverage

Tests added: src/domain/javascript/javascriptApplicationChangeGraph.test.ts. Through compareJavaScriptApplicationVersions, it checks that each changed_from edge carries the evidence of its own right-hand node's first observation, and that edge endpoints and labels match. The test passes on main and on this branch; it asserts behaviour, not timing.

Mutants applied to this change, run against the new test plus tests/boundary/filesystem/javascriptApplicationWorkflows.test.ts:

Mutant	Result
swap the left and right nodes passed to `comparisonEvidence`	1 of 12 tests fails
look up the right node with the left ID	1 of 12 tests fails
pass `undefined` for both nodes	1 of 12 tests fails

Performance: end-to-end compareJavaScriptApplicationVersions on synthetic version pairs with N matched modules, using the built dist of main (39dabd060) and of this branch.

Runs are interleaved base/fix/fix/base.
Each run is 1 warm-up plus 5 repetitions (3 at 16,000).
Values are best / median in ms.
The full result JSON sha256 is identical for every configuration.

Every module changed, about 2 edges per node:

N	`main`	This PR	Speedup (best)
1,000	522.6 / 552.4	499.7 / 525.7	1.05×
4,000	2,289.8 / 2,571.7	2,281.8 / 2,411.0	1.00×
8,000	4,973.9 / 5,136.5	4,504.6 / 4,608.3	1.10×
16,000	11,551.9 / 11,949.3	10,220.3 / 10,667.6	1.13×

Every module changed, about 6 edges per node:

N	`main`	This PR	Speedup (best)
1,000	937.6 / 1,003.5	897.1 / 936.3	1.05×
4,000	4,299.5 / 4,368.9	3,990.5 / 4,334.2	1.08×
8,000	9,270.4 / 10,409.7	8,870.0 / 9,170.2	1.05×
16,000	20,687.9 / 21,381.8	18,516.0 / 19,162.7	1.12×

No slowdown in any of the 36 swept configurations: shapes 2 and 6; N 10–4,000 (up to 16,000 for the changed case); identical and changed versions; with and without createApplicationVersionComparisonEvidence. Cells that first read 0.94–0.97× were re-run with 15 repetitions over three interleaved rounds, and the fix's runs fell inside main's own run-to-run spread. When versions are identical, the only added work is building the two maps: 0.2 ms at 1,000 nodes and 1.3 ms at 4,000 nodes per comparison, measured in isolation.

Bench script (set DIST to a built dist directory)

// DIST=path/to/dist SHAPE=2|6 SIZES=1000,8000 SAME=0|1 EVIDENCE=0|1 REPS=5 node bench.mjs
import { createHash } from "node:crypto";
import { resolve } from "node:path";
import { pathToFileURL } from "node:url";
const D = pathToFileURL(resolve(process.env.DIST)).href;
const G = await import(`${D}/domain/javascript/javascriptApplicationGraph.js`);
const { compareJavaScriptApplicationVersions: cmp } = await import(`${D}/domain/javascript/javascriptApplicationVersionComparison.js`);
const W = await import(`${D}/application/javascript/JavaScriptApplicationWorkflowEvidence.js`);
const hex = (n) => n.toString(16).padStart(64, "0");
const ev = (sha, path) => ({ authority: "artifact-bytes", state: "observed", confidence: "exact",
  artifact: { available: true, artifact_id: `art_${sha}`, sha256: sha },
  location: { available: true, value: { kind: "artifact-path", path } },
  extractor: { name: "b", version: "1", operation: "o", executable_sha256: null },
  coverage: { status: "complete", truncated: false, omitted_count: 0, limits: [] }, limitations: [], evidence_ids: [] });
const K = Number(process.env.SHAPE ?? 2), SAME = process.env.SAME === "1", EVID = process.env.EVIDENCE === "1";
const REPS = Number(process.env.REPS ?? 5);
const edgesOf = (nodes, art, ver) => {
  const e = [];
  for (let i = 0; i < nodes.length; i++) for (let k = 0; k < K; k++) {
    const j = k === 0 ? i + 1 : (i * (31 + 2 * k) + 7 * k) % nodes.length;
    if (j >= nodes.length || j === i) continue;
    e.push(G.createJavaScriptApplicationEdge({ source_node_id: nodes[i].node_id, target_node_id: nodes[j].node_id,
      relation: (i + j + (ver && i % 5 === 0 ? 1 : 0)) % 3 ? "imports" : "contains", properties: {}, evidence: ev(art, "m/" + i + ".js") }));
  }
  return [...new Map(e.map((x) => [x.edge_id, x])).values()];
};
const graph = (n, art, ver) => {
  const nodes = [];
  for (let i = 0; i < n; i++) nodes.push(G.createJavaScriptApplicationNode({ kind: "javascript-module",
    identity: { strategy: "canonical-path", stability: "artifact-version", artifact_sha256: art, path: `m/${i}.js` },
    observations: [{ label: `m${i}`, properties: { structural_fingerprint_sha256: hex(i + 1), structural_fingerprint_algorithm: "x", source_sha256: hex(i * 7 + ver) }, evidence: ev(art, `m/${i}.js`) }] }));
  return G.createJavaScriptApplicationGraph({ schema: "JavaScriptApplicationGraph", root_node_ids: [nodes[0].node_id], nodes,
    edges: edgesOf(nodes, art, ver), coverage: { status: "complete", truncated: false, omitted_count: 0, limits: [] }, limitations: [] });
};
const run = (input) => { const r = cmp(input); return EVID ? W.createApplicationVersionComparisonEvidence({ left_evidence_id: input.left.evidenceId, right_evidence_id: input.right.evidenceId, left_native_evidence_ids: [], right_native_evidence_ids: [] }, r) : r; };
const med = (a) => [...a].sort((x, y) => x - y)[Math.floor(a.length / 2)];
for (const n of (process.env.SIZES ?? "1000").split(",").map(Number)) {
  const L = graph(n, hex(900001), 0), R = graph(n, hex(900002), SAME ? 0 : 1);
  const input = { left: { evidenceId: "ev_" + hex(11), rootArtifactSha256: hex(900001), graph: L },
    right: { evidenceId: "ev_" + hex(12), rootArtifactSha256: hex(900002), graph: R }, leftNativeEvidence: [], rightNativeEvidence: [] };
  let res = run(input); const inner = Math.max(1, Math.floor(2000 / n));
  const ts = [];
  for (let k = 0; k < REPS; k++) { const t = performance.now(); for (let q = 0; q < inner; q++) res = run(input); ts.push((performance.now() - t) / inner); }
  const json = JSON.stringify(res);
  console.log(JSON.stringify({ dist: process.env.DIST, shape: K, same: SAME, evidence: EVID, n, best: +Math.min(...ts).toFixed(2), median: +med(ts).toFixed(2), digest: createHash("sha256").update(json).digest("hex").slice(0, 16) }));
}

User-visible CLI/MCP output: unchanged; only latency changes.
Remaining proof gaps: measured on synthetic graphs, not on a recorded real application pair. Below about 1,000 changed modules the difference is within run-to-run noise.

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

Run in a Linux arm64 container with Node 24, on this branch and on unchanged main at 39dabd060:

Command	This branch	`main`
`npm run build:cached`	3 of 3 tasks successful	3 of 3 tasks successful
`npx vitest run src/domain/javascript/javascriptApplicationChangeGraph.test.ts tests/boundary/filesystem/javascriptApplicationWorkflows.test.ts tests/acceptance/applications/applicationWorkflowCli.test.ts`	3 files, 26 tests passed	without the new file: 2 files, 25 tests passed
`npm run check`	6 of 6 tasks successful	6 of 6 tasks successful
`npm run verify:test-discovery`	all 699 test files discovered once	all 698 test files discovered once
`npx vitest run --project mcp-boundary` (after `npm run artifacts:mcp-catalog`)	314 passed, 2 skipped	314 passed, 2 skipped
`npm run test:fast`	3,547 passed, 4 skipped	3,546 passed, 4 skipped

The only difference is the new test file and its one test.

Compatibility, safety, and release

Breaking changes or migration steps: none.
Real Hopper/Ghidra, browser, or OS coverage: not applicable; pure domain change, no provider involved.
Package or release metadata impact: none.
Security, privacy, process, or containment review: none affected.

Review checklist

This PR addresses a concrete problem or an agreed enhancement.
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/1434 **Author:** [@keemsisi](https://github.com/keemsisi) **Created:** 10/10/2026 **Status:** ✅ Merged **Merged:** 10/10/2026 **Merged by:** [@N0zoM1z0](https://github.com/N0zoM1z0) **Base:** `main` ← **Head:** `perf/change-graph-node-lookup` --- ### 📝 Commits (1) - [`ac87752`](https://github.com/morluto/rea/commit/ac87752275a1fe3ec8200860e2019f73912c4e33) perf(javascript): index change-graph nodes once per comparison ### 📊 Changes **2 files changed** (+124 additions, -8 deletions) <details> <summary>View changed files</summary> ➕ `src/domain/javascript/javascriptApplicationChangeGraph.test.ts` (+107 -0) 📝 `src/domain/javascript/javascriptApplicationChangeGraph.ts` (+17 -8) </details> ### 📄 Description ## Summary When comparing two versions of a JavaScript application, the change graph resolves the left and right node of every `changed_from` edge with `Array.prototype.find` over the full node list of each graph. The cost of that step therefore grows as changed items × nodes. This change indexes both graphs' nodes by `node_id` once per change graph and looks each node up directly. Output is byte-identical. The gain is small at typical sizes and grows with size: 1.10–1.13× end to end at 8,000–16,000 changed modules, and no slowdown in any measured configuration. No issue is linked: this is a focused performance fix, and the measurements below describe the problem and the result. ## Problem and expected behavior Trigger: `compareJavaScriptApplicationVersions` on two application graphs where many matched modules changed. In `src/domain/javascript/javascriptApplicationChangeGraph.ts`, `changedFromEdge` runs once per comparison item, and its `comparisonEvidence` did: ```ts const right = input.right.nodes.find(({ node_id: id }) => id === item.right_node_id); const left = input.left.nodes.find(({ node_id: id }) => id === item.left_node_id); ``` That is two linear scans per changed item, which is quadratic in the number of changed modules. Expected: each node lookup is constant time. Evidence selection stays the same (the right-hand observation evidence, falling back to the left), with the same output. ## Change and scope - `buildJavaScriptApplicationChangeGraph` builds `leftById` and `rightById` maps once and passes them to `changedFromEdge`. - `comparisonEvidence` receives the already-resolved `left` and `right` nodes (`ApplicationNode | undefined`) instead of scanning. A missing node is still `undefined`, so the existing `??` fallback is unchanged. - Node IDs are unique within a validated graph (`checkGraphInvariants` rejects duplicates), so a map lookup returns the same node that `find` returned. Not included: no change to schemas, graph validation, evidence selection, edge construction, or result contracts. The public and owned schema split from #1370 is untouched. ## Contract and boundary impact - Semantic owner and earliest changed stage: domain, `src/domain/javascript/javascriptApplicationChangeGraph.ts`. - CLI and MCP/tool-catalog contract: none; inputs and results are unchanged. - Provider, bridge, target-format, or platform compatibility: none. - Evidence, artifact, provenance, or reconstruction contract: none. Comparison output, including `changed_from` edge evidence, is byte-identical. - Process execution, authorization, cleanup, or containment impact: none. - Generated metadata (`docs/public/product-catalog.json`), package, or installation impact: none. ## Evidence and regression coverage - Tests added: `src/domain/javascript/javascriptApplicationChangeGraph.test.ts`. Through `compareJavaScriptApplicationVersions`, it checks that each `changed_from` edge carries the evidence of its own right-hand node's first observation, and that edge endpoints and labels match. The test passes on `main` and on this branch; it asserts behaviour, not timing. - Mutants applied to this change, run against the new test plus `tests/boundary/filesystem/javascriptApplicationWorkflows.test.ts`: | Mutant | Result | |---|---| | swap the left and right nodes passed to `comparisonEvidence` | 1 of 12 tests fails | | look up the right node with the left ID | 1 of 12 tests fails | | pass `undefined` for both nodes | 1 of 12 tests fails | - Performance: end-to-end `compareJavaScriptApplicationVersions` on synthetic version pairs with N matched modules, using the built `dist` of `main` (`39dabd060`) and of this branch. - Runs are interleaved base/fix/fix/base. - Each run is 1 warm-up plus 5 repetitions (3 at 16,000). - Values are best / median in ms. - The full result JSON sha256 is identical for every configuration. Every module changed, about 2 edges per node: | N | `main` | This PR | Speedup (best) | |---|---|---|---| | 1,000 | 522.6 / 552.4 | 499.7 / 525.7 | 1.05× | | 4,000 | 2,289.8 / 2,571.7 | 2,281.8 / 2,411.0 | 1.00× | | 8,000 | 4,973.9 / 5,136.5 | 4,504.6 / 4,608.3 | 1.10× | | 16,000 | 11,551.9 / 11,949.3 | 10,220.3 / 10,667.6 | 1.13× | Every module changed, about 6 edges per node: | N | `main` | This PR | Speedup (best) | |---|---|---|---| | 1,000 | 937.6 / 1,003.5 | 897.1 / 936.3 | 1.05× | | 4,000 | 4,299.5 / 4,368.9 | 3,990.5 / 4,334.2 | 1.08× | | 8,000 | 9,270.4 / 10,409.7 | 8,870.0 / 9,170.2 | 1.05× | | 16,000 | 20,687.9 / 21,381.8 | 18,516.0 / 19,162.7 | 1.12× | No slowdown in any of the 36 swept configurations: shapes 2 and 6; N 10–4,000 (up to 16,000 for the changed case); identical and changed versions; with and without `createApplicationVersionComparisonEvidence`. Cells that first read 0.94–0.97× were re-run with 15 repetitions over three interleaved rounds, and the fix's runs fell inside `main`'s own run-to-run spread. When versions are identical, the only added work is building the two maps: 0.2 ms at 1,000 nodes and 1.3 ms at 4,000 nodes per comparison, measured in isolation. <details><summary>Bench script (set <code>DIST</code> to a built <code>dist</code> directory)</summary> ```js // DIST=path/to/dist SHAPE=2|6 SIZES=1000,8000 SAME=0|1 EVIDENCE=0|1 REPS=5 node bench.mjs import { createHash } from "node:crypto"; import { resolve } from "node:path"; import { pathToFileURL } from "node:url"; const D = pathToFileURL(resolve(process.env.DIST)).href; const G = await import(`${D}/domain/javascript/javascriptApplicationGraph.js`); const { compareJavaScriptApplicationVersions: cmp } = await import(`${D}/domain/javascript/javascriptApplicationVersionComparison.js`); const W = await import(`${D}/application/javascript/JavaScriptApplicationWorkflowEvidence.js`); const hex = (n) => n.toString(16).padStart(64, "0"); const ev = (sha, path) => ({ authority: "artifact-bytes", state: "observed", confidence: "exact", artifact: { available: true, artifact_id: `art_${sha}`, sha256: sha }, location: { available: true, value: { kind: "artifact-path", path } }, extractor: { name: "b", version: "1", operation: "o", executable_sha256: null }, coverage: { status: "complete", truncated: false, omitted_count: 0, limits: [] }, limitations: [], evidence_ids: [] }); const K = Number(process.env.SHAPE ?? 2), SAME = process.env.SAME === "1", EVID = process.env.EVIDENCE === "1"; const REPS = Number(process.env.REPS ?? 5); const edgesOf = (nodes, art, ver) => { const e = []; for (let i = 0; i < nodes.length; i++) for (let k = 0; k < K; k++) { const j = k === 0 ? i + 1 : (i * (31 + 2 * k) + 7 * k) % nodes.length; if (j >= nodes.length || j === i) continue; e.push(G.createJavaScriptApplicationEdge({ source_node_id: nodes[i].node_id, target_node_id: nodes[j].node_id, relation: (i + j + (ver && i % 5 === 0 ? 1 : 0)) % 3 ? "imports" : "contains", properties: {}, evidence: ev(art, "m/" + i + ".js") })); } return [...new Map(e.map((x) => [x.edge_id, x])).values()]; }; const graph = (n, art, ver) => { const nodes = []; for (let i = 0; i < n; i++) nodes.push(G.createJavaScriptApplicationNode({ kind: "javascript-module", identity: { strategy: "canonical-path", stability: "artifact-version", artifact_sha256: art, path: `m/${i}.js` }, observations: [{ label: `m${i}`, properties: { structural_fingerprint_sha256: hex(i + 1), structural_fingerprint_algorithm: "x", source_sha256: hex(i * 7 + ver) }, evidence: ev(art, `m/${i}.js`) }] })); return G.createJavaScriptApplicationGraph({ schema: "JavaScriptApplicationGraph", root_node_ids: [nodes[0].node_id], nodes, edges: edgesOf(nodes, art, ver), coverage: { status: "complete", truncated: false, omitted_count: 0, limits: [] }, limitations: [] }); }; const run = (input) => { const r = cmp(input); return EVID ? W.createApplicationVersionComparisonEvidence({ left_evidence_id: input.left.evidenceId, right_evidence_id: input.right.evidenceId, left_native_evidence_ids: [], right_native_evidence_ids: [] }, r) : r; }; const med = (a) => [...a].sort((x, y) => x - y)[Math.floor(a.length / 2)]; for (const n of (process.env.SIZES ?? "1000").split(",").map(Number)) { const L = graph(n, hex(900001), 0), R = graph(n, hex(900002), SAME ? 0 : 1); const input = { left: { evidenceId: "ev_" + hex(11), rootArtifactSha256: hex(900001), graph: L }, right: { evidenceId: "ev_" + hex(12), rootArtifactSha256: hex(900002), graph: R }, leftNativeEvidence: [], rightNativeEvidence: [] }; let res = run(input); const inner = Math.max(1, Math.floor(2000 / n)); const ts = []; for (let k = 0; k < REPS; k++) { const t = performance.now(); for (let q = 0; q < inner; q++) res = run(input); ts.push((performance.now() - t) / inner); } const json = JSON.stringify(res); console.log(JSON.stringify({ dist: process.env.DIST, shape: K, same: SAME, evidence: EVID, n, best: +Math.min(...ts).toFixed(2), median: +med(ts).toFixed(2), digest: createHash("sha256").update(json).digest("hex").slice(0, 16) })); } ``` </details> - User-visible CLI/MCP output: unchanged; only latency changes. - Remaining proof gaps: measured on synthetic graphs, not on a recorded real application pair. Below about 1,000 changed modules the difference is within run-to-run noise. 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 Run in a Linux arm64 container with Node 24, on this branch and on unchanged `main` at `39dabd060`: | Command | This branch | `main` | |---|---|---| | `npm run build:cached` | 3 of 3 tasks successful | 3 of 3 tasks successful | | `npx vitest run src/domain/javascript/javascriptApplicationChangeGraph.test.ts tests/boundary/filesystem/javascriptApplicationWorkflows.test.ts tests/acceptance/applications/applicationWorkflowCli.test.ts` | 3 files, 26 tests passed | without the new file: 2 files, 25 tests passed | | `npm run check` | 6 of 6 tasks successful | 6 of 6 tasks successful | | `npm run verify:test-discovery` | all 699 test files discovered once | all 698 test files discovered once | | `npx vitest run --project mcp-boundary` (after `npm run artifacts:mcp-catalog`) | 314 passed, 2 skipped | 314 passed, 2 skipped | | `npm run test:fast` | 3,547 passed, 4 skipped | 3,546 passed, 4 skipped | The only difference is the new test file and its one test. ## Compatibility, safety, and release - Breaking changes or migration steps: none. - Real Hopper/Ghidra, browser, or OS coverage: not applicable; pure domain change, no provider involved. - Package or release metadata impact: none. - Security, privacy, process, or containment review: none affected. ## Review checklist - [x] This PR addresses a concrete problem or an agreed enhancement. - [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-17 21:11:23 +00:00