A name written family-first with a comma gets quadratically slower as the part after the comma grows: "Doe, Jane " + "Smith " * n costs about 16× more time for 4× the input as n grows, while the same words with no comma stay linear. Only long inputs are affected, but it is a regression from 2.2.0.
Measured (py3.11, best of 5, GC off; time ratio for 4× the input):
| text |
n=100 |
n=400 |
n=1600 |
Doe, Jane + Smith ×n (2.3.0) |
4.18× |
5.51× |
8.26× |
Doe, Jane + Smith ×n (master e10e83b) |
4.22× |
5.61× |
8.63× |
Jane + Smith ×n (master) |
3.71× |
3.95× |
4.05× |
Doe, Jane + Smith ×n (2.2.0) |
3.81× |
3.97× |
4.04× |
Any word shows it: Ma, Ed and Smith read the same way.
Cause. In assign, the family-comma given part's trailing loop, for m in range(n + 1, len(pieces)), tests m not in walkable, and walkable is a list. Each test scans the list, so the loop is quadratic. It arrived in 96a511b6 ("one tail reading for assign and the P5 reserve"), first released in v2.3.0. Checked in a scratch copy of master: reading it as a set (walkable_set = set(walkable) before the loop) brings the ratio to 3.99× at n=1600, and no reading changes on the spot-checked names.
Why nothing caught it. The scan is a C-level in, which calls no Python function, so test_benchmark.py's frame-count guards can't see it; its frame ratio stays at 3.9×. The clock-based _SHAPES table repeats a single unit, and this shape needs a prefix (Doe, Jane ) before the repeated words, which AGENTS.md notes a _SHAPES row can't express. A few lines below that check, _assign.py already records the same trap from #531's work: a report's walk "re-scanned walkable -- a list" and went cubic.
Fix scope:
- Read
walkable as a set at that loop, or build it as one where membership is all it serves, keeping the list where order matters (trailing_titles and walkable[kept:] use it).
- Add a scaling guard for a long family-comma given part. It has to be clock-based, since frames can't see this, and built like
test_a_clause_link_run_does_not_cost_quadratically, which constructs its own prefixed input. Calibrate it against this regression the way _MAX_RATIO was (8.3× at n=1600 against about 4× clean).
- Sweep
_pipeline/ for other in <list> tests inside loops over pieces. The class is invisible to every frame-based guard.
PR #552 (#544) carries the same line at _assign.py:962; this is independent of it and can land before or after.
A name written family-first with a comma gets quadratically slower as the part after the comma grows:
"Doe, Jane " + "Smith " * ncosts about 16× more time for 4× the input as n grows, while the same words with no comma stay linear. Only long inputs are affected, but it is a regression from 2.2.0.Measured (py3.11, best of 5, GC off; time ratio for 4× the input):
Doe, Jane+Smith×n (2.3.0)Doe, Jane+Smith×n (master e10e83b)Jane+Smith×n (master)Doe, Jane+Smith×n (2.2.0)Any word shows it:
Ma,EdandSmithread the same way.Cause. In
assign, the family-comma given part's trailing loop,for m in range(n + 1, len(pieces)), testsm not in walkable, andwalkableis a list. Each test scans the list, so the loop is quadratic. It arrived in96a511b6("one tail reading for assign and the P5 reserve"), first released in v2.3.0. Checked in a scratch copy of master: reading it as a set (walkable_set = set(walkable)before the loop) brings the ratio to 3.99× at n=1600, and no reading changes on the spot-checked names.Why nothing caught it. The scan is a C-level
in, which calls no Python function, sotest_benchmark.py's frame-count guards can't see it; its frame ratio stays at 3.9×. The clock-based_SHAPEStable repeats a single unit, and this shape needs a prefix (Doe, Jane) before the repeated words, which AGENTS.md notes a_SHAPESrow can't express. A few lines below that check,_assign.pyalready records the same trap from #531's work: a report's walk "re-scannedwalkable-- a list" and went cubic.Fix scope:
walkableas a set at that loop, or build it as one where membership is all it serves, keeping the list where order matters (trailing_titlesandwalkable[kept:]use it).test_a_clause_link_run_does_not_cost_quadratically, which constructs its own prefixed input. Calibrate it against this regression the way_MAX_RATIOwas (8.3× at n=1600 against about 4× clean)._pipeline/for otherin <list>tests inside loops over pieces. The class is invisible to every frame-based guard.PR #552 (#544) carries the same line at
_assign.py:962; this is independent of it and can land before or after.