Containment counting benchmarks¶
All benchmarks · Measurement rules
Summary¶
containment_count counts how many
other intervals each row contains. In synthetic benchmarks, full Polars queries
were at least 1.2× faster than Polars and took under 1.1 s for three million
rows. Many small groups reverse the advantage.
Results¶
Full Polars query time · milliseconds
Native Polars uses ranking expressions to count the same containments without creating a row for every matching pair.
| Workload | Rows | polars-intervals (ms) | Native Polars (ms) | Compared with native |
|---|---|---|---|---|
| Repeated intervals, no grouping | 3,000,000 | 65.3 | 146 | 2.2× faster |
| Few containments, no grouping | 3,000,000 | 1,090 | 2,010 | 1.8× faster |
| Mixed intervals, no grouping | 3,000,000 | 363 | 459 | 1.3× faster |
| Few containments, 1,000 groups | 10,000 | 8.76 | 6.75 | 1.3× slower |
Repeated intervals are much cheaper to count than irregular inputs. With only ten rows per group on average, calling the function costs more than it saves.
Benchmark details
What was compared
The headline cases contrast large repeated and irregular inputs with a small grouped input where native Polars is faster.
The comparison uses Polars ranking expressions to count containment without building a row for every matching pair. Ranking expressions were the only native method measured in this run. Other native implementations were measured separately in the original selection run, whose timings are not mixed into this comparison.
Speedup is native median divided by package median. Above 1 means the package is faster. Below 1 means it is slower.
Exact values, sample ranges and counts · Source samples.
Polars query time (ms) · medians
| Workload | Input rows | containment_count (measured build) | Polars ranking expressions |
|---|---|---|---|
| Repeated intervals, no grouping | 3,000,000 | 65.3 | 146 |
| Few containments, no grouping | 3,000,000 | 1,090 | 2,010 |
| Mixed intervals, no grouping | 3,000,000 | 363 | 459 |
| Few containments, 1,000 groups | 10,000 | 8.76 | 6.75 |
Exact values, sample ranges and counts · Source samples.
Settings
The Polars run used 24 Polars threads, one warmup and five samples per case, with seed 42. The displayed times are medians. All endpoints are Int64. “No grouping” means that every interval is compared with the full input. Grouped row counts are totals across all groups.
Query times include preparing the data for counting and creating the output. See the shared hardware. Settings, software versions and source hashes are recorded in the run metadata.
Small cases are checked by comparing every pair directly. Larger outputs are cross-checked between implementations.
Limitations
Algorithm tests cover fourteen input patterns with 1,000 to three million rows, including nesting, duplicates, shared endpoints, empty intervals and different input orders. Polars tests also cover groups, Date and timezone-aware Datetime.
The function validates inputs, while the Polars comparison assumes valid endpoints. The Polars ranking APIs were marked unstable at that time.
Some join-based alternatives were skipped when they could create more than two million intermediate rows. The ranking comparison above avoids that expansion. Algorithm-only and Polars tests use different datasets, so their times cannot be subtracted to calculate Polars overhead. Detailed checks and memory accounting remain in the supporting notes.
Reproduce
cargo bench -p intervals-core --bench containment --locked
uv run --locked --no-sync python benchmarks/containment_count.py --methods plugin rank_runs --output target/containment-rank-runs.json
Use the shared release setup first. To reproduce the original native selection,
use --methods plugin rank rank_by join bands equality and a separate output.
CONTAINMENT_SIZES and CONTAINMENT_CSV select algorithm-test sizes and output.
The Python runner accepts --sizes and --repeats.
Shared setup and publishing · Core samples · Original native samples, skips, plans and metadata · Run-rank samples and metadata · Design notes and historical comparisons
History
The headline ranking follow-up used dirty base revision
925033f9990b47f473d9debb2779b4533e63f24f. The measured wheel's package version
and adapter source hash were not recorded, so the base revision's 0.1.0
manifest does not establish the installed wheel's identity. The run retains
kernel and runner hashes. Its historical adapter copied both endpoint columns.
The current shared extraction borrows contiguous columns and collects only
when necessary. That extraction is inside the complete-query timing. Moving
candidate files and consolidating provenance are outside the timed operation.
The earlier join-based comparison also favored Polars on small groups. Rust-only tests compared packed Fenwick, indirect Fenwick and segment-tree designs. The package uses packed Fenwick, which stores sortable records together. Indirect Fenwick sorts row indices instead. These timings include internal measurement overhead and exclude Polars: one thread, median of five samples, with measurement settings.
Algorithm time (ms) · medians
| Workload | Input rows | Package design (packed Fenwick) | Indirect Fenwick | Segment tree |
|---|---|---|---|---|
| Repeated intervals | 3,000,000 | 53.2 | 38.6 | 53.8 |
| Few containments | 3,000,000 | 1,010 | 1,340 | 1,120 |
| Many containments | 3,000,000 | 418 | 779 | 488 |
Exact values, sample ranges and counts · Source samples.
The selected design is faster on large irregular examples, but loses on duplicates. At three million distinct ends its live buffer capacity reaches 137 MiB, compared with 91.6 MiB for indirect Fenwick. This counts algorithm buffers, including output, rather than the memory of the whole process.