Skip to content

Commit 875b0b8

Browse files
author
Bertan Ari
committed
docs: record string-parsing performance guidance in AGENTS.md
1 parent 400bd37 commit 875b0b8

1 file changed

Lines changed: 28 additions & 0 deletions

File tree

‎AGENTS.md‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,6 +45,34 @@ Prefer the narrowest test layer that proves the behavior. This follows standard
4545
- Keep e2e tests focused on high-value smoke coverage across boundaries. Avoid placing detailed protocol, parsing, storage, retry, or edge-case assertions in e2e when they can be covered reliably at a lower layer.
4646
- When fixing a regression, add the regression test at the lowest layer that would have failed for the bug. Add an e2e test only if lower-level tests cannot represent the failure mode.
4747

48+
## String Parsing and Scanning Performance
49+
50+
Text scanners in this repo run on model output that can reach tens of kilobytes, so treat scanning cost as a design
51+
constraint, not a review afterthought. The leaked tool-call recovery parser in `src/api/providers/vscode-lm.ts` is the
52+
worked example for every point below.
53+
54+
- Never re-scan a growing prefix inside a per-match loop. Recomputing `text.slice(0, match.index)` and re-splitting or
55+
re-walking it for each match is O(n²) in message length, and it fires on ordinary output, not just adversarial input:
56+
measured 0.58 ms for 50 invokes / 4 KB versus 24.93 ms for 400 invokes / 32 KB, with lines walked quadrupling per
57+
doubling of input. Thread incremental state (last index, running line count) through the loop instead.
58+
- Streaming multiplies the exponent. Re-running a whole-buffer scan on every streamed chunk turns an O(n²) scan into
59+
O(n³); a 49 KB message across 400 chunks cost 4.2 s of main-thread time. A parser invoked per chunk must be
60+
incremental over the newly arrived text, never over the accumulated buffer.
61+
- Watch regex constructs whose cost is invisible when reading them:
62+
- Negative lookahead such as `(?![\s\S]*<tag>)` rescans to end-of-string at every match position — O(N·k) for k
63+
occurrences. Use `lastIndexOf` over the candidate spellings instead.
64+
- Lazy quantifiers such as `[\s\S]*?</tag>` rescan to end-of-text for every candidate when the closing tag is
65+
absent. Use `indexOf` with index-pair slicing, or pre-check that the tags balance.
66+
- Unanchored trailing patterns such as `[^.!?\n]*$` re-scan the line tail at every match when the terminator is
67+
absent. Slice at the last terminator first, then test only the remainder.
68+
- Iteratively stripping one nesting layer per pass is O(D·N) with allocation churn per pass. Prefer a single-pass
69+
stack scanner.
70+
- Measure before optimizing, and judge by whether realistic model output triggers the quadratic. A quadratic reachable
71+
only through adversarial input (tens of thousands of unclosed tags) is usually not worth hardening; one that fires on
72+
ordinary output is.
73+
- Pin complexity with a scaling assertion rather than a wall-clock threshold: assert that cost at 4× input stays within
74+
a fixed multiple of cost at 1× input. Absolute timings are machine-dependent and flaky in CI.
75+
4876
## Task Lifecycle Changes
4977

5078
- Read `docs/architecture/task-lifecycle-model.md` before changing task status, delegation, interruption, completion, abandonment, persistence ownership, or scheduler fan-out behavior.

0 commit comments

Comments
 (0)