Skip to content

armgit / ente

Public Imported from GitHub
0

πŸ’š End-to-end encrypted cloud for everything.

19.0 KB
Raw Blame
use super::{StorageKind, VecDbError};

pub(crate) const LANE_WIDTH: usize = 8;
pub(crate) const LANE_WIDTH_I8: usize = 32;
const I8_LIMIT: f32 = 127.0;
pub(crate) const MAX_DIMS_I8: usize =
    (i32::MAX / ((I8_LIMIT as i32) * (I8_LIMIT as i32))) as usize / LANE_WIDTH_I8 * LANE_WIDTH_I8;

pub(crate) fn is_within_quantized_range(value: i8) -> bool {
    i32::from(value).abs() <= I8_LIMIT as i32
}

#[repr(C, align(32))]
#[derive(Clone, Copy)]
pub(crate) struct Lane([f32; LANE_WIDTH]);

impl Lane {
    pub(crate) const ZERO: Self = Self([0.0; LANE_WIDTH]);

    pub(crate) fn to_array(self) -> [f32; LANE_WIDTH] {
        self.0
    }
}

impl From<[f32; LANE_WIDTH]> for Lane {
    fn from(values: [f32; LANE_WIDTH]) -> Self {
        Self(values)
    }
}

#[repr(C, align(32))]
#[derive(Clone, Copy)]
pub(crate) struct LaneI8([i8; LANE_WIDTH_I8]);

impl LaneI8 {
    pub(crate) const ZERO: Self = Self([0; LANE_WIDTH_I8]);

    pub(crate) fn to_array(self) -> [i8; LANE_WIDTH_I8] {
        self.0
    }
}

impl From<[i8; LANE_WIDTH_I8]> for LaneI8 {
    fn from(values: [i8; LANE_WIDTH_I8]) -> Self {
        Self(values)
    }
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub(crate) enum VectorPayload<'a> {
    F32(&'a [f32]),
    I8 { scale: f32, values: &'a [i8] },
}

impl VectorPayload<'_> {
    pub(crate) fn bitwise_eq(self, other: Self) -> bool {
        match (self, other) {
            (Self::F32(first), Self::F32(second)) => {
                first.len() == second.len()
                    && first
                        .iter()
                        .zip(second)
                        .all(|(a, b)| a.to_bits() == b.to_bits())
            }
            (
                Self::I8 {
                    scale: first_scale,
                    values: first,
                },
                Self::I8 {
                    scale: second_scale,
                    values: second,
                },
            ) => first_scale.to_bits() == second_scale.to_bits() && first == second,
            _ => false,
        }
    }

    pub(crate) fn storage(&self) -> StorageKind {
        match self {
            Self::F32(_) => StorageKind::F32,
            Self::I8 { .. } => StorageKind::I8,
        }
    }

    pub(crate) fn dims(&self) -> usize {
        match self {
            Self::F32(values) => values.len(),
            Self::I8 { values, .. } => values.len(),
        }
    }
}

#[derive(Debug, Clone, PartialEq)]
pub(crate) enum StoredVector {
    F32(Vec<f32>),
    I8 { scale: f32, values: Vec<i8> },
}

impl StoredVector {
    pub(crate) fn quantize(values: &[f32]) -> Self {
        let finite = values.iter().all(|value| value.is_finite());
        let max_abs = values
            .iter()
            .fold(0.0f32, |acc, value| acc.max(value.abs()));
        let scale = if finite { max_abs / I8_LIMIT } else { f32::NAN };
        let quantized = if scale > 0.0 {
            values
                .iter()
                .map(|value| (value / scale).round().clamp(-I8_LIMIT, I8_LIMIT) as i8)
                .collect()
        } else {
            vec![0; values.len()]
        };
        Self::I8 {
            scale,
            values: quantized,
        }
    }

    pub(crate) fn as_payload(&self) -> VectorPayload<'_> {
        match self {
            Self::F32(values) => VectorPayload::F32(values),
            Self::I8 { scale, values } => VectorPayload::I8 {
                scale: *scale,
                values,
            },
        }
    }
}

pub(crate) fn quantize_for(storage: StorageKind, values: &[f32]) -> Option<StoredVector> {
    match storage {
        StorageKind::F32 => None,
        StorageKind::I8 => Some(StoredVector::quantize(values)),
    }
}

pub(crate) fn dequantize(scale: f32, values: &[i8]) -> Vec<f32> {
    values
        .iter()
        .map(|&value| f32::from(value) * scale)
        .collect()
}

