partridge-cpp/BENCHMARKING.md

Solver benchmarks

The benchmark suite records repeatable performance data independently of the default correctness tests. It exercises the exhaustive infeasible order 7 and the first-solution orders 8 and 9. The benchmark executable is opt-in:

cmake -S . -B build-benchmark -DCMAKE_BUILD_TYPE=Release \
  -DPARTRIDGE_BUILD_BENCHMARKS=ON
cmake --build build-benchmark
python3 benchmarks/run.py --binary build-benchmark/partridge_benchmark \
  > benchmark.json

The default policy is one unrecorded warm-up followed by five repetitions per case, with a 600-second timeout for each process. Solver stdout is captured; the probe renders into an in-memory stream so grids do not perturb terminal I/O. Override the policy with --orders, --warmup, --repetitions, --timeout, and --candidate-order. The choices are ascending, descending, and best-fit; ascending candidate sizes are the production default. The production default also removes equivalent D4 board orientations by constraining the unique unit square. Pass --no-symmetry to obtain an otherwise identical unconstrained baseline. The production default also applies the pruning rules described below. Use --pruning valley-capacity, --pruning large-square, or --no-pruning to measure each rule alone or obtain an unpruned search. Use --component-pruning gcd, --component-pruning subset-sum, or --component-pruning none to compare the component-area rule separately. Component pruning is disabled by default because the measurements below do not recover its cost. Order 9 uses the constructive odd-order path, searching order 8 and then tiling the enlarged border, so it is suitable for normal local benchmarking:

python3 benchmarks/run.py --binary build-benchmark/partridge_benchmark \
  --orders 8 9 --warmup 1 --repetitions 5 --timeout 60 > benchmark.json

Use --direct-search when benchmarking the skyline core rather than the public even-predecessor construction used for odd orders from 9 onwards:

python3 benchmarks/run.py --binary build-benchmark/partridge_benchmark \
  --orders 6 7 8 9 --warmup 1 --repetitions 5 --timeout 60 \
  --candidate-order ascending --direct-search > direct.json

The JSON contains every run and median, range, and median absolute deviation for solve, construction, independent validation, and rendering. Direct-search cases report zero construction time: their setup and allocation remain part of solve time. Constructed odd-order cases report predecessor search and construction separately. The document also records compiler, flags, build type, commit, OS/CPU metadata, worker count, search policy, seed, timeouts, errors, invalid outputs, and the stdout policy. Search counts must be stable across repeated runs. Prune counters report enabled search rules; they are zero in the corresponding disabled modes. Task counters remain zero for the current single-threaded solver and reserve stable schema fields for later work.

The runner writes its JSON report before returning a failure status if any mode has no completed runs or produces an error or invalid output. Timeouts are reported but do not fail a case when another repetition completed.

Normal partridge_cpp calls instantiate a compile-time counter-free solver. Use --measure-overhead to run both counter-free and counted variants and report their median difference:

python3 benchmarks/run.py --binary build-benchmark/partridge_benchmark \
  --orders 8 --warmup 2 --repetitions 7 --timeout 60 --measure-overhead \
  > overhead.json

Counter-free and counted warm-ups and measurements are interleaved. The first mode alternates on each repetition, limiting systematic bias from temperature, frequency scaling, and run order. Reported overhead is the difference between the two independently summarized medians.

Do not use wall-clock thresholds as correctness checks. Keep the generated JSON outside version control unless it is being deliberately added as a named comparison baseline.

Valley-capacity pruning

For a selected valley, let its rim be the lower height of its two neighbours, treating a board edge as full height. Until the valley reaches that rim, no square wider than the valley can enter it. Therefore the combined area of all remaining squares no wider than the valley must be at least the valley width times its depth below the rim. Rejecting a state when that necessary inequality fails is sound. At widths one and two it provides the usual narrow-gap capacity checks without separate special cases.

