Nesting depth benchmarks¶
All benchmarks · Measurement rules
Summary¶
nesting_depth measures how deeply each
interval sits inside a chain of other intervals. Outermost intervals have depth
zero. In synthetic benchmarks with Polars restricted to four threads, full Polars
queries took under 210 ms for three million rows. Input order and grouping
can matter as much as nesting depth. A native Polars comparison has not been
measured.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | polars-intervals (ms) |
|---|---|---|
| Depth up to 7, shuffled, 1 group | 100,000 | 5.12 |
| Depth up to 7, shuffled, 1 group | 3,000,000 | 203 |
| Fully nested, shuffled, 1 group | 3,000,000 | 206 |
| Fully nested, sorted, 1 group | 3,000,000 | 42.6 |
| Depth up to 7, shuffled, 1,000 groups | 100,000 | 10.9 |
Sorting makes a large difference in the fully nested example. Splitting 100,000 rows into 1,000 groups roughly doubles runtime because each group adds work.
Benchmark details
What was compared
The headline cases contrast shallow and deep nesting, smaller and larger inputs, and the effects of sorting or splitting the input into many groups.
Exact values, sample ranges and counts · Source samples.
“Depth up to 7” is shallow nesting. “Fully nested” means each successive interval is inside another, producing a long chain. Row counts are totals across all groups. The columns compare integer, Date and microsecond Datetime endpoints.
Polars query time (ms) · medians
| Workload | Input rows | Integer | Date | Datetime |
|---|---|---|---|---|
| Depth up to 7, shuffled, 1 group | 100,000 | 5.12 | 4.5 | 5 |
| Depth up to 7, shuffled, 1 group | 3,000,000 | 203 | 170 | 200 |
| Fully nested, shuffled, 1 group | 3,000,000 | 206 | 167 | 206 |
| Fully nested, sorted, 1 group | 3,000,000 | 42.6 | — | — |
| Depth up to 7, shuffled, 1,000 groups | 100,000 | 10.9 | 11.5 | 12.1 |
— means no recorded measurement for that combination.
Exact values, sample ranges and counts · Source samples.
Sorting makes a large difference in the fully nested example. Splitting 100,000 rows into 1,000 groups increases runtime in the shallow example because each group adds processing overhead. Date columns were faster in these measurements, but the table does not establish that they will always be faster.
Settings
See the measurement guide and shared hardware.
The Polars run used four Polars threads, one warmup and five samples per case, with seed 731. The displayed times are medians. Settings, software versions and source hashes are recorded in the run metadata. The summary uses Int64 endpoints.
Small cases are checked by direct comparisons between intervals. Larger algorithm outputs are compared across implementations. Polars examples use datasets whose correct depths can be calculated independently.
Query times include planning, execution and retrieving the result. Creating the input data and converting its types are excluded. See the validation notes.
Limitations
Algorithm tests cover twenty patterns with 1,000 to three million rows. They include shallow and deep nesting, duplicates, shared endpoints, empty intervals and different input orders. Polars tests cover integer, Date and Datetime endpoints and up to 1,000 groups.
Algorithm-only and Polars datasets differ, so their times do not isolate Polars overhead. A native Polars comparison has not been measured. Whole-query memory was not measured. See the memory definitions.
Reproduce
$env:NESTING_SAMPLES = "5"
cargo bench -p intervals-core --bench nesting_depth --locked
$env:POLARS_MAX_THREADS = "4"
uv run --no-sync python benchmarks/nesting_depth.py --output target/nesting-polars.csv
The recorded collection run used an externally installed release wheel.
NESTING_SIZES and NESTING_SCENARIOS select algorithm tests.
Shared setup and publishing · Core samples · Collection samples · Repeat metadata · Recurrences, sorted-input investigation and historical evidence
History
Rust algorithm only · one thread · median of 5 samples · measurement settings
The package's frontier design tracks the ends of containment chains. The two Fenwick alternatives use tree-based counting structures. These comparisons include internal timing instrumentation and exclude Polars.
Algorithm time (ms) · medians
| Workload | Input rows | Package design (frontier) | Packed Fenwick | Indirect Fenwick |
|---|---|---|---|---|
| Fully nested, shuffled | 3,000,000 | 199 | 1,220 | 1,450 |
| Dense random | 3,000,000 | 250 | 376 | 731 |
| All identical | 3,000,000 | 36.1 | 48.2 | 32.5 |
Exact values, sample ranges and counts · Source samples.
The package's design has a large advantage on fully nested inputs. An alternative is slightly faster when every interval is identical. A separate direct run of the package's Rust function took 215 ms for three million fully nested rows. Its peak requested heap allocation was 91.6 MiB on shallow input and 124 MiB on a full chain. Deep nesting requires more working storage.
The runner now times only direct calls to the package's Rust function, without internal timing instrumentation. The original comparison and the repeat selected different candidate methods, recorded in their measurement settings. See the provenance guidance for the archived suite.