Struct Slice 

pub struct Slice<T, M> { /* private fields */ }

A wrapper for a traditional Rust slice that provides the addition of arbitrary metadata.

Examples

The Slice has several named variants that should be used instead of Slice directly:

• PolySlice: An owning, independently allocated Slice.
• SliceMut: A mutable, reference-like type.
• SliceRef: A const, reference-like type.

use diskann_quantization::{
    alloc::GlobalAllocator,
    meta::slice,
    bits::Unsigned,
};

use diskann_utils::{Reborrow, ReborrowMut};

#[derive(Debug, Default, Clone, Copy, PartialEq)]
struct Metadata {
    value: f32,
}

// Create a new heap-allocated Vector for 4-bit compressions capable of
// holding 3 elements.
//
// In this case, the associated m
let mut v = slice::PolySlice::new_in(3, GlobalAllocator).unwrap();

// We can inspect the underlying bitslice.
let data = v.vector();
assert_eq!(&data, &[0, 0, 0]);
assert_eq!(*v.meta(), Metadata::default(), "expected default metadata value");

// If we want, we can mutably borrow the bitslice and mutate its components.
let mut data = v.vector_mut();
assert_eq!(data.len(), 3);
data[0] = 1;
data[1] = 2;
data[2] = 3;

// Setting the underlying compensation will be visible in the original allocation.
*v.meta_mut() = Metadata { value: 10.5 };

// Check that the changes are visible.
assert_eq!(v.meta().value, 10.5);
assert_eq!(&v.vector(), &[1, 2, 3]);

Constructing a SliceMut From Components

The following example shows how to assemble a SliceMut from raw parts.

use diskann_quantization::meta::slice;

// For exposition purposes, we will use a slice of `u8` and `f32` as the metadata.
let mut data = vec![0u8; 4];
let mut metadata: f32 = 0.0;
{
    let mut v = slice::SliceMut::new(data.as_mut_slice(), &mut metadata);

    // Through `v`, we can set all the components in `slice` and the compensation.
    *v.meta_mut() = 123.4;
    let mut data = v.vector_mut();
    data[0] = 1;
    data[1] = 2;
    data[2] = 3;
    data[3] = 4;
}

// Now we can check that the changes made internally are visible.
assert_eq!(&data, &[1, 2, 3, 4]);
assert_eq!(metadata, 123.4);

Canonical Layout

When the slice element type T and metadata type M are both bytemuck::Pod, SliceRef and SliceMut support layout canonicalization, where a raw slice can be used as the backing store for such vectors, enabling inline storage.

The layout is specified by:

• A base alignment of the maximum alignments of T and M.
• The first M bytes contain the metadata.
• Padding if necessary to reach the alignment of T.
• The values of type T stored contiguously.

The canonical layout needs the following properties:

• T: bytemuck::Pod and `M: bytemuck::Pod: For safely storing and retrieving.
• The length for a vector with N dimensions must be equal to the value returned from SliceRef::canonical_bytes.
• The alignment of the base pointer must be equal to SliceRef::canonical_align().

The following functions can be used to construct slices from raw slices:

• SliceRef::from_canonical
• SliceMut::from_canonical_mut

An example is shown below.

use diskann_quantization::{
    alloc::{AlignedAllocator, Poly},
    meta::slice,
    num::PowerOfTwo,
};

let dim = 3;

// Since we don't control the alignment of the returned pointer, we need to oversize it.
let bytes = slice::SliceRef::<u16, f32>::canonical_bytes(dim);
let align = slice::SliceRef::<u16, f32>::canonical_align();
let mut data = Poly::broadcast(
    0u8,
    bytes,
    AlignedAllocator::new(align)
).unwrap();

// Construct a mutable compensated vector over the slice.
let mut v = slice::SliceMut::<u16, f32>::from_canonical_mut(&mut data, dim).unwrap();
*v.meta_mut() = 1.0;
v.vector_mut().copy_from_slice(&[1, 2, 3]);

// Reconstruct a constant CompensatedVector.
let cv = slice::SliceRef::<u16, f32>::from_canonical(&data, dim).unwrap();
assert_eq!(*cv.meta(), 1.0);
assert_eq!(&cv.vector(), &[1, 2, 3]);

Implementations

impl<T, M> Slice<T, M>

pub fn new<U>(slice: T, meta: U) -> Self

where U: Into<M>,

Construct a new Slice over the components.

pub fn meta(&self) -> &M::Target

where M: Deref,

Return the metadata value for this vector.

pub fn meta_mut(&mut self) -> &mut M::Target

where M: DerefMut,

Get a mutable reference to the metadata component.

impl<T, M, U, V> Slice<T, M>

where T: Deref<Target = [U]>, M: Deref<Target = V>,

pub fn len(&self) -> usize

Return the number of dimensions of in the slice

pub fn is_empty(&self) -> bool

Return whether or not the vector is empty.

pub fn vector(&self) -> &[U]

Borrow the data slice.

pub fn vector_mut(&mut self) -> &mut [U]

where T: DerefMut,

Borrow the integer compressed vector.

pub const fn canonical_align() -> PowerOfTwo

Return the necessary alignment for the base pointer required for SliceRef::from_canonical and SliceMut::from_canonical_mut.

The return value is guaranteed to be a power of two.

pub const fn canonical_bytes(count: usize) -> usize

Return the number of bytes required to store count elements plus metadata in a canonical layout.

See: SliceRef::from_canonical, SliceMut::from_canonical_mut.

impl<T, A, M> Slice<Poly<[T], A>, Owned<M>>

where A: AllocatorCore, T: Default, M: Default,

pub fn new_in(len: usize, allocator: A) -> Result<Self, AllocatorError>

Create a new owned VectorBase with its metadata default initialized.

impl<'a, T, M> Slice<&'a [T], Ref<'a, M>>

where T: Pod, M: Pod,

pub fn from_canonical(data: &'a [u8], dim: usize) -> Result<Self, NotCanonical>

Construct an instance of Self viewing data as the canonical layout for a vector. The canonical layout is as follows:

• std::mem::size_of::<T>().max(std::mem::size_of::<M>()) for the metadata.
• Necessary additional padding to achieve the alignment requirements for T.
• std::mem::size_of::<T>() * dim for the slice.

Returns an error if:

• data is not aligned to Self::canonical_align().
• data.len() != Self::canonical_bytes(dim)`.

