bench: add repeatable solver benchmark suite #8

New Issue

2026-07-30T16:23:34+01:00

mcp commented

2026-07-30 16:23:34 +01:00

Background

Elapsed time alone is noisy and first-solution search is highly sensitive to branch ordering. The investigation used temporary instrumentation to count placements, backtracks, loop iterations and occupancy writes, but the repository has no repeatable benchmark suite.

Observed Release baselines on Apple arm64 included approximately 1.75 seconds and 60.5 million placements for order 8. Compiler flags, LTO, PGO and narrower cells produced little or no improvement.

Benchmarking must be kept separate from correctness tests: correctness tests should be fast and deterministic, while performance runs need repetitions, environmental metadata and no pass/fail wall-clock threshold.

Proposed work

Add optional, zero-or-low-overhead counters for:
- search nodes and loop iterations;
- attempted placements and backtracks;
- individual pruning-rule checks and hits;
- generated and completed parallel tasks.
Add a repeatable benchmark command for representative cases:
- feasible first-solution cases, initially orders 8 and 9;
- a small exhaustive infeasible case, such as order 7;
- constructed odd solutions once supported.
Separate solver time from construction, validation and rendering/output time.
Capture compiler, flags, build type, commit, hardware, worker count, search policy and random seed.
Support repeated runs and report median plus spread, not only the best run.
Store a concise baseline and subsequent comparison results in a documented format.
Keep heavyweight benchmarks out of the default correctness-test path.

Acceptance criteria

Instrumentation can be disabled for production builds and its enabled overhead is measured.
Benchmark output is machine-readable or consistently structured.
Results include node counts, elapsed time and applicable prune/task counters.
Warm-up, repetition, timeout and stdout-handling policies are documented.
A clean post-correctness-fix baseline is recorded before the skyline redesign.
Each subsequent optimization issue reports comparable before/after measurements.
Normal automated tests do not fail because of timing variability.

Relationship to other work

Correctness and sanitizer blockers in #7 and #14 should be fixed before trusting the baseline.
The independent validator from #1 should validate benchmark solutions outside the timed solver section.
This issue supplies the measurement framework and decision gates for the optimization roadmap.

## Background Elapsed time alone is noisy and first-solution search is highly sensitive to branch ordering. The investigation used temporary instrumentation to count placements, backtracks, loop iterations and occupancy writes, but the repository has no repeatable benchmark suite. Observed Release baselines on Apple arm64 included approximately 1.75 seconds and 60.5 million placements for order 8. Compiler flags, LTO, PGO and narrower cells produced little or no improvement. Benchmarking must be kept separate from correctness tests: correctness tests should be fast and deterministic, while performance runs need repetitions, environmental metadata and no pass/fail wall-clock threshold. ## Proposed work - Add optional, zero-or-low-overhead counters for: - search nodes and loop iterations; - attempted placements and backtracks; - individual pruning-rule checks and hits; - generated and completed parallel tasks. - Add a repeatable benchmark command for representative cases: - feasible first-solution cases, initially orders 8 and 9; - a small exhaustive infeasible case, such as order 7; - constructed odd solutions once supported. - Separate solver time from construction, validation and rendering/output time. - Capture compiler, flags, build type, commit, hardware, worker count, search policy and random seed. - Support repeated runs and report median plus spread, not only the best run. - Store a concise baseline and subsequent comparison results in a documented format. - Keep heavyweight benchmarks out of the default correctness-test path. ## Acceptance criteria - Instrumentation can be disabled for production builds and its enabled overhead is measured. - Benchmark output is machine-readable or consistently structured. - Results include node counts, elapsed time and applicable prune/task counters. - Warm-up, repetition, timeout and stdout-handling policies are documented. - A clean post-correctness-fix baseline is recorded before the skyline redesign. - Each subsequent optimization issue reports comparable before/after measurements. - Normal automated tests do not fail because of timing variability. ## Relationship to other work - Correctness and sanitizer blockers in #7 and #14 should be fixed before trusting the baseline. - The independent validator from #1 should validate benchmark solutions outside the timed solver section. - This issue supplies the measurement framework and decision gates for the optimization roadmap.

mcp changed title from ~~bench: add repeatable search performance instrumentation~~ to bench: add repeatable solver benchmark suite

2026-07-30 16:25:50 +01:00

mcp referenced this issue

2026-07-30 16:26:18 +01:00

roadmap: improve time to the first square solution #16

mcp commented

2026-07-30 17:02:09 +01:00

Implemented on codex/issue-8-benchmarks (working tree; commit/PR handled by the coordinating task).

Design

