[PR #1229] [MERGED] perf(hopper): resolve string search records once per query #2741

New issue

Closed

opened 2026-10-17 21:09:43 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-17 21:09:43 +00:00

Owner

📋 Pull Request Information

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

Base: main ← Head: perf/hopper-string-search

📝 Commits (2)

c1afce8 perf(hopper): resolve string search records once per query
5efa8b0 perf(hopper): skip record resolution for empty string searches

📊 Changes

3 files changed (+198 additions, -1 deletions)

View changed files

📝 bridge/hopper_bridge.py (+6 -1)
➕ tests/boundary/providers/hopper/hopperStringSearch.test.ts (+80 -0)
➕ tests/fixtures/hopperStringSearchProbe.py (+112 -0)

📄 Description

Summary

search_strings on a Hopper document becomes quadratic in the number of matches: every matching string re-runs _string_inventory(document), which sorts every string address in the document and rebuilds a dictionary of all records. On a document with 8,000 strings where half match, one warm search takes about 12.6 s; at 16,000 strings it takes about 58 s. This change resolves the string records once per query, so the same searches take 4.4 ms and 11.1 ms, with byte-identical results.

No issue is linked: this is a small, self-contained performance fix, and the measurements below describe the problem and the result.

Problem and expected behavior

Trigger: search_strings with a literal pattern that matches many strings in a document with many strings.

In bridge/hopper_bridge.py, _search_results builds the string results with:

return [{"address": address, **_string_inventory(document)[address]} for address, _ in selected] if kind == "string" else [...]

_string_inventory(document) is evaluated once per selected match. With addresses=None, each call runs sorted() over every string address and builds a new {hex address: record} dictionary for all of them. A query with M matches over S strings therefore costs O(M × S log S), although the records themselves are already cached in _search_inventory_cache (the "string" search inventory is built from _strings(), which populates every record on first use).

Expected: one search costs one pass over the inventory, O(S log S + M), and returns exactly the same records in the same order.

Change and scope

_search_results now calls _string_inventory(document) once for a string query and indexes that dictionary for each match:

if kind == "string":
    records = _string_inventory(document)
    return [{"address": address, **records[address]} for address, _ in selected]
return [...]

The full-inventory form is kept on purpose: it is the same call with the same arguments, so record content, key normalization, decoding-unavailable records and ordering are unchanged. Procedure and name searches are untouched.

Not included: no new caches, no change to _string_inventory, _strings or _search_inventory, and no other bridge changes.

Contract and boundary impact

Semantic owner and earliest changed stage: Hopper bridge, _search_results in bridge/hopper_bridge.py.
CLI and MCP/tool-catalog contract: none; search_strings input and output are unchanged.
Provider, bridge, target-format, or platform compatibility: no change to the Hopper API calls made; the same native reads happen through the existing cached inventory.
Evidence, artifact, provenance, or reconstruction contract: none; results are byte-identical.
Process execution, authorization, cleanup, or containment impact: none.
Generated metadata (docs/public/product-catalog.json), package, or installation impact: none; no generated outputs committed.

Evidence and regression coverage

Tests added or updated:
- tests/fixtures/hopperStringSearchProbe.py: loads the real bridge against a Hopper-shaped document with three segments listed out of address order, ASCII and UTF-16 strings, and one string whose object extent is invalid. Expected results are computed independently in the probe from the raw string table. Seven queries run twice, so the second pass exercises the cached inventory.
- tests/boundary/providers/hopper/hopperStringSearch.test.ts:
  - returns the independently expected records for every query, including repeats;
  - matches case-insensitively and case-sensitively across segments in ascending address order (including an empty result);
  - preserves the decoding-unavailable record for an unreadable string.
- The tests assert behaviour only, not timing or call counts. They pass on main before the change and after it, confirming the output is unchanged.
Base reproduction or other evidence: the new tests pass on unchanged main (b34bdcdb2) and on this branch, so the output is unchanged. Each mutant below was applied to the final fix and the new tests were run; all were caught, and the restored code passes 3/3.

Mutant Result

index the wrong record 2 of 3 tests fail

drop the decoding field from records 2 of 3 tests fail

reverse the result order 2 of 3 tests fail

Mutant	Result
index the wrong record	2 of 3 tests fail
drop the `decoding` field from records	2 of 3 tests fail
reverse the result order	2 of 3 tests fail

Performance: measured with a bridge-level benchmark that loads the unmodified bridge/hopper_bridge.py from main and the changed file side by side against the same fake Hopper document (four segments). Measured at 089bbf58f; bridge/hopper_bridge.py is byte-identical at b34bdcdb2. A and B runs are interleaved, 7 repetitions each, caches warmed by one search first; times are best / median. At 16,000 strings with 8,000 matches, main was run once because a single search takes about a minute.

Strings	Matches	`main`	This PR	Speedup (best)	Output identical (sha256 prefix)
1,000	500	186.5 / 191.2 ms	0.5 / 0.5 ms	396×	yes, `a74cbb07a1a764f0`
2,000	1,000	742.0 / 764.5 ms	1.0 / 1.0 ms	734×	yes, `e6ae0e822e1370b9`
4,000	2,000	3,067.5 / 3,101.6 ms	2.0 / 2.6 ms	1,519×	yes, `2f09a5afd1b106b3`
8,000	4,000	12,563.1 / 13,034.5 ms	4.4 / 6.8 ms	2,842×	yes, `838700fea1506edb`
16,000	160	1,073.8 / 1,105.9 ms	7.6 / 8.3 ms	141×	yes, `d217c7ac3d5f2c9f`
16,000	8,000	58,413 ms (single run)	11.1 / 15.3 ms	≈ 5,260×	yes, `d91d617d0f0b8ed7`

First search on a fresh document (3 repetitions, best / median):

Strings	Matches	`main`	This PR
1,000	500	188.7 / 189.8 ms	4.4 / 4.6 ms
2,000	1,000	771.6 / 788.4 ms	15.2 / 17.6 ms
4,000	2,000	3,115.3 / 3,116.4 ms	22.0 / 36.7 ms
8,000	4,000	12,630.5 / 12,634.7 ms	56.4 / 69.3 ms
16,000	160	1,215.3 / 1,251.3 ms	129.4 / 152.1 ms

User-visible CLI/MCP output: unchanged; only latency changes.
Remaining proof gaps: real-Hopper verification was not performed (see Compatibility, safety, and release). The fake document implements the segment methods the bridge calls; real Hopper native reads are slower than the fake's, and those reads are unchanged by this PR.

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 on this branch, rebased on main at b34bdcdb2, in a Linux arm64 container with Node 24:

Command	Result
`npm run build:unlocked`	passed
`npx vitest run tests/boundary/providers/hopper/hopperStringSearch.test.ts`	1 file, 3 tests passed
`npx vitest run tests/boundary/providers/hopper`	this branch: 16 files, 111 tests passed; `main` at `b34bdcdb2`: 15 files, 108 tests passed (the difference is the new file)
`npm run check`	6 of 6 tasks successful
`npm run verify:test-discovery`	passed
`npx vitest run --project mcp-boundary`	73 files passed, 2 skipped; 251 tests passed, 2 skipped
`npm run test:fast`	320 files passed, 1 skipped; 3,433 tests passed, 4 skipped
bridge benchmark (described above)	results in the tables above

Compatibility, safety, and release

Breaking changes or migration steps: none.
Real Hopper/Ghidra, browser, or OS coverage: real-Hopper verification was not performed. On the only available host (arm64 macOS running an emulated x86-64 Linux container), npm run verify:hopper:linux failed on unchanged main (089bbf58f) before reaching any analysis, because the emulator reports itself as every process's executable and REA's launched-process ownership check correctly refuses it (exit code 74). The change makes no new or different Hopper API calls.
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/1229 **Author:** [@keemsisi](https://github.com/keemsisi) **Created:** 10/9/2026 **Status:** ✅ Merged **Merged:** 10/9/2026 **Merged by:** [@morluto](https://github.com/morluto) **Base:** `main` ← **Head:** `perf/hopper-string-search` --- ### 📝 Commits (2) - [`c1afce8`](https://github.com/morluto/rea/commit/c1afce8f6657c390c655908e4155345b8e53fe8a) perf(hopper): resolve string search records once per query - [`5efa8b0`](https://github.com/morluto/rea/commit/5efa8b001d4957e9a9a94fd61c12ece757a31647) perf(hopper): skip record resolution for empty string searches ### 📊 Changes **3 files changed** (+198 additions, -1 deletions) <details> <summary>View changed files</summary> 📝 `bridge/hopper_bridge.py` (+6 -1) ➕ `tests/boundary/providers/hopper/hopperStringSearch.test.ts` (+80 -0) ➕ `tests/fixtures/hopperStringSearchProbe.py` (+112 -0) </details> ### 📄 Description ## Summary `search_strings` on a Hopper document becomes quadratic in the number of matches: every matching string re-runs `_string_inventory(document)`, which sorts every string address in the document and rebuilds a dictionary of all records. On a document with 8,000 strings where half match, one warm search takes about 12.6 s; at 16,000 strings it takes about 58 s. This change resolves the string records once per query, so the same searches take 4.4 ms and 11.1 ms, with byte-identical results. No issue is linked: this is a small, self-contained performance fix, and the measurements below describe the problem and the result. ## Problem and expected behavior Trigger: `search_strings` with a literal pattern that matches many strings in a document with many strings. In `bridge/hopper_bridge.py`, `_search_results` builds the string results with: ```python return [{"address": address, **_string_inventory(document)[address]} for address, _ in selected] if kind == "string" else [...] ``` `_string_inventory(document)` is evaluated once per selected match. With `addresses=None`, each call runs `sorted()` over every string address and builds a new `{hex address: record}` dictionary for all of them. A query with M matches over S strings therefore costs O(M × S log S), although the records themselves are already cached in `_search_inventory_cache` (the `"string"` search inventory is built from `_strings()`, which populates every record on first use). Expected: one search costs one pass over the inventory, O(S log S + M), and returns exactly the same records in the same order. ## Change and scope `_search_results` now calls `_string_inventory(document)` once for a string query and indexes that dictionary for each match: ```python if kind == "string": records = _string_inventory(document) return [{"address": address, **records[address]} for address, _ in selected] return [...] ``` The full-inventory form is kept on purpose: it is the same call with the same arguments, so record content, key normalization, decoding-unavailable records and ordering are unchanged. Procedure and name searches are untouched. Not included: no new caches, no change to `_string_inventory`, `_strings` or `_search_inventory`, and no other bridge changes. ## Contract and boundary impact - Semantic owner and earliest changed stage: Hopper bridge, `_search_results` in `bridge/hopper_bridge.py`. - CLI and MCP/tool-catalog contract: none; `search_strings` input and output are unchanged. - Provider, bridge, target-format, or platform compatibility: no change to the Hopper API calls made; the same native reads happen through the existing cached inventory. - Evidence, artifact, provenance, or reconstruction contract: none; results are byte-identical. - Process execution, authorization, cleanup, or containment impact: none. - Generated metadata (`docs/public/product-catalog.json`), package, or installation impact: none; no generated outputs committed. ## Evidence and regression coverage - Tests added or updated: - `tests/fixtures/hopperStringSearchProbe.py`: loads the real bridge against a Hopper-shaped document with three segments listed out of address order, ASCII and UTF-16 strings, and one string whose object extent is invalid. Expected results are computed independently in the probe from the raw string table. Seven queries run twice, so the second pass exercises the cached inventory. - `tests/boundary/providers/hopper/hopperStringSearch.test.ts`: - returns the independently expected records for every query, including repeats; - matches case-insensitively and case-sensitively across segments in ascending address order (including an empty result); - preserves the decoding-unavailable record for an unreadable string. - The tests assert behaviour only, not timing or call counts. They pass on `main` before the change and after it, confirming the output is unchanged. - Base reproduction or other evidence: the new tests pass on unchanged `main` (`b34bdcdb2`) and on this branch, so the output is unchanged. Each mutant below was applied to the final fix and the new tests were run; all were caught, and the restored code passes 3/3. | Mutant | Result | |---|---| | index the wrong record | 2 of 3 tests fail | | drop the `decoding` field from records | 2 of 3 tests fail | | reverse the result order | 2 of 3 tests fail | - Performance: measured with a bridge-level benchmark that loads the unmodified `bridge/hopper_bridge.py` from `main` and the changed file side by side against the same fake Hopper document (four segments). Measured at `089bbf58f`; `bridge/hopper_bridge.py` is byte-identical at `b34bdcdb2`. A and B runs are interleaved, 7 repetitions each, caches warmed by one search first; times are best / median. At 16,000 strings with 8,000 matches, `main` was run once because a single search takes about a minute. | Strings | Matches | `main` | This PR | Speedup (best) | Output identical (sha256 prefix) | |---|---|---|---|---|---| | 1,000 | 500 | 186.5 / 191.2 ms | 0.5 / 0.5 ms | 396× | yes, `a74cbb07a1a764f0` | | 2,000 | 1,000 | 742.0 / 764.5 ms | 1.0 / 1.0 ms | 734× | yes, `e6ae0e822e1370b9` | | 4,000 | 2,000 | 3,067.5 / 3,101.6 ms | 2.0 / 2.6 ms | 1,519× | yes, `2f09a5afd1b106b3` | | 8,000 | 4,000 | 12,563.1 / 13,034.5 ms | 4.4 / 6.8 ms | 2,842× | yes, `838700fea1506edb` | | 16,000 | 160 | 1,073.8 / 1,105.9 ms | 7.6 / 8.3 ms | 141× | yes, `d217c7ac3d5f2c9f` | | 16,000 | 8,000 | 58,413 ms (single run) | 11.1 / 15.3 ms | ≈ 5,260× | yes, `d91d617d0f0b8ed7` | First search on a fresh document (3 repetitions, best / median): | Strings | Matches | `main` | This PR | |---|---|---|---| | 1,000 | 500 | 188.7 / 189.8 ms | 4.4 / 4.6 ms | | 2,000 | 1,000 | 771.6 / 788.4 ms | 15.2 / 17.6 ms | | 4,000 | 2,000 | 3,115.3 / 3,116.4 ms | 22.0 / 36.7 ms | | 8,000 | 4,000 | 12,630.5 / 12,634.7 ms | 56.4 / 69.3 ms | | 16,000 | 160 | 1,215.3 / 1,251.3 ms | 129.4 / 152.1 ms | - User-visible CLI/MCP output: unchanged; only latency changes. - Remaining proof gaps: real-Hopper verification was not performed (see Compatibility, safety, and release). The fake document implements the segment methods the bridge calls; real Hopper native reads are slower than the fake's, and those reads are unchanged by this PR. 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 on this branch, rebased on `main` at `b34bdcdb2`, in a Linux arm64 container with Node 24: | Command | Result | |---|---| | `npm run build:unlocked` | passed | | `npx vitest run tests/boundary/providers/hopper/hopperStringSearch.test.ts` | 1 file, 3 tests passed | | `npx vitest run tests/boundary/providers/hopper` | this branch: 16 files, 111 tests passed; `main` at `b34bdcdb2`: 15 files, 108 tests passed (the difference is the new file) | | `npm run check` | 6 of 6 tasks successful | | `npm run verify:test-discovery` | passed | | `npx vitest run --project mcp-boundary` | 73 files passed, 2 skipped; 251 tests passed, 2 skipped | | `npm run test:fast` | 320 files passed, 1 skipped; 3,433 tests passed, 4 skipped | | bridge benchmark (described above) | results in the tables above | ## Compatibility, safety, and release - Breaking changes or migration steps: none. - Real Hopper/Ghidra, browser, or OS coverage: real-Hopper verification was not performed. On the only available host (arm64 macOS running an emulated x86-64 Linux container), `npm run verify:hopper:linux` failed on unchanged `main` (`089bbf58f`) before reaching any analysis, because the emulator reports itself as every process's executable and REA's launched-process ownership check correctly refuses it (exit code 74). The change makes no new or different Hopper API calls. - 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:09:43 +00:00