Crate partition_point_veb_layout

vEB(van Emde Boas) layout partition_point (cache oblivious)

use partition_point_veb_layout::*;
let v = vec![0, 0, 1, 2, 2, 4, 6];
let lb = v.partition_point(|x| x < &2);
let w = veb_layout(&v);
let vlb = veb_partition_point(&w, |x| x < &2);
assert_eq!(lb, veb_index_rev(vlb, v.len()));

On larger than LLC(Last Level Cache), veb_partition_point is faster than slice’s partition_point.

But, get &v[lower_bound..upper_bound] is not fast. It takes O((upper_bound-lower_bound)*log(v.len())).

CPU: Ryzen7 2700X MEM: DDR4 2666MHz 2ch 64GB RUSTC: rustc 1.60.0-beta.3

Modules

binary

Functions

par_veb_layout

get vEB layout vector (parallel version)

veb_index

convert normal index to vEB index

veb_index_rev

convert vEB index to normal index

veb_layout

get vEB layout vector

veb_partition_point

like partition_point