Skip to content

Parsing slows quadratically for a long given part after a family comma (Doe, Jane …) #553

Description

@derek73

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:

  1. 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).
  2. 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).
  3. 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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions