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
Symptom. Parse time for a name ending in alternating credentials and titles grows with the square of that tail's length. Each ratio is the time for 4× the input (py3.11, 2026-09-28, best of 5); 4× is linear.
shape
2.2.0
2.3.0
master
"John Smith " + "MA Prof. " * n
4.0×
10.5×
12.3×
"John Smith " + "PhD Prof. " * n
4.0×
9.7×
10.4×
"Jane Doe nee Smith " + "MA Prof. " * n
4.0×
3.9×
14.8×
The clause shape has not been released yet. Controls: "John Smith " + "Prof. " * 2n and "Doe, John " + "MA Prof. " * n both read 4.0×.
Mechanism.tail_reading's while True loop in _pipeline/_pieces.py runs once per title the H5 chain takes:
Each pass splices out one trailing title, then calls peel_trailing over the whole of rest again.
peel_trailing asks listed_lean/ambiguous_lean for every member of the run peeled so far, so n pairs cost n passes of O(n) work. At n=400, cProfile shows 402 peel_trailing calls and 80,200 ambiguous_lean calls.
The loop also copies rest and prepends to titled on every pass.
The maiden clause's take in _group.py (_maiden_take / _release_reads_off) and trailing_start_past_titles run the same fixed point again, which multiplies the cost: 1,204 peel_trailing calls for the clause shape.
Scope.
Make the fixed point linear by carrying the peel forward between passes instead of redoing it from scratch. Readings must not move; the differential gate at every baseline is the check.
Add clock-guard rows to _PREFIXED_SHAPES in tests/v2/test_benchmark.py (added by Fix quadratic cost of a long given part after a family comma #557) for the no-comma shape and the clause shape. Record the negative control with repeated runs, as that table's comment does.
Frame guards might catch this one, since the cost is Python-level, but only on these input shapes, and no current shape reaches it.
Found by the
_pipeline/sweep for #553.Symptom. Parse time for a name ending in alternating credentials and titles grows with the square of that tail's length. Each ratio is the time for 4× the input (py3.11, 2026-09-28, best of 5); 4× is linear.
"John Smith " + "MA Prof. " * n"John Smith " + "PhD Prof. " * n"Jane Doe nee Smith " + "MA Prof. " * nThe clause shape has not been released yet. Controls:
"John Smith " + "Prof. " * 2nand"Doe, John " + "MA Prof. " * nboth read 4.0×.Mechanism.
tail_reading'swhile Trueloop in_pipeline/_pieces.pyruns once per title the H5 chain takes:peel_trailingover the whole ofrestagain.peel_trailingaskslisted_lean/ambiguous_leanfor every member of the run peeled so far, so n pairs cost n passes of O(n) work. At n=400, cProfile shows 402peel_trailingcalls and 80,200ambiguous_leancalls.restand prepends totitledon every pass.The maiden clause's take in
_group.py(_maiden_take/_release_reads_off) andtrailing_start_past_titlesrun the same fixed point again, which multiplies the cost: 1,204peel_trailingcalls for the clause shape.Scope.
_PREFIXED_SHAPESintests/v2/test_benchmark.py(added by Fix quadratic cost of a long given part after a family comma #557) for the no-comma shape and the clause shape. Record the negative control with repeated runs, as that table's comment does.Frame guards might catch this one, since the cost is Python-level, but only on these input shapes, and no current shape reaches it.