| 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 |