π End-to-end encrypted cloud for everything.
Dart 2faandroidauthye2eeencryptionend-to-end-encryptionfluttergolanggoogle-photosgoogle-photos-alternativeiosopensourcephotosprivacyprivacy-toolstypescriptzero-knowledge
use std::collections::HashMap;
use super::kernel::{
F32Kernel, I8Kernel, Lane, LaneI8, StoredVector, VectorKernel, VectorPayload, dequantize,
pack_lanes, pack_lanes_i8, pack_lanes_i8_into, pack_lanes_into, quantize_for, unpack_lanes,
unpack_lanes_i8, validate_dims,
};
use super::{StorageKind, VecDbError};
pub(crate) const VECTORS_PER_CHUNK: usize = 4096;
pub(crate) const MAX_KEY_BYTES: usize = 256;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum UpsertOutcome {
NewSlot(u32),
Unchanged(u32),
}
pub fn validate_key(key: &str) -> Result<(), VecDbError> {
if key.is_empty() {
return Err(VecDbError::InvalidKey("key is empty".to_string()));
}
if key.len() > MAX_KEY_BYTES {
return Err(VecDbError::InvalidKey(format!(
"key is {} bytes, limit is {MAX_KEY_BYTES}",
key.len()
)));
}
Ok(())
}
enum Storage {
F32 {
chunks: Vec<Vec<Lane>>,
},
I8 {
chunks: Vec<Vec<LaneI8>>,
scales: Vec<f32>,
},
}
impl Storage {
fn kind(&self) -> StorageKind {
match self {
Self::F32 { .. } => StorageKind::F32,
Self::I8 { .. } => StorageKind::I8,
}
}
fn chunk_count(&self) -> usize {
match self {
Self::F32 { chunks } => chunks.len(),
Self::I8 { chunks, .. } => chunks.len(),
}
}
fn push_chunk(&mut self, lanes_per_vector: usize) {
match self {
Self::F32 { chunks } => {
chunks.push(vec![Lane::ZERO; VECTORS_PER_CHUNK * lanes_per_vector]);
}
Self::I8 { chunks, .. } => {
chunks.push(vec![LaneI8::ZERO; VECTORS_PER_CHUNK * lanes_per_vector]);
}
}
}
}
pub(crate) enum PackedQuery {
F32(Vec<Lane>, f64),
I8 {
scale: f32,
lanes: Vec<LaneI8>,
norm: f64,
},
}
impl PackedQuery {
pub(crate) fn as_query(&self) -> Query<'_> {
match self {
Self::F32(lanes, norm) => Query::F32(lanes, *norm),
Self::I8 { scale, lanes, norm } => Query::I8 {
scale: *scale,
lanes,
norm: *norm,
},
}
}
}
#[derive(Clone, Copy)]
pub(crate) enum Query<'a> {
F32(&'a [Lane], f64),
I8 {
scale: f32,
lanes: &'a [LaneI8],
norm: f64,
},
}
impl Query<'_> {
pub(crate) fn is_finite(&self) -> bool {
match self {
Self::F32(lanes, _) => lanes
.iter()
.all(|lane| lane.to_array().iter().all(|value| value.is_finite())),
Self::I8 { scale, .. } => scale.is_finite(),
}
}
}
pub(crate) struct VectorArena {
dims: usize,
lanes_per_vector: usize,
storage: Storage,
norms: Vec<f64>,
keys_to_slots: HashMap<Box<str>, u32>,
slots_to_keys: Vec<Box<str>>,
alive: Vec<u64>,
live_count: usize,
}
impl VectorArena {
#[cfg(test)]
pub(crate) fn new(dims: usize) -> Result<Self, VecDbError> {
Self::with_storage(dims, StorageKind::F32)
}
pub(crate) fn with_storage(dims: usize, storage: StorageKind) -> Result<Self, VecDbError> {
validate_dims(dims, storage)?;
let storage = match storage {
StorageKind::F32 => Storage::F32 { chunks: Vec::new() },
StorageKind::I8 => Storage::I8 {
chunks: Vec::new(),
scales: Vec::new(),
},
};
Ok(Self {
dims,
lanes_per_vector: dims / storage.kind().lane_width(),
storage,
norms: Vec::new(),
keys_to_slots: HashMap::new(),
slots_to_keys: Vec::new(),
alive: Vec::new(),
live_count: 0,
})
}
pub(crate) fn dims(&self) -> usize {
self.dims
}
pub(crate) fn storage_kind(&self) -> StorageKind {
self.storage.kind()
}
pub(crate) fn live_count(&self) -> usize {
self.live_count
}
pub(crate) fn dead_count(&self) -> usize {
self.slot_count() - self.live_count
}
pub(crate) fn slot_count(&self) -> usize {
self.slots_to_keys.len()
}
pub(crate) fn is_empty(&self) -> bool {
self.live_count == 0
}
pub(crate) fn vector_memory_bytes(&self) -> usize {
let vectors = self.storage.chunk_count() * VECTORS_PER_CHUNK;
self.norms.capacity() * size_of::<f64>()
+ match &self.storage {
Storage::F32 { .. } => vectors * self.dims * size_of::<f32>(),
Storage::I8 { .. } => vectors * self.dims + self.slot_count() * size_of::<f32>(),
}
}
#[cfg(test)]
pub(crate) fn upsert(
&mut self,
key: &str,
vector: &[f32],
) -> Result<UpsertOutcome, VecDbError> {
match quantize_for(self.storage_kind(), vector) {
Some(quantized) => self.upsert_payload(key, quantized.as_payload()),
None => self.upsert_payload(key, VectorPayload::F32(vector)),
}
}
pub(crate) fn upsert_payload(
&mut self,
key: &str,
payload: VectorPayload<'_>,
) -> Result<UpsertOutcome, VecDbError> {
validate_key(key)?;
if payload.storage() != self.storage_kind() {
return Err(VecDbError::StorageMismatch {
expected: self.storage_kind(),
actual: payload.storage(),
});
}
if payload.dims() != self.dims {
return Err(VecDbError::DimensionMismatch {
expected: self.dims,
actual: payload.dims(),
});
}
if let Some(&slot) = self.keys_to_slots.get(key) {
if self.matches_payload(slot, payload) {
return Ok(UpsertOutcome::Unchanged(slot));
}
self.retire_slot(slot);
}
let slot = self.slots_to_keys.len() as u32;
if slot as usize == self.storage.chunk_count() * VECTORS_PER_CHUNK {
self.storage.push_chunk(self.lanes_per_vector);
}
if let Storage::I8 { scales, .. } = &mut self.storage {
scales.push(0.0);
}
if slot as usize / 64 == self.alive.len() {
self.alive.push(0);
}
self.norms.push(0.0);
self.slots_to_keys.push(Box::from(key));
self.keys_to_slots.insert(Box::from(key), slot);
self.mark_alive(slot);
self.live_count += 1;
self.write_vector(slot, payload);
Ok(UpsertOutcome::NewSlot(slot))
}
pub(crate) fn remove(&mut self, key: &str) -> Option<u32> {
let slot = self.keys_to_slots.remove(key)?;
self.retire_slot(slot);
Some(slot)
}
fn retire_slot(&mut self, slot: u32) {
self.mark_dead(slot);
self.live_count -= 1;
self.slots_to_keys[slot as usize] = Box::from("");
}
pub(crate) fn compact_in_place(&mut self) {
let mut dense: u32 = 0;
for slot in 0..self.slots_to_keys.len() as u32 {
if !self.is_alive(slot) {
continue;
}
if dense != slot {
self.move_vector(slot, dense);
let key = std::mem::take(&mut self.slots_to_keys[slot as usize]);
if let Some(mapped) = self.keys_to_slots.get_mut(&key) {
*mapped = dense;
}
self.slots_to_keys[dense as usize] = key;
}
dense += 1;
}
let live = dense as usize;
debug_assert_eq!(live, self.live_count);
self.slots_to_keys.truncate(live);
self.slots_to_keys.shrink_to_fit();
self.keys_to_slots.shrink_to_fit();
let chunk_count = live.div_ceil(VECTORS_PER_CHUNK);
match &mut self.storage {
Storage::F32 { chunks } => {
chunks.truncate(chunk_count);
chunks.shrink_to_fit();
}
Storage::I8 { chunks, scales } => {
chunks.truncate(chunk_count);
chunks.shrink_to_fit();
scales.truncate(live);
scales.shrink_to_fit();
}
}
self.norms.truncate(live);
self.norms.shrink_to_fit();
self.alive.clear();
self.alive.resize(live.div_ceil(64), u64::MAX);
self.alive.shrink_to_fit();
if !live.is_multiple_of(64)
&& let Some(word) = self.alive.last_mut()
{
*word = (1u64 << (live % 64)) - 1;
}
}
fn move_vector(&mut self, src: u32, dst: u32) {
self.norms[dst as usize] = self.norms[src as usize];
let lanes = self.lanes_per_vector;
match &mut self.storage {
Storage::F32 { chunks } => move_lanes(chunks, lanes, src, dst),
Storage::I8 { chunks, scales } => {
move_lanes(chunks, lanes, src, dst);
scales[dst as usize] = scales[src as usize];
}
}
}
pub(crate) fn slot_of_key(&self, key: &str) -> Option<u32> {
self.keys_to_slots.get(key).copied()
}
pub(crate) fn key_of_slot(&self, slot: u32) -> Option<&str> {
if self.is_alive(slot) {
Some(&self.slots_to_keys[slot as usize])
} else {
None
}
}
pub(crate) fn is_alive(&self, slot: u32) -> bool {
self.alive
.get(slot as usize / 64)
.is_some_and(|word| word & (1u64 << (slot % 64)) != 0)
}
pub(crate) fn live_slots(&self) -> impl Iterator<Item = u32> {
(0..self.slots_to_keys.len() as u32).filter(|slot| self.is_alive(*slot))
}
pub(crate) fn stored_query(&self, slot: u32) -> Query<'_> {
let norm = self.norms.get(slot as usize).copied().unwrap_or(0.0);
let lanes = self.lanes_per_vector;
match &self.storage {
Storage::F32 { chunks } => Query::F32(slot_lanes(chunks, lanes, slot), norm),
Storage::I8 { chunks, scales } => Query::I8 {
scale: scales[slot as usize],
lanes: slot_lanes(chunks, lanes, slot),
norm,
},
}
}
pub(crate) fn vector_values(&self, slot: u32) -> Vec<f32> {
match self.stored_query(slot) {
Query::F32(lanes, _) => unpack_lanes(lanes),
Query::I8 { scale, lanes, .. } => dequantize(scale, &unpack_lanes_i8(lanes)),
}
}
pub(crate) fn stored_vector(&self, slot: u32) -> StoredVector {
match self.stored_query(slot) {
Query::F32(lanes, _) => StoredVector::F32(unpack_lanes(lanes)),
Query::I8 { scale, lanes, .. } => StoredVector::I8 {
scale,
values: unpack_lanes_i8(lanes),
},
}
}
pub(crate) fn matches_payload(&self, slot: u32, payload: VectorPayload<'_>) -> bool {
if payload.dims() != self.dims {
return false;
}
match (self.stored_query(slot), payload) {
(Query::F32(lanes, _), VectorPayload::F32(values)) => lanes
.iter()
.flat_map(|lane| lane.to_array())
.zip(values)
.all(|(stored, value)| stored.to_bits() == value.to_bits()),
(
Query::I8 { scale, lanes, .. },
VectorPayload::I8 {
scale: other_scale,
values,
},
) => {
scale.to_bits() == other_scale.to_bits()
&& lanes
.iter()
.flat_map(|lane| lane.to_array())
.eq(values.iter().copied())
}
_ => false,
}
}
pub(crate) fn pack_query(&self, values: &[f32]) -> Result<PackedQuery, VecDbError> {
if values.len() != self.dims {
return Err(VecDbError::DimensionMismatch {
expected: self.dims,
actual: values.len(),
});
}
Ok(match quantize_for(self.storage_kind(), values) {
Some(StoredVector::I8 { scale, values }) => {
let lanes = pack_lanes_i8(&values);
let norm = i8_lanes_norm(scale, &lanes);
PackedQuery::I8 { scale, lanes, norm }
}
Some(StoredVector::F32(_)) | None => {
let lanes = pack_lanes(values);
let norm = f32_lanes_norm(&lanes);
PackedQuery::F32(lanes, norm)
}
})
}
pub(crate) fn distance_between_slots(&self, a: u32, b: u32) -> f32 {
self.distance_to_query(self.stored_query(a), b)
}
pub(crate) fn distance_to_query(&self, query: Query<'_>, slot: u32) -> f32 {
match (query, self.stored_query(slot)) {
(Query::F32(a, norm_a), Query::F32(b, norm_b)) => {
let denominator = norm_a * norm_b;
let dot = if denominator >= f64::from(f32::MIN_POSITIVE)
&& denominator <= f64::from(f32::MAX)
{
f64::from(F32Kernel::dot(a, b))
} else {
a.iter()
.zip(b)
.flat_map(|(a, b)| a.to_array().into_iter().zip(b.to_array()))
.map(|(a, b)| f64::from(a) * f64::from(b))
.sum()
};
cosine_distance(dot, denominator)
}
(
Query::I8 {
lanes: a,
norm: norm_a,
..
},
Query::I8 {
lanes: b,
norm: norm_b,
..
},
) => cosine_distance(f64::from(I8Kernel::dot(a, b)), norm_a * norm_b),
_ => unreachable!("queries are packed by the arena that searches them"),
}
}
fn stored_norm(&self, slot: u32) -> f64 {
let lanes = self.lanes_per_vector;
match &self.storage {
Storage::F32 { chunks } => f32_lanes_norm(slot_lanes(chunks, lanes, slot)),
Storage::I8 { chunks, scales } => {
i8_lanes_norm(scales[slot as usize], slot_lanes(chunks, lanes, slot))
}
}
}
fn write_vector(&mut self, slot: u32, payload: VectorPayload<'_>) {
let lanes = self.lanes_per_vector;
match (&mut self.storage, payload) {
(Storage::F32 { chunks }, VectorPayload::F32(values)) => {
pack_lanes_into(values, slot_lanes_mut(chunks, lanes, slot));
}
(Storage::I8 { chunks, scales }, VectorPayload::I8 { scale, values }) => {
pack_lanes_i8_into(values, slot_lanes_mut(chunks, lanes, slot));
scales[slot as usize] = scale;
}
(Storage::F32 { .. }, VectorPayload::I8 { .. })
| (Storage::I8 { .. }, VectorPayload::F32(_)) => {
unreachable!("payload kind is validated before a slot is written")
}
}
self.norms[slot as usize] = self.stored_norm(slot);
}
fn mark_alive(&mut self, slot: u32) {
self.alive[slot as usize / 64] |= 1u64 << (slot % 64);
}
fn mark_dead(&mut self, slot: u32) {
self.alive[slot as usize / 64] &= !(1u64 << (slot % 64));
}
}
fn f32_lanes_norm(lanes: &[Lane]) -> f64 {
lanes
.iter()
.flat_map(|lane| lane.to_array())
.map(|value| f64::from(value).powi(2))
.sum::<f64>()
.sqrt()
}
fn i8_lanes_norm(scale: f32, lanes: &[LaneI8]) -> f64 {
if scale == 0.0 {
return 0.0;
}
f64::from(I8Kernel::dot(lanes, lanes)).sqrt()
}
fn cosine_distance(dot: f64, denominator: f64) -> f32 {
if denominator == 0.0 {
return 1.0;
}
(1.0 - (dot / denominator).clamp(-1.0, 1.0)) as f32
}
fn slot_lanes<T>(chunks: &[Vec<T>], lanes_per_vector: usize, slot: u32) -> &[T] {
let start = (slot as usize % VECTORS_PER_CHUNK) * lanes_per_vector;
&chunks[slot as usize / VECTORS_PER_CHUNK][start..start + lanes_per_vector]
}
fn slot_lanes_mut<T>(chunks: &mut [Vec<T>], lanes_per_vector: usize, slot: u32) -> &mut [T] {
let start = (slot as usize % VECTORS_PER_CHUNK) * lanes_per_vector;
&mut chunks[slot as usize / VECTORS_PER_CHUNK][start..start + lanes_per_vector]
}
fn move_lanes<T: Copy>(chunks: &mut [Vec<T>], lanes: usize, src: u32, dst: u32) {
let src_chunk = src as usize / VECTORS_PER_CHUNK;
let dst_chunk = dst as usize / VECTORS_PER_CHUNK;
let src_start = (src as usize % VECTORS_PER_CHUNK) * lanes;
let dst_start = (dst as usize % VECTORS_PER_CHUNK) * lanes;
if src_chunk == dst_chunk {
chunks[src_chunk].copy_within(src_start..src_start + lanes, dst_start);
} else {
let (front, back) = chunks.split_at_mut(src_chunk);
front[dst_chunk][dst_start..dst_start + lanes]
.copy_from_slice(&back[0][src_start..src_start + lanes]);
}
}
#[cfg(test)]
mod tests {
use super::super::kernel::splitmix64;
use super::*;
fn seeded_vector(seed: u64, dims: usize) -> Vec<f32> {
let mut state = seed;
(0..dims)
.map(|_| {
let unit = (splitmix64(&mut state) >> 40) as f32 / (1u64 << 24) as f32;
unit * 2.0 - 1.0
})
.collect()
}
fn seeded_unit_vector(seed: u64, dims: usize) -> Vec<f32> {
let mut values = seeded_vector(seed, dims);
let norm = values.iter().map(|value| value * value).sum::<f32>().sqrt();
for value in &mut values {
*value /= norm;
}
values
}
fn basis_vector(dims: usize, axis: usize) -> Vec<f32> {
let mut values = vec![0.0; dims];
values[axis] = 1.0;
values
}
#[test]
fn cosine_norms_match_their_scalar_references_and_agree_between_query_and_slot() {
for dims in [512usize, 768] {
for storage in [StorageKind::F32, StorageKind::I8] {
let mut arena = VectorArena::with_storage(dims, storage).unwrap();
let vectors: Vec<Vec<f32>> = (0..16u64)
.map(|seed| seeded_vector(0x5E1F_0000 + seed, dims))
.collect();
for (index, vector) in vectors.iter().enumerate() {
arena.upsert(&format!("key-{index}"), vector).unwrap();
}
arena.upsert("zero", &vec![0.0; dims]).unwrap();
for (index, vector) in vectors.iter().enumerate() {
let slot = arena.slot_of_key(&format!("key-{index}")).unwrap();
let reference: f64 = match arena.stored_query(slot) {
Query::F32(lanes, _) => lanes
.iter()
.flat_map(|lane| lane.to_array())
.map(|value| f64::from(value).powi(2))
.sum::<f64>()
.sqrt(),
Query::I8 { lanes, .. } => unpack_lanes_i8(lanes)
.iter()
.map(|&value| f64::from(value).powi(2))
.sum::<f64>()
.sqrt(),
};
assert_eq!(arena.norms[slot as usize], reference);
let query = arena.pack_query(vector).unwrap();
let query_norm = match query.as_query() {
Query::F32(_, norm) => norm,
Query::I8 { norm, .. } => norm,
};
assert_eq!(query_norm, reference);
assert!(arena.distance_to_query(query.as_query(), slot) < 1.0e-6);
}
let zero = arena.slot_of_key("zero").unwrap();
assert_eq!(arena.norms[zero as usize], 0.0);
assert_eq!(arena.distance_between_slots(zero, zero), 1.0);
}
}
}
fn arena_with_keys(dims: usize, keys: &[&str]) -> VectorArena {
let mut arena = VectorArena::new(dims).unwrap();
for (index, key) in keys.iter().enumerate() {
arena
.upsert(key, &seeded_vector(index as u64, dims))
.unwrap();
}
arena
}
fn lane_address(query: Query<'_>) -> usize {
match query {
Query::F32(lanes, _) => lanes.as_ptr() as usize,
Query::I8 { lanes, .. } => lanes.as_ptr() as usize,
}
}
fn stored_i8(arena: &VectorArena, slot: u32) -> (f32, Vec<i8>) {
match arena.stored_vector(slot) {
StoredVector::I8 { scale, values } => (scale, values),
StoredVector::F32(_) => panic!("expected i8 storage"),
}
}
#[test]
fn rejects_invalid_dimensions() {
assert!(matches!(
VectorArena::new(0),
Err(VecDbError::InvalidDimensions {
dims: 0,
storage: StorageKind::F32
})
));
assert!(matches!(
VectorArena::new(12),
Err(VecDbError::InvalidDimensions {
dims: 12,
storage: StorageKind::F32
})
));
assert!(VectorArena::new(8).is_ok());
assert!(VectorArena::new(512).is_ok());
}
#[test]
fn i8_storage_requires_a_nonzero_multiple_of_32_dims() {
for dims in [0usize, 8, 16, 24, 40, 100] {
assert!(matches!(
VectorArena::with_storage(dims, StorageKind::I8),
Err(VecDbError::InvalidDimensions {
dims: rejected,
storage: StorageKind::I8
}) if rejected == dims
));
}
for dims in [32usize, 64, 512, 1024] {
let arena = VectorArena::with_storage(dims, StorageKind::I8).unwrap();
assert_eq!(arena.storage_kind(), StorageKind::I8);
assert_eq!(arena.dims(), dims);
}
assert_eq!(
VectorArena::with_storage(8, StorageKind::F32)
.unwrap()
.storage_kind(),
StorageKind::F32
);
assert_eq!(
VectorArena::new(8).unwrap().storage_kind(),
StorageKind::F32
);
let Err(error) = VectorArena::with_storage(8, StorageKind::I8) else {
panic!("expected an invalid dimensions error");
};
let message = error.to_string();
assert!(message.contains("i8"));
assert!(message.contains("32"));
}
#[test]
fn rejects_invalid_keys() {
let mut arena = VectorArena::new(8).unwrap();
let vector = seeded_vector(1, 8);
assert!(matches!(
arena.upsert("", &vector),
Err(VecDbError::InvalidKey(_))
));
let at_limit = "k".repeat(256);
assert!(arena.upsert(&at_limit, &vector).is_ok());
let over_limit = "k".repeat(257);
assert!(matches!(
arena.upsert(&over_limit, &vector),
Err(VecDbError::InvalidKey(_))
));
let multibyte_over_limit = format!("{}Γ©", "k".repeat(255));
assert_eq!(multibyte_over_limit.len(), 257);
assert!(matches!(
arena.upsert(&multibyte_over_limit, &vector),
Err(VecDbError::InvalidKey(_))
));
}
#[test]
fn rejects_dimension_mismatch() {
let mut arena = VectorArena::new(16).unwrap();
assert!(matches!(
arena.upsert("key", &seeded_vector(1, 8)),
Err(VecDbError::DimensionMismatch {
expected: 16,
actual: 8
})
));
assert!(matches!(
arena.pack_query(&seeded_vector(1, 24)),
Err(VecDbError::DimensionMismatch {
expected: 16,
actual: 24
})
));
let mut i8_arena = VectorArena::with_storage(32, StorageKind::I8).unwrap();
assert!(matches!(
i8_arena.upsert("key", &seeded_vector(1, 64)),
Err(VecDbError::DimensionMismatch {
expected: 32,
actual: 64
})
));
assert!(matches!(
i8_arena.pack_query(&seeded_vector(1, 8)),
Err(VecDbError::DimensionMismatch {
expected: 32,
actual: 8
})
));
assert_eq!(i8_arena.slot_count(), 0);
}
#[test]
fn payload_kind_must_match_the_arena_storage() {
let mut f32_arena = VectorArena::new(32).unwrap();
let mut i8_arena = VectorArena::with_storage(32, StorageKind::I8).unwrap();
let values = seeded_vector(3, 32);
let quantized = StoredVector::quantize(&values);
assert!(matches!(
f32_arena.upsert_payload("k", quantized.as_payload()),
Err(VecDbError::StorageMismatch {
expected: StorageKind::F32,
actual: StorageKind::I8
})
));
assert!(matches!(
i8_arena.upsert_payload("k", VectorPayload::F32(&values)),
Err(VecDbError::StorageMismatch {
expected: StorageKind::I8,
actual: StorageKind::F32
})
));
assert_eq!(f32_arena.slot_count(), 0);
assert_eq!(i8_arena.slot_count(), 0);
assert!(f32_arena.slot_of_key("k").is_none());
assert!(i8_arena.slot_of_key("k").is_none());
assert_eq!(
f32_arena
.upsert_payload("k", VectorPayload::F32(&values))
.unwrap(),
UpsertOutcome::NewSlot(0)
);
assert_eq!(
i8_arena
.upsert_payload("k", quantized.as_payload())
.unwrap(),
UpsertOutcome::NewSlot(0)
);
assert_eq!(f32_arena.vector_values(0), values);
assert_eq!(i8_arena.stored_vector(0), quantized);
}
#[test]
fn assigns_slots_in_encounter_order() {
let arena = arena_with_keys(8, &["a", "b", "c"]);
assert_eq!(arena.slot_of_key("a"), Some(0));
assert_eq!(arena.slot_of_key("b"), Some(1));
assert_eq!(arena.slot_of_key("c"), Some(2));
}
#[test]
fn upsert_appends_a_version_and_preserves_the_retired_vector() {
let mut arena = VectorArena::new(8).unwrap();
let first = seeded_vector(1, 8);
let second = seeded_vector(2, 8);
assert_eq!(
arena.upsert("key", &first).unwrap(),
UpsertOutcome::NewSlot(0)
);
assert_eq!(
arena.upsert("key", &second).unwrap(),
UpsertOutcome::NewSlot(1)
);
assert_eq!(arena.vector_values(0), first);
assert_eq!(arena.vector_values(1), second);
assert_eq!(arena.slot_of_key("key"), Some(1));
assert!(!arena.is_alive(0));
assert_eq!(arena.live_count(), 1);
assert_eq!(arena.slot_count(), 2);
}
#[test]
fn new_keys_never_reuse_retired_slots() {
let mut arena = arena_with_keys(8, &["a", "b", "c"]);
assert_eq!(arena.remove("a"), Some(0));
assert_eq!(arena.remove("c"), Some(2));
assert_eq!(
arena.upsert("d", &seeded_vector(4, 8)).unwrap(),
UpsertOutcome::NewSlot(3)
);
assert_eq!(
arena.upsert("e", &seeded_vector(5, 8)).unwrap(),
UpsertOutcome::NewSlot(4)
);
assert_eq!(
arena.upsert("f", &seeded_vector(6, 8)).unwrap(),
UpsertOutcome::NewSlot(5)
);
}
#[test]
fn remove_is_noop_for_absent_key() {
let mut arena = arena_with_keys(8, &["a"]);
assert_eq!(arena.remove("missing"), None);
assert_eq!(arena.remove("a"), Some(0));
assert_eq!(arena.remove("a"), None);
}
#[test]
fn lookups_work_in_both_directions() {
let mut arena = arena_with_keys(8, &["a", "b"]);
assert_eq!(arena.slot_of_key("b"), Some(1));
assert_eq!(arena.key_of_slot(1), Some("b"));
assert!(arena.is_alive(1));
arena.remove("b");
assert_eq!(arena.slot_of_key("b"), None);
assert_eq!(arena.key_of_slot(1), None);
assert!(!arena.is_alive(1));
assert_eq!(arena.key_of_slot(999), None);
assert!(!arena.is_alive(999));
}
#[test]
fn tracks_live_and_dead_counts() {
let mut arena = arena_with_keys(8, &["a", "b", "c"]);
assert_eq!(arena.live_count(), 3);
assert_eq!(arena.dead_count(), 0);
assert!(!arena.is_empty());
arena.remove("b");
assert_eq!(arena.live_count(), 2);
assert_eq!(arena.dead_count(), 1);
arena.upsert("d", &seeded_vector(9, 8)).unwrap();
assert_eq!(arena.live_count(), 3);
assert_eq!(arena.dead_count(), 1);
assert_eq!(arena.live_slots().collect::<Vec<_>>(), vec![0, 2, 3]);
}
#[test]
fn dead_slot_vectors_stay_readable_for_routing() {
let mut arena = VectorArena::new(8).unwrap();
let vector = seeded_vector(3, 8);
arena.upsert("a", &vector).unwrap();
arena.remove("a");
assert_eq!(arena.vector_values(0), vector);
}
#[test]
fn readding_a_removed_key_appends_like_any_new_key() {
let mut arena = arena_with_keys(8, &["a", "b"]);
assert_eq!(arena.remove("a"), Some(0));
let vector = seeded_vector(9, 8);
assert_eq!(
arena.upsert("a", &vector).unwrap(),
UpsertOutcome::NewSlot(2)
);
assert_eq!(arena.key_of_slot(0), None);
assert_eq!(arena.key_of_slot(2), Some("a"));
assert_eq!(arena.vector_values(2), vector);
assert_eq!(arena.live_count(), 2);
assert_eq!(arena.dead_count(), 1);
assert_eq!(arena.remove("b"), Some(1));
assert_eq!(
arena.upsert("c", &seeded_vector(10, 8)).unwrap(),
UpsertOutcome::NewSlot(3)
);
assert_eq!(
arena.upsert("b", &seeded_vector(11, 8)).unwrap(),
UpsertOutcome::NewSlot(4)
);
}
#[test]
fn identical_operation_sequences_assign_identical_slots() {
let mut first = VectorArena::new(8).unwrap();
let mut second = VectorArena::new(8).unwrap();
let mut state = 42u64;
let mut keys: Vec<String> = Vec::new();
let mut removed: Vec<String> = Vec::new();
let mut operations = Vec::new();
for step in 0..2000 {
let roll = splitmix64(&mut state);
match roll % 4 {
0 if !keys.is_empty() => {
let key = keys.remove(roll as usize % keys.len());
removed.push(key.clone());
operations.push((key, None));
}
1 if !removed.is_empty() => {
let key = removed.remove(roll as usize % removed.len());
keys.push(key.clone());
operations.push((key, Some(seeded_vector(roll, 8))));
}
_ => {
let key = format!("key-{step}");
keys.push(key.clone());
operations.push((key, Some(seeded_vector(roll, 8))));
}
}
}
for (key, vector) in &operations {
match vector {
Some(values) => {
let a = first.upsert(key, values).unwrap();
let b = second.upsert(key, values).unwrap();
assert_eq!(a, b);
}
None => assert_eq!(first.remove(key), second.remove(key)),
}
}
assert_eq!(first.live_count(), second.live_count());
assert_eq!(first.slot_count(), second.slot_count());
for slot in first.live_slots() {
assert_eq!(first.key_of_slot(slot), second.key_of_slot(slot));
assert_eq!(first.vector_values(slot), second.vector_values(slot));
}
}
#[test]
fn compact_in_place_repacks_live_entries_densely_in_order() {
let mut arena = VectorArena::new(8).unwrap();
for index in 0..10u64 {
arena
.upsert(&format!("key-{index}"), &seeded_vector(index, 8))
.unwrap();
}
assert_eq!(arena.remove("key-0"), Some(0));
assert_eq!(arena.remove("key-4"), Some(4));
assert_eq!(arena.remove("key-9"), Some(9));
assert_eq!(
arena.upsert("key-5", &seeded_vector(50, 8)).unwrap(),
UpsertOutcome::NewSlot(10)
);
assert_eq!(
arena.upsert("extra", &seeded_vector(60, 8)).unwrap(),
UpsertOutcome::NewSlot(11)
);
assert_eq!(arena.remove("key-2"), Some(2));
let expected: Vec<(String, Vec<f32>)> = arena
.live_slots()
.map(|slot| {
(
arena.key_of_slot(slot).unwrap().to_string(),
arena.vector_values(slot),
)
})
.collect();
assert_eq!(expected.len(), 7);
assert_eq!(arena.dead_count(), 5);
arena.compact_in_place();
assert_eq!(arena.live_count(), 7);
assert_eq!(arena.slot_count(), 7);
assert_eq!(arena.dead_count(), 0);
for (index, (key, vector)) in expected.iter().enumerate() {
let slot = index as u32;
assert!(arena.is_alive(slot));
assert_eq!(arena.key_of_slot(slot), Some(key.as_str()));
assert_eq!(arena.slot_of_key(key), Some(slot));
assert_eq!(&arena.vector_values(slot), vector);
}
assert!(!arena.is_alive(7));
assert_eq!(
arena.live_slots().collect::<Vec<_>>(),
(0..7).collect::<Vec<_>>()
);
assert_eq!(
arena.upsert("fresh", &seeded_vector(70, 8)).unwrap(),
UpsertOutcome::NewSlot(7)
);
let retired = arena.slot_of_key("key-5").unwrap();
assert_eq!(arena.remove("key-5"), Some(retired));
assert_eq!(arena.dead_count(), 1);
assert_eq!(
arena.upsert("reused", &seeded_vector(80, 8)).unwrap(),
UpsertOutcome::NewSlot(8)
);
}
#[test]
fn compact_in_place_moves_vectors_across_chunks_and_frees_the_tail() {
let mut arena = VectorArena::new(8).unwrap();
let count = VECTORS_PER_CHUNK + 300;
for index in 0..count as u64 {
arena
.upsert(&format!("key-{index}"), &seeded_vector(index, 8))
.unwrap();
}
assert_eq!(arena.storage.chunk_count(), 2);
for index in (0..1000u64).step_by(2) {
assert!(arena.remove(&format!("key-{index}")).is_some());
}
let expected: Vec<(String, Vec<f32>)> = arena
.live_slots()
.map(|slot| {
(
arena.key_of_slot(slot).unwrap().to_string(),
arena.vector_values(slot),
)
})
.collect();
arena.compact_in_place();
let live = count - 500;
assert_eq!(arena.live_count(), live);
assert_eq!(arena.slot_count(), live);
assert_eq!(arena.storage.chunk_count(), 1);
assert_eq!(arena.alive.len(), live.div_ceil(64));
for (index, (key, vector)) in expected.iter().enumerate() {
assert_eq!(arena.slot_of_key(key), Some(index as u32));
assert_eq!(&arena.vector_values(index as u32), vector);
}
for slot in arena.live_slots() {
assert_eq!(lane_address(arena.stored_query(slot)) % 32, 0);
}
}
#[test]
fn compact_in_place_with_no_dead_slots_preserves_everything() {
let mut arena = arena_with_keys(8, &["a", "b", "c"]);
arena.compact_in_place();
assert_eq!(arena.live_count(), 3);
assert_eq!(arena.slot_count(), 3);
assert_eq!(arena.dead_count(), 0);
for (index, key) in ["a", "b", "c"].iter().enumerate() {
assert_eq!(arena.key_of_slot(index as u32), Some(*key));
assert_eq!(
arena.vector_values(index as u32),
seeded_vector(index as u64, 8)
);
}
assert_eq!(
arena.upsert("d", &seeded_vector(9, 8)).unwrap(),
UpsertOutcome::NewSlot(3)
);
}
#[test]
fn compact_in_place_empties_a_fully_dead_arena() {
let mut arena = arena_with_keys(8, &["a", "b", "c"]);
for key in ["a", "b", "c"] {
assert!(arena.remove(key).is_some());
}
arena.compact_in_place();
assert!(arena.is_empty());
assert_eq!(arena.live_count(), 0);
assert_eq!(arena.slot_count(), 0);
assert_eq!(arena.dead_count(), 0);
assert_eq!(arena.storage.chunk_count(), 0);
assert!(arena.alive.is_empty());
assert_eq!(
arena.upsert("d", &seeded_vector(4, 8)).unwrap(),
UpsertOutcome::NewSlot(0)
);
assert_eq!(arena.vector_values(0), seeded_vector(4, 8));
}
#[test]
fn compact_in_place_reclaims_key_map_capacity() {
let mut arena = VectorArena::new(8).unwrap();
for index in 0..5000u64 {
arena
.upsert(&format!("key-{index}"), &seeded_vector(index, 8))
.unwrap();
}
for index in 0..4900u64 {
assert!(arena.remove(&format!("key-{index}")).is_some());
}
let before = arena.keys_to_slots.capacity();
assert!(before > arena.live_count() * 4);
arena.compact_in_place();
let after = arena.keys_to_slots.capacity();
assert_eq!(arena.live_count(), 100);
assert!(after < before);
assert!(after >= arena.live_count());
assert!(after <= arena.live_count() * 4);
assert_eq!(arena.slot_of_key("key-4999"), Some(99));
}
#[test]
fn compact_in_place_on_an_empty_arena_is_a_noop() {
let mut arena = VectorArena::new(8).unwrap();
arena.compact_in_place();
assert!(arena.is_empty());
assert_eq!(arena.slot_count(), 0);
assert_eq!(
arena.upsert("a", &seeded_vector(0, 8)).unwrap(),
UpsertOutcome::NewSlot(0)
);
}
#[test]
fn grows_across_chunks_with_correct_addressing() {
let mut arena = VectorArena::new(8).unwrap();
for index in 0..4100u64 {
arena
.upsert(&format!("key-{index}"), &seeded_vector(index, 8))
.unwrap();
}
assert_eq!(arena.slot_count(), 4100);
assert_eq!(arena.live_count(), 4100);
assert_eq!(arena.slot_of_key("key-4099"), Some(4099));
assert_eq!(arena.key_of_slot(4097), Some("key-4097"));
assert_eq!(arena.vector_values(0), seeded_vector(0, 8));
assert_eq!(arena.vector_values(4099), seeded_vector(4099, 8));
}
#[test]
fn every_slotted_vector_is_32_byte_aligned() {
let mut arena = VectorArena::new(16).unwrap();
for index in 0..4200u64 {
arena
.upsert(&format!("key-{index}"), &seeded_vector(index, 16))
.unwrap();
}
for slot in arena.live_slots() {
assert_eq!(lane_address(arena.stored_query(slot)) % 32, 0);
}
}
#[test]
fn every_i8_slotted_vector_is_32_byte_aligned_across_chunks() {
let mut arena = VectorArena::with_storage(32, StorageKind::I8).unwrap();
for index in 0..4200u64 {
arena
.upsert(&format!("key-{index}"), &seeded_vector(index, 32))
.unwrap();
}
assert_eq!(arena.storage.chunk_count(), 2);
assert_eq!(arena.slot_of_key("key-4199"), Some(4199));
for slot in arena.live_slots() {
assert_eq!(lane_address(arena.stored_query(slot)) % 32, 0);
}
let Storage::I8 { scales, .. } = &arena.storage else {
panic!("expected i8 storage");
};
assert_eq!(scales.len(), 4200);
}
#[test]
fn distances_are_cosine() {
let mut arena = VectorArena::new(16).unwrap();
arena.upsert("x", &basis_vector(16, 0)).unwrap();
arena.upsert("y", &basis_vector(16, 9)).unwrap();
assert_eq!(arena.distance_between_slots(0, 0), 0.0);
assert_eq!(arena.distance_between_slots(0, 1), 1.0);
let query = arena.pack_query(&basis_vector(16, 0)).unwrap();
assert_eq!(arena.distance_to_query(query.as_query(), 0), 0.0);
assert_eq!(arena.distance_to_query(query.as_query(), 1), 1.0);
}
#[test]
fn i8_upsert_quantizes_and_reads_back_within_half_a_step() {
let dims = 64;
let mut arena = VectorArena::with_storage(dims, StorageKind::I8).unwrap();
for seed in 0..20u64 {
let values = seeded_unit_vector(seed, dims);
let key = format!("key-{seed}");
assert_eq!(
arena.upsert(&key, &values).unwrap(),
UpsertOutcome::NewSlot(seed as u32)
);
let expected = StoredVector::quantize(&values);
assert_eq!(arena.stored_vector(seed as u32), expected);
let StoredVector::I8 { scale, .. } = expected else {
panic!("expected i8 storage");
};
let read_back = arena.vector_values(seed as u32);
assert_eq!(read_back.len(), dims);
for (original, restored) in values.iter().zip(&read_back) {
assert!((original - restored).abs() <= scale / 2.0 + scale * 1.0e-6);
}
}
assert_eq!(arena.storage_kind(), StorageKind::I8);
}
#[test]
fn i8_payloads_are_stored_and_returned_bit_for_bit() {
let dims = 32;
let mut arena = VectorArena::with_storage(dims, StorageKind::I8).unwrap();
let mut values: Vec<i8> = (0..dims as i32)
.map(|index| (index * 9 - 127) as i8)
.collect();
values[0] = -127;
values[1] = 127;
values[2] = 0;
values[3] = -1;
let scale = f32::from_bits(0x3a1f_8f3c);
let payload = VectorPayload::I8 {
scale,
values: &values,
};
assert_eq!(
arena.upsert_payload("exact", payload).unwrap(),
UpsertOutcome::NewSlot(0)
);
let (stored_scale, stored_values) = stored_i8(&arena, 0);
assert_eq!(stored_scale.to_bits(), scale.to_bits());
assert_eq!(stored_values, values);
assert_eq!(arena.vector_values(0), dequantize(scale, &values));
assert_eq!(
arena.upsert_payload("exact", payload).unwrap(),
UpsertOutcome::Unchanged(0)
);
assert_eq!(stored_i8(&arena, 0), (scale, values.clone()));
assert_eq!(arena.remove("exact"), Some(0));
assert_eq!(stored_i8(&arena, 0), (scale, values.clone()));
let other = VectorPayload::I8 {
scale: 0.5,
values: &vec![3i8; dims],
};
assert_eq!(
arena.upsert_payload("recycled", other).unwrap(),
UpsertOutcome::NewSlot(1)
);
assert_eq!(stored_i8(&arena, 0), (scale, values));
assert_eq!(stored_i8(&arena, 1), (0.5, vec![3i8; dims]));
}
#[test]
fn i8_distances_follow_the_quantized_cosine_formula() {
let dims = 64;
let mut arena = VectorArena::with_storage(dims, StorageKind::I8).unwrap();
let a = seeded_unit_vector(11, dims);
let b = seeded_unit_vector(12, dims);
arena.upsert("a", &a).unwrap();
arena.upsert("b", &b).unwrap();
let (_, values_a) = stored_i8(&arena, 0);
let (_, values_b) = stored_i8(&arena, 1);
let dot = |x: &[i8], y: &[i8]| -> f64 {
x.iter()
.zip(y)
.map(|(x, y)| f64::from(*x) * f64::from(*y))
.sum()
};
let norm = |values: &[i8]| dot(values, values).sqrt();
let expected =
(1.0 - dot(&values_a, &values_b) / (norm(&values_a) * norm(&values_b))) as f32;
assert_eq!(
arena.distance_between_slots(0, 1).to_bits(),
expected.to_bits()
);
assert_eq!(
arena.distance_between_slots(1, 0).to_bits(),
expected.to_bits()
);
let query = arena.pack_query(&a).unwrap();
assert_eq!(
arena.distance_to_query(query.as_query(), 1).to_bits(),
expected.to_bits()
);
assert_eq!(
arena.distance_to_query(arena.stored_query(0), 1).to_bits(),
expected.to_bits()
);
let f32_distance = 1.0 - a.iter().zip(&b).map(|(x, y)| x * y).sum::<f32>();
assert!((expected - f32_distance).abs() < 0.01);
assert!(arena.distance_between_slots(0, 0).abs() < 1.0e-6);
}
#[test]
fn i8_zero_vector_stores_scale_zero_and_sits_at_unit_distance() {
let dims = 32;
let mut arena = VectorArena::with_storage(dims, StorageKind::I8).unwrap();
arena.upsert("zero", &vec![0.0; dims]).unwrap();
arena.upsert("unit", &basis_vector(dims, 5)).unwrap();
assert_eq!(stored_i8(&arena, 0), (0.0, vec![0i8; dims]));
assert_eq!(arena.vector_values(0), vec![0.0; dims]);
assert_eq!(arena.distance_between_slots(0, 1), 1.0);
assert_eq!(arena.distance_between_slots(0, 0), 1.0);
let query = arena.pack_query(&basis_vector(dims, 5)).unwrap();
assert_eq!(arena.distance_to_query(query.as_query(), 0), 1.0);
let zero_query = arena.pack_query(&vec![0.0; dims]).unwrap();
assert!(zero_query.as_query().is_finite());
assert_eq!(arena.distance_to_query(zero_query.as_query(), 1), 1.0);
}
#[test]
fn non_finite_queries_pack_as_non_finite_for_both_storages() {
let f32_arena = VectorArena::new(32).unwrap();
let i8_arena = VectorArena::with_storage(32, StorageKind::I8).unwrap();
for bad in [f32::NAN, f32::INFINITY, f32::NEG_INFINITY] {
let mut values = seeded_vector(1, 32);
values[7] = bad;
assert!(
!f32_arena
.pack_query(&values)
.unwrap()
.as_query()
.is_finite()
);
assert!(!i8_arena.pack_query(&values).unwrap().as_query().is_finite());
}
let values = seeded_vector(2, 32);
assert!(
f32_arena
.pack_query(&values)
.unwrap()
.as_query()
.is_finite()
);
assert!(i8_arena.pack_query(&values).unwrap().as_query().is_finite());
}
#[test]
fn i8_compact_in_place_moves_scales_with_their_vectors_across_chunks() {
let dims = 32;
let mut arena = VectorArena::with_storage(dims, StorageKind::I8).unwrap();
let count = VECTORS_PER_CHUNK + 200;
for index in 0..count as u64 {
arena
.upsert(&format!("key-{index}"), &seeded_vector(index, dims))
.unwrap();
}
assert_eq!(arena.storage.chunk_count(), 2);
for index in (0..900u64).step_by(3) {
assert!(arena.remove(&format!("key-{index}")).is_some());
}
let expected: Vec<(String, StoredVector)> = arena
.live_slots()
.map(|slot| {
(
arena.key_of_slot(slot).unwrap().to_string(),
arena.stored_vector(slot),
)
})
.collect();
arena.compact_in_place();
assert_eq!(arena.live_count(), count - 300);
assert_eq!(arena.slot_count(), count - 300);
assert_eq!(arena.storage.chunk_count(), 1);
let Storage::I8 { scales, .. } = &arena.storage else {
panic!("expected i8 storage");
};
assert_eq!(scales.len(), count - 300);
for (index, (key, stored)) in expected.iter().enumerate() {
let slot = index as u32;
assert_eq!(arena.slot_of_key(key), Some(slot));
assert_eq!(&arena.stored_vector(slot), stored);
assert_eq!(lane_address(arena.stored_query(slot)) % 32, 0);
}
assert_eq!(
arena.upsert("fresh", &seeded_vector(9999, dims)).unwrap(),
UpsertOutcome::NewSlot((count - 300) as u32)
);
}
#[test]
fn i8_arena_reports_a_quarter_of_the_f32_vector_memory() {
let dims = 512;
let mut f32_arena = VectorArena::new(dims).unwrap();
let mut i8_arena = VectorArena::with_storage(dims, StorageKind::I8).unwrap();
assert_eq!(f32_arena.vector_memory_bytes(), 0);
assert_eq!(i8_arena.vector_memory_bytes(), 0);
for index in 0..100u64 {
let values = seeded_vector(index, dims);
f32_arena.upsert(&format!("key-{index}"), &values).unwrap();
i8_arena.upsert(&format!("key-{index}"), &values).unwrap();
}
let norm_bytes = f32_arena.norms.capacity() * size_of::<f64>();
assert_eq!(i8_arena.norms.capacity() * size_of::<f64>(), norm_bytes);
assert_eq!(
f32_arena.vector_memory_bytes(),
VECTORS_PER_CHUNK * dims * size_of::<f32>() + norm_bytes
);
assert_eq!(
i8_arena.vector_memory_bytes(),
VECTORS_PER_CHUNK * dims + 100 * size_of::<f32>() + norm_bytes
);
}
}