rust-lapper 2 is currently in beta. To try it, use 2.0.0-beta.1
explicitly; Cargo will not select it from a version = "2" requirement.
This was originally a Rust port of Brent Pedersen's
nim-lapper. find() and seek() return
lazy borrowed iterators in ascending start order, so normal iterator adaptors
work without collecting results first.
All stored intervals and query ranges use half-open [start, stop) semantics.
Lapper keeps its intervals sorted by start and builds a fixed 32-interval
block index that can skip regions proven not to overlap. Mixed blocks use NEON
on AArch64, runtime-detected AVX2 on x86-64, and an exact scalar fallback
elsewhere. The same algorithm handles both ordinary and pathological datasets
with long intervals that engulf many shorter intervals.
The count() method uses the
BITS algorithm
to count overlaps with two binary searches.
The block index and SIMD backends are private implementation details: there is
no mode flag, alternate query method, or architecture-specific API. Existing
call patterns for find(), seek(), count(), cov(), set_cov(),
merge_overlaps(), depth(), union_and_intersect(), union(), and
intersect() retain their range semantics and return types. count() remains
the independent BITS implementation; methods that use find() or seek()
internally automatically share the exact indexed query path.
| Target | Mixed-block backend | Selection |
|---|---|---|
| AArch64 | 128-bit NEON | Baseline for the architecture |
| x86-64 with AVX2 | 256-bit AVX2 | Runtime detected once per iterator |
| x86-64 without AVX2 | Scalar | Automatic fallback |
| Other architectures | Scalar | Automatic fallback |
NEON and AVX2 cover u8, i8, u16, i16, u32, i32, u64, i64,
usize, and isize. The same block algorithm uses exact scalar masks for
u128, i128, custom PrimInt types, and partial vector tails.
rust-lapper 2 supports Rust 1.59 and newer. Rust 1.59 is the first stable release that provides the AArch64 intrinsics used by the NEON query backend.
Query coordinates must be 'static so private dispatch code can use TypeId
before reinterpreting primitive integer slices for SIMD. This includes every
primitive integer and ordinary owned custom numeric type; it does not require a
Lapper value to live for the entire program. Non-primitive PrimInt types use
the scalar mask implementation. The bound is the API-breaking change that makes
this a major release.
Use insert() and merge_overlaps() for coordinate or structural changes so
the private query index is rebuilt. Directly changing Lapper::intervals
coordinates or length leaves derived metadata stale; changing payload values is
safe.
rust-lapper supports serialization with serde for Lapper and Interval objects:
[dependencies]
rust-lapper = { version = "2.0.0-beta.1", features = ["with_serde"] }See examples/serde.rs for a brief example.
The retained v2 release measurements, raw samples, compiler flags, and pinned competitor revisions live in lapper_bakeoff. On an AMD Ryzen 9 3950X with AVX2, the new implementation improved total time over rust-lapper 1.3.0 by 37.30%, 98.89%, and 34.64% on the three retained article cases. All implementations returned identical overlap counts.
Benchmark results are workload- and hardware-specific; use the linked harness and raw data when making comparisons.
use rust_lapper::{Interval, Lapper};
type Iv = Interval<usize, u32>;
fn main() {
// create some fake data
let data: Vec<Iv> = vec![
Iv {
start: 70,
stop: 120,
val: 0,
}, // a long interval
Iv {
start: 10,
stop: 15,
val: 0,
},
Iv {
start: 10,
stop: 15,
val: 0,
}, // exact overlap
Iv {
start: 12,
stop: 15,
val: 0,
}, // inner overlap
Iv {
start: 14,
stop: 16,
val: 0,
}, // overlap end
Iv {
start: 40,
stop: 45,
val: 0,
},
Iv {
start: 50,
stop: 55,
val: 0,
},
Iv {
start: 60,
stop: 65,
val: 0,
},
Iv {
start: 68,
stop: 71,
val: 0,
}, // overlap start
Iv {
start: 70,
stop: 75,
val: 0,
},
];
// make lapper structure
let mut lapper = Lapper::new(data);
// Find every interval that overlaps [11, 15).
// For queries in nondecreasing start order, seek() can reuse a caller-owned cursor.
assert_eq!(
lapper.find(11, 15).collect::<Vec<&Iv>>(),
vec![
&Iv {
start: 10,
stop: 15,
val: 0
},
&Iv {
start: 10,
stop: 15,
val: 0
}, // exact overlap
&Iv {
start: 12,
stop: 15,
val: 0
}, // inner overlap
&Iv {
start: 14,
stop: 16,
val: 0
}, // overlap end
]
);
assert_eq!(lapper.count(11, 15), 4);
// Merge overlapping regions to simplify queries that only depend on whether
// any interval overlaps.
lapper.merge_overlaps();
assert_eq!(
lapper.find(11, 15).collect::<Vec<&Iv>>(),
vec![&Iv {
start: 10,
stop: 16,
val: 0
},]
);
// Get the number of positions covered by the interval collection.
assert_eq!(lapper.cov(), 73);
// Get the union and intersection lengths of two interval collections.
let data = vec![
Iv {
start: 5,
stop: 15,
val: 0,
},
Iv {
start: 48,
stop: 80,
val: 0,
},
];
let (union, intersect) = lapper.union_and_intersect(&Lapper::new(data));
assert_eq!(union, 88);
assert_eq!(intersect, 27);
// Get the depth at each position covered by the lapper
for interval in lapper.depth().filter(|x| x.val > 2) {
println!(
"Depth at {} - {}: {}",
interval.start, interval.stop, interval.val
);
}
}2.0.0-beta.1: Begin the rust-lapper 2 beta with a portable SIMD block index, signed coordinates, Rust 1.59 as the MSRV, and theI: 'staticcoordinate bound.1.3.0: Add thesort_unstablefeature flag for allocation-sensitive sorting thanks to @jameslkingsley.1.1.0: Added insert functionality thanks to @zaporter1.0.0: Add serde support via thewith_serdefeature flag0.5.0: Make Interval start/stop generic0.4.3: Remove leftover print statement0.4.2: Bugfix in to update starts/stops vectors when overlaps merged0.4.0: Addition of the BITS count algorithm.