From 6882eea22b0c6dec539d7f3cdcb54a8360452196 Mon Sep 17 00:00:00 2001 From: blasty Date: Fri, 7 Aug 2026 06:11:46 +0200 Subject: autoresearch: record the trace-memory scaling finding --- .auto/ideas.md | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/.auto/ideas.md b/.auto/ideas.md index d1d2f92..876ed8b 100644 --- a/.auto/ideas.md +++ b/.auto/ideas.md @@ -103,3 +103,27 @@ a cleaner probe first. `targets/bash` with `/tmp/strcrash.py`, **and 3/3 on the pre-autoresearch commit 2b0ae8d** — so it is not something this work introduced. `ProjectPalette` has the same shape and the same latent race. + +## Trace memory reads scale with trace LENGTH (measured, not fixed) + +`idatui/trace.py` loads linearly (36.6 / 73.3 / 143.9 / 280.7 ms for 20k / 40k / +80k / 160k rows — x1.95 per doubling, exactly right) and `register_state` is +effectively O(1). But `Trace.memory(addr, length, idx)` costs 16.3 / 31.7 / 63.4 +/ 125.8 ms for 200 calls over those same traces: **linear in trace length per +call.** + +`_mem_index` sorts accesses by address and bisects to the window, which is the +right idea — but it then iterates *every* access in that address window across +all time, filtering by `t > idx`. A hot stack slot in a loop is written once per +iteration, so the stack pane's cost grows with how long the trace ran. On a +10M-instruction trace a single step could scan millions of entries. + +The fix is to find, per byte, the latest access with `t <= idx` rather than +scanning them all. The sort is already stable, so entries within one address are +in time order — but accesses have variable length and overlap, so grouping is +not trivial. Probe: `/tmp/traceprof.py`. + +**Do not attempt this until `tests/test_trace_vs_tenet.py` can run** — it is the +differential against Tenet's own reference reader and it is currently skipped +here, which leaves `tests/test_trace.py`'s 35 synthetic checks as the only guard +on a subtle indexing change. -- cgit v1.3.1-sl0p