use std::cmp::Ordering;
use std::collections::HashMap;
use std::hash::{BuildHasherDefault, Hasher};
use crate::error::{VectorError, VectorResult};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Metric {
Cosine,
Dot,
Euclidean,
}
impl Metric {
fn score(&self, a: &[f32], na: f32, entry: &Entry) -> f32 {
let b = &entry.vector;
match self {
Metric::Cosine => {
let nb = entry.norm;
if na == 0.0 || nb == 0.0 {
0.0
} else {
dot(a, b) / (na * nb)
}
}
Metric::Dot => dot(a, b),
Metric::Euclidean => -l2(a, b),
}
}
fn norm_of(&self, v: &[f32]) -> f32 {
match self {
Metric::Cosine => norm(v),
Metric::Dot | Metric::Euclidean => 0.0,
}
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Match {
pub id: String,
pub score: f32,
}
struct Entry {
id: String,
vector: Vec<f32>,
norm: f32,
}
pub struct VectorIndex {
dim: usize,
metric: Metric,
entries: Vec<Entry>,
positions: HashMap<String, usize, BuildHasherDefault<IdHasher>>,
}
#[derive(Default)]
struct IdHasher(u64);
impl Hasher for IdHasher {
fn write(&mut self, bytes: &[u8]) {
let mut h = if self.0 == 0 { 0xcbf2_9ce4_8422_2325 } else { self.0 };
for &b in bytes {
h = (h ^ b as u64).wrapping_mul(0x0000_0100_0000_01b3);
}
self.0 = h;
}
fn finish(&self) -> u64 {
self.0
}
}
impl VectorIndex {
pub fn new(dim: usize, metric: Metric) -> Self {
Self {
dim,
metric,
entries: Vec::new(),
positions: HashMap::default(),
}
}
pub fn dim(&self) -> usize {
self.dim
}
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn insert(&mut self, id: impl Into<String>, vector: Vec<f32>) -> VectorResult<()> {
if vector.len() != self.dim {
return Err(VectorError::DimMismatch {
expected: self.dim,
got: vector.len(),
});
}
let id = id.into();
let norm = self.metric.norm_of(&vector);
if let Some(&at) = self.positions.get(&id) {
let existing = &mut self.entries[at];
existing.vector = vector;
existing.norm = norm;
} else {
self.positions.insert(id.clone(), self.entries.len());
self.entries.push(Entry { id, vector, norm });
}
Ok(())
}
pub fn remove(&mut self, id: &str) -> bool {
let Some(at) = self.positions.remove(id) else {
return false;
};
self.entries.remove(at);
for entry in &self.entries[at..] {
if let Some(p) = self.positions.get_mut(&entry.id) {
*p -= 1;
}
}
true
}
pub fn search(&self, query: &[f32], k: usize) -> VectorResult<Vec<Match>> {
if query.len() != self.dim {
return Err(VectorError::DimMismatch {
expected: self.dim,
got: query.len(),
});
}
let query_norm = self.metric.norm_of(query);
let mut scored: Vec<(f32, usize)> = self
.entries
.iter()
.enumerate()
.map(|(at, e)| (self.metric.score(query, query_norm, e), at))
.collect();
let rank = |a: &(f32, usize), b: &(f32, usize)| {
b.0.partial_cmp(&a.0)
.unwrap_or(Ordering::Equal)
.then_with(|| self.entries[a.1].id.cmp(&self.entries[b.1].id))
};
if k < scored.len() && !scored.iter().any(|(s, _)| s.is_nan()) {
if k > 0 {
scored.select_nth_unstable_by(k - 1, rank);
}
scored.truncate(k);
}
scored.sort_by(rank);
scored.truncate(k);
Ok(scored
.into_iter()
.map(|(score, at)| Match {
id: self.entries[at].id.clone(),
score,
})
.collect())
}
}
const LANES: usize = 8;
#[inline]
fn fold(acc: [f32; LANES], tail: f32) -> f32 {
((acc[0] + acc[4]) + (acc[2] + acc[6])) + ((acc[1] + acc[5]) + (acc[3] + acc[7])) + tail
}
fn dot(a: &[f32], b: &[f32]) -> f32 {
let mut acc = [0f32; LANES];
let (ca, ra) = a.as_chunks::<LANES>();
let (cb, rb) = b.as_chunks::<LANES>();
for (x, y) in ca.iter().zip(cb) {
for l in 0..LANES {
acc[l] += x[l] * y[l];
}
}
let tail = ra.iter().zip(rb).fold(0f32, |s, (x, y)| s + x * y);
fold(acc, tail)
}
#[cfg(test)]
fn dot_serial(a: &[f32], b: &[f32]) -> f32 {
a.iter().zip(b).map(|(x, y)| x * y).sum()
}
fn norm(a: &[f32]) -> f32 {
dot(a, a).sqrt()
}
fn l2(a: &[f32], b: &[f32]) -> f32 {
let mut acc = [0f32; LANES];
let (ca, ra) = a.as_chunks::<LANES>();
let (cb, rb) = b.as_chunks::<LANES>();
for (x, y) in ca.iter().zip(cb) {
for l in 0..LANES {
let d = x[l] - y[l];
acc[l] += d * d;
}
}
let tail = ra.iter().zip(rb).fold(0f32, |s, (x, y)| {
let d = x - y;
s + d * d
});
fold(acc, tail).sqrt()
}
#[cfg(test)]
mod accumulator_tests {
use super::*;
fn vectors(n: usize, dim: usize, seed: u64) -> Vec<Vec<f32>> {
let mut s = seed | 1;
let mut next = move || {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
((s >> 40) as f32 / (1u64 << 24) as f32) - 0.5
};
(0..n).map(|_| (0..dim).map(|_| next()).collect()).collect()
}
#[test]
fn dot_matches_serial_within_tolerance_at_every_tail() {
for dim in [1, 7, 8, 9, 15, 16, 64, 65, 100] {
let vs = vectors(2, dim, dim as u64);
let (a, b) = (&vs[0], &vs[1]);
let fast = dot(a, b);
let slow = dot_serial(a, b);
let scale = slow.abs().max(1e-3);
assert!((fast - slow).abs() / scale < 1e-4, "dim {dim}: {fast} vs {slow}");
}
}
#[test]
fn top_k_sets_agree_with_serial_scoring() {
let dim = 64;
let corpus = vectors(500, dim, 3);
let queries = vectors(5, dim, 11);
for metric in [Metric::Cosine, Metric::Dot, Metric::Euclidean] {
let mut index = VectorIndex::new(dim, metric);
for (i, v) in corpus.iter().enumerate() {
index.insert(format!("v{i}"), v.clone()).unwrap();
}
for q in &queries {
let fast: Vec<String> = index.search(q, 10).unwrap().into_iter().map(|m| m.id).collect();
let mut slow: Vec<(f32, usize)> = corpus
.iter()
.enumerate()
.map(|(i, v)| {
let s = match metric {
Metric::Cosine => {
dot_serial(q, v) / (dot_serial(q, q).sqrt() * dot_serial(v, v).sqrt())
}
Metric::Dot => dot_serial(q, v),
Metric::Euclidean => -q
.iter()
.zip(v)
.map(|(x, y)| (x - y) * (x - y))
.sum::<f32>()
.sqrt(),
};
(s, i)
})
.collect();
slow.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
let slow: Vec<String> = slow.iter().take(10).map(|(_, i)| format!("v{i}")).collect();
let mut fs = fast.clone();
let mut ss = slow.clone();
fs.sort();
ss.sort();
assert_eq!(fs, ss, "{metric:?}");
}
}
}
}