Scheduling with changing capacity benchmarks¶
All benchmarks · Measurement rules
Summary¶
max_weight_with_capacity_profile
selects the highest-weight set of intervals when the allowed number of overlaps
changes over time. In synthetic examples with small, independent overlap groups,
full Polars queries took under 170 ms for one million intervals, with the
overlap limit varying between 2, 4, 6 and 8. The result is exact. Polars has no
built-in solver for this optimization problem.
Larger, interconnected groups can take much longer.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | polars-intervals (ms) |
|---|---|---|
| Constant capacity 4 | 1,000,000 | 77.6 |
| Enough capacity for all | 1,000,000 | 46.7 |
| Capacity varies: 2, 4, 6, 8 | 100,000 | 14.3 |
| Capacity varies: 2, 4, 6, 8 (larger input) | 1,000,000 | 160 |
Changing the overlap limit adds work on these inputs. Allowing every useful interval to be selected avoids the harder selection step.
Benchmark details
What was compared
The headline table uses integer endpoints to compare constant, changing and sufficient capacity, including changing-capacity inputs at 100,000 and one million rows.
Exact values, sample ranges and counts · Source samples.
The input consists of separate sets of at most 32 mutually overlapping intervals. Variable-capacity examples have no available capacity in the gaps between sets. “Enough capacity for all” allows every useful interval to be selected. Columns compare integer, Date and microsecond Datetime endpoints.
Polars operation time (ms) · medians
| Workload | Input rows | Integer | Date | Datetime |
|---|---|---|---|---|
| Constant capacity 4 | 1,000,000 | 77.6 | 56.5 | 71 |
| Enough capacity for all | 1,000,000 | 46.7 | 31.2 | 43.3 |
| Capacity varies: 2, 4, 6, 8 | 100,000 | 14.3 | 13.1 | 13.9 |
| Capacity varies: 2, 4, 6, 8 (larger input) | 1,000,000 | 160 | 146 | 160 |
Exact values, sample ranges and counts · Source samples.
A changing capacity profile adds work compared with a constant limit on these inputs. When capacity is sufficient for every interval, the optimizer can avoid the harder selection step. A constant profile uses the simpler constant-capacity solver, with some additional time to read and check the profile.
Settings
See the measurement guide and shared hardware.
Complete Polars operation · solver uses up to 8 workers · median of 3 samples · Polars thread count unrecorded · measurement settings
Small cases are checked by trying every subset. Full-sized outputs are checked against the capacity profile and compared across exact implementations. The Polars examples have independently calculable best weights. There is no Polars-only comparison.
Times include input extraction, validation and output construction. Data generation and type conversion are excluded.
Limitations
The final algorithm run covers 187 combinations of input size, overlap pattern, capacity changes, segment count, input order and weights. Large interconnected selection problems stop at 10,000 intervals. Independent sets and easier cases extend to one million. The Polars measurements cover integer and temporal endpoints on the separate-overlap-set inputs described above.
Algorithm-only alternatives have different input-preparation and instrumentation costs, so small differences need care. Their times cannot be subtracted from the Polars totals to estimate overhead.
The million-row parallel example requested 143 MB of live heap storage in the package call. This includes output and working storage, but excludes caller inputs and the rest of the process. The supporting notes retain memory comparisons, earlier experiments and validation details.
Reproduce
cargo bench -p intervals-core --bench max_weight_with_capacity_profile --locked > benchmarks/results/capacity-profile-local.csv
python -I /path/to/checkout/benchmarks/capacity_profile_temporal.py > capacity-profile-temporal-local.csv
PROFILE_BENCH_MAX_N, PROFILE_BENCH_MIN_N, PROFILE_BENCH_MIN_M,
PROFILE_BENCH_SAMPLES and PROFILE_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 · Final core samples · Polars samples · Metadata and historical run inventory · Design notes
History
Rust algorithm only · one thread · median of 3 samples · measurement settings
The package chooses between two exact optimization methods. “Transshipment” and “circulation” are their technical names. This table forces each method on sorted inputs where capacity alternates between four and five. More profile segments mean more capacity changes to process. The alternatives include internal timing instrumentation that the package's direct call does not.
Algorithm time (ms) · medians
| Workload | Input rows | Package algorithm | Always use transshipment | Always use circulation |
|---|---|---|---|---|
| Moderate overlap, 1,000 capacity segments | 10,000 | 37.9 | 386 | 39.5 |
| Moderate overlap, 10,000 capacity segments | 10,000 | 37.3 | 3,820 | 40.3 |
Exact values, sample ranges and counts · Source samples.
Choosing a suitable method matters much more than small implementation costs in these examples. The next table compares solving independent overlap sets one at a time with using eight workers. These are sorted integer inputs.
Algorithm time (ms) · medians
| Workload | Input rows | Package algorithm | Always use one worker | Always use eight workers |
|---|---|---|---|---|
| 32 intervals per overlap set, 16 capacity segments | 1,000 | 0.62 | 0.648 | 0.714 |
| 32 intervals per overlap set, 16 capacity segments | 10,000 | 5.74 | 6.02 | 2.25 |
| 32 intervals per overlap set, 16 capacity segments | 1,000,000 | 226 | 671 | 217 |
Exact values, sample ranges and counts · Source samples.
The package stays single-threaded below 16,384 rows. Forced parallel processing loses on the 1,000-row example but wins at 10,000 rows, so that threshold is a tradeoff. At one million rows, parallel processing is substantially faster.