Added SearchCounters with nodes, loop iterations, attempted placements, backtracks, and stable zero fields for prune checks/hits and generated/completed tasks.
Used find_solution_impl<Instrument> with if constexpr; normal find_solution() instantiates the counter-free path, while the opt-in probe calls find_solution_instrumented(). Disabled production overhead is therefore structurally zero rather than a per-event null check.
Added opt-in PARTRIDGE_BUILD_BENCHMARKS; heavyweight cases are not registered with default CTest.
Added partridge_benchmark, which emits one JSON object per process and separately times solve, independent validation, and rendering. Rendering is redirected to memory.
Added benchmarks/run.py, defaulting to orders 7/8/9, one warm-up, five repetitions, a 600-second per-process timeout, and captured stdout. It emits partridge-benchmark-v1 JSON with all runs, medians, min/max spread, MAD, stable-count checks, timeout status, compiler/flags/link flags/build/commit/dirty state, OS/hardware, worker count, policy, and seed.
--measure-overhead compares the counted and compile-time counter-free instantiations.
Added BENCHMARKING.md with repeatable commands, policy, post-#7/#14 baseline, order-9 runtime caveat, and before/after reporting guidance.

Fresh Release baseline

Apple arm64, Apple Clang 21.0.0, -O3 -DNDEBUG, one worker, one warm-up plus three measured repetitions:

Order 7 exhaustive infeasible: counted solve median 3.456 s, range 3.446–3.458 s; 110,483,315 nodes, 438,039,304 loop iterations, 110,483,314 placements/backtracks.
Order 8 first solution: counted solve median 1.863 s, range 1.853–1.863 s; 60,485,176 nodes/placements, 245,027,081 loop iterations, 60,485,140 backtracks.
Order 8 counter-free solve median 1.807 s; measured counted overhead 3.08% (0.0556 s).
Counts were identical across repetitions. Prune/task counts are zero as expected for the current solver.
Order 9 is supported by the default suite but was not rerun locally because the existing clean baseline in results.md is about 158.69 seconds elapsed; docs make it optional for iteration and retain its timeout.

Verification

Release opt-in build succeeded; CTest 7/7 passed.
Debug opt-in build succeeded; CTest 7/7 passed (including assertions).
Cheap default tests cover counter semantics and runner statistics/JSON parsing; there are no timing thresholds.
git diff --check passed.
A separate strict warning experiment found only pre-existing signed/unsigned loop warnings in unchanged main.cc lines 163, 172, and 274; those are outside this issue.

The benchmark JSON itself remains an intentionally generated artifact rather than a tracked file; the concise baseline and exact command/policy are tracked in BENCHMARKING.md.

Implemented on `codex/issue-8-benchmarks` (working tree; commit/PR handled by the coordinating task). ## Design - Added `SearchCounters` with nodes, loop iterations, attempted placements, backtracks, and stable zero fields for prune checks/hits and generated/completed tasks. - Used `find_solution_impl<Instrument>` with `if constexpr`; normal `find_solution()` instantiates the counter-free path, while the opt-in probe calls `find_solution_instrumented()`. Disabled production overhead is therefore structurally zero rather than a per-event null check. - Added opt-in `PARTRIDGE_BUILD_BENCHMARKS`; heavyweight cases are not registered with default CTest. - Added `partridge_benchmark`, which emits one JSON object per process and separately times solve, independent validation, and rendering. Rendering is redirected to memory. - Added `benchmarks/run.py`, defaulting to orders 7/8/9, one warm-up, five repetitions, a 600-second per-process timeout, and captured stdout. It emits `partridge-benchmark-v1` JSON with all runs, medians, min/max spread, MAD, stable-count checks, timeout status, compiler/flags/link flags/build/commit/dirty state, OS/hardware, worker count, policy, and seed. - `--measure-overhead` compares the counted and compile-time counter-free instantiations. - Added `BENCHMARKING.md` with repeatable commands, policy, post-#7/#14 baseline, order-9 runtime caveat, and before/after reporting guidance. ## Fresh Release baseline Apple arm64, Apple Clang 21.0.0, `-O3 -DNDEBUG`, one worker, one warm-up plus three measured repetitions: - Order 7 exhaustive infeasible: counted solve median 3.456 s, range 3.446–3.458 s; 110,483,315 nodes, 438,039,304 loop iterations, 110,483,314 placements/backtracks. - Order 8 first solution: counted solve median 1.863 s, range 1.853–1.863 s; 60,485,176 nodes/placements, 245,027,081 loop iterations, 60,485,140 backtracks. - Order 8 counter-free solve median 1.807 s; measured counted overhead 3.08% (0.0556 s). - Counts were identical across repetitions. Prune/task counts are zero as expected for the current solver. - Order 9 is supported by the default suite but was not rerun locally because the existing clean baseline in `results.md` is about 158.69 seconds elapsed; docs make it optional for iteration and retain its timeout. ## Verification - Release opt-in build succeeded; CTest 7/7 passed. - Debug opt-in build succeeded; CTest 7/7 passed (including assertions). - Cheap default tests cover counter semantics and runner statistics/JSON parsing; there are no timing thresholds. - `git diff --check` passed. - A separate strict warning experiment found only pre-existing signed/unsigned loop warnings in unchanged `main.cc` lines 163, 172, and 274; those are outside this issue. The benchmark JSON itself remains an intentionally generated artifact rather than a tracked file; the concise baseline and exact command/policy are tracked in `BENCHMARKING.md`.

mcp commented

2026-07-30 17:07:16 +01:00

