Minimum stabbing points benchmarks¶
All benchmarks · Measurement rules
Summary¶
minimum_stabbing_points
finds the fewest points needed so that every interval contains at least one
selected point. Complete Polars queries took under 140 ms for three million
intervals. The result is exact. Input order has a large effect because
intervals already sorted by their ends need less processing. Polars has no
built-in solver for this optimization problem.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | polars-intervals (ms) |
|---|---|---|
| Non-overlapping, sorted | 1,000 | 0.499 |
| Non-overlapping, sorted | 3,000,000 | 26.5 |
| Non-overlapping, shuffled | 1,000 | 0.21 |
| Non-overlapping, shuffled | 3,000,000 | 139 |
| Regular overlaps, sorted | 3,000,000 | 7.76 |
| Regular overlaps, shuffled | 3,000,000 | 115 |
The three-million-row examples are faster when sorted, and overlaps reduce how many points must be returned. At 1,000 non-overlapping rows, shuffled input is faster, though both queries take under 1 ms.
Benchmark details
What was compared
Exact values, sample ranges and counts · Source samples.
The compact table selects integer inputs at 1,000 and three million rows, with sorted and shuffled orders; only the larger size also includes regular overlaps.
Non-overlapping intervals each need their own point. In the regular overlapping inputs, one point can serve several intervals. Sorted rows are ordered by their ends. Columns compare integer, Date and microsecond Datetime endpoints.
Polars query time (ms) · medians
| Workload | Input rows | Integer | Date | Datetime |
|---|---|---|---|---|
| Non-overlapping, sorted | 3,000,000 | 26.5 | 15 | 27.6 |
| Non-overlapping, shuffled | 3,000,000 | 139 | 96.6 | 129 |
| Regular overlaps, sorted | 3,000,000 | 7.76 | 4.41 | 6.45 |
| Regular overlaps, shuffled | 3,000,000 | 115 | 78.7 | 114 |
Exact values, sample ranges and counts · Source samples.
The shuffled three-million-row examples take 79–139 ms across these endpoint types. Already sorted inputs take 4–28 ms. Overlap also changes the amount of output to create, so input row count alone does not determine runtime.
Settings
See the measurement guide and shared hardware.
Complete Polars queries · one solver thread, 24 Polars threads · median of 3 samples · measurement settings
Every output is checked to hit all intervals. A separate algorithm computes the minimum number of points using a different approach. Small exhaustive tests check both implementations. Polars examples also include independently verifiable evidence that fewer points cannot suffice.
Timings include validation, processing and output creation. Generating and converting inputs is excluded.
Limitations
Algorithm tests cover 1,000 to three million rows, twelve interval patterns, and sorted, reversed and shuffled orders. Integer endpoints have the widest coverage. Polars tests also cover Date and microsecond Datetime endpoints on non-overlapping, overlapping and identical intervals.
Algorithm-only and Polars inputs differ, so their times cannot be used to calculate Polars overhead. Equal endpoints can leave data effectively sorted even after shuffling.
Other datetime units, timezones and grouping have correctness tests but no matching performance measurements here. No Polars-only alternative was measured. The supporting notes retain the algorithms, correctness checks and exact measurement boundaries.
Reproduce
cargo bench -p intervals-core --bench minimum_stabbing_points --locked > benchmarks/results/stabbing-local.csv
python -I /path/to/checkout/benchmarks/stabbing_temporal.py > stabbing-temporal-local.csv
STABBING_BENCH_MAX and STABBING_BENCH_SAMPLES restrict the core run.
Run the temporal command with the installed release wheel's Python from outside
the checkout.
Setup, metrics and publishing · Core samples · Polars samples · Metadata and historical validation · Design notes
History
Rust algorithm only · one thread · median of 3 samples · integer endpoints · measurement settings
The package detects intervals that are already sorted by their ends. Both alternatives always sort, using either interval records or row indices. Their times include internal instrumentation that the package call does not.
Algorithm time (ms) · medians
| Workload | Input rows | Package algorithm | Always sort records | Always sort row indices |
|---|---|---|---|---|
| Non-overlapping, sorted | 3,000,000 | 17.8 | 31.4 | 24.6 |
| Non-overlapping, shuffled | 3,000,000 | 113 | 109 | 283 |
| Non-overlapping, reversed | 3,000,000 | 35.2 | 35.4 | 26.8 |
| All share a point, reversed | 3,000,000 | 23.7 | 23.7 | 14.4 |
| Many random overlaps, shuffled | 3,000,000 | 98.3 | 99.3 | 230 |
Exact values, sample ranges and counts · Source samples.
The package benefits from sorted input. Sorting row indices can be faster on reverse-ordered data, but is slower on the largest shuffled examples. On three million non-overlapping integer intervals, the package's peak requested heap storage is 32.0 MiB when sorted and 77.8 MiB when shuffled. This includes output and sorting buffers, not whole-process memory.