packages
The Louise packages, each released on its own
Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.
Dernier runRéussi#28 · main · 3 min 34 s
0Étoiles
0Forks
3Issues
| 1 | /// Rows of 32-bit floats packed little-endian in `Bytes` (4 bytes per |
| 2 | /// number, `dim` numbers per row), and a C kernel that ranks them by dot |
| 3 | /// product: the exact nearest-neighbour search of semantic search. |
| 4 | /// |
| 5 | /// import vectors |
| 6 | /// |
| 7 | /// let index = vectors.from_base64 384 text // Ok(...) or an error |
| 8 | /// let query = vectors.from_floats 384 numbers |
| 9 | /// vectors.top_k index query 10 // [Hit(row: 7, score: 0.83), ...] |
| 10 | /// |
| 11 | /// **Unit vectors** (L2-normalised, as embedding services send them) make |
| 12 | /// the dot product their cosine similarity; this package does not |
| 13 | /// normalise. Every float is checked when a `Vectors` is made: NaN and |
| 14 | /// infinities are refused, so scores are always numbers. |
| 15 | /// |
| 16 | /// **Cost:** `top_k` reads every row once and keeps the best `k` in a heap: |
| 17 | /// about 10 ms for 100,000 rows of 384 on one core (`bench/`). It runs on |
| 18 | /// the `cpu` blocking pool, like the checks of `from_bytes`, so the |
| 19 | /// scheduler is never stalled. Scores are computed in single precision. |
| 20 | /// |
| 21 | /// The interpreter cannot call C: this package's functions and tests need |
| 22 | /// a native build (`louise test --native`), as with the argon2 package. |
| 23 | |
| 24 | import std/base64 |
| 25 | import std/bytes as raw |
| 26 | import std/float |
| 27 | import std/int as bits |
| 28 | import std/list |
| 29 | |
| 30 | /// `count` rows of `dim` floats. Made only by the functions here, which |
| 31 | /// check the length and every float. |
| 32 | @derive Eq |
| 33 | pub opaque type Vectors { Vectors(Int, Bytes) } |
| 34 | |
| 35 | /// A row of a matrix and its dot product with the query. |
| 36 | @derive Eq Show Debug |
| 37 | pub type Hit { Hit(row: Int, score: Float) } |
| 38 | |
| 39 | // ---- making them ------------------------------------------------------------------ |
| 40 | |
| 41 | /// The rows packed in `data`: little-endian 32-bit floats, `dim` per row. |
| 42 | /// An `Error` names what is wrong: a `dim` below 1, a length that is not a |
| 43 | /// whole number of rows, or a float that is NaN or infinite. |
| 44 | pub fn from_bytes :: dim: Int data: Bytes -> Result<Vectors, String> / <ffi> |
| 45 | { |
| 46 | let length = raw.length data |
| 47 | if dim < 1 |
| 48 | { |
| 49 | Error("vectors: the dimension must be at least 1, not {dim}") |
| 50 | } |
| 51 | else if length % (dim * 4) != 0 |
| 52 | { |
| 53 | Error("vectors: {length} bytes are not whole rows of {dim} floats") |
| 54 | } |
| 55 | else |
| 56 | { |
| 57 | let bad = first_bad data |
| 58 | if bad >= 0 |
| 59 | { |
| 60 | Error("vectors: float {bad} (row {bad / dim}) is not a finite number") |
| 61 | } |
| 62 | else |
| 63 | { |
| 64 | Ok(Vectors(dim, data)) |
| 65 | } |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | /// [`from_bytes`] of base64 text (RFC 4648, padded): how embedding |
| 70 | /// services send vectors in JSON. |
| 71 | pub fn from_base64 :: dim: Int text: String -> Result<Vectors, String> / <ffi> |
| 72 | { |
| 73 | match base64.decode text |
| 74 | { Ok(data) -> from_bytes dim data, Error(e) -> Error("vectors: {e}") } |
| 75 | } |
| 76 | |
| 77 | /// The rows of `xs`, `dim` at a time, each rounded to single precision. |
| 78 | pub fn from_floats :: |
| 79 | dim: Int |
| 80 | xs: List<Float> |
| 81 | -> Result<Vectors, String> / <ffi> |
| 82 | { |
| 83 | let packed = |
| 84 | list.fold |
| 85 | xs |
| 86 | (raw.builder_with_capacity (4 * list.length xs)) |
| 87 | fn b x { put_f32 b (float.to_bits32 x) } |
| 88 | from_bytes dim (raw.build packed) |
| 89 | } |
| 90 | |
| 91 | /// No rows, of `dim` floats (at least 1). |
| 92 | pub fn empty :: dim: Int -> Vectors |
| 93 | { |
| 94 | if dim < 1 |
| 95 | { |
| 96 | panic "vectors.empty: the dimension must be at least 1, not {dim}" |
| 97 | } |
| 98 | Vectors(dim, raw.empty ()) |
| 99 | } |
| 100 | |
| 101 | /// Appends a single's 32 bits, little-endian. |
| 102 | fn put_f32 :: b: raw.Builder n: Int -> raw.Builder |
| 103 | { |
| 104 | list.fold |
| 105 | (list.range 0 3) |
| 106 | b |
| 107 | fn acc i |
| 108 | { |
| 109 | raw.append_byte acc (bits.low_bits (bits.shift_right n (8 * i)) 8) |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | // ---- reading them ----------------------------------------------------------------- |
| 114 | |
| 115 | /// The number of floats per row. |
| 116 | pub fn dim :: v: Vectors -> Int |
| 117 | { |
| 118 | match v { Vectors(d, _) -> d } |
| 119 | } |
| 120 | |
| 121 | /// The number of rows. |
| 122 | pub fn count :: v: Vectors -> Int |
| 123 | { |
| 124 | match v { Vectors(d, data) -> raw.length data / (d * 4) } |
| 125 | } |
| 126 | |
| 127 | /// The packed floats, as [`from_bytes`] takes them. |
| 128 | pub fn to_bytes :: v: Vectors -> Bytes |
| 129 | { |
| 130 | match v { Vectors(_, data) -> data } |
| 131 | } |
| 132 | |
| 133 | /// [`to_bytes`] as base64, as [`from_base64`] takes it. |
| 134 | pub fn to_base64 :: v: Vectors -> String |
| 135 | { |
| 136 | base64.encode (to_bytes v) |
| 137 | } |
| 138 | |
| 139 | /// Row `i` (from 0) as Floats, or `None` past the end. |
| 140 | pub fn row :: v: Vectors i: Int -> Option<List<Float>> |
| 141 | { |
| 142 | match v |
| 143 | { Vectors(d, data) -> |
| 144 | { |
| 145 | if i < 0 || i >= count v |
| 146 | { |
| 147 | None |
| 148 | } |
| 149 | else |
| 150 | { |
| 151 | Some( list.map |
| 152 | (list.range 0 (d - 1)) |
| 153 | fn j { get_f32 data (4 * (i * d + j)) } |
| 154 | ) |
| 155 | } |
| 156 | } |
| 157 | } |
| 158 | } |
| 159 | |
| 160 | /// The single at byte `off`, little-endian. |
| 161 | fn get_f32 :: data: Bytes off: Int -> Float |
| 162 | { |
| 163 | let n = |
| 164 | list.fold |
| 165 | (list.range 0 3) |
| 166 | 0 |
| 167 | fn acc i { acc + bits.shift_left (raw.read_u8 data (off + i)) (8 * i) } |
| 168 | float.from_bits32 n |
| 169 | } |
| 170 | |
| 171 | /// Rows `start` to `end` (excluded), clamped to the rows there are. |
| 172 | pub fn rows :: v: Vectors start: Int end: Int -> Vectors |
| 173 | { |
| 174 | match v |
| 175 | { Vectors(d, data) -> |
| 176 | { |
| 177 | let n = count v |
| 178 | let from = clamp start 0 n |
| 179 | let to = clamp end from n |
| 180 | Vectors(d, raw.slice data (from * d * 4) (to * d * 4)) |
| 181 | } |
| 182 | } |
| 183 | } |
| 184 | |
| 185 | fn clamp :: x: Int low: Int high: Int -> Int |
| 186 | { |
| 187 | if x < low |
| 188 | { |
| 189 | low |
| 190 | } |
| 191 | else if x > high |
| 192 | { |
| 193 | high |
| 194 | } |
| 195 | else |
| 196 | { |
| 197 | x |
| 198 | } |
| 199 | } |
| 200 | |
| 201 | /// The rows of `a`, then those of `b`; an `Error` when their dimensions |
| 202 | /// differ. |
| 203 | pub fn concat :: a: Vectors b: Vectors -> Result<Vectors, String> |
| 204 | { |
| 205 | concat_all (dim a) [a, b] |
| 206 | } |
| 207 | |
| 208 | /// The rows of every part, in order; an `Error` when a part's dimension |
| 209 | /// is not `dim`. |
| 210 | pub fn concat_all :: dim: Int parts: List<Vectors> -> Result<Vectors, String> |
| 211 | { |
| 212 | match list.find parts fn p { dim_of p != dim } |
| 213 | { Some(p) -> |
| 214 | Error("vectors.concat: rows of {dim_of p} floats among rows of {dim}") |
| 215 | , None -> Ok(Vectors(dim, raw.concat_all (list.map parts to_bytes))) |
| 216 | } |
| 217 | } |
| 218 | |
| 219 | fn dim_of :: v: Vectors -> Int |
| 220 | { |
| 221 | dim v |
| 222 | } |
| 223 | |
| 224 | // ---- ranking ---------------------------------------------------------------------- |
| 225 | |
| 226 | /// The dot product of row `i` of `a` and row `j` of `b`. Panics when the |
| 227 | /// dimensions differ or a row is out of range. |
| 228 | pub fn dot :: a: Vectors i: Int b: Vectors j: Int -> Float / <ffi> |
| 229 | { |
| 230 | if dim a != dim b |
| 231 | { |
| 232 | panic "vectors.dot: rows of {dim a} and {dim b} floats" |
| 233 | } |
| 234 | if i < 0 || i >= count a || j < 0 || j >= count b |
| 235 | { |
| 236 | panic |
| 237 | "vectors.dot: row {i} of {count a} or {j} of {count b} is out of range" |
| 238 | } |
| 239 | dot_raw (to_bytes a) i (to_bytes b) j (dim a) |
| 240 | } |
| 241 | |
| 242 | /// The `k` rows of `matrix` most similar to `query` (one row), best first: |
| 243 | /// the highest dot products, ties by row. Fewer when `matrix` has fewer |
| 244 | /// rows; none when `k` is below 1. Panics when the dimensions differ or |
| 245 | /// `query` is not one row. |
| 246 | pub fn top_k :: matrix: Vectors query: Vectors k: Int -> List<Hit> / <ffi> |
| 247 | { |
| 248 | if dim matrix != dim query |
| 249 | { |
| 250 | panic |
| 251 | "vectors.top_k: a query of {dim query} floats for rows of {dim matrix}" |
| 252 | } |
| 253 | if count query != 1 |
| 254 | { |
| 255 | panic "vectors.top_k: the query must be one row, not {count query}" |
| 256 | } |
| 257 | let want = if k < 0 { 0 } else if k > count matrix { count matrix } else { k } |
| 258 | if want == 0 |
| 259 | { |
| 260 | [] |
| 261 | } |
| 262 | else |
| 263 | { |
| 264 | let found = top_k_raw (to_bytes matrix) (to_bytes query) (dim matrix) want |
| 265 | if raw.length found != 8 * want |
| 266 | { |
| 267 | panic "vectors.top_k: the kernel ran out of memory for {want} rows" |
| 268 | } |
| 269 | list.map |
| 270 | (list.range 0 (want - 1)) |
| 271 | fn i |
| 272 | { |
| 273 | Hit( row: raw.read_u32be found (8 * i) |
| 274 | , score: float.from_bits32 (raw.read_u32be found (8 * i + 4)) |
| 275 | ) |
| 276 | } |
| 277 | } |
| 278 | } |
| 279 | |
| 280 | // ---- the kernel (csrc/vectors.c) --------------------------------------------------- |
| 281 | |
| 282 | @extern c "louise_vectors_first_bad" (blocking cpu) |
| 283 | fn first_bad :: data: Bytes -> Int / <ffi> |
| 284 | |
| 285 | @extern c "louise_vectors_dot" |
| 286 | fn dot_raw :: a: Bytes i: Int b: Bytes j: Int dim: Int -> Float / <ffi> |
| 287 | |
| 288 | @extern c "louise_vectors_top_k" (blocking cpu) |
| 289 | fn top_k_raw :: matrix: Bytes query: Bytes dim: Int k: Int -> Bytes / <ffi> |