Maximum-weight clique benchmarks¶
All benchmarks · Measurement rules
Summary¶
max_weight_clique selects the
highest-weight set of intervals that overlap one another. Without weights, it
selects the largest such set. With Polars restricted to one thread, complete
queries on one million intervals took under 150 ms. In the integer example,
at most eight intervals overlapped at once. The result is exact in both modes,
but overlap patterns and weights strongly affect runtime. Polars has no built-in
solver for this optimization problem.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | No weights (ms) | Positive weights (ms) |
|---|---|---|---|
| Up to 8 overlapping, shuffled integers | 1,000 | 0.0803 | 0.0972 |
| Up to 8 overlapping, shuffled integers | 100,000 | 3.87 | 7.45 |
| Up to 8 overlapping, shuffled integers | 1,000,000 | 43.1 | 140 |
| All overlap, shuffled dates | 1,000,000 | 2.06 | 10.6 |
| Up to 8 overlapping, shuffled UTC datetimes, streaming | 1,000,000 | 48.2 | 126 |
| 32 groups, shuffled integers, multiple chunks | 1,000 | 0.414 | 0.437 |
| 32 groups, shuffled integers, multiple chunks | 1,000,000 | 49.6 | 83.1 |
Supplying positive weights makes the million-row integer example about three times slower. When every interval overlaps every other one, the function can select all useful rows without sorting: the unweighted Date example takes 2.06 ms, a special case rather than a general million-row runtime.
Benchmark details
What was compared
Exact values, sample ranges and counts · Source samples.
The compact table keeps three sizes of the shuffled integer input and adds all-overlap Date, streaming Datetime and grouped integer cases, each with unweighted and positive-weight runs.
“No weights” uses the function's default. “All weights = 1” supplies a weight column explicitly, asking for the same objective. “Positive weights” assigns different positive values. “Positive and negative weights” also allows values that make intervals undesirable to select. Int64, Date and UTC Datetime describe the endpoint types. Grouped row counts are totals across groups.
Polars query time (ms) · medians
| Workload | Input rows | No weights | All weights = 1 | Positive weights | Positive and negative weights |
|---|---|---|---|---|---|
| Up to 8 overlapping, shuffled integers | 1,000 | 0.0803 | 0.0985 | 0.0972 | 0.0788 |
| Up to 8 overlapping, shuffled integers | 100,000 | 3.87 | 7.38 | 7.45 | 3.26 |
| Up to 8 overlapping, shuffled integers | 1,000,000 | 43.1 | 148 | 140 | 45.5 |
| All overlap, shuffled dates | 1,000,000 | 2.06 | 11 | 10.6 | 12.6 |
| Up to 8 overlapping, shuffled UTC datetimes, streaming | 1,000,000 | 48.2 | 129 | 126 | 48.6 |
| 32 groups, shuffled integers, multiple chunks | 1,000 | 0.414 | 0.409 | 0.437 | 0.433 |
| 32 groups, shuffled integers, multiple chunks | 1,000,000 | 49.6 | 82.9 | 83.1 | 44.7 |
Exact values, sample ranges and counts · Source samples.
Omitting weights is useful when every row is equally valuable. In the million-row integer example, supplying a column of ones increases runtime from 43.1 ms to 148 ms. Processing the unweighted data in 32 groups takes 49.6 ms.
Inputs where every interval overlaps every other interval are especially easy: the function can select all useful rows without sorting. The million-row Date example takes 2.06 ms without weights. It is a special case, not a general million-row runtime.
Settings
See the measurement guide and shared hardware.
Complete Polars queries · one Polars thread · median of 5 samples · measurement settings
Small tests compare against exhaustive subsets and direct interval comparisons. Large benchmark outputs are independently checked for mutual overlap and optimal total weight. Query times include validation, processing and creation of the selection mask. Building inputs and queries is excluded.
Limitations
Tests range from tiny inputs to one million rows. They cover different overlap patterns, weights, row orders, duplicates, empty intervals and extreme integer values. Polars tests also include dates, datetimes, groups and streaming input stored in multiple chunks. Only selected input patterns reach one million rows.
These synthetic inputs on one machine show the effect of overlap and weights, but do not predict every application. No Polars-only alternative is compared. The supporting notes retain the alternative algorithms, repeated runs and detailed validation.
Reproduce
Raw core samples, repeat samples, exploratory samples, and Polars samples remain separate. Each run has matching measurement settings and build details. Table downloads retain exact medians, sample ranges and counts. The supporting notes explain the independent correctness checks.
Follow release setup, then use new output filenames:
$env:CLIQUE_CSV = "$PWD/benchmarks/results/clique-core-new.csv"
cargo bench -p intervals-core --bench max_weight_clique --locked
$env:POLARS_MAX_THREADS = "1"
uv run --no-sync python benchmarks/max_weight_clique.py --output benchmarks/results/clique-polars-new
CLIQUE_SIZES, CLIQUE_CASES, CLIQUE_SEEDS, CLIQUE_DTYPES,
CLIQUE_WEIGHT_DTYPES, CLIQUE_SAMPLES, and
CLIQUE_WARMUPS select focused core runs. Run metadata records the settings
actually used. Regenerate tables with the reporting commands.
History
Rust algorithm only · one thread · median of 5 samples · measurement settings
The alternatives scan endpoints or keep track of active intervals in a heap. “128-bit weights” matches the wide integer representation used inside the function. “64-bit weights” is a narrower option for direct Rust callers.
Algorithm time (ms) · medians
| Workload | Input rows | Package algorithm | Endpoint scan | Packed endpoint lists | Active-interval heap |
|---|---|---|---|---|---|
| Up to 64 overlapping, shuffled, no weights | 100,000 | 3.16 | 6.52 | 3.39 | 5.74 |
| Up to 64 overlapping, shuffled, no weights | 1,000,000 | 40.6 | 75.5 | 42.1 | 119 |
| Up to 2 overlapping, shuffled, 128-bit weights | 100,000 | 6.56 | 7.12 | 7.91 | 4.58 |
| Up to 2 overlapping, shuffled, 128-bit weights | 1,000,000 | 116 | 112 | 99.3 | 122 |
| Repeated endpoints, shuffled, 128-bit weights | 1,000,000 | 49.3 | 53.3 | 47.5 | 130 |
| All overlap, shuffled, 128-bit weights | 1,000,000 | 6.04 | 125 | 97 | 103 |
| Non-overlapping, shuffled, 64-bit weights | 100,000 | 6.67 | 7.23 | 5.34 | 4.43 |
Exact values, sample ranges and counts · Source samples.
The package wins strongly when all intervals overlap. Other methods can be faster when few weighted intervals overlap: at one million such rows, packed endpoint lists take 99.3 ms compared with 116 ms, but request 64 MB of heap storage compared with 16 MB. Those allocations exclude caller inputs and the rest of the process. A separate repeat shows the same tradeoff.