GCC Code Coverage Report


Directory: src/
File: src/quant/matrix.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 191 227 84.1%
Functions: 16 22 72.7%
Branches: 111 132 84.1%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * matrix.c - Random orthogonal matrix generation for RaBitQ
6 *
7 * Generates random orthogonal matrices via QR decomposition of Gaussian
8 * random matrices, using modified Gram-Schmidt.
9 *
10 * The orthogonal matrix P ensures that residual vectors have isotropic
11 * distribution, which is essential for RaBitQ's theoretical error bounds.
12 */
13
14 #include "vs_config.h"
15
16 #include <math.h>
17 #include <stdint.h>
18 #include <string.h>
19
20 #ifdef VS_HAVE_CBLAS
21 /*
22 * macOS: cblas lives inside Accelerate's vecLib sub-framework. We
23 * include it directly rather than via the `Accelerate/Accelerate.h`
24 * umbrella because the umbrella pulls in MacTypes.h, which
25 * `typedef long Size` clashes with PostgreSQL's `typedef size_t
26 * Size` in the PG-extension build.
27 *
28 * The legacy `vecLib/cblas.h` deprecates every prototype past macOS
29 * 13.3; under -DACCELERATE_NEW_LAPACK (set in meson.build for the
30 * Apple branch) we use `vecLib/cblas_new.h` instead, which aliases
31 * the same call sites to the non-deprecated LP64 symbols.
32 */
33 #ifdef __APPLE__
34 #include <vecLib/cblas_new.h>
35 #else
36 #include <cblas.h>
37 #endif
38 #endif
39
40 #if defined(VS_SIMD_FULL) && (defined(__x86_64__) || defined(_M_X64))
41 #include <immintrin.h>
42 #elif defined(VS_SIMD_FULL) && (defined(__aarch64__) || defined(_M_ARM64))
43 #include <arm_neon.h>
44 #endif
45
46 #include "algo/simd_utils.h"
47 #include "algo/vecops.h"
48 #include "core/memory.h"
49 #include "core/platform.h"
50 #include "core/types.h"
51 #include "quant/matrix.h"
52
53 /*
54 * Simple xoshiro256** PRNG for reproducible random generation.
55 * Chosen for speed and quality - not cryptographic.
56 */
57 typedef struct
58 {
59 uint64_t s[4];
60 } Xoshiro256State;
61
62 static inline uint64_t
63 84326302 rotl(uint64_t x, int k)
64 {
65 84326302 return (x << k) | (x >> (64 - k));
66 }
67
68 static uint64_t
69 58652090 xoshiro256_next(Xoshiro256State *state)
70 {
71 58652090 uint64_t *s = state->s;
72 58652090 uint64_t result = rotl(s[1] * 5, 7) * 9;
73 58652090 uint64_t t = s[1] << 17;
74
75 58652090 s[2] ^= s[0];
76 58652090 s[3] ^= s[1];
77 58652090 s[1] ^= s[2];
78 58652090 s[0] ^= s[3];
79 58652090 s[2] ^= t;
80 58652090 s[3] = rotl(s[3], 45);
81
82 58652090 return result;
83 }
84
85 static void
86 366 xoshiro256_seed(Xoshiro256State *state, uint64_t seed)
87 {
88 /* SplitMix64 to expand seed into state */
89
2/2
✓ Branch 0 taken 1464 times.
✓ Branch 1 taken 366 times.
1830 for (int i = 0; i < 4; i++)
90 {
91 1464 seed += 0x9e3779b97f4a7c15ULL;
92 1464 uint64_t z = seed;
93 1464 z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
94 1464 z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
95 1464 state->s[i] = z ^ (z >> 31);
96 }
97 366 }
98
99 /*
100 * Generate uniform random double in [0, 1)
101 */
102 static double
103 58652090 random_uniform(Xoshiro256State *state)
104 {
105 /* Use upper 53 bits for double precision */
106 75141029 uint64_t x = xoshiro256_next(state) >> 11;
107 58652090 return (double)x / (double)(1ULL << 53);
108 }
109
110 /*
111 * Generate standard normal random variable using Box-Muller transform.
112 * Returns two independent samples for efficiency.
113 */
114 static void
115 29326045 random_normal_pair(Xoshiro256State *state, double *n1, double *n2)
116 {
117 29326045 double u1 = random_uniform(state);
118 29326045 double u2 = random_uniform(state);
119
120 /* Avoid log(0) */
121
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12837106 times.
29326045 if (u1 < 1e-15)
122 ✗ u1 = 1e-15;
123
124 29326045 double r = sqrt(-2.0 * log(u1));
125 29326045 double theta = 2.0 * M_PI * u2;
126
127 29326045 *n1 = r * cos(theta);
128 29326045 *n2 = r * sin(theta);
129 29326045 }
130
131 /*
132 * Fill matrix with standard normal random values.
133 * Matrix is dim x dim, stored in row-major order.
134 */
135 static void
136 366 fill_gaussian_matrix(float *matrix, Dimension dim, uint64_t seed)
137 {
138 234 Xoshiro256State state;
139 366 xoshiro256_seed(&state, seed);
140
141 366 size_t n = (size_t)dim * dim;
142 366 size_t i = 0;
143
144 /* Generate pairs of normal values */
145
2/2
✓ Branch 0 taken 29325790 times.
✓ Branch 1 taken 366 times.
29326156 while (i + 1 < n)
146 {
147 16488734 double n1, n2;
148 29325790 random_normal_pair(&state, &n1, &n2);
149 29325790 matrix[i] = (float)n1;
150 29325790 matrix[i + 1] = (float)n2;
151 29325790 i += 2;
152 }
153
154 /* Handle odd size */
155
2/2
✓ Branch 0 taken 255 times.
✓ Branch 1 taken 111 times.
366 if (i < n)
156 {
157 205 double n1, n2;
158 255 random_normal_pair(&state, &n1, &n2);
159 205 (void)n2;
160 255 matrix[i] = (float)n1;
161 }
162 366 }
163
164 /*
165 * The matrix is regenerated from its seed wherever an index is read, so its
166 * bits must not depend on the compiler. The QR code below is evaluated in
167 * source order, without reassociation or fused multiply-adds. The clang
168 * pragma needs -ffp-contract=fast-honor-pragmas, which meson.build sets.
169 */
170 #if defined(__clang__)
171 #define STRICT_FP_FN
172 #define STRICT_FP_BODY _Pragma("clang fp reassociate(off) contract(off)")
173 #elif defined(__GNUC__)
174 #define STRICT_FP_FN \
175 __attribute__((optimize("no-associative-math", "fp-contract=off")))
176 #define STRICT_FP_BODY
177 #else
178 #define STRICT_FP_FN
179 #define STRICT_FP_BODY
180 #endif
181
182 /* Columns orthogonalized together, packed so a strip stays in cache. */
183 #define QR_STRIP 32
184
185 /*
186 * Squared norm of a contiguous column. Summed in the order gcc 14 and later
187 * give it at -O2 on x86-64, so the matrix matches indexes built that way.
188 */
189 STRICT_FP_FN static float
190 43347 column_norm2(const float *x, Dimension n)
191 {
192 STRICT_FP_BODY
193 43347 float norm = 0.0f;
194 43347 Dimension i = 0;
195
196
2/2
✓ Branch 0 taken 42066 times.
✓ Branch 1 taken 1281 times.
43347 if (n > 20)
197 {
198 22200 float s0 = 0.0f;
199 22200 float s1 = 0.0f;
200
201
2/2
✓ Branch 0 taken 14657680 times.
✓ Branch 1 taken 42066 times.
14699746 for (; i + 4 <= n; i += 4)
202 {
203 14657680 s0 = (x[i + 2] * x[i + 2] + x[i] * x[i]) + s0;
204 14657680 s1 = (x[i + 3] * x[i + 3] + x[i + 1] * x[i + 1]) + s1;
205 }
206 42066 norm = s0 + s1;
207 }
208
2/2
✓ Branch 0 taken 21115 times.
✓ Branch 1 taken 43347 times.
64462 for (; i < n; i++)
209 21115 norm += x[i] * x[i];
210 43347 return norm;
211 }
212
213 /*
214 * One pass down a strip of QR_STRIP columns. With p set, subtract
215 * p_dots[c] * p from each column c. With q set, store q . column c in
216 * q_dots[c], after that update. p and q are columns with the given stride,
217 * outside the strip.
218 *
219 * Every kernel gives each column a lane of its own and rounds each multiply
220 * and add separately, so they all produce the same bits. The SIMD kernels
221 * use operators for arithmetic, not intrinsics: clang compiles intrinsics
222 * with the file's flags, which would let them fuse.
223 */
224 typedef void (*StripSweepFn)(
225 float *strip,
226 Dimension n,
227 const float *p,
228 const float *p_dots,
229 const float *q,
230 float *q_dots,
231 size_t stride);
232
233 STRICT_FP_FN static void
234 21014 strip_sweep_scalar(
235 float *restrict strip,
236 Dimension n,
237 const float *p,
238 const float *restrict p_dots,
239 const float *q,
240 float *restrict q_dots,
241 size_t stride)
242 {
243 STRICT_FP_BODY
244 21014 float acc[QR_STRIP] = {0};
245
246
2/2
✓ Branch 0 taken 5888306 times.
✓ Branch 1 taken 21014 times.
5909320 for (Dimension i = 0; i < n; i++)
247 {
248 5888306 float *restrict row = strip + (size_t)i * QR_STRIP;
249
250
2/2
✓ Branch 0 taken 5017154 times.
✓ Branch 1 taken 871152 times.
5888306 if (p != NULL)
251 {
252 5017154 float pi = p[i * stride];
253
254
2/2
✓ Branch 0 taken 160548928 times.
✓ Branch 1 taken 5017154 times.
165566082 for (int c = 0; c < QR_STRIP; c++)
255 160548928 row[c] = row[c] - p_dots[c] * pi;
256 }
257
2/2
✓ Branch 0 taken 5017154 times.
✓ Branch 1 taken 871152 times.
5888306 if (q != NULL)
258 {
259 5017154 float qi = q[i * stride];
260
261
2/2
✓ Branch 0 taken 160548928 times.
✓ Branch 1 taken 5017154 times.
165566082 for (int c = 0; c < QR_STRIP; c++)
262 160548928 acc[c] += qi * row[c];
263 }
264 }
265
266
2/2
✓ Branch 0 taken 17434 times.
✓ Branch 1 taken 3580 times.
21014 if (q != NULL)
267 17434 memcpy(q_dots, acc, sizeof(acc));
268 21014 }
269
270 #if defined(VS_SIMD_FULL) && (defined(__x86_64__) || defined(_M_X64))
271 /* Plain AVX2 on purpose: with FMA a lane would round differently. */
272 #define AVX2_LANES (QR_STRIP / 8)
273
274 __attribute__((target("avx2"))) STRICT_FP_FN static void
275 10856 strip_sweep_avx2(
276 float *strip,
277 Dimension n,
278 const float *p,
279 const float *p_dots,
280 const float *q,
281 float *q_dots,
282 size_t stride)
283 {
284 STRICT_FP_BODY
285 ✗ __m256 acc[AVX2_LANES];
286 ✗ __m256 pd[AVX2_LANES];
287
288 #pragma GCC unroll 8
289
2/2
✓ Branch 0 taken 43424 times.
✓ Branch 1 taken 10856 times.
54280 for (int v = 0; v < AVX2_LANES; v++)
290 {
291 43424 acc[v] = _mm256_setzero_ps();
292
2/2
✓ Branch 0 taken 35816 times.
✓ Branch 1 taken 7608 times.
79240 pd[v] = p != NULL ? _mm256_loadu_ps(p_dots + 8 * v) : acc[v];
293 }
294
295
2/2
✓ Branch 0 taken 2962262 times.
✓ Branch 1 taken 10856 times.
2973118 for (Dimension i = 0; i < n; i++)
296 {
297 2962262 float *row = strip + (size_t)i * QR_STRIP;
298
2/2
✓ Branch 0 taken 2521198 times.
✓ Branch 1 taken 441064 times.
2962262 __m256 pi = _mm256_set1_ps(p != NULL ? p[i * stride] : 0.0f);
299
2/2
✓ Branch 0 taken 2521198 times.
✓ Branch 1 taken 441064 times.
2962262 __m256 qi = _mm256_set1_ps(q != NULL ? q[i * stride] : 0.0f);
300
301 #pragma GCC unroll 8
302
2/2
✓ Branch 0 taken 11849048 times.
✓ Branch 1 taken 2962262 times.
14811310 for (int v = 0; v < AVX2_LANES; v++)
303 {
304
0/2
✗ Branch 0 not taken.
✗ Branch 1 not taken.
11849048 __m256 a = _mm256_loadu_ps(row + 8 * v);
305
306
2/2
✓ Branch 0 taken 10084792 times.
✓ Branch 1 taken 1764256 times.
11849048 if (p != NULL)
307 {
308 10084792 a = a - pd[v] * pi;
309 10084792 _mm256_storeu_ps(row + 8 * v, a);
310 }
311
2/2
✓ Branch 0 taken 10084792 times.
✓ Branch 1 taken 1764256 times.
11849048 if (q != NULL)
312 10084792 acc[v] = acc[v] + qi * a;
313 }
314 }
315
316
2/2
✓ Branch 0 taken 8954 times.
✓ Branch 1 taken 1902 times.
10856 if (q != NULL)
317 {
318 #pragma GCC unroll 8
319
2/2
✓ Branch 0 taken 35816 times.
✓ Branch 1 taken 8954 times.
44770 for (int v = 0; v < AVX2_LANES; v++)
320 35816 _mm256_storeu_ps(q_dots + 8 * v, acc[v]);
321 }
322 10856 }
323
324 #define AVX512_LANES (QR_STRIP / 16)
325
326 __attribute__((target("avx512f"))) STRICT_FP_FN static void
327 969177 strip_sweep_avx512(
328 float *strip,
329 Dimension n,
330 const float *p,
331 const float *p_dots,
332 const float *q,
333 float *q_dots,
334 size_t stride)
335 {
336 STRICT_FP_BODY
337 554827 __m512 acc[AVX512_LANES];
338 554827 __m512 pd[AVX512_LANES];
339
340 #pragma GCC unroll 8
341
2/2
✓ Branch 0 taken 1938354 times.
✓ Branch 1 taken 969177 times.
2907531 for (int v = 0; v < AVX512_LANES; v++)
342 {
343 1938354 acc[v] = _mm512_setzero_ps();
344
2/2
✓ Branch 0 taken 1863356 times.
✓ Branch 1 taken 74998 times.
2732678 pd[v] = p != NULL ? _mm512_loadu_ps(p_dots + 16 * v) : acc[v];
345 }
346
347
2/2
✓ Branch 0 taken 1801019044 times.
✓ Branch 1 taken 969177 times.
1801988221 for (Dimension i = 0; i < n; i++)
348 {
349 1801019044 float *row = strip + (size_t)i * QR_STRIP;
350
2/2
✓ Branch 0 taken 1743722772 times.
✓ Branch 1 taken 57296272 times.
1801019044 __m512 pi = _mm512_set1_ps(p != NULL ? p[i * stride] : 0.0f);
351
2/2
✓ Branch 0 taken 1743722772 times.
✓ Branch 1 taken 57296272 times.
1801019044 __m512 qi = _mm512_set1_ps(q != NULL ? q[i * stride] : 0.0f);
352
353 #pragma GCC unroll 8
354
2/2
✓ Branch 0 taken 3602038088 times.
✓ Branch 1 taken 1801019044 times.
5403057132 for (int v = 0; v < AVX512_LANES; v++)
355 {
356
2/2
✓ Branch 0 taken 2001614660 times.
✓ Branch 1 taken 65914256 times.
3602038088 __m512 a = _mm512_loadu_ps(row + 16 * v);
357
358
2/2
✓ Branch 0 taken 3487445544 times.
✓ Branch 1 taken 114592544 times.
3602038088 if (p != NULL)
359 {
360 3487445544 a = a - pd[v] * pi;
361 3487445544 _mm512_storeu_ps(row + 16 * v, a);
362 }
363
2/2
✓ Branch 0 taken 3487445544 times.
✓ Branch 1 taken 114592544 times.
3602038088 if (q != NULL)
364 3487445544 acc[v] = acc[v] + qi * a;
365 }
366 }
367
368
2/2
✓ Branch 0 taken 931678 times.
✓ Branch 1 taken 37499 times.
969177 if (q != NULL)
369 {
370 #pragma GCC unroll 8
371
2/2
✓ Branch 0 taken 1863356 times.
✓ Branch 1 taken 931678 times.
2795034 for (int v = 0; v < AVX512_LANES; v++)
372 1863356 _mm512_storeu_ps(q_dots + 16 * v, acc[v]);
373 }
374 969177 }
375 #endif /* x86_64 */
376
377 #if defined(VS_SIMD_FULL) && (defined(__aarch64__) || defined(_M_ARM64))
378 #define NEON_LANES (QR_STRIP / 4)
379
380 STRICT_FP_FN static void
381 strip_sweep_neon(
382 float *strip,
383 Dimension n,
384 const float *p,
385 const float *p_dots,
386 const float *q,
387 float *q_dots,
388 size_t stride)
389 {
390 STRICT_FP_BODY
391 float32x4_t acc[NEON_LANES];
392 float32x4_t pd[NEON_LANES];
393
394 #pragma GCC unroll 8
395 for (int v = 0; v < NEON_LANES; v++)
396 {
397 acc[v] = vdupq_n_f32(0.0f);
398 pd[v] = p != NULL ? vld1q_f32(p_dots + 4 * v) : acc[v];
399 }
400
401 for (Dimension i = 0; i < n; i++)
402 {
403 float *row = strip + (size_t)i * QR_STRIP;
404 float32x4_t pi = vdupq_n_f32(p != NULL ? p[i * stride] : 0.0f);
405 float32x4_t qi = vdupq_n_f32(q != NULL ? q[i * stride] : 0.0f);
406
407 #pragma GCC unroll 8
408 for (int v = 0; v < NEON_LANES; v++)
409 {
410 float32x4_t a = vld1q_f32(row + 4 * v);
411
412 if (p != NULL)
413 {
414 a = a - pd[v] * pi;
415 vst1q_f32(row + 4 * v, a);
416 }
417 if (q != NULL)
418 acc[v] = acc[v] + qi * a;
419 }
420 }
421
422 if (q != NULL)
423 {
424 #pragma GCC unroll 8
425 for (int v = 0; v < NEON_LANES; v++)
426 vst1q_f32(q_dots + 4 * v, acc[v]);
427 }
428 }
429 #endif /* aarch64 */
430
431 /* Resolved per matrix, so a SIMD override set in a test takes effect.
432 * Only simd=full builds have the hand-written kernels. */
433 static StripSweepFn
434 366 resolve_strip_sweep(void)
435 {
436 #if defined(VS_SIMD_FULL) && (defined(__x86_64__) || defined(_M_X64))
437
2/2
✓ Branch 1 taken 72 times.
✓ Branch 2 taken 294 times.
366 if (vs_has_simd(SIMD_AVX512F))
438 72 return strip_sweep_avx512;
439
2/2
✓ Branch 1 taken 22 times.
✓ Branch 2 taken 38 times.
60 if (vs_has_simd(SIMD_AVX2))
440 22 return strip_sweep_avx2;
441 #elif defined(VS_SIMD_FULL) && (defined(__aarch64__) || defined(_M_ARM64))
442 if (vs_has_simd(SIMD_NEON))
443 return strip_sweep_neon;
444 #endif
445 38 return strip_sweep_scalar;
446 }
447
448 /*
449 * QR decomposition using modified Gram-Schmidt, overwriting the row-major
450 * A with Q.
451 *
452 * Columns are processed in strips. A strip first has every finished column
453 * to its left projected out, one at a time and vectorized across the strip,
454 * then is orthogonalized within itself. Each column still sees the
455 * classic column-by-column order of operations.
456 */
457 STRICT_FP_FN static int
458 366 gram_schmidt_qr(float *A, Dimension dim)
459 {
460 STRICT_FP_BODY
461 366 StripSweepFn strip_sweep = resolve_strip_sweep();
462 234 float dots[2][QR_STRIP];
463
464 /* A context of its own, since standalone vs_free() keeps the memory. */
465 498 VS_MEMCTX_SCOPE(qr_ctx);
466
2/2
✓ Branch 0 taken 234 times.
✓ Branch 1 taken 132 times.
366 if (qr_ctx == NULL)
467 ✗ return -1;
468
469 366 VsMemCtx old = vs_memctx_switch(qr_ctx);
470 366 float *strip = vs_alloc((size_t)dim * QR_STRIP * sizeof(float));
471 366 float *col = vs_alloc((size_t)dim * sizeof(float));
472
473
1/2
✓ Branch 0 taken 234 times.
✗ Branch 1 not taken.
366 vs_memctx_switch(old);
474
2/4
✓ Branch 0 taken 366 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 132 times.
366 if (strip == NULL || col == NULL)
475 ✗ return -1;
476
477
2/2
✓ Branch 0 taken 1633 times.
✓ Branch 1 taken 366 times.
1999 for (Dimension s = 0; s < dim; s += QR_STRIP)
478 {
479 1633 Dimension width = dim - s < QR_STRIP ? dim - s : QR_STRIP;
480
481 /* Unused strip columns stay zero and come out of every update so. */
482 1633 memset(strip, 0, (size_t)dim * QR_STRIP * sizeof(float));
483
2/2
✓ Branch 0 taken 1855159 times.
✓ Branch 1 taken 1633 times.
1856792 for (Dimension i = 0; i < dim; i++)
484 1855159 memcpy(strip + (size_t)i * QR_STRIP,
485 1855159 A + (size_t)i * dim + s,
486 814416 width * sizeof(float));
487
488 /* Each update by column j - 1 is fused with the dots for column j. */
489
2/2
✓ Branch 0 taken 916352 times.
✓ Branch 1 taken 1633 times.
917985 for (Dimension j = 0; j < s; j++)
490 916352 strip_sweep(
491 strip,
492 dim,
493 915085 j > 0 ? A + j - 1 : NULL,
494 916352 dots[(j + 1) % 2],
495 916352 A + j,
496
2/2
✓ Branch 0 taken 915085 times.
✓ Branch 1 taken 1267 times.
916352 dots[j % 2],
497 dim);
498
2/2
✓ Branch 0 taken 1267 times.
✓ Branch 1 taken 366 times.
1633 if (s > 0)
499 1267 strip_sweep(
500 1267 strip, dim, A + s - 1, dots[(s + 1) % 2], NULL, NULL, dim);
501
502
1/2
✓ Branch 0 taken 43347 times.
✗ Branch 1 not taken.
43347 for (Dimension c = 0; c < width; c++)
503 {
504
2/2
✓ Branch 0 taken 58651835 times.
✓ Branch 1 taken 43347 times.
58695182 for (Dimension i = 0; i < dim; i++)
505 58651835 col[i] = strip[(size_t)i * QR_STRIP + c];
506
507 43347 float norm = sqrtf(column_norm2(col, dim));
508
509 /* Only a degenerate Gaussian draw has a zero column. */
510
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 43347 times.
43347 if (norm < 1e-10f)
511 ✗ norm = 1.0f;
512
513
2/2
✓ Branch 0 taken 58651835 times.
✓ Branch 1 taken 43347 times.
58695182 for (Dimension i = 0; i < dim; i++)
514 {
515 58651835 col[i] /= norm;
516 58651835 strip[(size_t)i * QR_STRIP + c] = col[i];
517 }
518
519
2/2
✓ Branch 0 taken 20488 times.
✓ Branch 1 taken 22859 times.
43347 if (c + 1 == width)
520 788 break;
521
522 /* Columns up to c are done, so a zero dot leaves them alone. */
523 41714 strip_sweep(strip, dim, NULL, NULL, col, dots[0], 1);
524 41714 memset(dots[0], 0, (c + 1) * sizeof(float));
525 41714 strip_sweep(strip, dim, col, dots[0], NULL, NULL, 1);
526 }
527
528
2/2
✓ Branch 0 taken 1855159 times.
✓ Branch 1 taken 1633 times.
1856792 for (Dimension i = 0; i < dim; i++)
529 1855159 memcpy(A + (size_t)i * dim + s,
530 1855159 strip + (size_t)i * QR_STRIP,
531 814416 width * sizeof(float));
532 }
533
534 132 return 0;
535 }
536
537 /*
538 * Generate random orthogonal matrix using QR decomposition.
539 *
540 * Creates a Gaussian random matrix and orthogonalizes it via QR.
541 * The resulting Q matrix is uniformly distributed over O(n)
542 * (orthogonal group) according to Haar measure.
543 *
544 * Parameters:
545 * matrix: Output buffer (dim * dim floats, row-major)
546 * dim: Matrix dimension
547 * seed: Random seed for reproducibility
548 *
549 * Returns 0 on success, -1 on failure.
550 */
551 int
552 366 vs_random_orthogonal_matrix(float *matrix, Dimension dim, uint64_t seed)
553 {
554
2/4
✓ Branch 0 taken 366 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 132 times.
366 if (matrix == NULL || dim == 0)
555 ✗ return -1;
556
557 /* Fill with Gaussian random values */
558 366 fill_gaussian_matrix(matrix, dim, seed);
559
560 /* QR decomposition to get orthogonal matrix */
561 366 return gram_schmidt_qr(matrix, dim);
562 }
563
564 /*
565 * Verify matrix is approximately orthogonal (for testing).
566 *
567 * Checks that M * M^T ≈ I within tolerance.
568 *
569 * Returns 1 if orthogonal, 0 if not.
570 */
571 int
572 4 vs_matrix_is_orthogonal(const float *matrix, Dimension dim, float tolerance)
573 {
574
2/4
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
4 if (matrix == NULL || dim == 0)
575 ✗ return 0;
576
577 /* Check M * M^T = I */
578
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 4 times.
148 for (Dimension i = 0; i < dim; i++)
579 {
580
2/2
✓ Branch 0 taken 8320 times.
✓ Branch 1 taken 144 times.
8464 for (Dimension j = 0; j < dim; j++)
581 {
582 /* Compute (i,j) element of M * M^T = dot(row_i, row_j) */
583 ✗ float dot =
584 8320 vs_dot_product(matrix + i * dim, matrix + j * dim, dim);
585
586 /* Expected value: 1 on diagonal, 0 elsewhere */
587
2/2
✓ Branch 0 taken 144 times.
✓ Branch 1 taken 8176 times.
8320 float expected = (i == j) ? 1.0f : 0.0f;
588 8320 float diff = fabsf(dot - expected);
589
590
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8320 times.
8320 if (diff > tolerance)
591 ✗ return 0;
592 }
593 }
594
595 4 return 1;
596 }
597
598 /*
599 * Matrix-vector multiplication: result = M^T * v
600 *
601 * Computes the product of the transpose of M with vector v.
602 * This is the common operation in RaBitQ for transforming residuals.
603 *
604 * Rewritten as: result = sum_j (v[j] * row_j)
605 * This accesses rows (contiguous in row-major), enabling auto-vectorization.
606 *
607 * Parameters:
608 * M: Input matrix (dim x dim, row-major)
609 * v: Input vector (dim elements)
610 * result: Output vector (dim elements)
611 * dim: Dimension
612 */
613 void
614 68680 vs_matrix_transpose_vector_mul(
615 const float *M, const float *v, float *result, Dimension dim)
616 {
617 /* Zero result */
618 68680 memset(result, 0, dim * sizeof(float));
619
620 /* Accumulate v[j] * row_j for each row j */
621
2/2
✓ Branch 0 taken 10409965 times.
✓ Branch 1 taken 68680 times.
10478645 for (Dimension j = 0; j < dim; j++)
622 {
623 10409965 const float *row = M + j * dim;
624 10409965 float scale = v[j];
625
626 /* This inner loop auto-vectorizes well */
627
2/2
✓ Branch 0 taken 18296478437 times.
✓ Branch 1 taken 10409965 times.
18306888402 for (Dimension i = 0; i < dim; i++)
628 18296478437 result[i] += scale * row[i];
629 }
630 68680 }
631
632 /*
633 * Matrix-vector multiplication: result = M * v
634 *
635 * Each output element is the dot product of a row with v.
636 * Rows are contiguous in row-major storage, enabling SIMD.
637 *
638 * Parameters:
639 * M: Input matrix (dim x dim, row-major)
640 * v: Input vector (dim elements)
641 * result: Output vector (dim elements)
642 * dim: Dimension
643 */
644 void
645 ✗ vs_matrix_vector_mul(
646 const float *M, const float *v, float *result, Dimension dim)
647 {
648 ✗ for (Dimension i = 0; i < dim; i++)
649 ✗ result[i] = vs_dot_product(M + i * dim, v, dim);
650 ✗ }
651
652 /*
653 * Batched matrix-vector multiplication: results = M^T * vectors
654 *
655 * Computes M^T * v for multiple vectors at once. This is more efficient
656 * than calling vs_matrix_transpose_vector_mul() repeatedly because:
657 * 1. Matrix M is loaded into cache once and reused for all vectors
658 * 2. Inner loop processes contiguous memory (good for SIMD)
659 *
660 * Memory layout:
661 * vectors: count vectors of dim elements each, contiguous (vectors[i*dim +
662 * j]) results: count output vectors, same layout
663 *
664 * Parameters:
665 * M: Input matrix (dim x dim, row-major)
666 * vectors: Input vectors (count * dim elements)
667 * results: Output vectors (count * dim elements)
668 * count: Number of vectors to process
669 * dim: Vector/matrix dimension
670 */
671 VS_TARGET_CLONES static void
672 ✗ matrix_transpose_mul_batch_inner(
673 const float *M_row,
674 const float *vectors,
675 float *results,
676 uint32_t count,
677 Dimension dim,
678 Dimension j)
679 {
680 /* Process each vector - inner loop is contiguous and vectorizes well */
681 ✗ for (uint32_t i = 0; i < count; i++)
682 {
683 ✗ float scale = vectors[i * dim + j];
684 ✗ float *result = results + i * dim;
685 ✗ const float *row = M_row;
686
687 ✗ for (Dimension k = 0; k < dim; k++)
688 ✗ result[k] += scale * row[k];
689 }
690 ✗ }
691
692 static void
693 ✗ matrix_transpose_mul_batch_builtin(
694 const float *M,
695 const float *vectors,
696 float *results,
697 uint32_t count,
698 Dimension dim)
699 {
700 /* Zero all results */
701 ✗ memset(results, 0, (size_t)count * dim * sizeof(float));
702
703 /* Process each row of M - row stays in cache while we update all vectors
704 */
705 ✗ for (Dimension j = 0; j < dim; j++)
706 {
707 ✗ const float *M_row = M + j * dim;
708 ✗ matrix_transpose_mul_batch_inner(
709 M_row, vectors, results, count, dim, j);
710 }
711 ✗ }
712
713 #ifdef VS_HAVE_CBLAS
714 static void
715 matrix_transpose_mul_batch_cblas(
716 const float *M,
717 const float *vectors,
718 float *results,
719 uint32_t count,
720 Dimension dim)
721 {
722 /*
723 * Use CBLAS sgemm for optimized matrix multiplication.
724 *
725 * We want: results[i] = M^T * vectors[i] for each vector i
726 * In row-major form: results = vectors * M
727 *
728 * sgemm: C = alpha * A * B + beta * C
729 * Where: A = vectors (count x dim), B = M (dim x dim), C = results
730 */
731 cblas_sgemm(
732 CblasRowMajor,
733 CblasNoTrans,
734 CblasNoTrans,
735 (int)count, /* M */
736 (int)dim, /* N */
737 (int)dim, /* K */
738 1.0f, /* alpha */
739 vectors, /* A */
740 (int)dim, /* lda */
741 M, /* B */
742 (int)dim, /* ldb */
743 0.0f, /* beta */
744 results, /* C */
745 (int)dim /* ldc */
746 );
747 }
748 #endif /* VS_HAVE_CBLAS */
749
750 /*
751 * Runtime selection of matrix multiplication implementation.
752 * Default: use CBLAS if available, else built-in.
753 */
754 static bool g_use_cblas = true;
755
756 void
757 ✗ vs_matrix_set_use_cblas(bool use_cblas)
758 {
759 ✗ g_use_cblas = use_cblas;
760 ✗ }
761
762 bool
763 2 vs_matrix_get_use_cblas(void)
764 {
765 #ifdef VS_HAVE_CBLAS
766 return g_use_cblas;
767 #else
768 2 return false;
769 #endif
770 }
771
772 const char *
773 ✗ vs_matrix_impl_name(void)
774 {
775 #ifdef VS_HAVE_CBLAS
776 return g_use_cblas ? "cblas" : "builtin";
777 #else
778 ✗ return "builtin";
779 #endif
780 }
781
782 void
783 ✗ vs_matrix_transpose_vector_mul_batch(
784 const float *M,
785 const float *vectors,
786 float *results,
787 uint32_t count,
788 Dimension dim)
789 {
790 #ifdef VS_HAVE_CBLAS
791 if (g_use_cblas)
792 {
793 matrix_transpose_mul_batch_cblas(M, vectors, results, count, dim);
794 return;
795 }
796 #endif
797 ✗ matrix_transpose_mul_batch_builtin(M, vectors, results, count, dim);
798 ✗ }
799