tobogganSe connecter

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.

289 lignes · 7823 octetsBrut · Historique
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
24import std/base64
25import std/bytes as raw
26import std/float
27import std/int as bits
28import 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
33pub 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
37pub 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.
44pub 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.
71pub 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.
78pub 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).
92pub 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.
102fn 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.
116pub fn dim :: v: Vectors -> Int
117{
118 match v { Vectors(d, _) -> d }
119}
120
121/// The number of rows.
122pub 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.
128pub 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.
134pub 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.
140pub 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.
161fn 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.
172pub 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
185fn 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.
203pub 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`.
210pub 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
219fn 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.
228pub 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.
246pub 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)
283fn first_bad :: data: Bytes -> Int / <ffi>
284
285@extern c "louise_vectors_dot"
286fn dot_raw :: a: Bytes i: Int b: Bytes j: Int dim: Int -> Float / <ffi>
287
288@extern c "louise_vectors_top_k" (blocking cpu)
289fn top_k_raw :: matrix: Bytes query: Bytes dim: Int k: Int -> Bytes / <ffi>