1use rand::rngs::StdRng;
24use rand::seq::SliceRandom;
25use rand::{Rng, SeedableRng};
26use serde::{Deserialize, Serialize};
27
28use crate::error::{MnemoError, Result};
29
30const VACANT: u32 = u32::MAX;
33
34pub(crate) fn slot_home(k: u128, cap: usize) -> usize {
40 let x = (k as u64) ^ ((k >> 64) as u64).rotate_left(29);
41 let h = x.wrapping_mul(0x9E37_79B9_7F4A_7C15);
42 ((h as u128 * cap as u128) >> 64) as usize
43}
44
45pub(crate) fn next_slot(i: usize, cap: usize) -> usize {
47 if i + 1 == cap {
48 0
49 } else {
50 i + 1
51 }
52}
53
54fn cyclic_dist(from: usize, to: usize, cap: usize) -> usize {
56 if to >= from {
57 to - from
58 } else {
59 to + cap - from
60 }
61}
62
63pub(crate) fn table_capacity_for(n: usize) -> usize {
65 (n * 4 / 3 + 1).max(16)
66}
67
68#[derive(Clone, Debug, Default)]
74pub(crate) struct U128Map {
75 keys: Vec<u128>,
76 vals: Vec<u32>,
77 len: usize,
78}
79
80impl U128Map {
81 pub(crate) fn with_capacity(n: usize) -> Self {
82 let mut m = Self::default();
83 m.resize(table_capacity_for(n));
84 m
85 }
86
87 fn resize(&mut self, cap: usize) {
88 let keys = std::mem::replace(&mut self.keys, vec![0; cap]);
89 let vals = std::mem::replace(&mut self.vals, vec![VACANT; cap]);
90 self.len = 0;
91 for (k, v) in keys.into_iter().zip(vals) {
92 if v != VACANT {
93 self.insert(k, v);
94 }
95 }
96 }
97
98 fn find(&self, k: u128) -> Option<usize> {
99 if self.vals.is_empty() {
100 return None;
101 }
102 let cap = self.vals.len();
103 let mut i = slot_home(k, cap);
104 loop {
105 if self.vals[i] == VACANT {
106 return None;
107 }
108 if self.keys[i] == k {
109 return Some(i);
110 }
111 i = next_slot(i, cap);
112 }
113 }
114
115 #[cfg(test)]
116 pub(crate) fn get(&self, k: u128) -> Option<u32> {
117 self.find(k).map(|i| self.vals[i])
118 }
119
120 pub(crate) fn contains_key(&self, k: u128) -> bool {
121 self.find(k).is_some()
122 }
123
124 pub(crate) fn insert(&mut self, k: u128, v: u32) {
125 debug_assert_ne!(v, VACANT);
126 if (self.len + 1) * 4 > self.vals.len() * 3 {
127 let cap = (self.vals.len() * 2).max(table_capacity_for(self.len + 1));
128 self.resize(cap);
129 }
130 let cap = self.vals.len();
131 let mut i = slot_home(k, cap);
132 loop {
133 if self.vals[i] == VACANT {
134 self.keys[i] = k;
135 self.vals[i] = v;
136 self.len += 1;
137 return;
138 }
139 if self.keys[i] == k {
140 self.vals[i] = v;
141 return;
142 }
143 i = next_slot(i, cap);
144 }
145 }
146
147 pub(crate) fn remove(&mut self, k: u128) -> Option<u32> {
148 let i = self.find(k)?;
149 let out = self.vals[i];
150 let cap = self.vals.len();
151 let mut hole = i;
154 let mut j = i;
155 loop {
156 j = next_slot(j, cap);
157 if self.vals[j] == VACANT {
158 break;
159 }
160 let home = slot_home(self.keys[j], cap);
161 let from_home = cyclic_dist(home, j, cap);
162 let from_hole = cyclic_dist(hole, j, cap);
163 if from_home >= from_hole {
164 self.keys[hole] = self.keys[j];
165 self.vals[hole] = self.vals[j];
166 hole = j;
167 }
168 }
169 self.vals[hole] = VACANT;
170 self.len -= 1;
171 Some(out)
172 }
173
174 #[cfg(test)]
175 pub(crate) fn len(&self) -> usize {
176 self.len
177 }
178
179 #[cfg(feature = "dev-hooks")]
181 pub(crate) fn heap_bytes(&self) -> usize {
182 self.keys.capacity() * std::mem::size_of::<u128>()
183 + self.vals.capacity() * std::mem::size_of::<u32>()
184 }
185}
186
187#[cfg(feature = "dev-hooks")]
192pub(crate) fn hash_map_bytes<K, V>(capacity: usize) -> usize {
193 if capacity == 0 {
194 return 0;
195 }
196 let buckets = (capacity * 8 / 7).next_power_of_two();
197 buckets * (std::mem::size_of::<(K, V)>() + 1)
198}
199
200const DEFAULT_SEED: u64 = 0x4d_4e_45_4d_4f_49_44_58; const TRAIN_CAP: usize = 50_000;
204const PQ_CODEWORDS: usize = 256;
206
207#[derive(Clone, Copy, Debug)]
209pub struct IndexConfig {
210 pub n_partitions: usize,
212 pub pq_subspaces: usize,
216 pub n_probe: usize,
220 pub n_rerank: usize,
223 pub kmeans_iters: usize,
225 pub seed: u64,
227}
228
229pub(crate) fn effective_auto_n_probe(partitions: usize) -> usize {
246 let half = partitions.div_ceil(2);
247 let full_up_to_100 = partitions.min(100);
248 half.max(full_up_to_100).max(1)
249}
250
251pub(crate) fn effective_auto_n_rerank(n_vectors: usize) -> usize {
266 (n_vectors / 200).clamp(100, 1000)
267}
268
269impl Default for IndexConfig {
270 fn default() -> Self {
271 Self {
301 n_partitions: 0,
302 pq_subspaces: 0,
303 n_probe: 0,
304 n_rerank: 0,
305 kmeans_iters: 25,
306 seed: DEFAULT_SEED,
307 }
308 }
309}
310
311#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
318pub struct IndexInfo {
319 pub vectors: usize,
321 pub partitions: usize,
323 pub subspaces: usize,
325 pub n_probe: usize,
327 pub n_rerank: usize,
329}
330
331fn squared_l2(a: &[f32], b: &[f32]) -> f32 {
333 let mut s = 0.0f32;
334 for i in 0..a.len() {
335 let d = a[i] - b[i];
336 s += d * d;
337 }
338 s
339}
340
341fn nearest(centroids: &[f32], stride: usize, v: &[f32]) -> usize {
343 let mut best = 0usize;
344 let mut best_d = f32::INFINITY;
345 let count = centroids.len() / stride;
346 for i in 0..count {
347 let d = squared_l2(¢roids[i * stride..(i + 1) * stride], v);
348 if d < best_d {
349 best_d = d;
350 best = i;
351 }
352 }
353 best
354}
355
356fn kmeans(points: &[&[f32]], k: usize, iters: usize, rng: &mut StdRng) -> Vec<f32> {
359 let n = points.len();
360 let dim = points[0].len();
361 let k = k.clamp(1, n);
362
363 let mut centroids: Vec<f32> = Vec::with_capacity(k * dim);
365 let first = rng.gen_range(0..n);
366 centroids.extend_from_slice(points[first]);
367 let mut d2: Vec<f32> = points
368 .iter()
369 .map(|p| squared_l2(p, ¢roids[0..dim]))
370 .collect();
371
372 while centroids.len() / dim < k {
373 let sum: f32 = d2.iter().sum();
374 let pick = if sum <= 0.0 {
375 rng.gen_range(0..n)
376 } else {
377 let mut t = rng.gen::<f32>() * sum;
378 let mut chosen = n - 1;
379 for (i, &w) in d2.iter().enumerate() {
380 t -= w;
381 if t <= 0.0 {
382 chosen = i;
383 break;
384 }
385 }
386 chosen
387 };
388 let base = centroids.len();
389 centroids.extend_from_slice(points[pick]);
390 let new = ¢roids[base..base + dim];
391 for (i, p) in points.iter().enumerate() {
392 let nd = squared_l2(p, new);
393 if nd < d2[i] {
394 d2[i] = nd;
395 }
396 }
397 }
398
399 let kk = centroids.len() / dim;
401 for _ in 0..iters {
402 let mut sums = vec![0.0f32; kk * dim];
403 let mut counts = vec![0usize; kk];
404 for p in points {
405 let a = nearest(¢roids, dim, p);
406 counts[a] += 1;
407 for d in 0..dim {
408 sums[a * dim + d] += p[d];
409 }
410 }
411 for c in 0..kk {
412 if counts[c] == 0 {
413 let r = rng.gen_range(0..n);
415 centroids[c * dim..(c + 1) * dim].copy_from_slice(points[r]);
416 } else {
417 let inv = 1.0 / counts[c] as f32;
418 for d in 0..dim {
419 centroids[c * dim + d] = sums[c * dim + d] * inv;
420 }
421 }
422 }
423 }
424 centroids
425}
426
427#[derive(Serialize, Deserialize, Clone, Debug)]
429struct PqCodebook {
430 sub_offsets: Vec<usize>,
432 centroids: Vec<Vec<f32>>,
434 ks: Vec<usize>,
436}
437
438impl PqCodebook {
439 fn m(&self) -> usize {
440 self.sub_offsets.len() - 1
441 }
442
443 fn train(
445 sub_offsets: &[usize],
446 train: &[&[f32]],
447 iters: usize,
448 rng: &mut StdRng,
449 ) -> PqCodebook {
450 let m = sub_offsets.len() - 1;
451 let mut centroids = Vec::with_capacity(m);
452 let mut ks = Vec::with_capacity(m);
453 for s in 0..m {
454 let (lo, hi) = (sub_offsets[s], sub_offsets[s + 1]);
455 let subs: Vec<Vec<f32>> = train.iter().map(|v| v[lo..hi].to_vec()).collect();
456 let refs: Vec<&[f32]> = subs.iter().map(|x| x.as_slice()).collect();
457 let k = PQ_CODEWORDS.min(refs.len()).max(1);
458 let cs = kmeans(&refs, k, iters, rng);
459 ks.push(cs.len() / (hi - lo));
460 centroids.push(cs);
461 }
462 PqCodebook {
463 sub_offsets: sub_offsets.to_vec(),
464 centroids,
465 ks,
466 }
467 }
468
469 fn encode(&self, v: &[f32]) -> Vec<u8> {
471 let m = self.m();
472 let mut code = vec![0u8; m];
473 for (s, slot) in code.iter_mut().enumerate().take(m) {
474 let (lo, hi) = (self.sub_offsets[s], self.sub_offsets[s + 1]);
475 *slot = nearest(&self.centroids[s], hi - lo, &v[lo..hi]) as u8;
476 }
477 code
478 }
479
480 fn distance_table(&self, q: &[f32]) -> Vec<f32> {
488 let m = self.m();
489 let mut table = vec![0.0f32; m * PQ_CODEWORDS];
490 for (s, row) in table.chunks_exact_mut(PQ_CODEWORDS).enumerate() {
491 let (lo, hi) = (self.sub_offsets[s], self.sub_offsets[s + 1]);
492 let sd = hi - lo;
493 let qs = &q[lo..hi];
494 let cs = &self.centroids[s];
495 for (c, slot) in row.iter_mut().enumerate().take(self.ks[s]) {
496 *slot = squared_l2(qs, &cs[c * sd..(c + 1) * sd]);
497 }
498 }
499 table
500 }
501}
502
503fn adc_distance(code: &[u8], table: &[f32]) -> f32 {
516 const K: usize = PQ_CODEWORDS;
517 let (mut a0, mut a1, mut a2, mut a3) = (0.0f32, 0.0f32, 0.0f32, 0.0f32);
518 let mut codes = code.chunks_exact(4);
519 let mut rows = table.chunks_exact(4 * K);
520 for (c, r) in (&mut codes).zip(&mut rows) {
521 a0 += r[c[0] as usize];
522 a1 += r[K + c[1] as usize];
523 a2 += r[2 * K + c[2] as usize];
524 a3 += r[3 * K + c[3] as usize];
525 }
526 let done = code.len() / 4 * 4;
527 for (&c, r) in codes
528 .remainder()
529 .iter()
530 .zip(table[done * K..].chunks_exact(K))
531 {
532 a0 += r[c as usize];
533 }
534 (a0 + a1) + (a2 + a3)
535}
536
537#[derive(Serialize, Deserialize, Clone, Debug, Default)]
539struct Posting {
540 ids: Vec<u128>,
541 codes: Vec<u8>,
543}
544
545#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
548pub(crate) enum IndexOp {
549 Add(u128, u32, Vec<u8>),
550 Remove(u128),
551}
552
553#[derive(Serialize, Deserialize, Clone, Debug)]
555pub struct IvfPqIndex {
556 dims: usize,
557 n_partitions: usize,
558 n_probe: usize,
559 n_rerank: usize,
560 centroids: Vec<f32>,
562 pq: PqCodebook,
563 partitions: Vec<Posting>,
564 #[serde(skip)]
567 assignment: U128Map,
568 #[serde(skip)]
572 assignment_ready: bool,
573 #[serde(skip)]
577 log: Option<Vec<IndexOp>>,
578 }
595
596impl IvfPqIndex {
597 pub fn build(dims: usize, items: &[(u128, &[f32])], cfg: IndexConfig) -> Result<IvfPqIndex> {
599 if items.is_empty() {
600 return Err(MnemoError::Invalid(
601 "cannot build an index over an empty database".into(),
602 ));
603 }
604 let n = items.len();
605 let mut rng = StdRng::seed_from_u64(cfg.seed);
606
607 let mut order: Vec<usize> = (0..n).collect();
609 let train_n = TRAIN_CAP.min(n);
610 order.partial_shuffle(&mut rng, train_n);
611 let train: Vec<&[f32]> = order[..train_n].iter().map(|&i| items[i].1).collect();
612
613 let n_partitions = if cfg.n_partitions > 0 {
615 cfg.n_partitions
616 } else {
617 (n as f64).sqrt().ceil() as usize
618 }
619 .clamp(1, n);
620 let centroids = kmeans(&train, n_partitions, cfg.kmeans_iters, &mut rng);
621 let n_partitions = centroids.len() / dims;
622
623 let m = if cfg.pq_subspaces > 0 {
628 cfg.pq_subspaces
629 } else {
630 (dims / 4).max(1)
631 }
632 .clamp(1, dims);
633 let mut sub_offsets = Vec::with_capacity(m + 1);
634 for s in 0..=m {
635 sub_offsets.push(s * dims / m);
636 }
637 let pq = PqCodebook::train(&sub_offsets, &train, cfg.kmeans_iters, &mut rng);
638
639 let n_probe = if cfg.n_probe > 0 {
647 cfg.n_probe
648 } else {
649 effective_auto_n_probe(n_partitions)
650 };
651 let n_rerank = if cfg.n_rerank > 0 {
652 cfg.n_rerank
653 } else {
654 effective_auto_n_rerank(items.len())
655 };
656
657 let mut index = IvfPqIndex {
658 dims,
659 n_partitions,
660 n_probe: n_probe.max(1),
661 n_rerank: n_rerank.max(1),
662 centroids,
663 pq,
664 partitions: vec![Posting::default(); n_partitions],
665 assignment: U128Map::with_capacity(n),
666 assignment_ready: true,
667 log: None,
668 };
669 for &(id, v) in items {
670 index.add(id, v);
671 }
672 Ok(index)
673 }
674
675 pub(crate) fn effective_defaults(&self) -> (usize, usize) {
701 if self.n_probe == 8 && self.n_rerank == 64 {
702 (
703 effective_auto_n_probe(self.n_partitions),
704 effective_auto_n_rerank(self.len()),
705 )
706 } else {
707 (self.n_probe, self.n_rerank)
708 }
709 }
710
711 pub fn dims(&self) -> usize {
713 self.dims
714 }
715
716 pub fn len(&self) -> usize {
718 self.partitions.iter().map(|p| p.ids.len()).sum()
719 }
720
721 pub(crate) fn contains(&mut self, id: u128) -> bool {
723 self.ensure_assignment();
724 self.assignment.contains_key(id)
725 }
726
727 pub(crate) fn ids(&self) -> impl Iterator<Item = u128> + '_ {
729 self.partitions.iter().flat_map(|p| p.ids.iter().copied())
730 }
731
732 #[cfg(feature = "dev-hooks")]
737 pub(crate) fn heap_bytes(&self) -> (usize, usize, usize, usize, usize) {
738 let f32s = std::mem::size_of::<f32>();
739 let centroids = self.centroids.capacity() * f32s;
740 let codebook = self
741 .pq
742 .centroids
743 .iter()
744 .map(|c| c.capacity() * f32s)
745 .sum::<usize>()
746 + self.pq.sub_offsets.capacity() * std::mem::size_of::<usize>()
747 + self.pq.ks.capacity() * std::mem::size_of::<usize>();
748 let ids = self
749 .partitions
750 .iter()
751 .map(|p| p.ids.capacity() * std::mem::size_of::<u128>())
752 .sum();
753 let codes = self.partitions.iter().map(|p| p.codes.capacity()).sum();
754 let assignment = self.assignment.heap_bytes();
755 (centroids, codebook, ids, codes, assignment)
756 }
757
758 pub fn info(&self) -> IndexInfo {
768 let (eff_probe, eff_rerank) = self.effective_defaults();
769 IndexInfo {
770 vectors: self.len(),
771 partitions: self.n_partitions,
772 subspaces: self.pq.m(),
773 n_probe: eff_probe,
774 n_rerank: eff_rerank,
775 }
776 }
777
778 pub fn rebuild_assignment(&mut self) {
781 let n = self.partitions.iter().map(|p| p.ids.len()).sum();
782 self.assignment = U128Map::with_capacity(n);
783 for (pi, p) in self.partitions.iter().enumerate() {
784 for &id in &p.ids {
785 self.assignment.insert(id, pi as u32);
786 }
787 }
788 self.assignment_ready = true;
789 }
790
791 pub(crate) fn ensure_assignment(&mut self) {
794 if !self.assignment_ready {
795 self.rebuild_assignment();
796 }
797 }
798
799 fn nearest_centroid(&self, v: &[f32]) -> usize {
800 nearest(&self.centroids, self.dims, v)
801 }
802
803 pub fn add(&mut self, id: u128, vector: &[f32]) {
808 self.remove(id);
809 let part = self.nearest_centroid(vector);
810 let code = self.pq.encode(vector);
811 if let Some(log) = &mut self.log {
812 log.push(IndexOp::Add(id, part as u32, code.clone()));
813 }
814 let p = &mut self.partitions[part];
815 p.ids.push(id);
816 p.codes.extend_from_slice(&code);
817 self.assignment.insert(id, part as u32);
818 }
819
820 pub fn remove(&mut self, id: u128) {
822 self.ensure_assignment();
823 if self.assignment.contains_key(id) {
824 if let Some(log) = &mut self.log {
825 log.push(IndexOp::Remove(id));
826 }
827 }
828 if let Some(part) = self.assignment.remove(id) {
829 let m = self.pq.m();
830 let p = &mut self.partitions[part as usize];
831 if let Some(pos) = p.ids.iter().position(|&x| x == id) {
832 p.ids.remove(pos);
833 p.codes.drain(pos * m..(pos + 1) * m);
834 }
835 }
836 }
837
838 pub(crate) fn enable_log(&mut self) {
840 if self.log.is_none() {
841 self.log = Some(Vec::new());
842 }
843 }
844
845 pub(crate) fn take_log(&mut self) -> Vec<IndexOp> {
847 self.log.as_mut().map(std::mem::take).unwrap_or_default()
848 }
849
850 pub(crate) fn apply_ops(&mut self, ops: Vec<IndexOp>) -> Result<()> {
854 if !ops.is_empty() {
855 self.ensure_assignment();
856 }
857 let log = self.log.take();
858 let m = self.pq.m();
859 let mut res = Ok(());
860 for op in ops {
861 match op {
862 IndexOp::Add(id, part, code) => {
863 if part as usize >= self.n_partitions || code.len() != m {
864 res = Err(MnemoError::Invalid(
865 "index delta does not fit the index".into(),
866 ));
867 break;
868 }
869 self.remove(id);
870 let p = &mut self.partitions[part as usize];
871 p.ids.push(id);
872 p.codes.extend_from_slice(&code);
873 self.assignment.insert(id, part);
874 }
875 IndexOp::Remove(id) => self.remove(id),
876 }
877 }
878 self.log = log;
879 res
880 }
881
882 pub fn query(&self, q: &[f32], n_probe: Option<usize>, n_rerank: Option<usize>) -> Vec<u128> {
892 let (auto_probe, auto_rerank) = self.effective_defaults();
893 let n_probe = n_probe.unwrap_or(auto_probe).clamp(1, self.n_partitions);
894 let n_rerank = n_rerank.unwrap_or(auto_rerank).max(1);
895
896 let mut parts: Vec<(usize, f32)> = (0..self.n_partitions)
898 .map(|i| {
899 let c = &self.centroids[i * self.dims..(i + 1) * self.dims];
900 (i, squared_l2(q, c))
901 })
902 .collect();
903 parts.sort_by(|a, b| a.1.total_cmp(&b.1));
904 parts.truncate(n_probe);
905
906 let table = self.pq.distance_table(q);
908 let m = self.pq.m();
909 let total: usize = parts
910 .iter()
911 .map(|&(pi, _)| self.partitions[pi].ids.len())
912 .sum();
913 let mut cands: Vec<(u128, f32)> = Vec::with_capacity(total);
914 for (pi, _) in parts {
915 let p = &self.partitions[pi];
916 for (&id, code) in p.ids.iter().zip(p.codes.chunks_exact(m)) {
917 cands.push((id, adc_distance(code, &table)));
918 }
919 }
920
921 if n_rerank < cands.len() {
929 cands.select_nth_unstable_by(n_rerank - 1, |a, b| a.1.total_cmp(&b.1));
930 cands.truncate(n_rerank);
931 }
932 cands.sort_by(|a, b| a.1.total_cmp(&b.1));
933 cands.into_iter().map(|(id, _)| id).collect()
934 }
935}
936
937#[cfg(test)]
938mod ann_1_1_tests {
939 use super::*;
949 use rand::rngs::StdRng;
950 use rand::SeedableRng;
951
952 #[derive(serde::Serialize, serde::Deserialize)]
958 struct V052IvfPqIndex {
959 dims: usize,
960 n_partitions: usize,
961 n_probe: usize,
962 n_rerank: usize,
963 centroids: Vec<f32>,
964 pq: PqCodebook,
965 partitions: Vec<Posting>,
966 }
967
968 fn tiny_pq(dims: usize) -> PqCodebook {
969 let sub_offsets = vec![0, dims];
970 let mut rng = StdRng::seed_from_u64(0);
971 let train: Vec<Vec<f32>> = (0..4).map(|i| vec![i as f32; dims]).collect();
972 let refs: Vec<&[f32]> = train.iter().map(|v| v.as_slice()).collect();
973 PqCodebook::train(&sub_offsets, &refs, 2, &mut rng)
974 }
975
976 #[test]
977 fn v0_5_2_index_blob_decodes_unchanged() {
978 let dims = 4;
982 let legacy = V052IvfPqIndex {
983 dims,
984 n_partitions: 2,
985 n_probe: 8,
986 n_rerank: 64,
987 centroids: vec![1.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0],
988 pq: tiny_pq(dims),
989 partitions: vec![Posting::default(); 2],
990 };
991 let bytes = rmp_serde::to_vec(&legacy).expect("serialize v0.5.2 layout");
992 let decoded: IvfPqIndex =
993 rmp_serde::from_slice(&bytes).expect("v0.5.2 bytes must decode under current schema");
994 assert_eq!(decoded.dims, 4);
995 assert_eq!(decoded.n_partitions, 2);
996 assert_eq!(decoded.n_probe, 8);
997 assert_eq!(decoded.n_rerank, 64);
998 }
999
1000 #[test]
1001 fn current_build_serializes_with_v0_5_2_field_count() {
1002 let dims = 4;
1009 let items: Vec<(u128, Vec<f32>)> = (0..32)
1010 .map(|i| (i as u128, vec![i as f32, i as f32 + 1.0, 0.0, 0.0]))
1011 .collect();
1012 let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1013 let idx = IvfPqIndex::build(dims, &refs, IndexConfig::default()).unwrap();
1014 let bytes = rmp_serde::to_vec(&idx).expect("serialize current layout");
1015 let as_v052: V052IvfPqIndex = rmp_serde::from_slice(&bytes)
1019 .expect("current index must decode under the v0.5.2 shape");
1020 assert_eq!(as_v052.dims, dims);
1021 }
1022
1023 #[test]
1024 fn legacy_8_64_triggers_auto_formulas_at_query_time() {
1025 let dims = 4;
1029 let legacy = V052IvfPqIndex {
1030 dims,
1031 n_partitions: 10,
1032 n_probe: 8,
1033 n_rerank: 64,
1034 centroids: vec![0.0; 10 * dims],
1035 pq: tiny_pq(dims),
1036 partitions: (0..10)
1037 .map(|_| Posting {
1038 ids: vec![0u128, 1u128],
1039 codes: vec![0u8; 2],
1040 })
1041 .collect(),
1042 };
1043 let bytes = rmp_serde::to_vec(&legacy).unwrap();
1044 let decoded: IvfPqIndex = rmp_serde::from_slice(&bytes).unwrap();
1045
1046 let (auto_probe, auto_rerank) = decoded.effective_defaults();
1047 assert_eq!(
1050 auto_probe, 10,
1051 "auto n_probe at <=100 partitions is full probe"
1052 );
1053 assert_eq!(auto_rerank, 100, "auto n_rerank at tiny N clamps up to 100");
1054 }
1055
1056 #[test]
1057 fn new_build_stores_resolved_auto_values() {
1058 let dims = 4;
1064 let items: Vec<(u128, Vec<f32>)> = (0..64)
1065 .map(|i| {
1066 let f = i as f32;
1067 (i as u128, vec![f, f + 1.0, f + 2.0, f + 3.0])
1068 })
1069 .collect();
1070 let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1071 let idx = IvfPqIndex::build(dims, &refs, IndexConfig::default()).unwrap();
1072 assert!(
1073 idx.n_probe > 0 && idx.n_rerank > 0,
1074 "resolved values must be concrete (never 0)"
1075 );
1076 let expected_rerank = (64 / 200usize).clamp(100, 1000);
1080 assert_eq!(idx.n_rerank, expected_rerank);
1081 }
1082
1083 #[test]
1084 fn explicit_build_values_persist_verbatim() {
1085 let dims = 4;
1092 let items: Vec<(u128, Vec<f32>)> =
1093 (0..64).map(|i| (i as u128, vec![i as f32; dims])).collect();
1094 let refs: Vec<(u128, &[f32])> = items.iter().map(|(id, v)| (*id, v.as_slice())).collect();
1095 let cfg = IndexConfig {
1096 n_probe: 3,
1097 n_rerank: 17,
1098 ..Default::default()
1099 };
1100 let idx = IvfPqIndex::build(dims, &refs, cfg).unwrap();
1101 assert_eq!(idx.n_probe, 3);
1102 assert_eq!(idx.n_rerank, 17);
1103 let (p, r) = idx.effective_defaults();
1104 assert_eq!(p, 3);
1105 assert_eq!(r, 17);
1106 }
1107}
1108
1109#[cfg(test)]
1110mod u128_map_tests {
1111 use super::U128Map;
1112 use std::collections::HashMap;
1113
1114 #[test]
1117 fn matches_hashmap_under_random_ops() {
1118 let mut ours = U128Map::default();
1119 let mut reference: HashMap<u128, u32> = HashMap::new();
1120 let mut x: u64 = 0x9E37_79B9;
1121 let mut next = || {
1122 x ^= x << 13;
1123 x ^= x >> 7;
1124 x ^= x << 17;
1125 x
1126 };
1127 for step in 0..60_000u32 {
1128 let k = (next() % 5_000) as u128 | ((next() % 3) as u128) << 100;
1130 match next() % 4 {
1131 0 | 1 => {
1132 ours.insert(k, step);
1133 reference.insert(k, step);
1134 }
1135 2 => assert_eq!(ours.remove(k), reference.remove(&k)),
1136 _ => assert_eq!(ours.get(k), reference.get(&k).copied()),
1137 }
1138 assert_eq!(ours.len(), reference.len());
1139 }
1140 for (k, v) in &reference {
1141 assert_eq!(ours.get(*k), Some(*v));
1142 }
1143 }
1144}
1145
1146const L2_MAX_DIMS: usize = 65_536;
1149
1150fn l2_take<R: std::io::Read>(r: &mut R, used: &mut u64, len: u64, n: usize) -> Result<Vec<u8>> {
1153 let end = (*used)
1154 .checked_add(n as u64)
1155 .filter(|&e| e <= len)
1156 .ok_or_else(|| {
1157 MnemoError::Serialize("index layout 2: a section runs past the run".into())
1158 })?;
1159 let mut b = vec![0u8; n];
1160 r.read_exact(&mut b)
1161 .map_err(|e| MnemoError::Serialize(format!("index layout 2: {e}")))?;
1162 *used = end;
1163 Ok(b)
1164}
1165
1166fn l2_u32s<R: std::io::Read>(r: &mut R, used: &mut u64, len: u64, n: usize) -> Result<Vec<usize>> {
1167 let b = l2_take(r, used, len, n.checked_mul(4).ok_or_else(l2_overflow)?)?;
1168 Ok(b.chunks_exact(4)
1169 .map(|c| u32::from_le_bytes(c.try_into().expect("4 bytes")) as usize)
1170 .collect())
1171}
1172
1173fn l2_f32s<R: std::io::Read>(r: &mut R, used: &mut u64, len: u64, n: usize) -> Result<Vec<f32>> {
1174 let b = l2_take(r, used, len, n.checked_mul(4).ok_or_else(l2_overflow)?)?;
1175 Ok(b.chunks_exact(4)
1176 .map(|c| f32::from_le_bytes(c.try_into().expect("4 bytes")))
1177 .collect())
1178}
1179
1180fn l2_overflow() -> MnemoError {
1181 MnemoError::Serialize("index layout 2: a length overflows".into())
1182}
1183
1184impl IvfPqIndex {
1185 pub(crate) fn write_layout2(&self, out: &mut Vec<u8>) {
1199 let m = self.pq.m();
1200 let total = self.len();
1201 out.reserve(
1202 20 + (2 * m + 1) * 4
1203 + self.centroids.len() * 4
1204 + self.pq.centroids.iter().map(|c| c.len() * 4).sum::<usize>()
1205 + self.n_partitions * 4
1206 + total * (16 + m),
1207 );
1208 let u32le = |out: &mut Vec<u8>, v: usize| out.extend_from_slice(&(v as u32).to_le_bytes());
1209 for v in [self.dims, self.n_partitions, self.n_probe, self.n_rerank, m] {
1210 u32le(out, v);
1211 }
1212 for &o in &self.pq.sub_offsets {
1213 u32le(out, o);
1214 }
1215 for &k in &self.pq.ks {
1216 u32le(out, k);
1217 }
1218 for &c in &self.centroids {
1219 out.extend_from_slice(&c.to_le_bytes());
1220 }
1221 for cb in &self.pq.centroids {
1222 for &c in cb {
1223 out.extend_from_slice(&c.to_le_bytes());
1224 }
1225 }
1226 for p in &self.partitions {
1227 u32le(out, p.ids.len());
1228 }
1229 for p in &self.partitions {
1230 for &id in &p.ids {
1231 out.extend_from_slice(&id.to_le_bytes());
1232 }
1233 }
1234 for p in &self.partitions {
1235 out.extend_from_slice(&p.codes);
1236 }
1237 }
1238
1239 pub(crate) fn read_layout2<R: std::io::Read>(r: &mut R, len: u64) -> Result<IvfPqIndex> {
1245 let bad = |what: &str| MnemoError::Serialize(format!("index layout 2: {what}"));
1246 let mut used = 0u64;
1247 let head = l2_u32s(r, &mut used, len, 5)?;
1248 let (dims, n_partitions, n_probe, n_rerank, m) =
1249 (head[0], head[1], head[2], head[3], head[4]);
1250 if dims == 0 || dims > L2_MAX_DIMS || n_partitions == 0 || m == 0 || m > dims {
1251 return Err(bad("a bad shape"));
1252 }
1253 let sub_offsets = l2_u32s(r, &mut used, len, m + 1)?;
1254 if sub_offsets[0] != 0
1255 || sub_offsets[m] != dims
1256 || sub_offsets.windows(2).any(|w| w[1] <= w[0])
1257 {
1258 return Err(bad("bad subspace offsets"));
1259 }
1260 let ks = l2_u32s(r, &mut used, len, m)?;
1261 if ks.iter().any(|&k| k == 0 || k > PQ_CODEWORDS) {
1262 return Err(bad("a bad codeword count"));
1263 }
1264 let centroids = l2_f32s(
1265 r,
1266 &mut used,
1267 len,
1268 n_partitions.checked_mul(dims).ok_or_else(l2_overflow)?,
1269 )?;
1270 let mut pq_centroids = Vec::with_capacity(m);
1271 for s in 0..m {
1272 let subdim = sub_offsets[s + 1] - sub_offsets[s];
1273 pq_centroids.push(l2_f32s(r, &mut used, len, ks[s] * subdim)?);
1274 }
1275 let counts = l2_u32s(r, &mut used, len, n_partitions)?;
1276 let total = counts
1277 .iter()
1278 .try_fold(0usize, |a, &c| a.checked_add(c))
1279 .ok_or_else(l2_overflow)?;
1280 let rest = total.checked_mul(16 + m).ok_or_else(l2_overflow)? as u64;
1281 if used.checked_add(rest) != Some(len) {
1282 return Err(bad("the postings don't match the run's length"));
1283 }
1284 let mut partitions: Vec<Posting> = Vec::with_capacity(n_partitions);
1287 for &c in &counts {
1288 let ids = l2_take(r, &mut used, len, c * 16)?
1289 .chunks_exact(16)
1290 .map(|b| u128::from_le_bytes(b.try_into().expect("16 bytes")))
1291 .collect();
1292 partitions.push(Posting {
1293 ids,
1294 codes: Vec::new(),
1295 });
1296 }
1297 for (p, &c) in partitions.iter_mut().zip(&counts) {
1298 p.codes = l2_take(r, &mut used, len, c * m)?;
1299 }
1300 Ok(IvfPqIndex {
1301 dims,
1302 n_partitions,
1303 n_probe,
1304 n_rerank,
1305 centroids,
1306 pq: PqCodebook {
1307 sub_offsets,
1308 centroids: pq_centroids,
1309 ks,
1310 },
1311 partitions,
1312 assignment: U128Map::default(),
1313 assignment_ready: false,
1314 log: None,
1315 })
1316 }
1317}
1318
1319#[cfg(test)]
1320mod adc_tests {
1321 use super::{adc_distance, PQ_CODEWORDS};
1322
1323 #[test]
1326 fn unrolled_adc_matches_the_plain_sum() {
1327 let mut x: u32 = 0xA5A5_1234;
1328 let mut next = || {
1329 x ^= x << 13;
1330 x ^= x >> 17;
1331 x ^= x << 5;
1332 x
1333 };
1334 for m in 1..=13usize {
1335 let table: Vec<f32> = (0..m * PQ_CODEWORDS)
1336 .map(|_| (next() % 10_000) as f32 / 100.0)
1337 .collect();
1338 for _ in 0..50 {
1339 let code: Vec<u8> = (0..m).map(|_| next() as u8).collect();
1340 let plain: f32 = code
1341 .iter()
1342 .enumerate()
1343 .map(|(s, &c)| table[s * PQ_CODEWORDS + c as usize])
1344 .sum();
1345 let fast = adc_distance(&code, &table);
1346 assert!(
1347 (plain - fast).abs() <= 1e-3 * plain.abs().max(1.0),
1348 "m={m}: {plain} vs {fast}"
1349 );
1350 }
1351 }
1352 }
1353}
1354
1355#[cfg(test)]
1356mod layout2_tests {
1357 use super::{IndexConfig, IvfPqIndex};
1358
1359 fn index(n: usize, dims: usize) -> IvfPqIndex {
1360 let mut x: u32 = 0x1234_5678;
1361 let mut next = || {
1362 x ^= x << 13;
1363 x ^= x >> 17;
1364 x ^= x << 5;
1365 (x % 2_000) as f32 / 1_000.0 - 1.0
1366 };
1367 let vs: Vec<(u128, Vec<f32>)> = (0..n)
1368 .map(|i| (i as u128 * 7 + 1, (0..dims).map(|_| next()).collect()))
1369 .collect();
1370 let items: Vec<(u128, &[f32])> = vs.iter().map(|(i, v)| (*i, v.as_slice())).collect();
1371 IvfPqIndex::build(dims, &items, IndexConfig::default()).unwrap()
1372 }
1373
1374 fn encode(idx: &IvfPqIndex) -> Vec<u8> {
1375 let mut b = Vec::new();
1376 idx.write_layout2(&mut b);
1377 b
1378 }
1379
1380 #[test]
1384 fn layout_2_round_trips() {
1385 let idx = index(600, 16);
1386 let b = encode(&idx);
1387 let mut back = IvfPqIndex::read_layout2(&mut b.as_slice(), b.len() as u64).unwrap();
1388 assert!(!back.assignment_ready);
1389 let shape = |i: &IvfPqIndex| {
1390 let x = i.info();
1391 (x.vectors, x.partitions, x.subspaces, x.n_probe, x.n_rerank)
1392 };
1393 assert_eq!(shape(&back), shape(&idx));
1394 assert_eq!(back.len(), 600);
1395 for q in [vec![0.5f32; 16], vec![-0.25f32; 16]] {
1396 assert_eq!(back.query(&q, None, None), idx.query(&q, None, None));
1397 }
1398 assert!(back.contains(8));
1399 assert!(back.assignment_ready);
1400 back.remove(8);
1401 assert!(!back.contains(8));
1402 assert_eq!(encode(&back).len(), b.len() - 16 - back.pq.m());
1403 }
1404
1405 #[test]
1408 fn a_damaged_layout_2_run_is_an_error() {
1409 let b = encode(&index(300, 8));
1410 let len = b.len() as u64;
1411 for cut in [0, 3, 20, 40, b.len() / 2, b.len() - 1] {
1412 assert!(
1413 IvfPqIndex::read_layout2(&mut &b[..cut], cut as u64).is_err(),
1414 "cut at {cut}"
1415 );
1416 assert!(
1418 IvfPqIndex::read_layout2(&mut &b[..cut], len).is_err(),
1419 "short read at {cut}"
1420 );
1421 }
1422 let mut long = b.clone();
1423 long.push(0);
1424 assert!(IvfPqIndex::read_layout2(&mut long.as_slice(), long.len() as u64).is_err());
1425 let m = u32::from_le_bytes(b[16..20].try_into().unwrap()) as usize;
1427 let parts = u32::from_le_bytes(b[4..8].try_into().unwrap()) as usize;
1428 let dims = u32::from_le_bytes(b[0..4].try_into().unwrap()) as usize;
1429 let ks: Vec<usize> = (0..m)
1430 .map(|s| {
1431 let at = 20 + (m + 1) * 4 + s * 4;
1432 u32::from_le_bytes(b[at..at + 4].try_into().unwrap()) as usize
1433 })
1434 .collect();
1435 let sub = dims / m;
1436 let counts_at =
1437 20 + (2 * m + 1) * 4 + parts * dims * 4 + ks.iter().map(|k| k * sub * 4).sum::<usize>();
1438 let mut huge = b.clone();
1439 huge[counts_at..counts_at + 4].copy_from_slice(&u32::MAX.to_le_bytes());
1440 assert!(IvfPqIndex::read_layout2(&mut huge.as_slice(), len).is_err());
1441 for (at, v) in [(0usize, 0u32), (16, 9), (20 + (m + 1) * 4, 0)] {
1443 let mut x = b.clone();
1444 x[at..at + 4].copy_from_slice(&v.to_le_bytes());
1445 assert!(
1446 IvfPqIndex::read_layout2(&mut x.as_slice(), len).is_err(),
1447 "at {at}"
1448 );
1449 }
1450 }
1451}