GCC Code Coverage Report


Directory: src/
File: src/quant/fastscan_avx512.c
Date: 2026-11-18 16:12:57
Exec Total Coverage
Lines: 165 169 97.6%
Functions: 5 5 100.0%
Branches: 41 48 85.4%

Line Branch Exec Source
1 /*
2 * Copyright (c) 2026 Tiger Data, Inc.
3 * Licensed under the PostgreSQL License. See LICENSE for details.
4 *
5 * fastscan_avx512.c - AVX-512 VPSHUFB accumulate kernel
6 *
7 * Matches the RaBitQ Library's approach: loads 64B codes + 64B LUT
8 * per iteration (4 subquantizers), uses even/odd byte accumulation
9 * with 4 uint16 accumulator registers.
10 *
11 * Each iteration:
12 * 1. Load 64B codes (4 columns x 16 bytes per nibble group)
13 * 2. Load 64B LUT (4 subquantizer tables x 16 entries)
14 * 3. Split lo/hi nibbles (2 ops)
15 * 4. 2x VPSHUFB: res_lo (vectors 0-15), res_hi (vectors 16-31)
16 * 5. Accumulate with even/odd byte trick (4 add + 2 srli = 6 ops)
17 *
18 * After loop: subtract upper byte contamination, shuffle to output
19 * order, store 32 uint16 results.
20 */
21
22 #include "vs_config.h"
23
24 #ifdef VS_SIMD_FULL
25
26 #if defined(__x86_64__) || defined(_M_X64)
27
28 #include <immintrin.h>
29 #include <stdint.h>
30 #include <string.h>
31
32 #include "quant/fastscan.h"
33
34 __attribute__((target("avx512f,avx512bw"))) void
35 1322 vs_fastscan_accumulate_avx512(
36 const uint8_t *codes,
37 const uint8_t *lut,
38 uint16_t *accum,
39 Dimension dim)
40 {
41 1322 uint32_t code_length = VS_FASTSCAN_GROUP_BYTES(dim);
42
43 1322 const __m512i lo_mask = _mm512_set1_epi8(0x0F);
44 1322 __m512i accu0 = _mm512_setzero_si512();
45 1322 __m512i accu1 = _mm512_setzero_si512();
46 1322 __m512i accu2 = _mm512_setzero_si512();
47 1322 __m512i accu3 = _mm512_setzero_si512();
48
49 /* Accumulate one code block from already-loaded code/LUT registers. */
50 #define ACCUM_BLOCK_512(c_, tab_) \
51 do \
52 { \
53 __m512i lo_ = _mm512_and_si512((c_), lo_mask); \
54 __m512i hi_ = _mm512_and_si512(_mm512_srli_epi16((c_), 4), lo_mask); \
55 __m512i rlo_ = _mm512_shuffle_epi8((tab_), lo_); \
56 __m512i rhi_ = _mm512_shuffle_epi8((tab_), hi_); \
57 accu0 = _mm512_add_epi16(accu0, rlo_); \
58 accu1 = _mm512_add_epi16(accu1, _mm512_srli_epi16(rlo_, 8)); \
59 accu2 = _mm512_add_epi16(accu2, rhi_); \
60 accu3 = _mm512_add_epi16(accu3, _mm512_srli_epi16(rhi_, 8)); \
61 } while (0)
62
63 /* Full 64B blocks with plain loads (unchanged from the original hot
64 * path). code_length is a multiple of 32 but not always 64: a lone
65 * trailing 32B column (when ceil(dim/8) is odd) is read with a masked
66 * load that touches only the valid 32B -- masked-out lanes read as
67 * zero and shuffle to zero, so the phantom column contributes nothing
68 * and nothing is read past the code region. */
69 1322 uint32_t i = 0;
70
2/2
✓ Branch 0 taken 52946 times.
✓ Branch 1 taken 1322 times.
54268 for (; i + 64 <= code_length; i += 64)
71 847136 ACCUM_BLOCK_512(
72 _mm512_loadu_si512((const __m512i *)(codes + i)),
73 _mm512_loadu_si512((const __m512i *)(lut + i)));
74
2/2
✓ Branch 0 taken 74 times.
✓ Branch 1 taken 1248 times.
1322 if (i < code_length)
75 {
76 74 __mmask64 m = 0x00000000FFFFFFFFULL;
77 1184 ACCUM_BLOCK_512(
78 _mm512_maskz_loadu_epi8(m, codes + i),
79 _mm512_maskz_loadu_epi8(m, lut + i));
80 }
81
82 #undef ACCUM_BLOCK_512
83
84 /* Remove upper byte contamination */
85 2644 accu0 = _mm512_sub_epi16(accu0, _mm512_slli_epi16(accu1, 8));
86 2644 accu2 = _mm512_sub_epi16(accu2, _mm512_slli_epi16(accu3, 8));
87
88 /* Combine 4 x 128-bit lanes into final 32 uint16 results.
89 *
90 * Each accumulator has 4 x 128-bit lanes. We need to sum
91 * corresponding lanes across accumulators and reorder to
92 * get vectors 0-31 in order.
93 *
94 * accu0 lanes: [0-7 from lane0, 0-7 from lane1, ...]
95 * accu1 lanes: [8-15 from lane0, 8-15 from lane1, ...]
96 *
97 * Use blend + shuffle_i64x2 to cross-lane sum. */
98 2644 __m512i ret1 = _mm512_add_epi16(
99 _mm512_mask_blend_epi64(0b11110000, accu0, accu1),
100 1322 _mm512_shuffle_i64x2(accu0, accu1, 0b01001110));
101 2644 __m512i ret2 = _mm512_add_epi16(
102 _mm512_mask_blend_epi64(0b11110000, accu2, accu3),
103 1322 _mm512_shuffle_i64x2(accu2, accu3, 0b01001110));
104
105 1322 __m512i ret = _mm512_setzero_si512();
106 2644 ret = _mm512_add_epi16(ret, _mm512_shuffle_i64x2(ret1, ret2, 0b10001000));
107 2644 ret = _mm512_add_epi16(ret, _mm512_shuffle_i64x2(ret1, ret2, 0b11011101));
108
109 ✗ _mm512_storeu_si512((__m512i *)accum, ret);
110 1322 }
111
112 /* ----------------------------------------------------------------
113 * AVX-512 high-accuracy accumulate (uint16 LUT → int32 output)
114 *
115 * Two VPSHUFB passes per code block: one for lo-byte table, one
116 * for hi-byte table. Same codes in registers for both passes.
117 * 8 accumulators: accu[lo/hi][0-3].
118 * Final: result = lo_result + (hi_result << 8)
119 * ---------------------------------------------------------------- */
120
121 /* Accumulate VPSHUFB results into even/odd accumulators */
122 #define HACC_ACCUM_512(tab, lo, hi, a) \
123 do \
124 { \
125 __m512i rlo_ = _mm512_shuffle_epi8(tab, lo); \
126 __m512i rhi_ = _mm512_shuffle_epi8(tab, hi); \
127 a[0] = _mm512_add_epi16(a[0], rlo_); \
128 a[1] = _mm512_add_epi16(a[1], _mm512_srli_epi16(rlo_, 8)); \
129 a[2] = _mm512_add_epi16(a[2], rhi_); \
130 a[3] = _mm512_add_epi16(a[3], _mm512_srli_epi16(rhi_, 8)); \
131 } while (0)
132
133 /* Reduce 4 ZMM accumulators to 16 int32 results */
134 static inline __attribute__((target("avx512f,avx512bw"))) __m512i
135 14871620 hacc_reduce_16(__m512i even, __m512i odd)
136 {
137 15228188 __m256i e = _mm256_add_epi16(
138 356568 _mm512_castsi512_si256(even), _mm512_extracti64x4_epi64(even, 1));
139 15228188 __m256i o = _mm256_add_epi16(
140 356568 _mm512_castsi512_si256(odd), _mm512_extracti64x4_epi64(odd, 1));
141 14871620 e = _mm256_sub_epi16(e, _mm256_slli_epi16(o, 8));
142 15228188 return _mm512_add_epi32(
143 356568 _mm512_cvtepu16_epi32(_mm256_permute2f128_si256(e, o, 0x21)),
144 356568 _mm512_cvtepu16_epi32(_mm256_blend_epi32(e, o, 0xF0)));
145 }
146
147 __attribute__((target("avx512f,avx512bw"))) void
148 3717905 vs_fastscan_accumulate_hacc_avx512(
149 const uint8_t *codes,
150 const uint8_t *lut,
151 int32_t *accum,
152 Dimension dim)
153 {
154 3717905 uint32_t code_length = VS_FASTSCAN_GROUP_BYTES(dim);
155 3717905 const __m512i lo_mask = _mm512_set1_epi8(0x0F);
156
157 3628763 __m512i accu[2][4];
158
2/2
✓ Branch 0 taken 7435810 times.
✓ Branch 1 taken 3717905 times.
11153715 for (int q = 0; q < 2; q++)
159
2/2
✓ Branch 0 taken 29743240 times.
✓ Branch 1 taken 7435810 times.
37179050 for (int r = 0; r < 4; r++)
160 29743240 accu[q][r] = _mm512_setzero_si512();
161
162 /* Accumulate one code block from already-loaded code/LUT registers. */
163 #define HACC_BLOCK_512(c_, tl_, th_) \
164 do \
165 { \
166 __m512i lo_ = _mm512_and_si512((c_), lo_mask); \
167 __m512i hi_ = _mm512_and_si512(_mm512_srli_epi16((c_), 4), lo_mask); \
168 HACC_ACCUM_512((tl_), lo_, hi_, accu[0]); \
169 HACC_ACCUM_512((th_), lo_, hi_, accu[1]); \
170 } while (0)
171
172 /* Full 64B blocks (4 subquantizers) with plain loads -- unchanged
173 * from the original hot path. A lone trailing 32B column (2
174 * subquantizers, when ceil(dim/8) is odd) is read with a masked load
175 * that touches only the valid 32B; masked-out code and LUT lanes read
176 * as zero and shuffle to zero, so the phantom subquantizers
177 * contribute nothing and nothing is read past the code region. */
178 89142 const uint8_t *lp = lut;
179 89142 uint32_t i = 0;
180
2/2
✓ Branch 0 taken 15905053 times.
✓ Branch 1 taken 3717905 times.
19622958 for (; i + 64 <= code_length; i += 64, lp += 128)
181 38891753 HACC_BLOCK_512(
182 _mm512_loadu_si512((const __m512i *)(codes + i)),
183 _mm512_loadu_si512((const __m512i *)lp),
184 _mm512_loadu_si512((const __m512i *)(lp + 64)));
185
2/2
✓ Branch 0 taken 391398 times.
✓ Branch 1 taken 3326507 times.
3717905 if (i < code_length)
186 {
187 391398 __mmask64 m = 0x00000000FFFFFFFFULL;
188 1743248 HACC_BLOCK_512(
189 _mm512_maskz_loadu_epi8(m, codes + i),
190 _mm512_maskz_loadu_epi8(m, lp),
191 _mm512_maskz_loadu_epi8(m, lp + 64));
192 }
193
194 #undef HACC_BLOCK_512
195
196 /* Reduce and combine lo + (hi << 8) */
197 3717905 __m512i lo0 = hacc_reduce_16(accu[0][0], accu[0][1]);
198 3717905 __m512i lo1 = hacc_reduce_16(accu[0][2], accu[0][3]);
199 3717905 __m512i hi0 = hacc_reduce_16(accu[1][0], accu[1][1]);
200 3717905 __m512i hi1 = hacc_reduce_16(accu[1][2], accu[1][3]);
201
202 3717905 _mm512_storeu_si512(
203 (__m512i *)accum,
204 89142 _mm512_add_epi32(lo0, _mm512_slli_epi32(hi0, 8)));
205 3807047 _mm512_storeu_si512(
206 3717905 (__m512i *)(accum + 16),
207 89142 _mm512_add_epi32(lo1, _mm512_slli_epi32(hi1, 8)));
208 3717905 }
209
210 #undef HACC_ACCUM_512
211
212 /* ----------------------------------------------------------------
213 * AVX-512 high-accuracy LUT construction
214 * ---------------------------------------------------------------- */
215
216 __attribute__((target("avx512f,avx512bw,avx512vl"))) void
217 397225 vs_fastscan_build_lut_hacc_avx512(
218 const float *transformed,
219 Dimension dim,
220 uint8_t *lut_out,
221 float *delta_out,
222 float *bias_out)
223 {
224 397225 uint32_t nsq = VS_FASTSCAN_NSQ(dim);
225
226 /* Vectorized min/max */
227 397225 __m512 pos_sum = _mm512_setzero_ps();
228 397225 __m512 neg_sum = _mm512_setzero_ps();
229 397225 __m512 zero = _mm512_setzero_ps();
230
231 397225 uint32_t d = 0;
232
2/2
✓ Branch 0 taken 2001806 times.
✓ Branch 1 taken 397225 times.
2399031 for (; d + 16 <= dim; d += 16)
233 {
234 2267402 __m512 v = _mm512_loadu_ps(transformed + d);
235 2267402 pos_sum = _mm512_add_ps(pos_sum, _mm512_max_ps(v, zero));
236 2267402 neg_sum = _mm512_add_ps(neg_sum, _mm512_min_ps(v, zero));
237 }
238 397225 float global_max = _mm512_reduce_add_ps(pos_sum);
239 397225 float global_min = _mm512_reduce_add_ps(neg_sum);
240
2/2
✓ Branch 0 taken 642057 times.
✓ Branch 1 taken 397225 times.
1039282 for (; d < dim; d++)
241 {
242
2/2
✓ Branch 0 taken 312810 times.
✓ Branch 1 taken 329247 times.
642057 if (transformed[d] > 0)
243 312810 global_max += transformed[d];
244 else
245 329247 global_min += transformed[d];
246 }
247
248 397225 float range = global_max - global_min;
249
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8068 times.
397225 if (range < VS_FASTSCAN_MIN_RANGE)
250 ✗ range = VS_FASTSCAN_MIN_RANGE;
251
252 397225 float delta = range / (float)UINT16_MAX;
253 397225 float inv_delta = 1.0f / delta;
254 397225 *delta_out = delta;
255 397225 *bias_out = global_min * (float)nsq;
256
257 397225 float bias_scaled = -global_min * inv_delta + 0.5f;
258
259 397225 uint32_t lut_bytes = VS_FASTSCAN_LUT_HACC_BYTES(dim);
260 397225 memset(lut_out, 0, lut_bytes);
261
262 397225 __m512 lo_v = _mm512_setzero_ps();
263 397225 __m512 hi_v = _mm512_set1_ps((float)UINT16_MAX);
264 397225 __m512i mask8 = _mm512_set1_epi32(0xFF);
265
266 397225 const float *q = transformed;
267
2/2
✓ Branch 0 taken 8175912 times.
✓ Branch 1 taken 397225 times.
8573137 for (uint32_t sq = 0; sq < nsq; sq++)
268 {
269 8175912 Dimension base = sq * 4;
270
1/2
✓ Branch 0 taken 8175912 times.
✗ Branch 1 not taken.
8175912 float s0 = (base + 0 < dim) ? q[0] * inv_delta : 0.0f;
271
1/2
✓ Branch 0 taken 8175912 times.
✗ Branch 1 not taken.
8175912 float s1 = (base + 1 < dim) ? q[1] * inv_delta : 0.0f;
272
2/2
✓ Branch 0 taken 8175910 times.
✓ Branch 1 taken 2 times.
8175912 float s2 = (base + 2 < dim) ? q[2] * inv_delta : 0.0f;
273
2/2
✓ Branch 0 taken 8143219 times.
✓ Branch 1 taken 32693 times.
8175912 float s3 = (base + 3 < dim) ? q[3] * inv_delta : 0.0f;
274
275 8175912 float p01 = s0 + s1;
276 8175912 float p23 = s2 + s3;
277 8175912 float f0 = bias_scaled;
278 8175912 float f4 = f0 + s2;
279 8175912 float f8 = f0 + s3;
280 8175912 float f12 = f0 + p23;
281
282 9250342 __m512 entries = _mm512_setr_ps(
283 f0,
284 f0 + s0,
285 f0 + s1,
286 f0 + p01,
287 f4,
288 f4 + s0,
289 f4 + s1,
290 f4 + p01,
291 f8,
292 f8 + s0,
293 f8 + s1,
294 f8 + p01,
295 f12,
296 f12 + s0,
297 f12 + s1,
298 f12 + p01);
299
300 8175912 entries = _mm512_max_ps(entries, lo_v);
301 8175912 entries = _mm512_min_ps(entries, hi_v);
302
303 8175912 __m512i int_ent = _mm512_cvttps_epi32(entries);
304
305 /* Split into lo and hi bytes */
306 8175912 __m512i lo_bytes = _mm512_and_si512(int_ent, mask8);
307 7101482 __m512i hi_bytes =
308 9250342 _mm512_and_si512(_mm512_srli_epi32(int_ent, 8), mask8);
309
310 /* Pack 16 int32 → 16 uint8 */
311 8175912 __m256i lo16 = _mm512_cvtepi32_epi16(lo_bytes);
312 8175912 __m128i lo8 = _mm256_cvtepi16_epi8(lo16);
313
314 8175912 __m256i hi16 = _mm512_cvtepi32_epi16(hi_bytes);
315 8175912 __m128i hi8 = _mm256_cvtepi16_epi8(hi16);
316
317 /* Store to interleaved layout */
318 8175912 uint32_t group4 = sq / 4;
319 8175912 uint32_t pos_in_group = sq % 4;
320 8175912 uint8_t *lo_dst = lut_out + group4 * 128 + pos_in_group * 16;
321 8175912 uint8_t *hi_dst = lo_dst + 64;
322
323 7101482 _mm_storeu_si128((__m128i *)lo_dst, lo8);
324 7101482 _mm_storeu_si128((__m128i *)hi_dst, hi8);
325
326 8175912 q += 4;
327 }
328 397225 }
329
330 /* ----------------------------------------------------------------
331 * AVX-512 LUT construction
332 *
333 * Vectorizes both the min/max scan and the per-sq LUT build.
334 * Processes 4 subquantizers (16 floats) per iteration, producing
335 * 64 uint8 LUT entries.
336 * ---------------------------------------------------------------- */
337
338 __attribute__((target("avx512f,avx512bw,avx512vl"))) void
339 126 vs_fastscan_build_lut_avx512(
340 const float *transformed,
341 Dimension dim,
342 uint8_t *lut_out,
343 float *delta_out,
344 float *bias_out)
345 {
346 126 uint32_t nsq = VS_FASTSCAN_NSQ(dim);
347 126 uint32_t nsq_pairs = VS_FASTSCAN_NSQ_PAIRS(dim);
348
349 /* Vectorized min/max: split positive/negative and sum */
350 126 __m512 pos_sum = _mm512_setzero_ps();
351 126 __m512 neg_sum = _mm512_setzero_ps();
352 126 __m512 zero = _mm512_setzero_ps();
353
354 126 uint32_t d = 0;
355
2/2
✓ Branch 0 taken 12522 times.
✓ Branch 1 taken 126 times.
12648 for (; d + 16 <= dim; d += 16)
356 {
357 25044 __m512 v = _mm512_loadu_ps(transformed + d);
358 25044 pos_sum = _mm512_add_ps(pos_sum, _mm512_max_ps(v, zero));
359 25044 neg_sum = _mm512_add_ps(neg_sum, _mm512_min_ps(v, zero));
360 }
361 126 float global_max = _mm512_reduce_add_ps(pos_sum);
362 126 float global_min = _mm512_reduce_add_ps(neg_sum);
363
2/2
✓ Branch 0 taken 206 times.
✓ Branch 1 taken 126 times.
332 for (; d < dim; d++)
364 {
365
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 86 times.
206 if (transformed[d] > 0)
366 120 global_max += transformed[d];
367 else
368 86 global_min += transformed[d];
369 }
370
371 126 float range = global_max - global_min;
372
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 126 times.
126 if (range < VS_FASTSCAN_MIN_RANGE)
373 ✗ range = VS_FASTSCAN_MIN_RANGE;
374
375 126 float delta = range / (float)UINT8_MAX;
376 126 float inv_delta = 1.0f / delta;
377 126 *delta_out = delta;
378 126 *bias_out = global_min * (float)nsq;
379
380 /* +0.5f for round-half-up via truncation (matches scalar) */
381 126 float bias_scaled = -global_min * inv_delta + 0.5f;
382
383 126 memset(lut_out, 0, nsq_pairs * 2 * 16);
384
385 126 __m512 lo_v = _mm512_setzero_ps();
386 126 __m512 hi_v = _mm512_set1_ps((float)UINT8_MAX);
387
388 126 const float *q = transformed;
389
2/2
✓ Branch 0 taken 50140 times.
✓ Branch 1 taken 126 times.
50266 for (uint32_t sq = 0; sq < nsq; sq++)
390 {
391 50140 uint8_t *out = lut_out + sq * 16;
392
393 50140 Dimension base = sq * 4;
394
1/2
✓ Branch 0 taken 50140 times.
✗ Branch 1 not taken.
50140 float s0 = (base + 0 < dim) ? q[0] * inv_delta : 0.0f;
395
1/2
✓ Branch 0 taken 50140 times.
✗ Branch 1 not taken.
50140 float s1 = (base + 1 < dim) ? q[1] * inv_delta : 0.0f;
396
1/2
✓ Branch 0 taken 50140 times.
✗ Branch 1 not taken.
50140 float s2 = (base + 2 < dim) ? q[2] * inv_delta : 0.0f;
397
2/2
✓ Branch 0 taken 50138 times.
✓ Branch 1 taken 2 times.
50140 float s3 = (base + 3 < dim) ? q[3] * inv_delta : 0.0f;
398
399 50140 float p01 = s0 + s1;
400 50140 float p23 = s2 + s3;
401
402 50140 float f0 = bias_scaled;
403 50140 float f4 = f0 + s2;
404 50140 float f8 = f0 + s3;
405 50140 float f12 = f0 + p23;
406
407 /* Build 16 float entries in a ZMM register */
408 100280 __m512 entries = _mm512_setr_ps(
409 f0,
410 f0 + s0,
411 f0 + s1,
412 f0 + p01,
413 f4,
414 f4 + s0,
415 f4 + s1,
416 f4 + p01,
417 f8,
418 f8 + s0,
419 f8 + s1,
420 f8 + p01,
421 f12,
422 f12 + s0,
423 f12 + s1,
424 f12 + p01);
425
426 /* Clamp to [0, 255] and truncate to int32 (matching scalar) */
427 50140 entries = _mm512_max_ps(entries, lo_v);
428 50140 entries = _mm512_min_ps(entries, hi_v);
429 /* Truncate (not round) to match scalar (int)(val) behavior.
430 * The +0.5f in bias_scaled provides round-half-up. */
431 50140 __m512i int_ent = _mm512_cvttps_epi32(entries);
432
433 /* Pack 16 int32 → 16 uint8 via two-stage narrowing:
434 * epi32 → epi16 → epi8. Use pmovdw + pmovwb. */
435 50140 __m256i i16 = _mm512_cvtepi32_epi16(int_ent);
436 50140 __m128i i8 = _mm256_cvtepi16_epi8(i16);
437
438 ✗ _mm_storeu_si128((__m128i *)out, i8);
439
440 50140 q += 4;
441 }
442 126 }
443
444 #endif /* x86_64 */
445
446 #endif /* VS_SIMD_FULL */
447