Pixie
Loading...
Searching...
No Matches
select.h
1#pragma once
2
3/*
4 * Select512 benchmark summary, 2026-06-09.
5 *
6 * Conditions: taskset -c 0, FillPermille=500, 3 repetitions, aggregate CPU ns.
7 * RankMode columns:
8 * - r0: first valid rank in the block.
9 * - r1: middle valid rank in the block.
10 * - r2: last valid rank in the block.
11 * - r3: random valid rank in the block.
12 *
13 * AVX512 disabled, BMI2 enabled:
14 *
15 * | Query | Variant | r0 ns | r1 ns | r2 ns | r3 ns |
16 * |---------|----------|-------|-------|-------|-------|
17 * | select1 | Current | 1.63 | 2.26 | 3.19 | 2.34 |
18 * | select1 | AVX2PDEP | 1.67 | 2.82 | 4.07 | 2.89 |
19 * | select0 | Current | 1.64 | 2.67 | 3.77 | 2.77 |
20 * | select0 | AVX2PDEP | 1.81 | 2.90 | 4.24 | 2.96 |
21 *
22 * AVX512 disabled, BMI2 disabled:
23 *
24 * | Query | Variant | r0 ns | r1 ns | r2 ns | r3 ns |
25 * |---------|------------|-------|-------|-------|-------|
26 * | select1 | Current | 1.82 | 3.25 | 4.38 | 3.26 |
27 * | select1 | AVX2NoPDEP | 2.18 | 3.66 | 5.30 | 3.81 |
28 * | select0 | Current | 1.89 | 3.65 | 5.20 | 3.61 |
29 * | select0 | AVX2NoPDEP | 2.16 | 3.72 | 5.28 | 3.89 |
30 *
31 * Interpretation: for 512-bit blocks, AVX2 setup costs more than it saves.
32 * Production therefore dispatches AVX-512 -> scalar and deliberately skips AVX2
33 * in the default path. The AVX2 variants stay here for explicit experiments.
34 * With AVX-512 available, the vector prefix path remains useful for late or
35 * fixed-latency ranks, while ScalarPDEP is usually faster for first, middle,
36 * and random ranks.
37 */
38
39#include <pixie/bits.h>
40
41#include <bit>
42#include <cstddef>
43#include <cstdint>
44
45namespace pixie::experimental {
46
58
59struct SelectByteLut {
60 uint8_t popcounts[256];
61 uint8_t select[256][8];
62
63 constexpr SelectByteLut() : popcounts{}, select{} {
64 for (int b = 0; b < 256; ++b) {
65 for (int r = 0; r < 8; ++r) {
66 select[b][r] = 8;
67 }
68
69 int rank = 0;
70 for (int i = 0; i < 8; ++i) {
71 if (((b >> i) & 1) != 0) {
72 select[b][rank++] = static_cast<uint8_t>(i);
73 }
74 }
75 popcounts[b] = static_cast<uint8_t>(rank);
76 }
77 }
78};
79
80inline constexpr SelectByteLut kSelectByteLut;
81
82static inline uint64_t select_64_pdep(uint64_t x, uint64_t rank) noexcept {
83 return ::select_64(x, rank);
84}
85
86static inline uint64_t select_64_vigna_broadword(uint64_t x,
87 uint64_t rank) noexcept {
88 constexpr uint64_t kOnesStep4 = 0x1111111111111111ull;
89 constexpr uint64_t kOnesStep8 = 0x0101010101010101ull;
90 constexpr uint64_t kHighBitsStep8 = 0x8080808080808080ull;
91
92 uint64_t sums = x;
93 sums = sums - ((sums & (0xAull * kOnesStep4)) >> 1);
94 sums = (sums & (0x3ull * kOnesStep4)) + ((sums >> 2) & (0x3ull * kOnesStep4));
95 sums = (sums + (sums >> 4)) & (0xFull * kOnesStep8);
96
97 const uint64_t byte_sums = sums * kOnesStep8;
98 const uint64_t rank_bytes = rank * kOnesStep8;
99 const uint64_t ge_rank =
100 ((rank_bytes | kHighBitsStep8) - byte_sums) & kHighBitsStep8;
101 const uint64_t byte_index = std::popcount(ge_rank);
102 const uint64_t byte_rank =
103 rank - (((byte_sums << 8) >> (8 * byte_index)) & 0xFFull);
104 const auto byte = static_cast<uint8_t>(x >> (8 * byte_index));
105 return 8 * byte_index + kSelectByteLut.select[byte][byte_rank];
106}
107
108static inline uint64_t select_64_byte_lut(uint64_t x, uint64_t rank) noexcept {
109 for (uint64_t byte_index = 0; byte_index < 8; ++byte_index) {
110 const auto byte = static_cast<uint8_t>(x >> (8 * byte_index));
111 const uint8_t count = kSelectByteLut.popcounts[byte];
112 if (rank < count) {
113 return 8 * byte_index + kSelectByteLut.select[byte][rank];
114 }
115 rank -= count;
116 }
117 return 64;
118}
119
120static inline uint64_t select_64_broadword_lut(uint64_t x,
121 uint64_t rank) noexcept {
122 constexpr uint64_t kOnes = 0x0101010101010101ull;
123 constexpr uint64_t kHighBits = 0x8080808080808080ull;
124
125 uint64_t byte_counts = x - ((x >> 1) & 0x5555555555555555ull);
126 byte_counts = (byte_counts & 0x3333333333333333ull) +
127 ((byte_counts >> 2) & 0x3333333333333333ull);
128 byte_counts = (byte_counts + (byte_counts >> 4)) & 0x0F0F0F0F0F0F0F0Full;
129
130 const uint64_t prefix = byte_counts * kOnes;
131 const uint64_t threshold = rank + 1;
132 const uint64_t prefix_less_than_threshold =
133 (kOnes * (127 + threshold) - (prefix & 0x7F7F7F7F7F7F7F7Full)) & ~prefix &
134 kHighBits;
135 const uint64_t byte_index = std::popcount(prefix_less_than_threshold);
136 const uint64_t previous =
137 byte_index == 0 ? 0 : ((prefix >> (8 * (byte_index - 1))) & 0xFFull);
138 const auto byte = static_cast<uint8_t>(x >> (8 * byte_index));
139 return 8 * byte_index + kSelectByteLut.select[byte][rank - previous];
140}
141
142static inline uint64_t select_64_binary_lut(uint64_t x,
143 uint64_t rank) noexcept {
144 uint64_t offset = 0;
145
146 uint64_t count = std::popcount(static_cast<uint32_t>(x));
147 if (rank >= count) {
148 rank -= count;
149 x >>= 32;
150 offset += 32;
151 }
152
153 count = std::popcount(static_cast<uint16_t>(x));
154 if (rank >= count) {
155 rank -= count;
156 x >>= 16;
157 offset += 16;
158 }
159
160 const auto low_byte = static_cast<uint8_t>(x);
161 count = kSelectByteLut.popcounts[low_byte];
162 if (rank >= count) {
163 rank -= count;
164 x >>= 8;
165 offset += 8;
166 }
167
168 return offset + kSelectByteLut.select[static_cast<uint8_t>(x)][rank];
169}
170
171static inline uint64_t select_64_no_pdep(uint64_t x, uint64_t rank) noexcept {
172 return select_64_binary_lut(x, rank);
173}
174
175static inline uint64_t select_64_experimental_default(uint64_t x,
176 uint64_t rank) noexcept {
177#ifdef PIXIE_EXPERIMENTAL_SELECT_NO_PDEP
178 return select_64_no_pdep(x, rank);
179#else
180 return select_64_pdep(x, rank);
181#endif
182}
183
184template <bool Invert>
185static inline uint64_t select_512_word_count(uint64_t word) noexcept {
186 if constexpr (Invert) {
187 return std::popcount(~word);
188 } else {
189 return std::popcount(word);
190 }
191}
192
193template <bool Invert>
194static inline uint64_t select_512_select_word(uint64_t word) noexcept {
195 if constexpr (Invert) {
196 return ~word;
197 } else {
198 return word;
199 }
200}
201
202template <uint64_t (*SelectWord)(uint64_t, uint64_t), bool Invert>
203static inline uint64_t select_512_scalar_impl(const uint64_t* x,
204 uint64_t rank) noexcept {
205 for (size_t i = 0; i < 8; ++i) {
206 const uint64_t count = select_512_word_count<Invert>(x[i]);
207 if (rank < count) {
208 const uint64_t word = select_512_select_word<Invert>(x[i]);
209 return i * 64 + SelectWord(word, rank);
210 }
211 rank -= count;
212 }
213 return 512;
214}
215
216static inline uint64_t select_512_scalar_pdep(const uint64_t* x,
217 uint64_t rank) noexcept {
218 return select_512_scalar_impl<select_64_pdep, false>(x, rank);
219}
220
221static inline uint64_t select0_512_scalar_pdep(const uint64_t* x,
222 uint64_t rank) noexcept {
223 return select_512_scalar_impl<select_64_pdep, true>(x, rank);
224}
225
226static inline uint64_t select_512_scalar_byte_lut(const uint64_t* x,
227 uint64_t rank) noexcept {
228 return select_512_scalar_impl<select_64_byte_lut, false>(x, rank);
229}
230
231static inline uint64_t select0_512_scalar_byte_lut(const uint64_t* x,
232 uint64_t rank) noexcept {
233 return select_512_scalar_impl<select_64_byte_lut, true>(x, rank);
234}
235
236static inline uint64_t select_512_scalar_broadword_lut(const uint64_t* x,
237 uint64_t rank) noexcept {
238 return select_512_scalar_impl<select_64_broadword_lut, false>(x, rank);
239}
240
241static inline uint64_t select0_512_scalar_broadword_lut(
242 const uint64_t* x,
243 uint64_t rank) noexcept {
244 return select_512_scalar_impl<select_64_broadword_lut, true>(x, rank);
245}
246
247static inline uint64_t select_512_scalar_binary_lut(const uint64_t* x,
248 uint64_t rank) noexcept {
249 return select_512_scalar_impl<select_64_binary_lut, false>(x, rank);
250}
251
252static inline uint64_t select0_512_scalar_binary_lut(const uint64_t* x,
253 uint64_t rank) noexcept {
254 return select_512_scalar_impl<select_64_binary_lut, true>(x, rank);
255}
256
257static inline uint64_t select_512_scalar_vigna_broadword(
258 const uint64_t* x,
259 uint64_t rank) noexcept {
260 return select_512_scalar_impl<select_64_vigna_broadword, false>(x, rank);
261}
262
263static inline uint64_t select0_512_scalar_vigna_broadword(
264 const uint64_t* x,
265 uint64_t rank) noexcept {
266 return select_512_scalar_impl<select_64_vigna_broadword, true>(x, rank);
267}
268
269static inline uint64_t select_512_scalar_no_pdep(const uint64_t* x,
270 uint64_t rank) noexcept {
271 return select_512_scalar_impl<select_64_no_pdep, false>(x, rank);
272}
273
274static inline uint64_t select0_512_scalar_no_pdep(const uint64_t* x,
275 uint64_t rank) noexcept {
276 return select_512_scalar_impl<select_64_no_pdep, true>(x, rank);
277}
278
279static inline uint64_t select_512_scalar_experimental_default(
280 const uint64_t* x,
281 uint64_t rank) noexcept {
282 return select_512_scalar_impl<select_64_experimental_default, false>(x, rank);
283}
284
285static inline uint64_t select0_512_scalar_experimental_default(
286 const uint64_t* x,
287 uint64_t rank) noexcept {
288 return select_512_scalar_impl<select_64_experimental_default, true>(x, rank);
289}
290
291#ifdef PIXIE_AVX2_SUPPORT
292template <bool Invert>
293static inline void select_512_avx2_counts(const uint64_t* x,
294 uint64_t* counts) noexcept {
295 const __m256i low_mask = _mm256_set1_epi8(0x0F);
296 const __m256i zero = _mm256_setzero_si256();
297 const __m256i sixty_four = _mm256_set1_epi64x(64);
298
299 for (int half = 0; half < 2; ++half) {
300 const __m256i words =
301 _mm256_loadu_si256(reinterpret_cast<const __m256i*>(x + 4 * half));
302
303 const __m256i low_nibbles = _mm256_and_si256(words, low_mask);
304 const __m256i high_nibbles =
305 _mm256_and_si256(_mm256_srli_epi16(words, 4), low_mask);
306 const __m256i byte_counts =
307 _mm256_add_epi8(_mm256_shuffle_epi8(lookup_popcount_4, low_nibbles),
308 _mm256_shuffle_epi8(lookup_popcount_4, high_nibbles));
309 __m256i word_counts = _mm256_sad_epu8(byte_counts, zero);
310 if constexpr (Invert) {
311 word_counts = _mm256_sub_epi64(sixty_four, word_counts);
312 }
313 _mm256_store_si256(reinterpret_cast<__m256i*>(counts + 4 * half),
314 word_counts);
315 }
316}
317
318template <uint64_t (*SelectWord)(uint64_t, uint64_t), bool Invert>
319static inline uint64_t select_512_avx2_impl(const uint64_t* x,
320 uint64_t rank) noexcept {
321 alignas(32) uint64_t counts[8];
322 select_512_avx2_counts<Invert>(x, counts);
323
324 for (size_t i = 0; i < 8; ++i) {
325 if (rank < counts[i]) {
326 const uint64_t word = select_512_select_word<Invert>(x[i]);
327 return i * 64 + SelectWord(word, rank);
328 }
329 rank -= counts[i];
330 }
331 return 512;
332}
333#endif
334
335static inline uint64_t select_512_avx2_pdep(const uint64_t* x,
336 uint64_t rank) noexcept {
337#ifdef PIXIE_AVX2_SUPPORT
338 return select_512_avx2_impl<select_64_pdep, false>(x, rank);
339#else
340 return select_512_scalar_pdep(x, rank);
341#endif
342}
343
344static inline uint64_t select0_512_avx2_pdep(const uint64_t* x,
345 uint64_t rank) noexcept {
346#ifdef PIXIE_AVX2_SUPPORT
347 return select_512_avx2_impl<select_64_pdep, true>(x, rank);
348#else
349 return select0_512_scalar_pdep(x, rank);
350#endif
351}
352
353static inline uint64_t select_512_avx2_byte_lut(const uint64_t* x,
354 uint64_t rank) noexcept {
355#ifdef PIXIE_AVX2_SUPPORT
356 return select_512_avx2_impl<select_64_byte_lut, false>(x, rank);
357#else
358 return select_512_scalar_byte_lut(x, rank);
359#endif
360}
361
362static inline uint64_t select0_512_avx2_byte_lut(const uint64_t* x,
363 uint64_t rank) noexcept {
364#ifdef PIXIE_AVX2_SUPPORT
365 return select_512_avx2_impl<select_64_byte_lut, true>(x, rank);
366#else
367 return select0_512_scalar_byte_lut(x, rank);
368#endif
369}
370
371static inline uint64_t select_512_avx2_broadword_lut(const uint64_t* x,
372 uint64_t rank) noexcept {
373#ifdef PIXIE_AVX2_SUPPORT
374 return select_512_avx2_impl<select_64_broadword_lut, false>(x, rank);
375#else
376 return select_512_scalar_broadword_lut(x, rank);
377#endif
378}
379
380static inline uint64_t select0_512_avx2_broadword_lut(const uint64_t* x,
381 uint64_t rank) noexcept {
382#ifdef PIXIE_AVX2_SUPPORT
383 return select_512_avx2_impl<select_64_broadword_lut, true>(x, rank);
384#else
385 return select0_512_scalar_broadword_lut(x, rank);
386#endif
387}
388
389static inline uint64_t select_512_avx2_binary_lut(const uint64_t* x,
390 uint64_t rank) noexcept {
391#ifdef PIXIE_AVX2_SUPPORT
392 return select_512_avx2_impl<select_64_binary_lut, false>(x, rank);
393#else
394 return select_512_scalar_binary_lut(x, rank);
395#endif
396}
397
398static inline uint64_t select0_512_avx2_binary_lut(const uint64_t* x,
399 uint64_t rank) noexcept {
400#ifdef PIXIE_AVX2_SUPPORT
401 return select_512_avx2_impl<select_64_binary_lut, true>(x, rank);
402#else
403 return select0_512_scalar_binary_lut(x, rank);
404#endif
405}
406
407static inline uint64_t select_512_avx2_vigna_broadword(const uint64_t* x,
408 uint64_t rank) noexcept {
409#ifdef PIXIE_AVX2_SUPPORT
410 return select_512_avx2_impl<select_64_vigna_broadword, false>(x, rank);
411#else
412 return select_512_scalar_vigna_broadword(x, rank);
413#endif
414}
415
416static inline uint64_t select0_512_avx2_vigna_broadword(
417 const uint64_t* x,
418 uint64_t rank) noexcept {
419#ifdef PIXIE_AVX2_SUPPORT
420 return select_512_avx2_impl<select_64_vigna_broadword, true>(x, rank);
421#else
422 return select0_512_scalar_vigna_broadword(x, rank);
423#endif
424}
425
426static inline uint64_t select_512_avx2_no_pdep(const uint64_t* x,
427 uint64_t rank) noexcept {
428#ifdef PIXIE_AVX2_SUPPORT
429 return select_512_avx2_impl<select_64_no_pdep, false>(x, rank);
430#else
431 return select_512_scalar_no_pdep(x, rank);
432#endif
433}
434
435static inline uint64_t select0_512_avx2_no_pdep(const uint64_t* x,
436 uint64_t rank) noexcept {
437#ifdef PIXIE_AVX2_SUPPORT
438 return select_512_avx2_impl<select_64_no_pdep, true>(x, rank);
439#else
440 return select0_512_scalar_no_pdep(x, rank);
441#endif
442}
443
444static inline uint64_t select_512_avx2_experimental_default(
445 const uint64_t* x,
446 uint64_t rank) noexcept {
447#ifdef PIXIE_AVX2_SUPPORT
448 return select_512_avx2_impl<select_64_experimental_default, false>(x, rank);
449#else
450 return select_512_scalar_experimental_default(x, rank);
451#endif
452}
453
454static inline uint64_t select0_512_avx2_experimental_default(
455 const uint64_t* x,
456 uint64_t rank) noexcept {
457#ifdef PIXIE_AVX2_SUPPORT
458 return select_512_avx2_impl<select_64_experimental_default, true>(x, rank);
459#else
460 return select0_512_scalar_experimental_default(x, rank);
461#endif
462}
463
464#ifdef PIXIE_AVX512_SUPPORT
465static inline __m512i select_512_avx512_prefix_sum_u64(
466 __m512i counts) noexcept {
467 const __m512i idx_shift1 = _mm512_set_epi64(6, 5, 4, 3, 2, 1, 0, 0);
468 const __m512i idx_shift2 = _mm512_set_epi64(5, 4, 3, 2, 1, 0, 0, 0);
469 const __m512i idx_shift4 = _mm512_set_epi64(3, 2, 1, 0, 0, 0, 0, 0);
470
471 __m512i tmp = _mm512_maskz_permutexvar_epi64(0xFE, idx_shift1, counts);
472 counts = _mm512_add_epi64(counts, tmp);
473 tmp = _mm512_maskz_permutexvar_epi64(0xFC, idx_shift2, counts);
474 counts = _mm512_add_epi64(counts, tmp);
475 tmp = _mm512_maskz_permutexvar_epi64(0xF0, idx_shift4, counts);
476 return _mm512_add_epi64(counts, tmp);
477}
478
479static inline uint64_t select_512_avx512_previous_prefix(
480 __m512i prefix,
481 uint32_t lane) noexcept {
482 if (lane == 0) {
483 return 0;
484 }
485 const __m512i idx_previous =
486 _mm512_set1_epi64(static_cast<int64_t>(lane - 1));
487 const __m512i previous_vec = _mm512_permutexvar_epi64(idx_previous, prefix);
488 return static_cast<uint64_t>(
489 _mm_cvtsi128_si64(_mm512_castsi512_si128(previous_vec)));
490}
491
492template <uint64_t (*SelectWord)(uint64_t, uint64_t), bool Invert>
493static inline uint64_t select_512_avx512_impl(const uint64_t* x,
494 uint64_t rank) noexcept {
495 __m512i words = _mm512_loadu_epi64(x);
496 __m512i prefix = _mm512_popcnt_epi64(words);
497 if constexpr (Invert) {
498 prefix = _mm512_sub_epi64(_mm512_set1_epi64(64), prefix);
499 }
500
501 prefix = select_512_avx512_prefix_sum_u64(prefix);
502
503 const __mmask8 mask = _mm512_cmpgt_epu64_mask(
504 prefix, _mm512_set1_epi64(static_cast<int64_t>(rank)));
505 const uint32_t lane = _tzcnt_u32(static_cast<uint32_t>(mask));
506
507 const uint64_t previous = select_512_avx512_previous_prefix(prefix, lane);
508 const uint64_t word = select_512_select_word<Invert>(x[lane]);
509 return lane * 64 + SelectWord(word, rank - previous);
510}
511
512template <uint64_t (*SelectWord)(uint64_t, uint64_t), bool Invert>
513static inline uint64_t select_512_avx512_tail_impl(
514 const uint64_t* x,
515 uint64_t rank,
516 uint32_t base_word,
517 uint32_t word_count) noexcept {
518 const __mmask8 active_mask =
519 static_cast<__mmask8>((uint32_t{1} << word_count) - 1);
520 const __m512i words = _mm512_maskz_loadu_epi64(active_mask, x + base_word);
521 __m512i counts = _mm512_popcnt_epi64(words);
522 if constexpr (Invert) {
523 counts = _mm512_maskz_sub_epi64(active_mask, _mm512_set1_epi64(64), counts);
524 }
525
526 const __m512i prefix = select_512_avx512_prefix_sum_u64(counts);
527 const __mmask8 mask = _mm512_mask_cmpgt_epu64_mask(
528 active_mask, prefix, _mm512_set1_epi64(static_cast<int64_t>(rank)));
529 if (mask == 0) {
530 return 512;
531 }
532
533 const uint32_t lane = _tzcnt_u32(static_cast<uint32_t>(mask));
534 const uint64_t previous = select_512_avx512_previous_prefix(prefix, lane);
535 const uint64_t word = select_512_select_word<Invert>(x[base_word + lane]);
536 return (base_word + lane) * 64 + SelectWord(word, rank - previous);
537}
538
539template <uint64_t (*SelectWord)(uint64_t, uint64_t),
540 bool Invert,
541 uint32_t ProbeWords>
542static inline uint64_t select_512_avx512_hybrid_impl(const uint64_t* x,
543 uint64_t rank) noexcept {
544 for (uint32_t i = 0; i < ProbeWords; ++i) {
545 const uint64_t count = select_512_word_count<Invert>(x[i]);
546 if (rank < count) {
547 const uint64_t word = select_512_select_word<Invert>(x[i]);
548 return i * 64 + SelectWord(word, rank);
549 }
550 rank -= count;
551 }
552 return select_512_avx512_tail_impl<SelectWord, Invert>(x, rank, ProbeWords,
553 8 - ProbeWords);
554}
555#endif
556
557static inline uint64_t select_512_avx512_pdep(const uint64_t* x,
558 uint64_t rank) noexcept {
559#ifdef PIXIE_AVX512_SUPPORT
560 return select_512_avx512_impl<select_64_pdep, false>(x, rank);
561#else
562 return select_512_avx2_pdep(x, rank);
563#endif
564}
565
566static inline uint64_t select0_512_avx512_pdep(const uint64_t* x,
567 uint64_t rank) noexcept {
568#ifdef PIXIE_AVX512_SUPPORT
569 return select_512_avx512_impl<select_64_pdep, true>(x, rank);
570#else
571 return select0_512_avx2_pdep(x, rank);
572#endif
573}
574
575static inline uint64_t select_512_avx512_byte_lut(const uint64_t* x,
576 uint64_t rank) noexcept {
577#ifdef PIXIE_AVX512_SUPPORT
578 return select_512_avx512_impl<select_64_byte_lut, false>(x, rank);
579#else
580 return select_512_avx2_byte_lut(x, rank);
581#endif
582}
583
584static inline uint64_t select0_512_avx512_byte_lut(const uint64_t* x,
585 uint64_t rank) noexcept {
586#ifdef PIXIE_AVX512_SUPPORT
587 return select_512_avx512_impl<select_64_byte_lut, true>(x, rank);
588#else
589 return select0_512_avx2_byte_lut(x, rank);
590#endif
591}
592
593static inline uint64_t select_512_avx512_broadword_lut(const uint64_t* x,
594 uint64_t rank) noexcept {
595#ifdef PIXIE_AVX512_SUPPORT
596 return select_512_avx512_impl<select_64_broadword_lut, false>(x, rank);
597#else
598 return select_512_avx2_broadword_lut(x, rank);
599#endif
600}
601
602static inline uint64_t select0_512_avx512_broadword_lut(
603 const uint64_t* x,
604 uint64_t rank) noexcept {
605#ifdef PIXIE_AVX512_SUPPORT
606 return select_512_avx512_impl<select_64_broadword_lut, true>(x, rank);
607#else
608 return select0_512_avx2_broadword_lut(x, rank);
609#endif
610}
611
612static inline uint64_t select_512_avx512_binary_lut(const uint64_t* x,
613 uint64_t rank) noexcept {
614#ifdef PIXIE_AVX512_SUPPORT
615 return select_512_avx512_impl<select_64_binary_lut, false>(x, rank);
616#else
617 return select_512_avx2_binary_lut(x, rank);
618#endif
619}
620
621static inline uint64_t select0_512_avx512_binary_lut(const uint64_t* x,
622 uint64_t rank) noexcept {
623#ifdef PIXIE_AVX512_SUPPORT
624 return select_512_avx512_impl<select_64_binary_lut, true>(x, rank);
625#else
626 return select0_512_avx2_binary_lut(x, rank);
627#endif
628}
629
630static inline uint64_t select_512_avx512_vigna_broadword(
631 const uint64_t* x,
632 uint64_t rank) noexcept {
633#ifdef PIXIE_AVX512_SUPPORT
634 return select_512_avx512_impl<select_64_vigna_broadword, false>(x, rank);
635#else
636 return select_512_avx2_vigna_broadword(x, rank);
637#endif
638}
639
640static inline uint64_t select0_512_avx512_vigna_broadword(
641 const uint64_t* x,
642 uint64_t rank) noexcept {
643#ifdef PIXIE_AVX512_SUPPORT
644 return select_512_avx512_impl<select_64_vigna_broadword, true>(x, rank);
645#else
646 return select0_512_avx2_vigna_broadword(x, rank);
647#endif
648}
649
650static inline uint64_t select_512_avx512_no_pdep(const uint64_t* x,
651 uint64_t rank) noexcept {
652#ifdef PIXIE_AVX512_SUPPORT
653 return select_512_avx512_impl<select_64_no_pdep, false>(x, rank);
654#else
655 return select_512_avx2_no_pdep(x, rank);
656#endif
657}
658
659static inline uint64_t select0_512_avx512_no_pdep(const uint64_t* x,
660 uint64_t rank) noexcept {
661#ifdef PIXIE_AVX512_SUPPORT
662 return select_512_avx512_impl<select_64_no_pdep, true>(x, rank);
663#else
664 return select0_512_avx2_no_pdep(x, rank);
665#endif
666}
667
668static inline uint64_t select_512_avx512_hybrid1_pdep(const uint64_t* x,
669 uint64_t rank) noexcept {
670#ifdef PIXIE_AVX512_SUPPORT
671 return select_512_avx512_hybrid_impl<select_64_pdep, false, 1>(x, rank);
672#else
673 return select_512_scalar_pdep(x, rank);
674#endif
675}
676
677static inline uint64_t select0_512_avx512_hybrid1_pdep(const uint64_t* x,
678 uint64_t rank) noexcept {
679#ifdef PIXIE_AVX512_SUPPORT
680 return select_512_avx512_hybrid_impl<select_64_pdep, true, 1>(x, rank);
681#else
682 return select0_512_scalar_pdep(x, rank);
683#endif
684}
685
686static inline uint64_t select_512_avx512_hybrid2_pdep(const uint64_t* x,
687 uint64_t rank) noexcept {
688#ifdef PIXIE_AVX512_SUPPORT
689 return select_512_avx512_hybrid_impl<select_64_pdep, false, 2>(x, rank);
690#else
691 return select_512_scalar_pdep(x, rank);
692#endif
693}
694
695static inline uint64_t select0_512_avx512_hybrid2_pdep(const uint64_t* x,
696 uint64_t rank) noexcept {
697#ifdef PIXIE_AVX512_SUPPORT
698 return select_512_avx512_hybrid_impl<select_64_pdep, true, 2>(x, rank);
699#else
700 return select0_512_scalar_pdep(x, rank);
701#endif
702}
703
704static inline uint64_t select_512_avx512_hybrid4_pdep(const uint64_t* x,
705 uint64_t rank) noexcept {
706#ifdef PIXIE_AVX512_SUPPORT
707 return select_512_avx512_hybrid_impl<select_64_pdep, false, 4>(x, rank);
708#else
709 return select_512_scalar_pdep(x, rank);
710#endif
711}
712
713static inline uint64_t select0_512_avx512_hybrid4_pdep(const uint64_t* x,
714 uint64_t rank) noexcept {
715#ifdef PIXIE_AVX512_SUPPORT
716 return select_512_avx512_hybrid_impl<select_64_pdep, true, 4>(x, rank);
717#else
718 return select0_512_scalar_pdep(x, rank);
719#endif
720}
721
722static inline uint64_t select_512_avx512_hybrid2_no_pdep(
723 const uint64_t* x,
724 uint64_t rank) noexcept {
725#ifdef PIXIE_AVX512_SUPPORT
726 return select_512_avx512_hybrid_impl<select_64_no_pdep, false, 2>(x, rank);
727#else
728 return select_512_scalar_no_pdep(x, rank);
729#endif
730}
731
732static inline uint64_t select0_512_avx512_hybrid2_no_pdep(
733 const uint64_t* x,
734 uint64_t rank) noexcept {
735#ifdef PIXIE_AVX512_SUPPORT
736 return select_512_avx512_hybrid_impl<select_64_no_pdep, true, 2>(x, rank);
737#else
738 return select0_512_scalar_no_pdep(x, rank);
739#endif
740}
741
742static inline uint64_t select_512_avx512_experimental_default(
743 const uint64_t* x,
744 uint64_t rank) noexcept {
745#ifdef PIXIE_AVX512_SUPPORT
746 return select_512_avx512_impl<select_64_experimental_default, false>(x, rank);
747#else
748 return select_512_avx2_experimental_default(x, rank);
749#endif
750}
751
752static inline uint64_t select0_512_avx512_experimental_default(
753 const uint64_t* x,
754 uint64_t rank) noexcept {
755#ifdef PIXIE_AVX512_SUPPORT
756 return select_512_avx512_impl<select_64_experimental_default, true>(x, rank);
757#else
758 return select0_512_avx2_experimental_default(x, rank);
759#endif
760}
761
762static inline uint64_t select_512_experimental_default(const uint64_t* x,
763 uint64_t rank) noexcept {
764#ifdef PIXIE_EXPERIMENTAL_SELECT_NO_PDEP
765 return select_512_scalar_no_pdep(x, rank);
766#elif defined(PIXIE_AVX512_SUPPORT)
767 return select_512_avx512_experimental_default(x, rank);
768#else
769 return select_512_scalar_experimental_default(x, rank);
770#endif
771}
772
773static inline uint64_t select0_512_experimental_default(
774 const uint64_t* x,
775 uint64_t rank) noexcept {
776#ifdef PIXIE_EXPERIMENTAL_SELECT_NO_PDEP
777 return select0_512_scalar_no_pdep(x, rank);
778#elif defined(PIXIE_AVX512_SUPPORT)
779 return select0_512_avx512_experimental_default(x, rank);
780#else
781 return select0_512_scalar_experimental_default(x, rank);
782#endif
783}
784
786
787} // namespace pixie::experimental
pixie::experimental
Definition excess.h:90