int-interval-set 0.3.4

Integer half-open interval set structures built on top of int-interval.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

use criterion::{BenchmarkId, Criterion, Throughput, black_box, criterion_group, criterion_main};
use int_interval::I32CO;
use int_interval_set::I32COSet;
use range_collections::RangeSet2;
use range_set_blaze::RangeSetBlaze;

type Bounds = (i32, i32);

const N: usize = 64;
const STRIDE: i32 = 8;

/// Produces the left-hand set: `[0, 4), [8, 12), ...`, 64 intervals total.
fn lhs_bounds() -> Vec<Bounds> {
    (0..N)
        .map(|i| {
            let start = i as i32 * STRIDE;
            (start, start + 4)
        })
        .collect()
}

/// Produces a right-hand set fully disjoint from the left-hand set.
fn disjoint_rhs() -> Vec<Bounds> {
    (0..N)
        .map(|i| {
            let start = i as i32 * STRIDE + 4;
            (start, start + 4)
        })
        .collect()
}

/// Produces a right-hand set equal to the left-hand set.
fn equal_rhs() -> Vec<Bounds> {
    lhs_bounds()
}

/// Produces intervals that overlap half of each left-hand interval.
fn partial_overlap_rhs() -> Vec<Bounds> {
    (0..N)
        .map(|i| {
            let start = i as i32 * STRIDE + 2;
            (start, start + 4)
        })
        .collect()
}

/// Produces intervals that cover only even-indexed left-hand intervals.
fn alternating_rhs() -> Vec<Bounds> {
    (0..N)
        .step_by(2)
        .map(|i| {
            let start = i as i32 * STRIDE;
            (start, start + 4)
        })
        .collect()
}

/// Produces one broad interval covering the middle portion of the left-hand set.
fn broad_middle_rhs() -> Vec<Bounds> {
    vec![(16 * STRIDE, 48 * STRIDE)]
}

#[inline]
fn build_int_interval_set(bounds: &[Bounds]) -> I32COSet {
    bounds
        .iter()
        .map(|&(start, end_excl)| I32CO::try_new(start, end_excl).unwrap())
        .collect()
}

#[inline]
fn build_range_set_blaze(bounds: &[Bounds]) -> RangeSetBlaze<i32> {
    bounds
        .iter()
        .map(|&(start, end_excl)| start..=(end_excl - 1))
        .collect()
}

#[inline]
fn build_range_collections(bounds: &[Bounds]) -> RangeSet2<i32> {
    let mut set = RangeSet2::empty();

    for &(start, end_excl) in bounds {
        set |= RangeSet2::from(start..end_excl);
    }

    set
}

fn bench_case(c: &mut Criterion, case: &str, lhs: &[Bounds], rhs: &[Bounds]) {
    let int_interval_lhs = build_int_interval_set(lhs);
    let int_interval_rhs = build_int_interval_set(rhs);

    let blaze_lhs = build_range_set_blaze(lhs);
    let blaze_rhs = build_range_set_blaze(rhs);

    let collections_lhs = build_range_collections(lhs);
    let collections_rhs = build_range_collections(rhs);

    let mut group = c.benchmark_group("intersection_with_set");
    group.throughput(Throughput::Elements((lhs.len() + rhs.len()) as u64));

    group.bench_function(BenchmarkId::new("int_interval_set", case), |b| {
        b.iter(|| black_box(&int_interval_lhs).intersection_with_set(black_box(&int_interval_rhs)))
    });

    group.bench_function(BenchmarkId::new("range_set_blaze", case), |b| {
        b.iter(|| black_box(&blaze_lhs) & black_box(&blaze_rhs))
    });

    group.bench_function(BenchmarkId::new("range_collections", case), |b| {
        b.iter(|| black_box(&collections_lhs) & black_box(&collections_rhs))
    });

    group.finish();
}

fn bench_intersection_with_set(c: &mut Criterion) {
    let lhs = lhs_bounds();

    bench_case(c, "disjoint_64x64", &lhs, &disjoint_rhs());
    bench_case(c, "equal_64x64", &lhs, &equal_rhs());
    bench_case(c, "partial_overlap_64x64", &lhs, &partial_overlap_rhs());
    bench_case(c, "alternating_64x32", &lhs, &alternating_rhs());
    bench_case(c, "broad_middle_64x1", &lhs, &broad_middle_rhs());
}

mod support;

criterion_group! {
    name = benches;
    config = support::config();
    targets = bench_intersection_with_set
}

criterion_main!(benches);