Minimum-cost covering benchmarks¶
All benchmarks · Measurement rules
Summary¶
minimum_cost_cover covers a
target range without gaps while minimizing the total cost of selected intervals.
Full Polars queries took under 270 ms for one million intervals in the two
synthetic examples below. The result is exact. Polars has no built-in solver for
this optimization problem. The number and arrangement of useful intervals affect
runtime and working memory.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | polars-intervals (ms) |
|---|---|---|
| End-to-end intervals, shuffled | 1,000,000 | 211 |
| Many overlaps, shuffled | 1,000,000 | 263 |
These million-row examples take roughly a quarter of a second. Having many overlapping alternatives takes longer than covering a continuous chain.
Benchmark details
What was compared
The headline table compares the two measured shuffled integer workloads at one million rows: a continuous chain and many overlapping alternatives.
Exact values, sample ranges and counts · Source samples.
If costs tie, the operation selects fewer intervals.
The first input forms a continuous chain of intervals whose endpoints touch. The second has many overlapping alternatives for covering the target. Both are shuffled. Columns compare integer, Date and microsecond Datetime endpoints.
Polars query time (ms) · medians
| Workload | Input rows | Integer | Date | Datetime |
|---|---|---|---|---|
| End-to-end intervals, shuffled | 1,000,000 | 211 | 196 | 206 |
| Many overlaps, shuffled | 1,000,000 | 263 | 238 | 264 |
Exact values, sample ranges and counts · Source samples.
The overlapping case takes longer than the chain for each endpoint type. Date values are somewhat faster in this run.
Settings
See the measurement guide and shared hardware.
Complete Polars queries · one solver thread · median of 3 samples · Polars thread count unrecorded · measurement settings
Results are checked for complete target coverage and agreement on optimal cost across implementations. Small tests try every possible subset. A simpler reference algorithm is limited to 1,000 benchmark rows. Polars tests check coverage and repeatable selections, without independently proving optimality for every large input.
Query times include validation, optimization and output construction. Input generation, query construction and type conversion are excluded. See the shared validation notes for the full checks and timing scope.
Limitations
The shared covering tests span 1,000 to one million rows and seventeen input patterns. They include different input orders, duplicate intervals, gaps, impossible covers, zero costs, tied costs and expensive intervals competing with cheaper ones. The separate Polars tests cover eight integer and temporal endpoint types on four patterns. No Polars-only optimizer was benchmarked.
Algorithm-only inputs and costs differ from the Polars examples, so their timings cannot isolate Polars overhead. The measurements do not separate type-handling costs from the rest of the computation.
Reproduce
cargo bench -p intervals-core --bench covering --locked > benchmarks/results/covering-local.csv
python -I /path/to/checkout/benchmarks/covering_temporal.py > covering-temporal-local.csv
The target measures both covering operations. COVER_BENCH_MAX and
COVER_BENCH_SAMPLES restrict it. Run the final command with the installed release
wheel's Python from outside the checkout, following the shared setup guide.
Setup, metrics and publishing · Core samples · Polars samples · Completion log · Design notes · Validation and source hashes
History
The saved measurement record names base revision
cee8e52e96a9a260af712d84fb86574c6225d309. Artifact hashes identify
an explicitly recorded polars_intervals-0.1.0-cp314-cp314-win_amd64.whl.
The measured core source hash matches the covering solver in 1f27171.
Metadata records the later adapter cleanup separately, including common plugin
input validation and fewer scalar copies. The record does not isolate the
runtime effect of those adapter changes. Harness verification and CSV summary
cleanup are outside the timed query, and no cleanup speedup is claimed.
Rust algorithm only · one thread · median of 3 samples · measurement settings
The package and its alternative use different tree structures to track the cheapest way to reach each part of the target. Their technical names are Fenwick tree and segment tree. These examples use shuffled input and random nonnegative costs. Timings include internal measurement overhead. “32-bit endpoints” uses the storage width of Date values without calling Polars.
Algorithm time (ms) · medians
| Workload | Input rows | Package algorithm (Fenwick tree) | Segment tree |
|---|---|---|---|
| 64-bit endpoints, end-to-end intervals | 1,000,000 | 188 | 205 |
| 64-bit endpoints, many overlaps | 1,000,000 | 226 | 390 |
| 64-bit endpoints, same start | 1,000,000 | 199 | 274 |
| 64-bit endpoints, mostly outside target | 1,000,000 | 2.05 | 2.04 |
| 32-bit endpoints, end-to-end intervals | 1,000,000 | 211 | 196 |
Exact values, sample ranges and counts · Source samples.
The package's tree is faster on most of these examples, but the alternative wins on the chain with 32-bit endpoints. It also uses more memory: on the million-row integer chain, peak requested heap storage is 158 MB compared with 105 MB for the package. These figures include output and working buffers, not total process memory.