| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2026 Tiger Data, Inc. | ||
| 3 | * Licensed under the PostgreSQL License. See LICENSE for details. | ||
| 4 | * | ||
| 5 | * vecops.c - General vector operations with SIMD dispatch | ||
| 6 | * | ||
| 7 | * Provides compiler-vectorized implementations with target_clones for | ||
| 8 | * automatic ISA selection. Hand-optimized SIMD implementations can be | ||
| 9 | * added in vecops_avx2.c, vecops_avx512.c, vecops_neon.c if needed. | ||
| 10 | */ | ||
| 11 | |||
| 12 | #include "vs_config.h" | ||
| 13 | |||
| 14 | #include <math.h> | ||
| 15 | #include <stdatomic.h> | ||
| 16 | #include <stddef.h> | ||
| 17 | #include <string.h> | ||
| 18 | |||
| 19 | #include "algo/simd_utils.h" | ||
| 20 | #include "algo/vecops.h" | ||
| 21 | #include "core/platform.h" | ||
| 22 | |||
| 23 | /* | ||
| 24 | * Compiler-Vectorized Implementations | ||
| 25 | * | ||
| 26 | * These use target_clones to generate multiple versions for different ISAs. | ||
| 27 | * The dynamic linker selects the best version at load time. | ||
| 28 | */ | ||
| 29 | |||
| 30 | VS_TARGET_CLONES static float | ||
| 31 | 36832941 | vecops_dot_product_compiler(const float *a, const float *b, Dimension dim) | |
| 32 | { | ||
| 33 | 36832941 | float sum = 0.0f; | |
| 34 |
2/2✓ Branch 0 taken 1734840877 times.
✓ Branch 1 taken 36832941 times.
|
1771673818 | for (Dimension i = 0; i < dim; i++) |
| 35 | 1734840877 | sum += a[i] * b[i]; | |
| 36 | 36832941 | return sum; | |
| 37 | } | ||
| 38 | |||
| 39 | VS_TARGET_CLONES static float | ||
| 40 | 36034779 | vecops_l2_norm_squared_compiler(const float *v, Dimension dim) | |
| 41 | { | ||
| 42 | 36034779 | float sum = 0.0f; | |
| 43 |
2/2✓ Branch 0 taken 1848711420 times.
✓ Branch 1 taken 36034779 times.
|
1884746199 | for (Dimension i = 0; i < dim; i++) |
| 44 | 1848711420 | sum += v[i] * v[i]; | |
| 45 | 36034779 | return sum; | |
| 46 | } | ||
| 47 | |||
| 48 | VS_TARGET_CLONES static float | ||
| 49 | 656569 | vecops_vector_sum_compiler(const float *v, Dimension dim) | |
| 50 | { | ||
| 51 | 656569 | float sum = 0.0f; | |
| 52 |
2/2✓ Branch 0 taken 119227500 times.
✓ Branch 1 taken 656569 times.
|
119884069 | for (Dimension i = 0; i < dim; i++) |
| 53 | 119227500 | sum += v[i]; | |
| 54 | 656569 | return sum; | |
| 55 | } | ||
| 56 | |||
| 57 | VS_TARGET_CLONES static void | ||
| 58 | 784002 | vecops_vector_sub_compiler( | |
| 59 | const float *a, const float *b, float *out, Dimension dim) | ||
| 60 | { | ||
| 61 |
2/2✓ Branch 0 taken 183493929 times.
✓ Branch 1 taken 784002 times.
|
184277931 | for (Dimension i = 0; i < dim; i++) |
| 62 | 183493929 | out[i] = a[i] - b[i]; | |
| 63 | 784002 | } | |
| 64 | |||
| 65 | VS_TARGET_CLONES static void | ||
| 66 | 743 | vecops_vector_add_compiler( | |
| 67 | const float *a, const float *b, float *out, Dimension dim) | ||
| 68 | { | ||
| 69 |
2/2✓ Branch 0 taken 164179 times.
✓ Branch 1 taken 743 times.
|
164922 | for (Dimension i = 0; i < dim; i++) |
| 70 | 164179 | out[i] = a[i] + b[i]; | |
| 71 | 743 | } | |
| 72 | |||
| 73 | VS_TARGET_CLONES static void | ||
| 74 | 39651 | vecops_vector_scale_compiler( | |
| 75 | const float *v, float scalar, float *out, Dimension dim) | ||
| 76 | { | ||
| 77 |
2/2✓ Branch 0 taken 6357206 times.
✓ Branch 1 taken 39651 times.
|
6396857 | for (Dimension i = 0; i < dim; i++) |
| 78 | 6357206 | out[i] = v[i] * scalar; | |
| 79 | 39651 | } | |
| 80 | |||
| 81 | VS_TARGET_CLONES static float | ||
| 82 | 20313791 | vecops_l2_distance_squared_compiler( | |
| 83 | const float *a, const float *b, Dimension dim) | ||
| 84 | { | ||
| 85 | 20313791 | float sum = 0.0f; | |
| 86 |
2/2✓ Branch 0 taken 1617306738 times.
✓ Branch 1 taken 20313791 times.
|
1637620529 | for (Dimension i = 0; i < dim; i++) |
| 87 | { | ||
| 88 | 1617306738 | float diff = a[i] - b[i]; | |
| 89 | 1617306738 | sum += diff * diff; | |
| 90 | } | ||
| 91 | 20313791 | return sum; | |
| 92 | } | ||
| 93 | |||
| 94 | /* | ||
| 95 | * Function Pointer Dispatch | ||
| 96 | */ | ||
| 97 | |||
| 98 | typedef float (*DotProductFn)(const float *, const float *, Dimension); | ||
| 99 | typedef float (*NormFn)(const float *, Dimension); | ||
| 100 | typedef float (*SumFn)(const float *, Dimension); | ||
| 101 | typedef void (*BinaryOpFn)(const float *, const float *, float *, Dimension); | ||
| 102 | typedef void (*ScaleFn)(const float *, float, float *, Dimension); | ||
| 103 | typedef float (*DistanceFn)(const float *, const float *, Dimension); | ||
| 104 | |||
| 105 | /* | ||
| 106 | * Selected implementations, published on first use. | ||
| 107 | * | ||
| 108 | * Atomic because two threads racing the first call can both pass the | ||
| 109 | * g_initialized check and both store here. The stores pick the same | ||
| 110 | * implementation, but concurrent non-atomic stores to one object are | ||
| 111 | * a data race whatever they write. Only standalone runs threads; a | ||
| 112 | * PostgreSQL backend is a process with its own copy. | ||
| 113 | */ | ||
| 114 | static _Atomic(DotProductFn) g_dot_product_fn = NULL; | ||
| 115 | static _Atomic(NormFn) g_l2_norm_squared_fn = NULL; | ||
| 116 | static _Atomic(SumFn) g_vector_sum_fn = NULL; | ||
| 117 | static _Atomic(BinaryOpFn) g_vector_sub_fn = NULL; | ||
| 118 | static _Atomic(BinaryOpFn) g_vector_add_fn = NULL; | ||
| 119 | static _Atomic(ScaleFn) g_vector_scale_fn = NULL; | ||
| 120 | static _Atomic(DistanceFn) g_l2_distance_squared_fn = NULL; | ||
| 121 | |||
| 122 | static _Atomic(const char *) g_impl_name = NULL; | ||
| 123 | static _Atomic(bool) g_initialized = false; | ||
| 124 | |||
| 125 | void | ||
| 126 | 16 | vs_vecops_force_reinit(void) | |
| 127 | { | ||
| 128 | 16 | g_initialized = false; | |
| 129 | 16 | g_dot_product_fn = NULL; | |
| 130 | 16 | g_l2_norm_squared_fn = NULL; | |
| 131 | 16 | g_vector_sum_fn = NULL; | |
| 132 | 16 | g_vector_sub_fn = NULL; | |
| 133 | 16 | g_vector_add_fn = NULL; | |
| 134 | 16 | g_vector_scale_fn = NULL; | |
| 135 | 16 | g_l2_distance_squared_fn = NULL; | |
| 136 | 16 | g_impl_name = NULL; | |
| 137 | 16 | } | |
| 138 | |||
| 139 | int | ||
| 140 | 239 | vs_vecops_init(void) | |
| 141 | { | ||
| 142 |
2/2✓ Branch 0 taken 209 times.
✓ Branch 1 taken 30 times.
|
239 | if (g_initialized) |
| 143 | 6 | return 0; | |
| 144 | |||
| 145 | /* | ||
| 146 | * For now, use compiler-vectorized implementations for all operations. | ||
| 147 | * Hand-optimized SIMD can be added later if profiling shows benefit. | ||
| 148 | * | ||
| 149 | * The compiler does a good job with these simple loops, especially | ||
| 150 | * with target_clones generating AVX2/AVX-512 versions automatically. | ||
| 151 | */ | ||
| 152 | 233 | g_dot_product_fn = vecops_dot_product_compiler; | |
| 153 | 233 | g_l2_norm_squared_fn = vecops_l2_norm_squared_compiler; | |
| 154 | 233 | g_vector_sum_fn = vecops_vector_sum_compiler; | |
| 155 | 233 | g_vector_sub_fn = vecops_vector_sub_compiler; | |
| 156 | 233 | g_vector_add_fn = vecops_vector_add_compiler; | |
| 157 | 233 | g_vector_scale_fn = vecops_vector_scale_compiler; | |
| 158 | 233 | g_l2_distance_squared_fn = vecops_l2_distance_squared_compiler; | |
| 159 | 233 | g_impl_name = "compiler"; | |
| 160 | |||
| 161 | 233 | g_initialized = true; | |
| 162 | 233 | return 0; | |
| 163 | } | ||
| 164 | |||
| 165 | const char * | ||
| 166 | 4 | vs_vecops_impl_name(void) | |
| 167 | { | ||
| 168 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
|
4 | if (vs_unlikely(!g_initialized)) |
| 169 | 2 | vs_vecops_init(); | |
| 170 | 4 | return g_impl_name; | |
| 171 | } | ||
| 172 | |||
| 173 | /* | ||
| 174 | * Public API | ||
| 175 | */ | ||
| 176 | |||
| 177 | float | ||
| 178 | 36832941 | vs_dot_product(const float *a, const float *b, Dimension dim) | |
| 179 | { | ||
| 180 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 36832938 times.
|
36832941 | if (vs_unlikely(!g_initialized)) |
| 181 | 3 | vs_vecops_init(); | |
| 182 | 36832941 | return g_dot_product_fn(a, b, dim); | |
| 183 | } | ||
| 184 | |||
| 185 | float | ||
| 186 | 36034779 | vs_l2_norm_squared(const float *v, Dimension dim) | |
| 187 | { | ||
| 188 |
2/2✓ Branch 0 taken 137 times.
✓ Branch 1 taken 36034642 times.
|
36034779 | if (vs_unlikely(!g_initialized)) |
| 189 | 137 | vs_vecops_init(); | |
| 190 | 36034779 | return g_l2_norm_squared_fn(v, dim); | |
| 191 | } | ||
| 192 | |||
| 193 | float | ||
| 194 | 25467 | vs_l2_norm(const float *v, Dimension dim) | |
| 195 | { | ||
| 196 | 25467 | return sqrtf(vs_l2_norm_squared(v, dim)); | |
| 197 | } | ||
| 198 | |||
| 199 | float | ||
| 200 | 656569 | vec32_sum(const float *v, Dimension dim) | |
| 201 | { | ||
| 202 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 656567 times.
|
656569 | if (vs_unlikely(!g_initialized)) |
| 203 | 2 | vs_vecops_init(); | |
| 204 | 656569 | return g_vector_sum_fn(v, dim); | |
| 205 | } | ||
| 206 | |||
| 207 | void | ||
| 208 | 784002 | vec32_sub(const float *a, const float *b, float *out, Dimension dim) | |
| 209 | { | ||
| 210 |
2/2✓ Branch 0 taken 73 times.
✓ Branch 1 taken 783929 times.
|
784002 | if (vs_unlikely(!g_initialized)) |
| 211 | 73 | vs_vecops_init(); | |
| 212 | 784002 | g_vector_sub_fn(a, b, out, dim); | |
| 213 | 784002 | } | |
| 214 | |||
| 215 | void | ||
| 216 | 743 | vec32_add(const float *a, const float *b, float *out, Dimension dim) | |
| 217 | { | ||
| 218 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 741 times.
|
743 | if (vs_unlikely(!g_initialized)) |
| 219 | 2 | vs_vecops_init(); | |
| 220 | 743 | g_vector_add_fn(a, b, out, dim); | |
| 221 | 743 | } | |
| 222 | |||
| 223 | void | ||
| 224 | 39651 | vec32_scale(const float *v, float scalar, float *out, Dimension dim) | |
| 225 | { | ||
| 226 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 39649 times.
|
39651 | if (vs_unlikely(!g_initialized)) |
| 227 | 2 | vs_vecops_init(); | |
| 228 | 39651 | g_vector_scale_fn(v, scalar, out, dim); | |
| 229 | 39651 | } | |
| 230 | |||
| 231 | void | ||
| 232 | 100 | vec32_mean(const float *vectors, uint32_t nvecs, Dimension dim, float *out) | |
| 233 | { | ||
| 234 | 100 | memset(out, 0, dim * sizeof(float)); | |
| 235 |
2/2✓ Branch 0 taken 735 times.
✓ Branch 1 taken 100 times.
|
835 | for (uint32_t i = 0; i < nvecs; i++) |
| 236 | 735 | vec32_add(out, vectors + (size_t)i * dim, out, dim); | |
| 237 | 100 | vec32_scale(out, 1.0f / (float)nvecs, out, dim); | |
| 238 | 100 | } | |
| 239 | |||
| 240 | void | ||
| 241 | 18 | vs_global_mean( | |
| 242 | const float *centroids, | ||
| 243 | uint32_t ncentroids, | ||
| 244 | Dimension dim, | ||
| 245 | DistanceMetric metric, | ||
| 246 | float *out) | ||
| 247 | { | ||
| 248 | 18 | vec32_mean(centroids, ncentroids, dim, out); | |
| 249 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 16 times.
|
18 | if (metric == DISTANCE_COSINE) |
| 250 | 2 | vs_l2_normalize(out, dim); | |
| 251 | 18 | } | |
| 252 | |||
| 253 | float | ||
| 254 | 20313791 | vs_l2_distance_squared(const float *a, const float *b, Dimension dim) | |
| 255 | { | ||
| 256 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 20313779 times.
|
20313791 | if (vs_unlikely(!g_initialized)) |
| 257 | 12 | vs_vecops_init(); | |
| 258 | 20313791 | return g_l2_distance_squared_fn(a, b, dim); | |
| 259 | } | ||
| 260 |