The rule is compiled out of the recursive search in --no-pruning mode. Instrumented output records valley_capacity_checks and valley_capacity_prunes as well as the aggregate pruning counters, allowing enabled and disabled runs to report nodes, checks, hits, and elapsed time.

Measurements used the issue #10 working tree based on commit f37e087, Apple Clang 21.0.0, -O3 -DNDEBUG, macOS arm64, one worker, one warm-up, and five measured repetitions. The production ascending policy and D4 constraint were enabled. Every result passed the benchmark's independent validator and all counters were stable:

Order	Valley capacity	Median solve (range)	Nodes	Checks	Prunes
7 exhaustive	enabled	0.996 s (0.990-0.998 s)	13,833,048	13,833,048	7,411,551
7 exhaustive	disabled	1.110 s (1.109-1.111 s)	14,997,603	0	0
8 first solution	enabled	0.205 s (0.204-0.208 s)	2,724,096	2,724,095	1,606,836
8 first solution	disabled	0.228 s (0.228-0.233 s)	2,931,203	0	0

The rule reduced nodes by 7.8% for order 7 and 7.1% for order 8. Its low per-node cost also reduced median counted solve time by 10.3% and 9.9%, respectively, so it remains enabled by default.

Remaining-large-square pruning

For a remaining side k, a skyline can contain an empty k-by-k box only if it has k consecutive columns whose filled heights are no greater than the board height minus k. A single linear scan tracks qualifying consecutive columns. If no such run exists, the square cannot be placed and the state is infeasible even when its total empty area is sufficient.

Empty-box feasibility is monotonic in the side length: a box which fits the largest remaining square also fits every smaller remaining size. The solver therefore invokes only one O(board width) scan per surviving node, after the cheaper valley-capacity check. It does not attempt an unproven multiplicity bound. --pruning large-square measures the rule independently; --pruning valley-capacity provides the production baseline without it. Instrumented output records large_square_checks and large_square_prunes.

Measurements used the issue #15 working tree based on commit e27427d, Apple Clang 21.0.0, -O3 -DNDEBUG, macOS arm64, one worker, one warm-up, and seven measured repetitions. Counter-free and counted runs were interleaved; the table reports the counter-free production instantiation. The baseline keeps valley-capacity pruning enabled, so it isolates the new rule. All results passed independent validation and counters were stable:

Search	Large-square check	Median solve	Nodes	Checks	Prunes
Order 7 exhaustive	enabled	0.946 s	13,221,239	6,163,390	227,321
Order 7 exhaustive	disabled	0.947 s	13,833,048	0	0
Order 8 first solution	enabled	0.195 s	2,597,678	1,063,472	38,177
Order 8 first solution	disabled	0.197 s	2,724,096	0	0
Order 9 direct	enabled	1.225 s	14,840,146	5,592,843	54,900
Order 9 direct	disabled	1.208 s	14,995,127	0	0

The rule reduced nodes by 4.4% for order 7, 4.6% for order 8, and 1.0% for direct order 9. Counter-free median time improved by 0.12% and 0.89% on the two distinct searches in the public benchmark set. Public order 9 constructs from the improving order-8 search. Direct order 9, which bypasses that public route, regressed by 1.39%; it remains documented as a caution for future policy tuning.

Checking only every fourth placement depth was also measured. It retained fewer prunes and was slower than checking every surviving node by 2.2% for order 7, 2.3% for order 8, and 0.6% for direct order 9, so the periodic schedule was rejected. Incremental maintenance would need additional per-size window state and undo logic for an O(W) scan whose public net cost is already recovered; it was not added without evidence that the complexity would improve elapsed time. The simple every-node scan remains enabled by default for the measured public benchmark benefit.

Component-area pruning

In a skyline, every non-full column is empty from its filled height to the top of the board. Adjacent non-full columns therefore belong to the same empty component, while a full-height column is an impassable separator. Each remaining square must lie wholly within one such component, so every component area must be the sum of a bounded subset of the remaining square areas.

