Capacity scheduling benchmarks¶
All benchmarks · Measurement rules
Summary¶
max_weight_with_capacity
selects intervals with the highest total weight while limiting how many may
overlap at once. In synthetic examples with small, independent overlap groups,
full Polars queries took under 120 ms for one million intervals and
returned an exact optimum. Polars has no built-in solver for this optimization
problem. Large, interconnected groups can take much longer.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | polars-intervals (ms) |
|---|---|---|
| 32 overlapping per set, capacity 1 | 1,000,000 | 28 |
| 32 overlapping per set, capacity 2 | 1,000,000 | 62.5 |
| 32 overlapping per set, capacity 31 | 1,000,000 | 119 |
| 32 overlapping per set, capacity 32 | 1,000,000 | 43.2 |
Each overlap group has 32 intervals. A limit of 31 still requires choosing one to leave out, while a limit of 32 allows all intervals in these examples and makes the task easier.
Benchmark details
What was compared
The headline table uses integer endpoints at one million rows and shows overlap limits from selecting one interval per group through selecting all 32.
Exact values, sample ranges and counts · Source samples.
Each set contains 32 intervals that overlap one another, with no overlap between sets. Capacity is the maximum number that may be selected at the same time. The columns compare integer, Date and microsecond Datetime endpoints.
Polars query time (ms) · medians
| Workload | Input rows | Integer | Date | Datetime |
|---|---|---|---|---|
| 32 overlapping per set, capacity 1 | 1,000,000 | 28 | 44.2 | 28.3 |
| 32 overlapping per set, capacity 2 | 1,000,000 | 62.5 | 49.1 | 83.3 |
| 32 overlapping per set, capacity 31 | 1,000,000 | 119 | 101 | 126 |
| 32 overlapping per set, capacity 32 | 1,000,000 | 43.2 | 31.7 | 41 |
Exact values, sample ranges and counts · Source samples.
Runtime does not simply increase with capacity. A capacity of 31 still requires choosing which interval to leave out. At 32, every interval in these positive- weight examples can be selected, making the task much easier.
Settings
See the measurement guide and shared hardware.
Complete Polars queries · solver uses up to 8 workers · median of 3 samples · Polars thread count unrecorded · measurement settings
Small cases are checked by trying all subsets. Larger results are checked for capacity violations and compared with independent optimization implementations. The Polars examples also have independently calculable best weights.
Query times include validation and output construction, but exclude generating and converting input data.
Limitations
Algorithm tests cover empty inputs through one million rows, varied overlap, sorted and shuffled order, seven weight distributions and different capacity limits. Polars tests cover integer, Date and Datetime endpoints, including timezone-aware nanosecond timestamps. No equivalent Polars-only optimizer was benchmarked.
The algorithm-only datasets differ from the Polars examples. Some expensive alternative-method combinations were omitted, and the largest inputs have narrower test coverage.
Reproduce
cargo bench -p intervals-core --bench max_weight_with_capacity --locked > benchmarks/results/capacity-local.csv
python -I /path/to/checkout/benchmarks/capacity_temporal.py > capacity-temporal-local.csv
CAPACITY_BENCH_MAX_N, CAPACITY_BENCH_SAMPLES and CAPACITY_BENCH_FAMILY
restrict the core run. Run the temporal command with the installed release
wheel's Python from outside the checkout, following the shared setup.
Setup, metrics and publishing · Core samples · Polars samples · Omission log · Cleanup samples · Design and historical validation
History
The saved run record names base revision
cd3a0181232bda9a2c1f7b0aafdfef1adcd8233f. The measured package
version was not recorded. The original core source hash matches 29d75ee,
before cee8e52 removed the per-interval edge-index vector and intermediate
worker-result buffering. Those changes affect allocations and reconstruction
inside the timed solver. The separately recorded cleanup run measures core
calls, not the full Polars queries in the headline table.
Rust algorithm only · package uses up to 8 workers · median of 3 samples · measurement settings
These inputs are shuffled and have positive weights. The package can solve independent overlap sets in parallel. The alternatives solve those sets one at a time, solve the entire input together, or use a general-purpose optimizer. All return an exact optimum.
Algorithm time (ms) · medians
| Workload | Input rows | Package algorithm | One overlap set at a time | Whole-input optimizer | General-purpose optimizer |
|---|---|---|---|---|---|
| Non-overlapping, capacity 2 | 1,000,000 | 85.6 | 86.4 | 443 | 2,450 |
| Many overlaps, capacity 2 | 1,000,000 | 1,090 | 1,120 | 1,060 | 3,220 |
| Identical intervals, capacity 2 | 1,000,000 | 138 | 106 | 93.1 | 90.3 |
| Independent overlap sets, capacity 2 | 10,000 | 2.21 | 2.27 | 3.24 | 7.23 |
| Independent overlap sets, capacity 2 | 1,000,000 | 128 | 268 | 502 | 1,970 |
| Independent overlap sets, capacity 8 | 100,000 | 17.8 | 76.8 | 152 | 295 |
| Independent overlap sets, capacity 16 (enough for all) | 100,000 | 6.44 | 6.29 | 262 | 456 |
Exact values, sample ranges and counts · Source samples.
One million rows in independent overlap sets take 128 ms at capacity two. A dense overlapping dataset of the same size takes 1.09 seconds. Parallel processing helps independent sets, but the alternatives win on some dense or identical-interval inputs.
On the million-row independent-set example, peak requested heap storage is 96.4 MiB for the package versus 56.6 MiB when processing sets one at a time. The extra memory helps reduce runtime. These are algorithm allocations, not whole-process memory.
The displayed run predates a memory-allocation cleanup. A separate before/after run is retained, but does not establish a speedup from that change. Details and omissions are in the supporting notes.