#[cfg(target_arch = "x86_64")]
pub mod x86;
pub mod portable;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Backend {
Avx512,
Avx2,
Portable,
}
impl Backend {
#[must_use]
pub const fn lanes_64bit(self) -> usize {
match self {
Self::Avx512 => 8,
Self::Avx2 => 4,
Self::Portable => 1,
}
}
#[must_use]
pub const fn as_str(self) -> &'static str {
match self {
Self::Avx512 => "avx512",
Self::Avx2 => "avx2",
Self::Portable => "portable",
}
}
}
#[must_use]
pub fn detect_backend() -> Backend {
#[cfg(target_arch = "x86_64")]
{
if std::arch::is_x86_feature_detected!("avx512f") {
return Backend::Avx512;
}
if std::arch::is_x86_feature_detected!("avx2") {
return Backend::Avx2;
}
}
Backend::Portable
}
#[must_use]
pub fn scan_greater_than_i64(data: &[i64], target: i64) -> usize {
scan_greater_than_i64_with(data, target, detect_backend())
}
#[must_use]
pub fn scan_greater_than_i64_with(data: &[i64], target: i64, backend: Backend) -> usize {
match backend {
#[cfg(target_arch = "x86_64")]
Backend::Avx512 if std::arch::is_x86_feature_detected!("avx512f") => {
unsafe { x86::scan_gt_i64_avx512(data, target) }
}
#[cfg(target_arch = "x86_64")]
Backend::Avx2 if std::arch::is_x86_feature_detected!("avx2") => {
unsafe { x86::scan_gt_i64_avx2(data, target) }
}
_ => portable::scan_gt_i64(data, target),
}
}
#[cfg(test)]
mod tests {
use super::*;
fn oracle(data: &[i64], target: i64) -> usize {
data.iter().filter(|&&x| x > target).count()
}
fn all_backends() -> Vec<Backend> {
let mut v = vec![Backend::Portable];
#[cfg(target_arch = "x86_64")]
{
if std::arch::is_x86_feature_detected!("avx2") {
v.push(Backend::Avx2);
}
if std::arch::is_x86_feature_detected!("avx512f") {
v.push(Backend::Avx512);
}
}
v
}
#[test]
fn matches_oracle_across_all_lengths_and_backends() {
for backend in all_backends() {
for len in 0..=257_usize {
let data: Vec<i64> = (0..len).map(|i| (i % 50) as i64).collect();
let target = 24;
let expected = oracle(&data, target);
let got = scan_greater_than_i64_with(&data, target, backend);
assert_eq!(
got, expected,
"backend {backend:?} disagreed at len {len}: got {got}, want {expected}",
);
}
}
}
#[test]
fn all_match_and_no_match_boundaries() {
for backend in all_backends() {
for len in [0_usize, 1, 7, 8, 9, 63, 64, 65, 257] {
let data = vec![10_i64; len];
assert_eq!(
scan_greater_than_i64_with(&data, 9, backend),
len,
"backend {backend:?}: all elements should match at len {len}",
);
assert_eq!(
scan_greater_than_i64_with(&data, 10, backend),
0,
"backend {backend:?}: equal target must not match at len {len}",
);
assert_eq!(
scan_greater_than_i64_with(&data, 11, backend),
0,
"backend {backend:?}: larger target must not match at len {len}",
);
}
}
}
#[test]
fn handles_extremes_without_overflow() {
let data = [i64::MIN, -1, 0, 1, i64::MAX];
for backend in all_backends() {
for target in [i64::MIN, -1, 0, 1, i64::MAX] {
assert_eq!(
scan_greater_than_i64_with(&data, target, backend),
oracle(&data, target),
"backend {backend:?} disagreed for target {target}",
);
}
}
}
#[test]
fn backends_agree_with_each_other() {
let mut state: i64 = 0x2545_F491;
let data: Vec<i64> = (0..10_000)
.map(|_| {
state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1_442_695_040_888_963_407);
state.rem_euclid(1000)
})
.collect();
let reference = portable::scan_gt_i64(&data, 500);
for backend in all_backends() {
assert_eq!(
scan_greater_than_i64_with(&data, 500, backend),
reference,
"backend {backend:?} disagreed with the portable reference",
);
}
}
}