Repository navigation
TestPatternLinearity still fails on a busy machine: the wall-clock ratio check flakes (42.8x against a 20x limit) #1047
Description
Summary
TestPatternLinearity::test_growth_is_approximately_linear in tests/test_check_source_path_refs.py asserts a wall-clock ratio (timings[10_000] / timings[1_000] < 20). It still fails when the machine is busy, although the regex it guards is linear. It is the same test as the nightly failure #72 (21.0x against the 20x limit), which was closed without the wall-clock dependence being removed.
Evidence
During a full gauntlet run on 2026-10-21 (about 6 minutes, load average 16 to 50 from other work on the machine), two parametrisations failed in the pytest step:
FAILED tests/test_check_source_path_refs.py::TestPatternLinearity::test_growth_is_approximately_linear[root and prefix interleaved-<lambda>]
FAILED tests/test_check_source_path_refs.py::TestPatternLinearity::test_growth_is_approximately_linear[body quantifier, no extension ever-<lambda>]
AssertionError: root and prefix interleaved: 10x input cost 42.8x time (super-linear)
The same tests pass in isolation (3 of 3 runs, 4.7 s each) with and without the change that was under test, and on a clean development. Because the gauntlet is a && chain, the failed step also skipped every guard after it until a rerun.
Why it matters
A contributor who runs the documented self-review chain on a busy laptop gets a red pytest step that has nothing to do with their change, and the chain stops there. CI runners have the same exposure when a neighbour is busy.
Options
The existing test already takes a median of repeated scans and has a jitter test. Remaining choices, pick one and say why in the pull request:
- Measure CPU time (
time.process_time) instead of wall-clock time, so waiting for a busy CPU does not count. - Take the minimum instead of the median of the repetitions per size, which is the standard way to remove scheduling noise from a microbenchmark.
- Keep the wall-clock shape check but run it only in the nightly workflow (a marker), and leave the deterministic safety floor (
< 1.0 sfor 10K input) in the normal run.
Acceptance criteria
- The linearity check no longer fails because the machine is busy: demonstrate with a loaded run (for example several parallel
pytestprocesses) and say which option removed the flake. - A real ReDoS shape still fails it: the calibrated quadratic test (
calibrated quadratic scan) stays green and the check still catches a competing-quantifier regression. - No
pytest.skip, retry loop or looser limit that hides a genuine super-linear pattern.
Context
Found while validating #1046. Related: #72 (closed). Standard: docs/standards/regex.md, docs/standards/testing.md.
Activity
cemililik commentedon Oct 20, 2026
Second data point, same day: in another full gauntlet run at a moderate load (load average about 10, nothing else heavy running)
near-miss tailfailed with10x input cost 22.7x time (super-linear); the rerun passed. So it flakes well below the extreme load of the first report, which makes the gauntlet'spyteststep an unreliable gate for anyone running the documented chain.cemililik commentedon Oct 22, 2026
Where to start
Thanks for taking a look. Claim it by starting a comment with
/assignso nobody duplicates the work.File:
tests/test_check_source_path_refs.py, classTestPatternLinearity(about lines 503-595). This is a test-only change.Approach (already decided): option 1, CPU time, keeping the median of 5. We measured it with 30 competing busy processes (load average about 54). The 10K/1K ratio of today's wall-clock median moved between 3.5x and 17.2x; the limit is 20x and a linear scan is about 10x. The
time.process_time()median stayed between 8.5x and 10.4x. The quadratic control stayed above 80x with both clocks. Taking the minimum of the wall clock instead only narrowed the range to 4.0x-14.4x._median_scan_time, replace the twotime.perf_counter()calls withtime.process_time().0.025in the calibration check withmax(0.025, 8 * time.get_clock_info("process_time").resolution). On Windows the CPU clock ticks at about 15.6 ms, and the release workflow runs the tests onwindows-latest, so a 25 ms batch would be measured too coarsely there.test_calibrated_quadratic_scan_is_rejectedandtest_scheduler_jitter_does_not_reject_linear_scanmonkeypatchtime.perf_counter; patchtime.process_timeinstead and keep their assertions.< 1.0s floor and the< 20limit. Noskip, no retry loop and no looser limit.Evidence for the PR. The unmodified test may not fail on your machine, so show the distribution rather than a red-to-green run. Start some busy loops, for example
for i in $(seq 1 40); do timeout 180 python3 -c 'while True: pass' & done. Then record the 10K/1K ratio about 20 times with the old clock and with the new one, and paste the min/max of each. Also show thattest_quadratic_scan_is_still_rejectedand the calibrated quadratic test stay green.No GPU, network access or model download is needed. It is test-only, so there is no CHANGELOG entry and no Turkish mirror to update.
Open the PR against
developmentwithFixes #1047.cemililik commentedon Oct 23, 2026
Third data point, and the first on a GitHub-hosted runner: the pull-request CI run of #1061 failed
test (3.11)on two parametrisations (run 39977008225):The same commit (
beea6f6) passed all four Python versions in the push run ondevelopmenta few minutes earlier, and neither the test nortools/check_source_path_refs.pychanged sincemain. Measured locally on an idle machine, the four shapes stay at 8.2x to 11.1x over 15 rounds each. Among the last 150 CI runs this is the only failure of this test, so it is rare on CI, but it does happen there too, not only on a busy laptop.