The gcd mode first rejects a component area which is not divisible by the greatest common divisor of all remaining square areas. The subset-sum mode then computes exact reachable areas using each remaining multiplicity as a bound. Each component is checked against the same reachable set; this is a necessary condition, not a claim that independently selected subsets are mutually disjoint.

The check is triggered only after a placement reaches full board height and can create or extend a component boundary. This keeps the potentially more expensive bounded subset sum off ordinary nodes. Instrumented output records component_area_checks, component_area_prunes, component_gcd_prunes, and component_subset_prunes. The three --component-pruning modes allow the trigger cost, cheap gcd rule, and bounded subset sum to be compared directly. Use --component-schedule periodic-8 to compare the event-driven boundary trigger with checking every eighth placement depth.

Measurements used the issue #13 working tree based on commit 220cec0, Apple Clang 21.0.0, -O3 -DNDEBUG, macOS arm64, one worker, one warm-up, and seven measured repetitions for the boundary-trigger modes. Counter-free and counted runs were interleaved; the table reports counter-free medians. The existing valley-capacity and large-square rules remained enabled. All results passed independent validation and counters were stable:

Order	Component rule	Median solve	Nodes	Checks	Prunes
7 exhaustive	disabled	0.985 s	13,221,239	0	0
7 exhaustive	gcd	1.027 s	13,220,729	171,088	2,568
7 exhaustive	subset sum	1.052 s	13,189,961	161,706	69,483
8 first solution	disabled	0.203 s	2,597,678	0	0
8 first solution	gcd	0.212 s	2,597,548	23,943	637
8 first solution	subset sum	0.219 s	2,592,212	23,097	11,858

Gcd-only checking changed fewer than 0.005% of nodes while slowing the counter-free solver by 4.3% for both orders. Bounded subset sum reduced nodes by only 0.24% for order 7 and 0.21% for order 8, while slowing them by 6.8% and 7.5%. Neither rule is enabled by default.

The boundary trigger is an incremental event check: it runs only when the latest placement reaches full height and can change the component partition. For comparison, subset sum was also sampled every eighth placement depth with one warm-up and three measured repetitions. Periodic checking made 1,501,035 checks for order 7 and 290,774 for order 8, versus 161,706 and 23,097 at boundary events. Its counter-free medians were 1.088 s and 0.227 s, 10.5% and 11.7% slower than disabled pruning and materially worse than boundary triggering. The periodic schedule is retained only as an opt-in measurement mode; event-triggered checking is the cheaper schedule if component pruning is reconsidered with new evidence.

D4 board symmetry

Every solution contains exactly one 1-by-1 square. Rotations and reflections of the whole board preserve square sizes, multiplicities, and coverage, so the unit square can select the orientation without assigning identities to any of the repeated larger squares. For a board of width W, the solver accepts the unit square only in the closed fundamental triangle x <= y <= floor((W - 1) / 2). Reflecting a cell toward the left edge, swapping its coordinates if necessary, and reflecting toward the top edge maps every D4 orbit into this triangle. Closed diagonal and midline boundaries retain the smaller orbits of symmetric cells.

The check is made only when the skyline search is ready to place the unit square, so it never rejects a partial state before the square's position is decidable. The implementation remains compile-time counter-free in normal solver calls and keeps the single-threaded deterministic search policy. Instrumented runs count examined and rejected unit-square placements as prune checks and hits.

Measurements used the issue #3 dirty working tree based on commit 74bde26, Apple Clang 21.0.0, -O3 -DNDEBUG, macOS arm64, one worker, one warm-up, and five sequential measured repetitions. All results passed the benchmark's independent cell-coverage validator and counts were stable:

Route	D4 constraint	Median solve (range)	Nodes	Prune hits
Order 8 public	enabled	0.245 s (0.244-0.248 s)	2,931,203	1,329,567
Order 8 public	disabled	0.679 s (0.659-0.709 s)	7,735,369	0
Order 9 direct	enabled	1.705 s (1.671-1.740 s)	16,231,918	6,755,171
Order 9 direct	disabled	4.542 s (4.482-4.662 s)	45,840,266	0

