/// Rows of 32-bit floats packed little-endian in `Bytes` (4 bytes per /// number, `dim` numbers per row), and a C kernel that ranks them by dot /// product: the exact nearest-neighbour search of semantic search. /// /// import vectors /// /// let index = vectors.from_base64 384 text // Ok(...) or an error /// let query = vectors.from_floats 384 numbers /// vectors.top_k index query 10 // [Hit(row: 7, score: 0.83), ...] /// /// **Unit vectors** (L2-normalised, as embedding services send them) make /// the dot product their cosine similarity; this package does not /// normalise. Every float is checked when a `Vectors` is made: NaN and /// infinities are refused, so scores are always numbers. /// /// **Cost:** `top_k` reads every row once and keeps the best `k` in a heap: /// about 10 ms for 100,000 rows of 384 on one core (`bench/`). It runs on /// the `cpu` blocking pool, like the checks of `from_bytes`, so the /// scheduler is never stalled. Scores are computed in single precision. /// /// The interpreter cannot call C: this package's functions and tests need /// a native build (`louise test --native`), as with the argon2 package. import std/base64 import std/bytes as raw import std/float import std/int as bits import std/list /// `count` rows of `dim` floats. Made only by the functions here, which /// check the length and every float. @derive Eq pub opaque type Vectors { Vectors(Int, Bytes) } /// A row of a matrix and its dot product with the query. @derive Eq Show Debug pub type Hit { Hit(row: Int, score: Float) } // ---- making them ------------------------------------------------------------------ /// The rows packed in `data`: little-endian 32-bit floats, `dim` per row. /// An `Error` names what is wrong: a `dim` below 1, a length that is not a /// whole number of rows, or a float that is NaN or infinite. pub fn from_bytes :: dim: Int data: Bytes -> Result / { let length = raw.length data if dim < 1 { Error("vectors: the dimension must be at least 1, not {dim}") } else if length % (dim * 4) != 0 { Error("vectors: {length} bytes are not whole rows of {dim} floats") } else { let bad = first_bad data if bad >= 0 { Error("vectors: float {bad} (row {bad / dim}) is not a finite number") } else { Ok(Vectors(dim, data)) } } } /// [`from_bytes`] of base64 text (RFC 4648, padded): how embedding /// services send vectors in JSON. pub fn from_base64 :: dim: Int text: String -> Result / { match base64.decode text { Ok(data) -> from_bytes dim data, Error(e) -> Error("vectors: {e}") } } /// The rows of `xs`, `dim` at a time, each rounded to single precision. pub fn from_floats :: dim: Int xs: List -> Result / { let packed = list.fold xs (raw.builder_with_capacity (4 * list.length xs)) fn b x { put_f32 b (float.to_bits32 x) } from_bytes dim (raw.build packed) } /// No rows, of `dim` floats (at least 1). pub fn empty :: dim: Int -> Vectors { if dim < 1 { panic "vectors.empty: the dimension must be at least 1, not {dim}" } Vectors(dim, raw.empty ()) } /// Appends a single's 32 bits, little-endian. fn put_f32 :: b: raw.Builder n: Int -> raw.Builder { list.fold (list.range 0 3) b fn acc i { raw.append_byte acc (bits.low_bits (bits.shift_right n (8 * i)) 8) } } // ---- reading them ----------------------------------------------------------------- /// The number of floats per row. pub fn dim :: v: Vectors -> Int { match v { Vectors(d, _) -> d } } /// The number of rows. pub fn count :: v: Vectors -> Int { match v { Vectors(d, data) -> raw.length data / (d * 4) } } /// The packed floats, as [`from_bytes`] takes them. pub fn to_bytes :: v: Vectors -> Bytes { match v { Vectors(_, data) -> data } } /// [`to_bytes`] as base64, as [`from_base64`] takes it. pub fn to_base64 :: v: Vectors -> String { base64.encode (to_bytes v) } /// Row `i` (from 0) as Floats, or `None` past the end. pub fn row :: v: Vectors i: Int -> Option> { match v { Vectors(d, data) -> { if i < 0 || i >= count v { None } else { Some( list.map (list.range 0 (d - 1)) fn j { get_f32 data (4 * (i * d + j)) } ) } } } } /// The single at byte `off`, little-endian. fn get_f32 :: data: Bytes off: Int -> Float { let n = list.fold (list.range 0 3) 0 fn acc i { acc + bits.shift_left (raw.read_u8 data (off + i)) (8 * i) } float.from_bits32 n } /// Rows `start` to `end` (excluded), clamped to the rows there are. pub fn rows :: v: Vectors start: Int end: Int -> Vectors { match v { Vectors(d, data) -> { let n = count v let from = clamp start 0 n let to = clamp end from n Vectors(d, raw.slice data (from * d * 4) (to * d * 4)) } } } fn clamp :: x: Int low: Int high: Int -> Int { if x < low { low } else if x > high { high } else { x } } /// The rows of `a`, then those of `b`; an `Error` when their dimensions /// differ. pub fn concat :: a: Vectors b: Vectors -> Result { concat_all (dim a) [a, b] } /// The rows of every part, in order; an `Error` when a part's dimension /// is not `dim`. pub fn concat_all :: dim: Int parts: List -> Result { match list.find parts fn p { dim_of p != dim } { Some(p) -> Error("vectors.concat: rows of {dim_of p} floats among rows of {dim}") , None -> Ok(Vectors(dim, raw.concat_all (list.map parts to_bytes))) } } fn dim_of :: v: Vectors -> Int { dim v } // ---- ranking ---------------------------------------------------------------------- /// The dot product of row `i` of `a` and row `j` of `b`. Panics when the /// dimensions differ or a row is out of range. pub fn dot :: a: Vectors i: Int b: Vectors j: Int -> Float / { if dim a != dim b { panic "vectors.dot: rows of {dim a} and {dim b} floats" } if i < 0 || i >= count a || j < 0 || j >= count b { panic "vectors.dot: row {i} of {count a} or {j} of {count b} is out of range" } dot_raw (to_bytes a) i (to_bytes b) j (dim a) } /// The `k` rows of `matrix` most similar to `query` (one row), best first: /// the highest dot products, ties by row. Fewer when `matrix` has fewer /// rows; none when `k` is below 1. Panics when the dimensions differ or /// `query` is not one row. pub fn top_k :: matrix: Vectors query: Vectors k: Int -> List / { if dim matrix != dim query { panic "vectors.top_k: a query of {dim query} floats for rows of {dim matrix}" } if count query != 1 { panic "vectors.top_k: the query must be one row, not {count query}" } let want = if k < 0 { 0 } else if k > count matrix { count matrix } else { k } if want == 0 { [] } else { let found = top_k_raw (to_bytes matrix) (to_bytes query) (dim matrix) want if raw.length found != 8 * want { panic "vectors.top_k: the kernel ran out of memory for {want} rows" } list.map (list.range 0 (want - 1)) fn i { Hit( row: raw.read_u32be found (8 * i) , score: float.from_bits32 (raw.read_u32be found (8 * i + 4)) ) } } } // ---- the kernel (csrc/vectors.c) --------------------------------------------------- @extern c "louise_vectors_first_bad" (blocking cpu) fn first_bad :: data: Bytes -> Int / @extern c "louise_vectors_dot" fn dot_raw :: a: Bytes i: Int b: Bytes j: Int dim: Int -> Float / @extern c "louise_vectors_top_k" (blocking cpu) fn top_k_raw :: matrix: Bytes query: Bytes dim: Int k: Int -> Bytes /