Review follow-up applied in the issue #8 working tree:

The probe now emits timing_seconds.construction = 0; the runner summarizes its distribution. Documentation clarifies that current direct-search setup/allocation remains inside solve time and construction is reserved for future constructive paths.
Summaries now count errors and invalid outputs separately from timeouts. The runner always emits the JSON report, then exits nonzero when any mode has no completed repetitions or contains an error/invalid output. Timeouts may coexist with a completed repetition without failing the report.
Counter-free and counted warm-ups/measurements are now interleaved, alternating which mode runs first on each trial. Overhead remains the difference between independently summarized medians; the method and bias rationale are documented.
Self-tests now cover the zero construction distribution, all result categories, failure policy (including timeout-only versus timeout plus completion), and alternating mode order.
Removed the numeric working-tree baseline and overhead claim from tracked documentation. It now contains an explicit placeholder for a clean post-framework-commit baseline. Therefore the numbers in my previous comment are diagnostic measurements only, not the canonical baseline.

Focused verification: opt-in Release rebuild passed; CTest passed 7/7; a normal interleaved two-mode smoke run emitted construction distributions; an invalid-output end-to-end run emitted its JSON report and returned status 1; git diff --check passed.

Review follow-up applied in the issue #8 working tree: - The probe now emits `timing_seconds.construction = 0`; the runner summarizes its distribution. Documentation clarifies that current direct-search setup/allocation remains inside solve time and construction is reserved for future constructive paths. - Summaries now count errors and invalid outputs separately from timeouts. The runner always emits the JSON report, then exits nonzero when any mode has no completed repetitions or contains an error/invalid output. Timeouts may coexist with a completed repetition without failing the report. - Counter-free and counted warm-ups/measurements are now interleaved, alternating which mode runs first on each trial. Overhead remains the difference between independently summarized medians; the method and bias rationale are documented. - Self-tests now cover the zero construction distribution, all result categories, failure policy (including timeout-only versus timeout plus completion), and alternating mode order. - Removed the numeric working-tree baseline and overhead claim from tracked documentation. It now contains an explicit placeholder for a clean post-framework-commit baseline. Therefore the numbers in my previous comment are diagnostic measurements only, not the canonical baseline. Focused verification: opt-in Release rebuild passed; CTest passed 7/7; a normal interleaved two-mode smoke run emitted construction distributions; an invalid-output end-to-end run emitted its JSON report and returned status 1; `git diff --check` passed.

mcp commented

2026-07-30 17:11:37 +01:00

Clean post-correctness baseline recorded after review fixes.

Framework commit: 598667b2f310dbba88c111aac26e6005972558d5
Working tree reported clean: yes
Build: Apple Clang 21.0.0, -O3 -DNDEBUG, Apple arm64, one worker
Policy: one warm-up, three measured repetitions, counters/plain interleaved, 60 s per-run timeout

Order 7: infeasible; counted median 3.452864 s (3.444231–3.454834); 110,483,315 nodes; 110,483,314 placements/backtracks; plain median 3.434528 s; counted overhead 0.53%.
Order 8: valid first solution; counted median 1.816794 s (1.814239–1.816804); 60,485,176 nodes/placements; 60,485,140 backtracks; plain median 1.805297 s; counted overhead 0.64%.
Counts were stable. Construction time was zero. Median independent validation and rendering were each below 0.02 ms.

Order 9 remains supported by the runner but was not repeated because the existing historical result is about 158.69 s per run. The final independent re-review found no remaining issues with provenance, timing semantics, failure signaling, or overhead interleaving.

Clean post-correctness baseline recorded after review fixes. Framework commit: `598667b2f310dbba88c111aac26e6005972558d5` Working tree reported clean: yes Build: Apple Clang 21.0.0, `-O3 -DNDEBUG`, Apple arm64, one worker Policy: one warm-up, three measured repetitions, counters/plain interleaved, 60 s per-run timeout - Order 7: infeasible; counted median 3.452864 s (3.444231–3.454834); 110,483,315 nodes; 110,483,314 placements/backtracks; plain median 3.434528 s; counted overhead 0.53%. - Order 8: valid first solution; counted median 1.816794 s (1.814239–1.816804); 60,485,176 nodes/placements; 60,485,140 backtracks; plain median 1.805297 s; counted overhead 0.64%. - Counts were stable. Construction time was zero. Median independent validation and rendering were each below 0.02 ms. Order 9 remains supported by the runner but was not repeated because the existing historical result is about 158.69 s per run. The final independent re-review found no remaining issues with provenance, timing semantics, failure signaling, or overhead interleaving.

mgrettondann referenced this issue from a commit

2026-07-30 17:11:55 +01:00

bench: add repeatable solver measurements

mgrettondann referenced this issue from a commit

2026-07-30 17:11:55 +01:00

bench: record clean solver baseline

mcp referenced a pull request that will close this issue

2026-07-30 17:12:14 +01:00

bench: add repeatable solver measurements #20

mcp closed this issue

2026-07-30 17:12:29 +01:00

mcp referenced this issue