Thus the constraint reduced nodes by 62% for order 8 and 65% for direct order 9; counted median solve time fell by 64% and 62%, respectively.

A public order-10 probe with the D4 constraint, ascending policy, and a 45-second per-process bound did not complete. Public order 11 first performs that identical order-10 core search and only then adds its inexpensive odd border, so adding either order to routine correctness tests would duplicate the same unresolved bottleneck. They remain useful opt-in heavyweight benchmark targets with explicit timeouts. A direct order-11 benchmark is a different experiment: it bypasses the public odd construction and searches the larger core itself, so it must not be presented as public order-11 performance.

Smallest-valley skyline

The solver stores one filled height per board column instead of one value per cell. Equal adjacent heights form conceptual vertical bars. A valley is a maximal bar lower than both neighbours, with board edges treated as bars of full board height. Each node scans for the smallest-width valley, breaking ties by lower height and then leftmost position, and tries every available square which fits at that valley's far-left edge.

This branching remains complete: the bottom-left cell of the selected valley must be covered, a square covering it cannot begin to the left across the taller neighbour, and it cannot extend beyond the equal-height run without overlap or leaving an unreachable hole. Trying every fitting available size therefore includes the placement used by every possible completion.

For board width W and order n, the skyline scan is O(W). A node tries at most n candidates and each placement or exact undo changes at most n heights, giving O(W + n^2) local work. The skyline, multiplicities, placements, and recursion stack use O(W + n^2) state, compared with the former O(W^2) cell grid.

One-run exploratory measurements used the issue #4 dirty worktree at base commit 0a7ce1e, Apple Clang 21.0.0, -O3 -DNDEBUG, macOS arm64, one worker, no warm-up, and a 15-second timeout. Every completed result passed the independent benchmark validator:

Order	Result	Ascending time	Ascending nodes	Descending time	Descending nodes
6	infeasible	0.040 s	659,598	0.039 s	659,598
7	infeasible	3.103 s	43,604,507	3.071 s	43,604,507
8	solution	0.585 s	7,735,369	0.941 s	12,186,125
9 direct	solution	3.831 s	45,840,266	timeout	unavailable

The infeasible orders exhaust the same tree in either direction. Ascending was selected as the default because it reaches the first order-8 solution with 36% fewer nodes and also completed direct order 9 within the timeout; descending direct order 9 did not.

A direct ascending order-10 probe exceeded 20 seconds. Public order 10 is also a direct search, and public order 11 first searches order 10 before using odd-predecessor construction. Consequently neither 10 nor 11 is in the routine correctness suite: doing so would test the same unresolved order-10 search bottleneck, while the existing route-boundary test still verifies that 11 selects construction. Revisit both sizes when order 10 completes within a practical test budget.

Candidate policy selection

Candidate ordering is a deterministic search policy and does not alter the smallest-valley selection or set of placements tried. ascending tries smaller available squares first and descending tries larger ones first. best-fit first tries a square exactly as wide as the selected valley, because that placement closes the valley without leaving a shelf remainder, then tries the other sizes in ascending order. If no exact-width square fits, best-fit and ascending are identical at that node.

The policy comparison used the issue #12 working tree based on commit d751d1b, Apple Clang 21.0.0, -O3 -DNDEBUG, macOS arm64, and one worker. Order 8 used two warm-ups and seven sequential measured repetitions; direct order 9 used one warm-up and three measured repetitions. All completed results passed independent validation and node counts were stable:

Order	Policy	Counted median (range)	Counter-free median	Nodes
8	ascending	0.808 s (0.790–0.852 s)	0.794 s	7,735,369
8	descending	1.310 s (1.279–1.449 s)	1.268 s	12,186,125
8	best-fit	0.817 s (0.813–0.857 s)	0.823 s	7,679,349
9 direct	ascending	5.522 s (5.499–5.830 s)	not measured	45,840,266
9 direct	best-fit	5.651 s (5.533–5.820 s)	not measured	45,746,016

