Maximum covered length benchmarks¶
All benchmarks · Measurement rules
Summary¶
max_k_coverage selects at most k
intervals to cover the greatest total length, counting overlaps only once. The
result is exact. A complete Polars query took under 690 ms for one million
intervals with a selection limit of 64. Allowing more selected intervals can
increase both runtime and working memory. Polars has no built-in solver for
this optimization problem.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | polars-intervals (ms) |
|---|---|---|
| Overlapping steps, sorted, select up to 8 | 10,000 | 1.08 |
| Overlapping steps, sorted, select up to 8 | 1,000,000 | 125 |
| Overlapping steps, shuffled, select up to 8 | 1,000,000 | 161 |
| Overlapping steps, shuffled, select up to 64 | 1,000,000 | 681 |
On these integer inputs, increasing the selection limit from 8 to 64 makes the query about four times slower, while sorting helps at the smaller limit. These overlapping-step examples show a measured tradeoff, not a fixed scaling rule for every input.
Benchmark details
What was compared
Exact values, sample ranges and counts · Source samples.
The compact table selects integer overlapping-step inputs: sorted cases at 10,000 and one million rows with a selection limit of 8, and shuffled million-row cases with limits of 8 and 64.
The inputs form overlapping steps along the coordinate range. The selection limit is the most intervals the function may choose. Columns compare integer, Date and microsecond Datetime endpoints.
Polars query time (ms) · medians
| Workload | Input rows | Integer | Date | Datetime |
|---|---|---|---|---|
| Overlapping steps, sorted, select up to 8 | 10,000 | 1.08 | 1.01 | 1.12 |
| Overlapping steps, sorted, select up to 8 | 1,000,000 | 125 | 117 | 126 |
| Overlapping steps, shuffled, select up to 8 | 1,000,000 | 161 | 139 | 164 |
| Overlapping steps, shuffled, select up to 64 | 1,000,000 | 681 | 630 | 689 |
Exact values, sample ranges and counts · Source samples.
On one million integer rows, increasing the limit from 8 to 64 makes this example about four times slower. Sorting helps at the smaller limit: the sorted example takes 125 ms compared with 161 ms when shuffled. These are measured cases, not a fixed scaling rule for every input.
Settings
See the measurement guide and shared hardware.
Complete Polars queries · 24 Polars threads · median of 3 samples · measurement settings
Small tests try every possible subset. A separate slower optimizer checks larger test cases. Benchmark selections are independently combined to verify their covered length and compared with reference answers. The Polars examples have known best results.
Query times include planning, execution and retrieving the selection. Creating and converting inputs is excluded.
Limitations
The algorithm run covers 1,506 combinations of size, interval pattern, input order and selection limit. It spans 1,000 to one million rows and limits from zero to 64, with extra tests for limits larger than the input. Only a subset of patterns and limits reaches one million rows.
Polars performance coverage is narrower: three input patterns, sorted and shuffled orders, and integer, Date and microsecond Datetime endpoints. Grouping and other datetime variants have no matching timings here. No equivalent Polars-only optimizer was measured.
Some slower algorithm comparisons were limited to smaller datasets. The supporting notes retain these limits, memory tradeoffs and correctness checks.
Reproduce
cargo bench -p intervals-core --bench max_k_coverage --locked > target/coverage-core.csv
# From an external environment with the release wheel installed:
python -I /path/to/checkout/benchmarks/coverage_temporal.py > coverage-temporal.csv
The core harness performs separate correctness and allocation calls before three timed invocations. See the shared guide for release setup.
Shared setup and publishing · Core samples · Collection samples · Metadata, source hashes and validation · Recurrence, proofs and experiments
History
Rust algorithm only · one thread · median of 3 samples · integer endpoints · measurement settings
The package avoids work on intervals that cannot improve the answer. One reference uses a simpler version of the same optimization method. Another solves independent overlap sets separately. The references include internal timing instrumentation and use different input wrappers.
Algorithm time (ms) · medians
| Workload | Input rows | Package algorithm | Simpler optimization reference | Solve overlap sets separately |
|---|---|---|---|---|
| Overlapping steps, shuffled, select up to 32 | 10,000 | 1.71 | 2.45 | 4.66 |
| Independent overlap sets, sorted, select up to 8 | 10,000 | 0.475 | 0.671 | 1.11 |
| Independent overlap sets, sorted, select up to 64 | 10,000 | 3.1 | 4.71 | 2.65 |
| Limit covers full range, shuffled, select up to 64 | 100,000 | 4.29 | 57.4 | — |
— means no recorded measurement for that combination.
Exact values, sample ranges and counts · Source samples.
Solving independent sets separately wins at the larger selection limit in this example, but adds overhead at the smaller limit. It is not a mode exposed by the package. When the limit is sufficient to cover the entire input range, the package can skip much of the optimization work.
On the million-row overlapping-step input, the package's peak requested heap storage rises from 162 MiB at a limit of 8 to 216 MiB at 64. These are algorithm-only allocations, including output and working storage. They do not measure the memory of a complete Polars query.