You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 875b0b8
Browse filesBrowse the repository at this point in the historyBrowse files
Bertan Ari
committed
docs: record string-parsing performance guidance in AGENTS.md
Copy file name to clipboardExpand all lines: AGENTS.md
+28Lines changed: 28 additions & 0 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -45,6 +45,34 @@ Prefer the narrowest test layer that proves the behavior. This follows standard
45
45
- 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.
46
46
- 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.
47
47
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
+
48
76
## Task Lifecycle Changes
49
77
50
78
- 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