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
Parsing slows quadratically for a long given part after a family comma (Doe, Jane …) #553
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):
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.
Activity
test(#553): the prefixed guard skips under a tracer; probes pin the c…
test(#553): skip only under a line tracer; ja-extra fails rather than…
docs(#553): the ja-extra env var catches a line tracer, not coverage …
docs(AGENTS.md): when the frame budget outweighs a shared predicate
fix(derek73#553): the family-comma given-part walk asks membership of…
ci: collect coverage on 3.14 alone, the job that uploads it