pub unsafe fn from_canonical_unchecked(data: &'a [u8], dim: usize) -> Self

Construct a VectorRef from the raw data.

Safety

• data.as_ptr() must be aligned to Self::canonical_align().
• data.len() must be equal to Self::canonical_bytes(dim).

This invariant is checked in debug builds and will panic if not satisfied.

impl<'a, T, M> Slice<&'a mut [T], Mut<'a, M>>

where T: Pod, M: Pod,

pub fn from_canonical_mut( data: &'a mut [u8], dim: usize, ) -> Result<Self, NotCanonical>

Construct an instance of Self viewing data as the canonical layout for a vector. The canonical layout is as follows:

• std::mem::size_of::<T>().max(std::mem::size_of::<M>()) for the metadata.
• Necessary additional padding to achieve the alignment requirements for T.
• std::mem::size_of::<T>() * dim for the slice.

Returns an error if:

• data is not aligned to Self::canonical_align().
• data.len() != Self::canonical_bytes(dim)`.

Trait Implementations

impl<T: Clone, M: Clone> Clone for Slice<T, M>

fn clone(&self) -> Slice<T, M>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<'a, T> CompressInto<&[T], Slice<&'a mut [f32], Mut<'a, FullQueryMeta>>> for MinMaxQuantizer

where T: Copy + Into<f32>,

fn compress_into( &self, from: &[T], to: FullQueryMut<'a>, ) -> Result<(), Self::Error>

Compress the input vector from into a FullQueryMut to.

This method simply applies the transformation to the input without any compression.

Error

Returns an error if the input contains NaN.

Panics

Panics if:

• from.len() != self.dim(): Vector to be compressed must have the same dimensionality as the quantizer.
• to.len() != self.output_dim(): Compressed vector must have the same dimensionality as the quantizer.

type Error = InputContainsNaN

Errors that may occur during compression.

type Output = ()

An output type resulting from compression.

impl<A> CompressIntoWith<&[f32], Slice<&mut [f32], Mut<'_, FullQueryMeta>>, ScopedAllocator<'_>> for SphericalQuantizer<A>

where A: Allocator,

fn compress_into_with( &self, from: &[f32], into: FullQueryMut<'_>, allocator: ScopedAllocator<'_>, ) -> Result<(), Self::Error>

Compress the input vector from into the bitslice into.

Error

Returns an error if

• The input contains NaN.
• from.len() != self.dim(): Vector to be compressed must have the same dimensionality as the quantizer.
• into.len() != self.output_dim(): Compressed vector must have the same dimensionality as the output of the distance-preserving transform. Importantely, this may be different than self.dim() and should be retrieved from self.output_dim().

type Error = CompressionError

Errors that may occur during compression.

impl<T: Debug, M: Debug> Debug for Slice<T, M>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const NBITS: usize> PureDistanceFunction<Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, MinMaxCompensation>>, Result<MathematicalValue<f32>, UnequalLengths>> for MinMaxIP

where Unsigned: Representation<NBITS>, InnerProduct: for<'a, 'b> PureDistanceFunction<&'a [f32], BitSlice<'b, NBITS, Unsigned>, MathematicalResult<f32>>,

fn evaluate( x: FullQueryRef<'_>, y: DataRef<'_, NBITS>, ) -> MathematicalResult<f32>

impl<const NBITS: usize> PureDistanceFunction<Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, MinMaxCompensation>>, Result<MathematicalValue<f32>, UnequalLengths>> for MinMaxL2Squared

where Unsigned: Representation<NBITS>, InnerProduct: for<'a, 'b> PureDistanceFunction<&'a [f32], BitSlice<'b, NBITS, Unsigned>, MathematicalResult<f32>>,

fn evaluate( x: FullQueryRef<'_>, y: DataRef<'_, NBITS>, ) -> MathematicalResult<f32>

impl<const NBITS: usize> PureDistanceFunction<Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, MinMaxCompensation>>, Result<f32, UnequalLengths>> for MinMaxCosine

where Unsigned: Representation<NBITS>, MinMaxIP: for<'a, 'b> PureDistanceFunction<FullQueryRef<'a>, DataRef<'b, NBITS>, MathematicalResult<f32>>,

fn evaluate(x: FullQueryRef<'_>, y: DataRef<'_, NBITS>) -> Result<f32>

impl<const NBITS: usize> PureDistanceFunction<Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, MinMaxCompensation>>, Result<f32, UnequalLengths>> for MinMaxCosineNormalized

where Unsigned: Representation<NBITS>, MinMaxIP: for<'a, 'b> PureDistanceFunction<FullQueryRef<'a>, DataRef<'b, NBITS>, MathematicalResult<f32>>,

fn evaluate(x: FullQueryRef<'_>, y: DataRef<'_, NBITS>) -> Result<f32>

impl<const NBITS: usize> PureDistanceFunction<Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, MinMaxCompensation>>, Result<f32, UnequalLengths>> for MinMaxIP

where Unsigned: Representation<NBITS>, InnerProduct: for<'a, 'b> PureDistanceFunction<&'a [f32], BitSlice<'b, NBITS, Unsigned>, MathematicalResult<f32>>,

fn evaluate(x: FullQueryRef<'_>, y: DataRef<'_, NBITS>) -> Result<f32>

impl<const NBITS: usize> PureDistanceFunction<Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, MinMaxCompensation>>, Result<f32, UnequalLengths>> for MinMaxL2Squared

where Unsigned: Representation<NBITS>, InnerProduct: for<'a, 'b> PureDistanceFunction<&'a [f32], BitSlice<'b, NBITS, Unsigned>, MathematicalResult<f32>>,

fn evaluate(x: FullQueryRef<'_>, y: DataRef<'_, NBITS>) -> Result<f32>

impl<'a, T, A, M> Reborrow<'a> for Slice<Poly<[T], A>, Owned<M>>

where A: AllocatorCore, M: 'static,

type Target = Slice<&'a [T], Ref<'a, M>>

fn reborrow(&'a self) -> Self::Target

Borrow self into a generalized reference type and reborrow

impl<'a, T, A, M> ReborrowMut<'a> for Slice<Poly<[T], A>, Owned<M>>

where A: AllocatorCore, M: 'static,

type Target = Slice<&'a mut [T], Mut<'a, M>>

fn reborrow_mut(&'a mut self) -> Self::Target

Mutably borrow self into a generalized reference type and reborrow.

impl<A, const NBITS: usize> Target2<A, Result<MathematicalValue<f32>, UnequalLengths>, Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, DataMeta>>> for CompensatedIP

where A: Architecture, Unsigned: Representation<NBITS>, InnerProduct: for<'a> Target2<A, MathematicalResult<f32>, &'a [f32], BitSlice<'a, NBITS, Unsigned>>,

Compute the inner product between a full-precision query and a spherically quantized data vector.

Returns an error if the arguments have different lengths.

fn run( self, arch: A, x: FullQueryRef<'_>, y: DataRef<'_, NBITS>, ) -> MathematicalResult<f32>

Run the operation with the provided Architecture.

impl<A, const NBITS: usize> Target2<A, Result<MathematicalValue<f32>, UnequalLengths>, Slice<&[f32], Ref<'_, FullQueryMeta>>, VectorBase<NBITS, Unsigned, SlicePtr<'_, u8>, Ref<'_, DataMeta>>> for CompensatedSquaredL2

where A: Architecture, Unsigned: Representation<NBITS>, InnerProduct: for<'a> Target2<A, MathematicalResult<f32>, &'a [f32], BitSlice<'a, NBITS, Unsigned>>,

Compute the inner product between a full-precision query and a spherically quantized data vector.

Returns an error if the arguments have different lengths.

fn run( self, arch: A, x: FullQueryRef<'_>, y: DataRef<'_, NBITS>, ) -> MathematicalResult<f32>

Run the operation with the provided Architecture.

impl<T: Copy, M: Copy> Copy for Slice<T, M>