use crate::format::VectorId;
mod simd;
#[cfg(all(target_arch = "x86_64", any(test, feature = "bench")))]
pub(crate) mod hamming_x86_64_bench {
#[inline(always)]
pub unsafe fn hamming_popcnt(a: &[u64], b: &[u64]) -> u32 {
unsafe { super::simd::x86_64::hamming_popcnt(a, b) }
}
#[inline(always)]
pub unsafe fn hamming_shuffle(a: &[u64], b: &[u64]) -> u32 {
unsafe { super::simd::x86_64::hamming_shuffle(a, b) }
}
}
pub(crate) fn pack_query_sketch(rot: &[f32]) -> Vec<u64> {
let mut o = vec![0u64; rot.len().div_ceil(64)];
for (i, &x) in rot.iter().enumerate() {
if x >= 0.0 {
o[i >> 6] |= 1u64 << (i & 63);
}
}
o
}
#[inline(always)]
pub(crate) fn hamming_scalar(a: &[u64], b: &[u64]) -> u32 {
let mut h = 0u32;
for w in 0..a.len() {
h += (a[w] ^ b[w]).count_ones();
}
h
}
#[inline]
pub(crate) fn hamming(a: &[u64], b: &[u64]) -> u32 {
#[cfg(target_arch = "aarch64")]
unsafe {
return simd::aarch64::hamming(a, b);
}
#[allow(unreachable_code)]
hamming_scalar(a, b)
}
#[allow(clippy::too_many_arguments)]
pub(crate) fn scan_candidates(
sketches: &[u64],
words: usize,
rows: &[(u32, usize)],
q_sketch: &[u64],
ck: usize,
dim: usize,
parallel: bool,
hbuf: &mut Vec<u16>,
) -> Vec<(VectorId, i32)> {
#[cfg(all(
target_arch = "x86_64",
target_feature = "avx2",
target_feature = "popcnt"
))]
return unsafe {
scan_candidates_avx2(sketches, words, rows, q_sketch, ck, dim, parallel, hbuf)
};
#[cfg(all(
target_arch = "x86_64",
not(all(target_feature = "avx2", target_feature = "popcnt"))
))]
{
if std::is_x86_feature_detected!("avx2") && std::is_x86_feature_detected!("popcnt") {
return unsafe {
scan_candidates_avx2(sketches, words, rows, q_sketch, ck, dim, parallel, hbuf)
};
}
}
#[allow(unreachable_code)]
scan_candidates_scalar(sketches, words, rows, q_sketch, ck, dim, parallel, hbuf)
}
#[cfg(target_arch = "x86_64")]
const HAMMING_POPCNT_WORDS_THRESHOLD: usize = 20;
#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "avx2,popcnt")]
#[allow(clippy::too_many_arguments)]
unsafe fn scan_candidates_avx2(
sketches: &[u64],
words: usize,
rows: &[(u32, usize)],
q_sketch: &[u64],
ck: usize,
dim: usize,
parallel: bool,
hbuf: &mut Vec<u16>,
) -> Vec<(VectorId, i32)> {
if words < HAMMING_POPCNT_WORDS_THRESHOLD {
unsafe {
scan_candidates_avx2_inner::<true>(
sketches, words, rows, q_sketch, ck, dim, parallel, hbuf,
)
}
} else {
unsafe {
scan_candidates_avx2_inner::<false>(
sketches, words, rows, q_sketch, ck, dim, parallel, hbuf,
)
}
}
}
#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "avx2,popcnt")]
#[allow(clippy::too_many_arguments)]
unsafe fn scan_candidates_avx2_inner<const USE_SHUFFLE: bool>(
sketches: &[u64],
words: usize,
rows: &[(u32, usize)],
q_sketch: &[u64],
ck: usize,
dim: usize,
parallel: bool,
hbuf: &mut Vec<u16>,
) -> Vec<(VectorId, i32)> {
use rayon::prelude::*;
#[inline]
#[target_feature(enable = "avx2,popcnt")]
unsafe fn ham_inner<const SHUFFLE: bool>(q: &[u64], v: &[u64]) -> u32 {
if SHUFFLE {
unsafe { simd::x86_64::hamming_shuffle(q, v) }
} else {
unsafe { simd::x86_64::hamming_popcnt(q, v) }
}
}
let n = rows.len();
if n == 0 {
return Vec::new();
}
hbuf.clear();
hbuf.resize(n, 0);
let hist: Vec<u32> = if parallel {
hbuf.par_chunks_mut(4096)
.enumerate()
.map(|(c, chunk)| {
let base = c * 4096;
let mut local = vec![0u32; dim + 2];
for (j, slot) in chunk.iter_mut().enumerate() {
let i = base + j;
let h = unsafe {
ham_inner::<USE_SHUFFLE>(q_sketch, &sketches[i * words..(i + 1) * words])
};
*slot = h as u16;
local[h as usize] += 1;
}
local
})
.reduce(
|| vec![0u32; dim + 2],
|mut a, b| {
for d in 0..a.len() {
a[d] += b[d];
}
a
},
)
} else {
let mut hh = vec![0u32; dim + 2];
for (i, slot) in hbuf.iter_mut().enumerate() {
let h = unsafe {
ham_inner::<USE_SHUFFLE>(q_sketch, &sketches[i * words..(i + 1) * words])
};
*slot = h as u16;
hh[h as usize] += 1;
}
hh
};
let mut acc = 0u32;
let mut thr = dim + 1;
for (d, &c) in hist.iter().enumerate() {
if acc + c >= ck as u32 {
thr = d;
break;
}
acc += c;
}
let mut rem = (ck as u32).saturating_sub(acc);
let mut out: Vec<(VectorId, i32)> = Vec::with_capacity(ck + 64);
for (i, &h) in hbuf.iter().enumerate() {
let h = h as usize;
let take = if h < thr {
true
} else if h == thr && rem > 0 {
rem -= 1;
true
} else {
false
};
if take {
out.push((VectorId(rows[i].0 as u64), h as i32));
}
}
out
}
#[allow(clippy::too_many_arguments)]
fn scan_candidates_scalar(
sketches: &[u64],
words: usize,
rows: &[(u32, usize)],
q_sketch: &[u64],
ck: usize,
dim: usize,
parallel: bool,
hbuf: &mut Vec<u16>,
) -> Vec<(VectorId, i32)> {
use rayon::prelude::*;
let n = rows.len();
if n == 0 {
return Vec::new();
}
hbuf.clear();
hbuf.resize(n, 0);
let hist: Vec<u32> = if parallel {
hbuf.par_chunks_mut(4096)
.enumerate()
.map(|(c, chunk)| {
let base = c * 4096;
let mut local = vec![0u32; dim + 2];
for (j, slot) in chunk.iter_mut().enumerate() {
let i = base + j;
let h = hamming(q_sketch, &sketches[i * words..(i + 1) * words]);
*slot = h as u16;
local[h as usize] += 1;
}
local
})
.reduce(
|| vec![0u32; dim + 2],
|mut a, b| {
for d in 0..a.len() {
a[d] += b[d];
}
a
},
)
} else {
let mut hh = vec![0u32; dim + 2];
for (i, slot) in hbuf.iter_mut().enumerate() {
let h = hamming(q_sketch, &sketches[i * words..(i + 1) * words]);
*slot = h as u16;
hh[h as usize] += 1;
}
hh
};
let mut acc = 0u32;
let mut thr = dim + 1;
for (d, &c) in hist.iter().enumerate() {
if acc + c >= ck as u32 {
thr = d;
break;
}
acc += c;
}
let mut rem = (ck as u32).saturating_sub(acc);
let mut out: Vec<(VectorId, i32)> = Vec::with_capacity(ck + 64);
for (i, &h) in hbuf.iter().enumerate() {
let h = h as usize;
let take = if h < thr {
true
} else if h == thr && rem > 0 {
rem -= 1;
true
} else {
false
};
if take {
out.push((VectorId(rows[i].0 as u64), h as i32));
}
}
out
}