pub(crate) fn validate_dims(dims: usize, storage: StorageKind) -> Result<(), VecDbError> {
    if dims == 0
        || !dims.is_multiple_of(storage.lane_width())
        || u32::try_from(dims).is_err()
        || dims > storage.max_dims()
    {
        return Err(VecDbError::InvalidDimensions { dims, storage });
    }
    Ok(())
}

pub(crate) fn splitmix64(state: &mut u64) -> u64 {
    *state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
    let mut mixed = *state;
    mixed = (mixed ^ (mixed >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    mixed = (mixed ^ (mixed >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    mixed ^ (mixed >> 31)
}

pub(crate) trait VectorKernel {
    type Lane;

    fn dot(a: &[Self::Lane], b: &[Self::Lane]) -> f32;
}

pub(crate) struct F32Kernel;

impl VectorKernel for F32Kernel {
    type Lane = Lane;

    fn dot(a: &[Lane], b: &[Lane]) -> f32 {
        debug_assert_eq!(a.len(), b.len());
        let mut partials = [0.0f32; LANE_WIDTH];
        for (x, y) in a.iter().zip(b.iter()) {
            for (partial, (left, right)) in partials.iter_mut().zip(x.0.iter().zip(&y.0)) {
                *partial += left * right;
            }
        }
        partials.iter().sum()
    }
}

pub(crate) struct I8Kernel;

impl I8Kernel {
    pub(crate) fn dot(a: &[LaneI8], b: &[LaneI8]) -> i32 {
        debug_assert_eq!(a.len(), b.len());
        let mut total = 0i32;
        for (x, y) in a.iter().zip(b) {
            let mut lane = 0i32;
            for (left, right) in x.0.iter().zip(&y.0) {
                lane += i32::from(*left) * i32::from(*right);
            }
            total += lane;
        }
        total
    }
}

pub(crate) fn pack_lanes_i8(values: &[i8]) -> Vec<LaneI8> {
    debug_assert_eq!(values.len() % LANE_WIDTH_I8, 0);
    let mut lanes = vec![LaneI8::ZERO; values.len() / LANE_WIDTH_I8];
    pack_lanes_i8_into(values, &mut lanes);
    lanes
}

pub(crate) fn pack_lanes_i8_into(values: &[i8], lanes: &mut [LaneI8]) {
    debug_assert_eq!(values.len(), lanes.len() * LANE_WIDTH_I8);
    let (groups, remainder) = values.as_chunks::<LANE_WIDTH_I8>();
    debug_assert!(remainder.is_empty());
    for (lane, group) in lanes.iter_mut().zip(groups) {
        *lane = LaneI8::from(*group);
    }
}

pub(crate) fn unpack_lanes_i8(lanes: &[LaneI8]) -> Vec<i8> {
    let mut values = Vec::with_capacity(lanes.len() * LANE_WIDTH_I8);
    for lane in lanes {
        values.extend_from_slice(&lane.to_array());
    }
    values
}

pub(crate) fn pack_lanes(values: &[f32]) -> Vec<Lane> {
    debug_assert_eq!(values.len() % LANE_WIDTH, 0);
    let mut lanes = vec![Lane::ZERO; values.len() / LANE_WIDTH];
    pack_lanes_into(values, &mut lanes);
    lanes
}

pub(crate) fn pack_lanes_into(values: &[f32], lanes: &mut [Lane]) {
    debug_assert_eq!(values.len(), lanes.len() * LANE_WIDTH);
    let (groups, remainder) = values.as_chunks::<LANE_WIDTH>();
    debug_assert!(remainder.is_empty());
    for (lane, group) in lanes.iter_mut().zip(groups) {
        *lane = Lane::from(*group);
    }
}

pub(crate) fn unpack_lanes(lanes: &[Lane]) -> Vec<f32> {
    let mut values = Vec::with_capacity(lanes.len() * LANE_WIDTH);
    for lane in lanes {
        values.extend_from_slice(&lane.to_array());
    }
    values
}

#[cfg(test)]
mod tests {
    use super::*;

    fn seeded_values(seed: u64, count: usize) -> Vec<f32> {
        let mut state = seed;
        (0..count)
            .map(|index| {
                let unit = (splitmix64(&mut state) >> 40) as f32 / (1u64 << 24) as f32;
                let signed = unit * 2.0 - 1.0;
                match index % 5 {
                    0 => signed * 1.0e6,
                    1 => signed * 1.0e-6,
                    _ => signed,
                }
            })
            .collect()
    }

    fn reference_dot(a: &[f32], b: &[f32]) -> f32 {
        let mut partials = [0.0f32; LANE_WIDTH];
        for (index, (x, y)) in a.iter().zip(b).enumerate() {
            partials[index % LANE_WIDTH] += x * y;
        }
        partials.iter().sum()
    }

    fn basis_vector(dims: usize, axis: usize) -> Vec<f32> {
        let mut values = vec![0.0; dims];
        values[axis] = 1.0;
        values
    }

    #[test]
    fn the_quantized_range_excludes_only_the_int8_minimum() {
        assert!(is_within_quantized_range(I8_LIMIT as i8));
        assert!(is_within_quantized_range(-(I8_LIMIT as i8)));
        assert!(is_within_quantized_range(0));
        assert!(!is_within_quantized_range(i8::MIN));
    }

    #[test]
    fn dot_matches_scalar_reference_bit_exactly() {
        for (dims, seed) in [(128, 11), (192, 22), (512, 33)] {
            let a = seeded_values(seed, dims);
            let b = seeded_values(seed.wrapping_mul(977), dims);
            let simd = F32Kernel::dot(&pack_lanes(&a), &pack_lanes(&b));
            let reference = reference_dot(&a, &b);
            assert!(reference.is_finite());
            assert_ne!(reference, 0.0);
            assert_eq!(simd.to_bits(), reference.to_bits());
        }
    }

    #[test]
    fn dot_of_basis_vectors_is_exact() {
        let e0 = pack_lanes(&basis_vector(128, 0));
        let e1 = pack_lanes(&basis_vector(128, 100));
        assert_eq!(F32Kernel::dot(&e0, &e0), 1.0);
        assert_eq!(F32Kernel::dot(&e0, &e1), 0.0);
    }

    #[test]
    fn pack_unpack_round_trips() {
        let values = seeded_values(99, 512);
        let lanes = pack_lanes(&values);
        assert_eq!(lanes.len(), 64);
        assert_eq!(unpack_lanes(&lanes), values);
    }

    #[test]
    fn packed_lanes_are_32_byte_aligned() {
        assert_eq!(align_of::<Lane>(), 32);
        for dims in [128, 192, 512] {
            let lanes = pack_lanes(&seeded_values(5, dims));
            assert_eq!(lanes.as_ptr() as usize % 32, 0);
        }
    }

    fn seeded_unit_values(seed: u64, count: usize) -> Vec<f32> {
        let mut state = seed;
        let mut values: Vec<f32> = (0..count)
            .map(|_| {
                let unit = (splitmix64(&mut state) >> 40) as f32 / (1u64 << 24) as f32;
                unit * 2.0 - 1.0
            })
            .collect();
        let norm = values.iter().map(|value| value * value).sum::<f32>().sqrt();
        for value in &mut values {
            *value /= norm;
        }
        values
    }

    fn seeded_i8_values(seed: u64, count: usize) -> Vec<i8> {
        let mut state = seed;
        (0..count)
            .map(|_| ((splitmix64(&mut state) % 255) as i64 - 127) as i8)
            .collect()
    }

    fn quantized_parts(values: &[f32]) -> (f32, Vec<i8>) {
        match StoredVector::quantize(values) {
            StoredVector::I8 { scale, values } => (scale, values),
            StoredVector::F32(_) => panic!("quantize must produce i8 storage"),
        }
    }

    #[test]
    fn i8_dot_matches_the_scalar_reference_bit_exactly() {
        for (dims, seed) in [(32, 11), (64, 22), (512, 33)] {
            let a = seeded_i8_values(seed, dims);
            let b = seeded_i8_values(seed.wrapping_mul(977), dims);
            let simd = I8Kernel::dot(&pack_lanes_i8(&a), &pack_lanes_i8(&b));
            let mut partials = [0i32; LANE_WIDTH_I8];
            for (index, (x, y)) in a.iter().zip(&b).enumerate() {
                partials[index % LANE_WIDTH_I8] += i32::from(*x) * i32::from(*y);
            }
            let reference: i32 = partials.iter().sum();
            assert_ne!(reference, 0);
            assert_eq!(simd, reference);
            let saturated = vec![127i8; dims];
            let negated = vec![-127i8; dims];
            assert_eq!(
                I8Kernel::dot(&pack_lanes_i8(&saturated), &pack_lanes_i8(&negated)),
                -(dims as i32) * 127 * 127
            );
        }
    }

    #[test]
    fn i8_dims_are_capped_where_a_saturated_dot_still_fits_i32() {
        assert!(validate_dims(MAX_DIMS_I8, StorageKind::I8).is_ok());
        assert!(validate_dims(MAX_DIMS_I8 + LANE_WIDTH_I8, StorageKind::F32).is_ok());
        assert!(matches!(
            validate_dims(MAX_DIMS_I8 + LANE_WIDTH_I8, StorageKind::I8),
            Err(VecDbError::InvalidDimensions {
                dims,
                storage: StorageKind::I8
            }) if dims == MAX_DIMS_I8 + LANE_WIDTH_I8
        ));
        let saturated_product = i64::from(I8_LIMIT as i32) * i64::from(I8_LIMIT as i32);
        assert!(MAX_DIMS_I8 as i64 * saturated_product <= i64::from(i32::MAX));
        assert!((MAX_DIMS_I8 + LANE_WIDTH_I8) as i64 * saturated_product > i64::from(i32::MAX));
        let saturated = vec![127i8; MAX_DIMS_I8];
        let packed = pack_lanes_i8(&saturated);
        assert_eq!(
            i64::from(I8Kernel::dot(&packed, &packed)),
            MAX_DIMS_I8 as i64 * saturated_product
        );
    }

    #[test]
    fn i8_dot_of_basis_vectors_is_orthogonal_exactly_and_self_within_rounding() {
        let (scale_0, values_0) = quantized_parts(&basis_vector(32, 0));
        let (scale_5, values_5) = quantized_parts(&basis_vector(32, 5));
        assert_eq!(scale_0, 1.0 / 127.0);
        assert_eq!(values_0[0], 127);
        assert!(values_0[1..].iter().all(|&value| value == 0));
        let e0 = pack_lanes_i8(&values_0);
        let e5 = pack_lanes_i8(&values_5);
        assert_eq!(I8Kernel::dot(&e0, &e5), 0);
        assert!((I8Kernel::dot(&e0, &e0) as f32 * scale_0 * scale_0 - 1.0).abs() < 1.0e-6);
        assert_eq!(scale_5, scale_0);
    }

    #[test]
    fn quantize_bounds_every_value_and_maps_the_extreme_component_to_127() {
        for seed in 0..40u64 {
            let values = seeded_values(seed, 128);
            let max_abs = values
                .iter()
                .fold(0.0f32, |acc, value| acc.max(value.abs()));
            let (scale, quantized) = quantized_parts(&values);
            assert_eq!(scale.to_bits(), (max_abs / 127.0).to_bits());
            assert!(quantized.iter().all(|&value| (-127..=127).contains(&value)));
            let extreme = values
                .iter()
                .position(|value| value.abs() == max_abs)
                .unwrap();
            assert_eq!(
                quantized[extreme],
                if values[extreme] > 0.0 { 127 } else { -127 }
            );
            for (value, &q) in values.iter().zip(&quantized) {
                if value.abs() >= scale {
                    assert_eq!(q.signum(), value.signum() as i8);
                }
            }
        }
    }

    #[test]
    fn quantize_is_bit_stable_and_handles_zero_and_non_finite_inputs() {
        let values = seeded_unit_values(7, 512);
        let first = StoredVector::quantize(&values);
        for _ in 0..5 {
            let again = StoredVector::quantize(&values);
            let (
                StoredVector::I8 { scale, values: q },
                StoredVector::I8 {
                    scale: s2,
                    values: q2,
                },
            ) = (&first, &again)
            else {
                panic!("quantize must produce i8 storage");
            };
            assert_eq!(scale.to_bits(), s2.to_bits());
            assert_eq!(q, q2);
        }
        let (zero_scale, zeros) = quantized_parts(&[0.0; 64]);
        assert_eq!(zero_scale.to_bits(), 0.0f32.to_bits());
        assert!(zeros.iter().all(|&value| value == 0));
        let (negative_zero_scale, _) = quantized_parts(&[-0.0; 64]);
        assert_eq!(negative_zero_scale.to_bits(), 0.0f32.to_bits());
        for bad in [f32::NAN, f32::INFINITY, f32::NEG_INFINITY] {
            let mut poisoned = values.clone();
            poisoned[100] = bad;
            let (scale, q) = quantized_parts(&poisoned);
            assert!(scale.is_nan());
            assert!(q.iter().all(|&value| value == 0));
        }
        assert_eq!(quantize_for(StorageKind::F32, &values), None);
        assert_eq!(quantize_for(StorageKind::I8, &values), Some(first));
    }

    #[test]
    fn quantize_pins_half_way_ties_signed_zeros_and_denormals() {
        let mut values = [0.0f32; 32];
        values[..14].copy_from_slice(&[
            127.0,
            2.5,
            -2.5,
            0.5,
            -0.5,
            1.5,
            -1.5,
            126.5,
            -126.5,
            0.0,
            -0.0,
            1.0e-40,
            -1.0e-40,
            f32::MIN_POSITIVE,
        ]);
        let (scale, quantized) = quantized_parts(&values);
        assert_eq!(scale.to_bits(), 1.0f32.to_bits());
        let mut expected = [0i8; 32];
        expected[..9].copy_from_slice(&[127, 3, -3, 1, -1, 2, -2, 127, -127]);
        assert_eq!(quantized, expected);
        let mut tiny = [0.0f32; 32];
        tiny[0] = 1.0e-40;
        tiny[1] = -1.0e-40;
        tiny[2] = f32::from_bits(1);
        let (tiny_scale, tiny_quantized) = quantized_parts(&tiny);
        assert_eq!(tiny_scale.to_bits(), (1.0e-40f32 / 127.0).to_bits());
        assert!(tiny_scale > 0.0);
        assert_eq!(tiny_quantized[0], 127);
        assert_eq!(tiny_quantized[1], -127);
        assert_eq!(tiny_quantized[2], 0);
        assert!(tiny_quantized[3..].iter().all(|&value| value == 0));
        let (min_scale, min_quantized) = quantized_parts(&[f32::from_bits(1); 32]);
        assert_eq!(min_scale.to_bits(), 0.0f32.to_bits());
        assert!(min_quantized.iter().all(|&value| value == 0));
        for _ in 0..3 {
            assert_eq!(quantized_parts(&values), (scale, quantized.clone()));
            assert_eq!(quantized_parts(&tiny), (tiny_scale, tiny_quantized.clone()));
        }
    }

    #[test]
    fn dequantize_stays_within_half_a_step_of_the_input() {
        for (dims, seed) in [(64usize, 1u64), (512, 2), (32, 3)] {
            let values = seeded_unit_values(seed, dims);
            let (scale, quantized) = quantized_parts(&values);
            let restored = dequantize(scale, &quantized);
            assert_eq!(restored.len(), dims);
            for (original, restored) in values.iter().zip(&restored) {
                assert!((original - restored).abs() <= scale / 2.0 + scale * 1.0e-6);
            }
        }
    }

    #[test]
    fn i8_dot_tracks_f32_dot_on_unit_vectors_within_the_bound() {
        let mut max_delta = 0.0f32;
        for (dims, pairs, seed) in [(512usize, 300u64, 0x1000u64), (64, 300, 0x2000)] {
            for pair in 0..pairs {
                let a = seeded_unit_values(seed + pair * 2, dims);
                let b = seeded_unit_values(seed + pair * 2 + 1, dims);
                let f32_dot = F32Kernel::dot(&pack_lanes(&a), &pack_lanes(&b));
                let (scale_a, qa) = quantized_parts(&a);
                let (scale_b, qb) = quantized_parts(&b);
                let i8_dot = I8Kernel::dot(&pack_lanes_i8(&qa), &pack_lanes_i8(&qb)) as f32
                    * scale_a
                    * scale_b;
                let delta = (i8_dot - f32_dot).abs();
                assert!(delta <= 0.01, "dims {dims} pair {pair}: delta {delta}");
                max_delta = max_delta.max(delta);
            }
        }
        assert!(max_delta > 0.0);
        assert!(max_delta <= 0.005, "max delta {max_delta}");
    }

    #[test]
    fn packed_i8_lanes_are_32_byte_aligned_and_round_trip() {
        assert_eq!(align_of::<LaneI8>(), 32);
        assert_eq!(size_of::<LaneI8>(), 32);
        for dims in [32, 64, 512] {
            let values = seeded_i8_values(9, dims);
            let lanes = pack_lanes_i8(&values);
            assert_eq!(lanes.len(), dims / LANE_WIDTH_I8);
            assert_eq!(lanes.as_ptr() as usize % 32, 0);
            assert_eq!(unpack_lanes_i8(&lanes), values);
        }
    }
}