The earlier direct-order-9 descending probe exceeded its 15-second limit. Ascending is retained as the stable single-threaded default because it had the lowest measured median time to the first solution at both measured solvable sizes. Best-fit's slightly smaller trees did not compensate for its policy checks, while descending was substantially worse. Exhaustive infeasible order-5 tests visit the same number of nodes under all three policies, which checks that ordering does not affect completeness.

One policy therefore applies to the currently measured sizes 8 and 9. This does not establish that ascending is optimal for order 10: a bounded best-fit order-9 comparison changed the search tree by only 0.2%, so there was no evidence that repeating the known long order-10/11 search would be useful. Keep 10 and 11 as opt-in benchmark cases. Public order 11 is particularly important to interpret correctly: it constructs from an order-10 search, so it does not independently measure an odd-order candidate policy.

A worker portfolio was considered but not added. Running identical policies duplicates the same deterministic traversal. Pairing ascending with best-fit adds little diversity on the measured trees, and pairing ascending with descending dedicates a worker to the consistently slower policy. Splitting a shared frontier could avoid duplicated prefixes, but that is the parallel frontier work tracked separately in issue #11. Seeded randomized ordering was also rejected for now: the deterministic alternatives already select a clear default, and there is no measurement showing that seed distributions would improve time to first solution. The benchmark schema retains its nullable seed field so a future evidence-backed randomized policy can report reproducible runs without changing the format.

Post-correctness baseline

This framework starts from commit ce39d0a after the rendering assertion fix in #7 and completion check fix in #14. The earlier Apple M1 Release results in results.md are approximately 1.76 seconds for order 8 and 158.69 seconds elapsed for order 9; they predate the structured runner and do not contain search counters.

The first clean structured baseline used commit 598667b, Apple Clang 21.0.0 with -O3 -DNDEBUG, Apple arm64, one worker, one warm-up, and three measured repetitions. The runner reported a clean working tree:

Order	Result	Counted solve median (range)	Nodes	Placements	Backtracks
7	infeasible	3.453 s (3.444–3.455 s)	110,483,315	110,483,314	110,483,314
8	solution	1.817 s (1.814–1.817 s)	60,485,176	60,485,176	60,485,140

Counts were stable across repetitions. Interleaved counter-free medians were 3.435 seconds for order 7 and 1.805 seconds for order 8, giving counted overheads of 0.53% and 0.64% respectively. Construction time was zero; median independent validation and rendering times were each below 0.02 milliseconds.

Order 9 was not rerun for this initial baseline because the former direct search took several minutes. The default suite includes it with a per-run timeout.

Odd construction comparison

The order-9 construction was measured from the issue 6 working tree based on commit ddf07e7, using Apple Clang 21.0.0 with -O3 -DNDEBUG, macOS arm64, one worker, one warm-up, and three measured repetitions. Counter-free and counted runs were interleaved:

Order	Mode	Search median (range)	Construction median	Nodes
8	counter-free	1.773 s (1.770–1.775 s)	0	0
8	counted	1.849 s (1.848–1.850 s)	0	60,485,176
9	counter-free	1.778 s (1.773–1.779 s)	0.458 us	0
9	counted	1.852 s (1.845–1.912 s)	0.416 us	60,485,176

All runs completed with valid results and stable counters. The matching order-8 and order-9 search counts demonstrate that the new path searches only the predecessor. Compared with the recorded 158.69-second direct order-9 elapsed time in results.md, the 1.778-second counter-free median plus construction is approximately 89 times faster. The benchmark working tree was necessarily dirty with the issue 6 implementation.

New optimization issues should quote the exact JSON environment, policy, median/spread, stable counters, and counted overhead from this runner for both before and after revisions.

The separate optional CP-SAT reference benchmark and its model, memory, worker, and timing report are documented in CP_SAT_REFERENCE.md.