Lane balancing benchmarks¶
All benchmarks · Measurement rules
Summary¶
assign_balanced_lanes places
intervals in the fewest possible lanes without overlaps within a lane, then
tries to distribute their row counts evenly. With Polars restricted to one
thread, complete queries on three synthetic 100,000-row inputs took under
25 ms. In a separate suite,
it improved balance in 108 of 132 datasets. It never worsens its starting
balance but does not guarantee the best balance. Polars has no built-in solver
for this optimization problem.
Results¶
Full Polars query time · milliseconds
| Workload | Rows | Ordinary assignment (ms) | Balanced assignment (ms) |
|---|---|---|---|
| 9 empty intervals among 2 overlapping ones | 11 | 0.0887 | 0.1 |
| Separate intervals followed by 8 overlapping ones | 100,000 | 0.911 | 3.76 |
| One long interval overlapping short ones | 100,000 | 1.16 | 9.41 |
| 50,000 long intervals overlapping short ones | 100,000 | 1.39 | 24.1 |
On the eight-lane input, balancing reduced the gap between the fullest and emptiest lanes from 99,992 rows to zero, giving 12,500 rows in each lane. The two long-interval examples stay uneven because their overlaps force it, so the extra search time brings no improvement.
Ordinary assignment minimizes the number of lanes without trying to balance their row counts. It is a cost baseline for a different objective.
Benchmark details
What was compared
Exact values, sample ranges and counts · Source samples.
The compact table selects a small input with empty intervals, an input that can balance evenly across eight lanes, and two long/short-interval inputs whose overlaps force uneven lane sizes.
Ordinary assignment uses assign_lanes. New balanced assignment uses
assign_balanced_lanes with its default settings. Improving existing lanes uses
the same function with initial_lanes supplied. Its times exclude creating the
original assignment.
Polars query time (ms) · medians
| Workload | Input rows | Ordinary assignment | Improve existing lanes | New balanced assignment |
|---|---|---|---|---|
| 9 empty intervals among 2 overlapping ones | 11 | 0.0887 | 0.105 | 0.1 |
| Separate intervals followed by 8 overlapping ones | 100,000 | 0.911 | 3.17 | 3.76 |
| One long interval overlapping short ones | 100,000 | 1.16 | 3.4 | 9.41 |
| 50,000 long intervals overlapping short ones | 100,000 | 1.39 | 6.09 | 24.1 |
Exact values, sample ranges and counts · Source samples.
In the eight-lane example, ordinary assignment put 99,993 rows in one lane and one row in each of the others. New balanced assignment produced 12,500 rows in every lane, taking 3.76 ms instead of 0.91 ms. Improving the existing assignment did not achieve that improvement with the default search limit.
The table below shows the difference between the largest and smallest lane's row counts on the same inputs. Smaller is better, and zero means equal counts.
| Input | Ordinary assignment | Improve existing lanes | New balanced assignment |
|---|---|---|---|
| 11 rows, including 9 empty intervals | 9 | 1 | 1 |
| 100,000 rows needing 8 lanes | 99,992 | 99,992 | 0 |
| One long interval overlapping 99,999 short ones | 99,998 | 99,998 | 99,998 |
| 50,000 long intervals overlapping 50,000 short ones | 49,999 | 49,999 | 49,999 |
The last two examples show the cost of searching without improving balance. Their overlaps force uneven lane sizes when using the minimum number of lanes. In the last example, balanced assignment takes 24.1 ms compared with 1.39 ms. The saved quality results include the lane counts behind these comparisons.
Settings
See the measurement guide and shared hardware.
Complete Polars queries · one thread · median of 5 samples after warmup · measurement settings
Query times include planning, validation, preparation, extraction and output materialization. Input generation, correctness checks and final Series destruction are outside timing. Temporary collection-container teardown can occur inside timing. Construction includes its initial assignment; improving existing lanes excludes creating that assignment. Every timed result is checked for overlaps within lanes and for the minimum lane count.
The default max_work=100_000 limits search effort, not elapsed milliseconds.
Input checks and preparation still take time outside that search limit.
Limitations
Balance measures numbers of rows, including empty intervals. It does not measure the total duration of intervals in each lane.
Of the 132 datasets in the separate size-scaling suite, 24 were constructed with a known best balance. New balanced assignment reached it in all 24. Improving ordinary assignments reached it in 12. The best possible balance is unknown for the remaining 108 datasets, so improvement alone does not establish optimality.
Other tests cover small datasets whose assignments can be checked exhaustively, Date/Datetime endpoints, groups and streaming queries. A supplied three-lane example remains at counts 15, 16 and 17 even though 16 in every lane is possible. This demonstrates a real limit of the search. Million-row performance and other machines were not measured here.
Reproduce
Follow the release setup. Generate the existing corpora first, then run the complete commands in the supporting notes. A small offline run is:
python benchmarks/generate_interval_graphs.py synthetic --suite smoke --seed 42 --output target/balance-smoke
uv run --no-sync python benchmarks/balance_lanes.py --dataset target/balance-smoke --handcrafted --max-work 100000 --warmups 1 --repeats 5 --output benchmarks/results/balance-local-new
cargo bench -p intervals-core --bench balance_lanes --locked
Set POLARS_MAX_THREADS=1 before Python. Use fresh output prefixes and run
benchmarks one at a time after compilation. The runner saves the build version,
settings and dataset identifiers. The supporting notes list the settings needed
to reproduce the complete run.
Saved quality, scaling and execution-variant records link raw samples, provenance and source hashes. The verification log records executed checks. Generated datasets stay outside version control. Table downloads retain sample ranges and exact medians.
History
Rust algorithm only · median of 5 samples after two warmups · measurement settings
“Initial choices only” selects the best starting assignment without further search. The other columns correspond to the user-facing operations above. These inputs differ from the Polars examples.
Algorithm time (ms) · medians
| Workload | Input rows | Ordinary assignment | Initial choices only | Improve existing lanes | New balanced assignment |
|---|---|---|---|---|---|
| Mixed long and short intervals, sorted | 10,000 | 0.087 | 0.673 | 0.293 | 0.869 |
| Mixed long and short intervals, sorted | 100,000 | 0.609 | 7.7 | 2.59 | 9.36 |
| Includes empty intervals, shuffled | 100,000 | 3.62 | 9.46 | 8.01 | 9.56 |
| Long intervals spanning short ones, sorted | 1,000 | 0.0056 | 0.06 | 0.0242 | 0.0727 |
| All overlap, shuffled | 100,000 | 0.925 | 2.02 | 2.18 | 1.39 |
Exact values, sample ranges and counts · Source samples.
Across 60 algorithm test cases, increasing max_work from 10,000 to 100,000
improved balance in four cases. Increasing it to one million improved two more.
More search can help, but does not guarantee improvement.
The saved runs use older names for the same construction and improvement modes. The supporting notes retain their mapping, detailed quality checks and measurement boundaries.