1use std::cmp::Ordering;
19use std::collections::HashMap;
20use std::hash::{BuildHasherDefault, Hasher};
21
22use crate::error::{VectorError, VectorResult};
23
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
27pub enum Metric {
28 Cosine,
30 Dot,
32 Euclidean,
34}
35
36impl Metric {
37 fn score(&self, a: &[f32], na: f32, entry: &Entry) -> f32 {
42 let b = &entry.vector;
43 match self {
44 Metric::Cosine => {
45 let nb = entry.norm;
46 if na == 0.0 || nb == 0.0 {
47 0.0
48 } else {
49 dot(a, b) / (na * nb)
50 }
51 }
52 Metric::Dot => dot(a, b),
53 Metric::Euclidean => -l2(a, b),
54 }
55 }
56
57 fn norm_of(&self, v: &[f32]) -> f32 {
59 match self {
60 Metric::Cosine => norm(v),
61 Metric::Dot | Metric::Euclidean => 0.0,
62 }
63 }
64}
65
66#[derive(Clone, Debug, PartialEq)]
69pub struct Match {
70 pub id: String,
71 pub score: f32,
72}
73
74struct Entry {
75 id: String,
76 vector: Vec<f32>,
77 norm: f32,
79}
80
81pub struct VectorIndex {
83 dim: usize,
84 metric: Metric,
85 entries: Vec<Entry>,
86 positions: HashMap<String, usize, BuildHasherDefault<IdHasher>>,
91}
92
93#[derive(Default)]
95struct IdHasher(u64);
96
97impl Hasher for IdHasher {
98 fn write(&mut self, bytes: &[u8]) {
99 let mut h = if self.0 == 0 { 0xcbf2_9ce4_8422_2325 } else { self.0 };
100 for &b in bytes {
101 h = (h ^ b as u64).wrapping_mul(0x0000_0100_0000_01b3);
102 }
103 self.0 = h;
104 }
105
106 fn finish(&self) -> u64 {
107 self.0
108 }
109}
110
111impl VectorIndex {
112 pub fn new(dim: usize, metric: Metric) -> Self {
114 Self {
115 dim,
116 metric,
117 entries: Vec::new(),
118 positions: HashMap::default(),
119 }
120 }
121
122 pub fn dim(&self) -> usize {
123 self.dim
124 }
125
126 pub fn len(&self) -> usize {
127 self.entries.len()
128 }
129
130 pub fn is_empty(&self) -> bool {
131 self.entries.is_empty()
132 }
133
134 pub fn insert(&mut self, id: impl Into<String>, vector: Vec<f32>) -> VectorResult<()> {
136 if vector.len() != self.dim {
137 return Err(VectorError::DimMismatch {
138 expected: self.dim,
139 got: vector.len(),
140 });
141 }
142 let id = id.into();
143 let norm = self.metric.norm_of(&vector);
144 if let Some(&at) = self.positions.get(&id) {
145 let existing = &mut self.entries[at];
146 existing.vector = vector;
147 existing.norm = norm;
148 } else {
149 self.positions.insert(id.clone(), self.entries.len());
150 self.entries.push(Entry { id, vector, norm });
151 }
152 Ok(())
153 }
154
155 pub fn remove(&mut self, id: &str) -> bool {
157 let Some(at) = self.positions.remove(id) else {
158 return false;
159 };
160 self.entries.remove(at);
162 for entry in &self.entries[at..] {
163 if let Some(p) = self.positions.get_mut(&entry.id) {
164 *p -= 1;
165 }
166 }
167 true
168 }
169
170 pub fn search(&self, query: &[f32], k: usize) -> VectorResult<Vec<Match>> {
174 if query.len() != self.dim {
175 return Err(VectorError::DimMismatch {
176 expected: self.dim,
177 got: query.len(),
178 });
179 }
180 let query_norm = self.metric.norm_of(query);
181 let mut scored: Vec<(f32, usize)> = self
183 .entries
184 .iter()
185 .enumerate()
186 .map(|(at, e)| (self.metric.score(query, query_norm, e), at))
187 .collect();
188 let rank = |a: &(f32, usize), b: &(f32, usize)| {
189 b.0.partial_cmp(&a.0)
190 .unwrap_or(Ordering::Equal)
191 .then_with(|| self.entries[a.1].id.cmp(&self.entries[b.1].id))
192 };
193 if k < scored.len() && !scored.iter().any(|(s, _)| s.is_nan()) {
197 if k > 0 {
198 scored.select_nth_unstable_by(k - 1, rank);
199 }
200 scored.truncate(k);
201 }
202 scored.sort_by(rank);
203 scored.truncate(k);
204 Ok(scored
205 .into_iter()
206 .map(|(score, at)| Match {
207 id: self.entries[at].id.clone(),
208 score,
209 })
210 .collect())
211 }
212}
213
214const LANES: usize = 8;
220
221#[inline]
223fn fold(acc: [f32; LANES], tail: f32) -> f32 {
224 ((acc[0] + acc[4]) + (acc[2] + acc[6])) + ((acc[1] + acc[5]) + (acc[3] + acc[7])) + tail
225}
226
227fn dot(a: &[f32], b: &[f32]) -> f32 {
228 let mut acc = [0f32; LANES];
229 let (ca, ra) = a.as_chunks::<LANES>();
230 let (cb, rb) = b.as_chunks::<LANES>();
231 for (x, y) in ca.iter().zip(cb) {
232 for l in 0..LANES {
233 acc[l] += x[l] * y[l];
234 }
235 }
236 let tail = ra.iter().zip(rb).fold(0f32, |s, (x, y)| s + x * y);
237 fold(acc, tail)
238}
239
240#[cfg(test)]
242fn dot_serial(a: &[f32], b: &[f32]) -> f32 {
243 a.iter().zip(b).map(|(x, y)| x * y).sum()
244}
245
246fn norm(a: &[f32]) -> f32 {
247 dot(a, a).sqrt()
248}
249
250fn l2(a: &[f32], b: &[f32]) -> f32 {
251 let mut acc = [0f32; LANES];
252 let (ca, ra) = a.as_chunks::<LANES>();
253 let (cb, rb) = b.as_chunks::<LANES>();
254 for (x, y) in ca.iter().zip(cb) {
255 for l in 0..LANES {
256 let d = x[l] - y[l];
257 acc[l] += d * d;
258 }
259 }
260 let tail = ra.iter().zip(rb).fold(0f32, |s, (x, y)| {
261 let d = x - y;
262 s + d * d
263 });
264 fold(acc, tail).sqrt()
265}
266
267#[cfg(test)]
268mod accumulator_tests {
269 use super::*;
270
271 fn vectors(n: usize, dim: usize, seed: u64) -> Vec<Vec<f32>> {
272 let mut s = seed | 1;
273 let mut next = move || {
274 s ^= s << 13;
275 s ^= s >> 7;
276 s ^= s << 17;
277 ((s >> 40) as f32 / (1u64 << 24) as f32) - 0.5
278 };
279 (0..n).map(|_| (0..dim).map(|_| next()).collect()).collect()
280 }
281
282 #[test]
283 fn dot_matches_serial_within_tolerance_at_every_tail() {
284 for dim in [1, 7, 8, 9, 15, 16, 64, 65, 100] {
285 let vs = vectors(2, dim, dim as u64);
286 let (a, b) = (&vs[0], &vs[1]);
287 let fast = dot(a, b);
288 let slow = dot_serial(a, b);
289 let scale = slow.abs().max(1e-3);
290 assert!((fast - slow).abs() / scale < 1e-4, "dim {dim}: {fast} vs {slow}");
291 }
292 }
293
294 #[test]
295 fn top_k_sets_agree_with_serial_scoring() {
296 let dim = 64;
299 let corpus = vectors(500, dim, 3);
300 let queries = vectors(5, dim, 11);
301 for metric in [Metric::Cosine, Metric::Dot, Metric::Euclidean] {
302 let mut index = VectorIndex::new(dim, metric);
303 for (i, v) in corpus.iter().enumerate() {
304 index.insert(format!("v{i}"), v.clone()).unwrap();
305 }
306 for q in &queries {
307 let fast: Vec<String> = index.search(q, 10).unwrap().into_iter().map(|m| m.id).collect();
308 let mut slow: Vec<(f32, usize)> = corpus
309 .iter()
310 .enumerate()
311 .map(|(i, v)| {
312 let s = match metric {
313 Metric::Cosine => {
314 dot_serial(q, v) / (dot_serial(q, q).sqrt() * dot_serial(v, v).sqrt())
315 }
316 Metric::Dot => dot_serial(q, v),
317 Metric::Euclidean => -q
318 .iter()
319 .zip(v)
320 .map(|(x, y)| (x - y) * (x - y))
321 .sum::<f32>()
322 .sqrt(),
323 };
324 (s, i)
325 })
326 .collect();
327 slow.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
328 let slow: Vec<String> = slow.iter().take(10).map(|(_, i)| format!("v{i}")).collect();
329 let mut fs = fast.clone();
330 let mut ss = slow.clone();
331 fs.sort();
332 ss.sort();
333 assert_eq!(fs, ss, "{metric:?}");
334 }
335 }
336 }
337}