4 // A reimplementation of parts of the TurboPFor codecs, using the same
5 // storage format. These are not as fast as the reference implementation
6 // (about 60% of the performance, averaged over a real plocate corpus),
7 // and do not support the same breadth of codecs (in particular, only
8 // delta-plus-1 is implemented, and only 32-bit docids are tested),
9 // but aim to be more portable and (ideally) easier-to-understand.
10 // In particular, they will compile on x86 without SSE4.1 or AVX support.
12 // The main reference is https://michael.stapelberg.ch/posts/2019-02-05-turbopfor-analysis/,
13 // although some implementation details have been worked out by studying the
24 #if defined(__i386__) || defined(__x86_64__)
25 #define COULD_HAVE_SSE2
26 #include <immintrin.h>
29 // Forward declarations to declare to the template code below that they exist.
30 // (These must seemingly be non-templates for function multiversioning to work.)
31 __attribute__((target("default")))
32 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
33 __attribute__((target("default")))
34 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
35 __attribute__((target("default")))
36 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
38 #ifdef COULD_HAVE_SSE2
39 __attribute__((target("sse2")))
40 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out);
41 __attribute__((target("sse2")))
42 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out);
43 __attribute__((target("sse2")))
44 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out);
48 Docid read_le(const void *in)
51 memcpy(&val, in, sizeof(val));
52 if constexpr (sizeof(Docid) == 8) {
54 } else if constexpr (sizeof(Docid) == 4) {
56 } else if constexpr (sizeof(Docid) == 2) {
58 } else if constexpr (sizeof(Docid) == 1) {
65 // Reads a single value with an encoding that looks a bit like PrefixVarint.
66 // It's unclear why this doesn't use the varbyte encoding.
68 const unsigned char *read_baseval(const unsigned char *in, Docid *out)
70 //fprintf(stderr, "baseval: 0x%02x 0x%02x 0x%02x 0x%02x\n", in[0], in[1], in[2], in[3]);
74 } else if (*in < 192) {
75 *out = ((uint32_t(in[0]) << 8) | uint32_t(in[1])) & 0x3fff;
77 } else if (*in < 224) {
78 *out = ((uint32_t(in[0]) << 16) |
79 (uint32_t(in[2]) << 8) |
80 (uint32_t(in[1]))) & 0x1fffff;
83 assert(false); // Not implemented.
88 const unsigned char *read_vb(const unsigned char *in, Docid *out)
93 } else if (*in <= 240) {
94 *out = ((uint32_t(in[0] - 177) << 8) | uint32_t(in[1])) + 177;
96 } else if (*in <= 248) {
97 *out = ((uint32_t(in[0] - 241) << 16) | read_le<uint16_t>(in + 1)) + 16561;
99 } else if (*in == 249) {
100 *out = (uint32_t(in[1])) |
101 (uint32_t(in[2]) << 8) |
102 (uint32_t(in[3]) << 16);
104 } else if (*in == 250) {
105 *out = read_le<uint32_t>(in + 1);
114 BitReader(const unsigned char *in, unsigned bits)
115 : in(in), bits(bits), mask((1U << bits) - 1) {}
118 uint32_t val = (read_le<uint32_t>(in) >> bits_used) & mask;
128 const unsigned char *in;
131 unsigned bits_used = 0;
134 template<unsigned NumStreams>
135 struct InterleavedBitReader {
137 InterleavedBitReader(const unsigned char *in, unsigned bits)
138 : in(in), bits(bits), mask((1U << bits) - 1) {}
142 if (bits_used + bits > 32) {
143 val = (read_le<uint32_t>(in) >> bits_used) | (read_le<uint32_t>(in + Stride) << (32 - bits_used));
145 val = (read_le<uint32_t>(in) >> bits_used);
149 in += Stride * (bits_used / 32);
156 static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
157 const unsigned char *in;
160 unsigned bits_used = 0;
163 // Does not properly account for overflow.
164 inline unsigned div_round_up(unsigned val, unsigned div)
166 return (val + div - 1) / div;
169 inline unsigned bytes_for_packed_bits(unsigned num, unsigned bit_width)
171 return div_round_up(num * bit_width, CHAR_BIT);
174 // Constant block. Layout:
176 // - Bit width (6 bits) | type << 6
177 // - Base values (<bits> bits, rounded up to nearest byte)
178 template<class Docid>
179 const unsigned char *decode_constant(const unsigned char *in, unsigned num, Docid *out)
181 const unsigned bit_width = *in++ & 0x3f;
182 Docid val = read_le<Docid>(in);
183 if (bit_width < sizeof(Docid) * 8) {
184 val &= ((1U << bit_width) - 1);
187 Docid prev_val = out[-1];
188 for (unsigned i = 0; i < num; ++i) {
189 out[i] = prev_val = val + prev_val + 1;
191 return in + div_round_up(bit_width, 8);
194 // FOR block (ie., PFor without exceptions). Layout:
196 // - Bit width (6 bits) | type << 6
197 // - Base values (<num> values of <bits> bits, rounded up to a multiple of 32 values)
198 template<class Docid>
199 const unsigned char *decode_for(const unsigned char *in, unsigned num, Docid *out)
201 const unsigned bit_width = *in++ & 0x3f;
203 Docid prev_val = out[-1];
204 BitReader bs(in, bit_width);
205 for (unsigned i = 0; i < num; ++i) {
206 prev_val = out[i] = bs.read() + prev_val + 1;
208 return in + bytes_for_packed_bits(num, bit_width);
211 #ifdef COULD_HAVE_SSE2
212 class DeltaDecoderSSE2 {
214 DeltaDecoderSSE2(uint32_t prev_val) : prev_val(_mm_set1_epi32(prev_val)) {}
215 __m128i decode(__m128i val) {
216 val = _mm_add_epi32(val, _mm_slli_si128(val, 4));
217 val = _mm_add_epi32(val, _mm_slli_si128(val, 8));
218 val = _mm_add_epi32(val, _mm_add_epi32(prev_val, delta));
219 prev_val = _mm_shuffle_epi32(val, _MM_SHUFFLE(3, 3, 3, 3));
224 // Use 4/3/2/1 as delta instead of fixed 1, so that we can do the prev_val + delta
225 // in parallel with something else.
226 const __m128i delta = _mm_set_epi32(4, 3, 2, 1);
231 template<unsigned BlockSize>
232 __attribute__((target("sse2")))
233 inline void delta_decode_sse2(uint32_t *out)
235 DeltaDecoderSSE2 delta(out[-1]);
236 __m128i *outvec = reinterpret_cast<__m128i *>(out);
237 for (unsigned i = 0; i < BlockSize / 4; ++i) {
238 __m128i val = _mm_loadu_si128(outvec + i);
239 _mm_storeu_si128(outvec + i, delta.decode(val));
243 template<unsigned BlockSize, bool OrWithExisting, bool DeltaDecode>
244 __attribute__((target("sse2")))
245 const unsigned char *decode_bitmap_sse2(const unsigned char *in, unsigned bit_width, uint32_t *out)
247 const __m128i *invec = reinterpret_cast<const __m128i *>(in);
248 __m128i *outvec = reinterpret_cast<__m128i *>(out);
249 const __m128i mask = _mm_set1_epi32((1U << bit_width) - 1);
250 unsigned bits_used = 0;
251 DeltaDecoderSSE2 delta(out[-1]);
252 for (unsigned i = 0; i < BlockSize / 4; ++i) {
253 __m128i val = _mm_srli_epi32(_mm_loadu_si128(invec), bits_used);
254 if (bits_used + bit_width > 32) {
255 __m128i val_upper = _mm_slli_epi32(_mm_loadu_si128(invec + 1), 32 - bits_used);
256 val = _mm_or_si128(val, val_upper);
258 val = _mm_and_si128(val, mask);
259 if constexpr (OrWithExisting) {
260 val = _mm_or_si128(val, _mm_loadu_si128(outvec + i));
262 if constexpr (DeltaDecode) {
263 val = delta.decode(val);
265 _mm_storeu_si128(outvec + i, val);
267 bits_used += bit_width;
268 invec += bits_used / 32;
271 in += bytes_for_packed_bits(BlockSize, bit_width);
276 // Like decode_for(), but the values are organized in four independent streams,
277 // for SIMD (presumably SSE2). Supports a whole block only.
278 template<unsigned BlockSize, class Docid>
279 const unsigned char *decode_for_interleaved_generic(const unsigned char *in, Docid *out)
281 const unsigned bit_width = *in++ & 0x3f;
283 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
284 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
285 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
286 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
287 for (unsigned i = 0; i < BlockSize / 4; ++i) {
288 out[i * 4 + 0] = bs0.read();
289 out[i * 4 + 1] = bs1.read();
290 out[i * 4 + 2] = bs2.read();
291 out[i * 4 + 3] = bs3.read();
293 Docid prev_val = out[-1];
294 for (unsigned i = 0; i < BlockSize; ++i) {
295 out[i] = prev_val = out[i] + prev_val + 1;
297 return in + bytes_for_packed_bits(BlockSize, bit_width);
300 template<unsigned BlockSize, class Docid>
301 const unsigned char *decode_for_interleaved(const unsigned char *in, Docid *out)
303 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
304 return decode_for_interleaved_128_32(in, out);
306 return decode_for_interleaved_generic(in, out);
310 __attribute__((target("default")))
311 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
313 return decode_for_interleaved_generic<128>(in, out);
316 #ifdef COULD_HAVE_SSE2
317 // Specialized version for SSE2.
318 __attribute__((target("sse2")))
319 const unsigned char *decode_for_interleaved_128_32(const unsigned char *in, uint32_t *out)
321 constexpr unsigned BlockSize = 128;
323 const unsigned bit_width = *in++ & 0x3f;
325 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/true>(in, bit_width, out);
331 template<class Docid>
332 const unsigned char *decode_pfor_bitmap_exceptions(const unsigned char *in, unsigned num, unsigned bit_width, Docid *out)
334 const unsigned exception_bit_width = *in++;
335 const uint64_t *exception_bitmap_ptr = reinterpret_cast<const uint64_t *>(in);
336 in += div_round_up(num, 8);
338 int num_exceptions = 0;
340 BitReader bs(in, exception_bit_width);
341 for (unsigned i = 0; i < num; i += 64, ++exception_bitmap_ptr) {
342 uint64_t exceptions = read_le<uint64_t>(exception_bitmap_ptr);
344 // We've read some bytes past the end, so clear out the junk bits.
345 exceptions &= (1ULL << (num - i)) - 1;
347 for (; exceptions != 0; exceptions &= exceptions - 1, ++num_exceptions) {
348 unsigned idx = (ffsll(exceptions) - 1) + i;
349 out[idx] = bs.read() << bit_width;
352 in += bytes_for_packed_bits(num_exceptions, exception_bit_width);
356 // PFor block with bitmap exceptions. Layout:
358 // - Bit width (6 bits) | type << 6
359 // - Exception bit width (8 bits)
360 // - Bitmap of which values have exceptions (<num> bits, rounded up to a byte)
361 // - Exceptions (<num_exc> values of <bits_exc> bits, rounded up to a byte)
362 // - Base values (<num> values of <bits> bits, rounded up to a byte)
363 template<class Docid>
364 const unsigned char *decode_pfor_bitmap(const unsigned char *in, unsigned num, Docid *out)
366 memset(out, 0, num * sizeof(Docid));
368 const unsigned bit_width = *in++ & 0x3f;
370 in = decode_pfor_bitmap_exceptions(in, num, bit_width, out);
372 // Decode the base values, and delta-decode.
373 Docid prev_val = out[-1];
374 BitReader bs(in, bit_width);
375 for (unsigned i = 0; i < num; ++i) {
376 out[i] = prev_val = (out[i] | bs.read()) + prev_val + 1;
378 return in + bytes_for_packed_bits(num, bit_width);
381 // Like decode_pfor_bitmap(), but the base values are organized in four
382 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
383 template<unsigned BlockSize, class Docid>
384 const unsigned char *decode_pfor_bitmap_interleaved_generic(const unsigned char *in, Docid *out)
386 memset(out, 0, BlockSize * sizeof(Docid));
388 const unsigned bit_width = *in++ & 0x3f;
390 in = decode_pfor_bitmap_exceptions(in, BlockSize, bit_width, out);
392 // Decode the base values.
393 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
394 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
395 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
396 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
397 for (unsigned i = 0; i < BlockSize / 4; ++i) {
398 out[i * 4 + 0] |= bs0.read();
399 out[i * 4 + 1] |= bs1.read();
400 out[i * 4 + 2] |= bs2.read();
401 out[i * 4 + 3] |= bs3.read();
405 Docid prev_val = out[-1];
406 for (unsigned i = 0; i < BlockSize; ++i) {
407 out[i] = prev_val = out[i] + prev_val + 1;
409 return in + bytes_for_packed_bits(BlockSize, bit_width);
412 template<unsigned BlockSize, class Docid>
413 const unsigned char *decode_pfor_bitmap_interleaved(const unsigned char *in, Docid *out)
415 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
416 return decode_pfor_bitmap_interleaved_128_32(in, out);
418 return decode_pfor_bitmap_interleaved_generic(in, out);
422 __attribute__((target("default")))
423 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
425 return decode_pfor_bitmap_interleaved_generic<128>(in, out);
428 #ifdef COULD_HAVE_SSE2
429 // Specialized version for SSE2.
430 __attribute__((target("sse2")))
431 const unsigned char *decode_pfor_bitmap_interleaved_128_32(const unsigned char *in, uint32_t *out)
433 constexpr unsigned BlockSize = 128;
434 using Docid = uint32_t;
436 memset(out, 0, BlockSize * sizeof(Docid));
438 const unsigned bit_width = *in++ & 0x3f;
440 in = decode_pfor_bitmap_exceptions(in, BlockSize, bit_width, out);
441 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/true, /*DeltaDecode=*/true>(in, bit_width, out);
447 // PFor block with variable-byte exceptions. Layout:
449 // - Bit width (6 bits) | type << 6
450 // - Number of exceptions (8 bits)
451 // - Base values (<num> values of <bits> bits, rounded up to a byte)
453 // - If first byte is 255, <num_exc> 32-bit values (does not include the 255 byte)
454 // - Else, <num_exc> varbyte-encoded values (includes the non-255 byte)
455 // - Indexes of exceptions (<num_exc> bytes).
456 template<unsigned BlockSize, class Docid>
457 const unsigned char *decode_pfor_vb(const unsigned char *in, unsigned num, Docid *out)
459 //fprintf(stderr, "in=%p out=%p num=%u\n", in, out, num);
461 const unsigned bit_width = *in++ & 0x3f;
462 unsigned num_exceptions = *in++;
464 // Decode the base values.
465 BitReader bs(in, bit_width);
466 for (unsigned i = 0; i < num; ++i) {
469 in += bytes_for_packed_bits(num, bit_width);
471 // Decode exceptions.
472 Docid exceptions[BlockSize];
475 for (unsigned i = 0; i < num_exceptions; ++i) {
476 exceptions[i] = read_le<Docid>(in);
480 for (unsigned i = 0; i < num_exceptions; ++i) {
481 in = read_vb(in, &exceptions[i]);
485 for (unsigned i = 0; i < num_exceptions; ++i) {
486 unsigned idx = *in++;
487 out[idx] |= exceptions[i] << bit_width;
491 Docid prev_val = out[-1];
492 for (unsigned i = 0; i < num; ++i) {
493 out[i] = prev_val = out[i] + prev_val + 1;
499 // Like decode_pfor_vb(), but the base values are organized in four
500 // independent streams, for SIMD (presumably SSE2). Supports a whole block only.
501 template<unsigned BlockSize, class Docid>
502 const unsigned char *decode_pfor_vb_interleaved_generic(const unsigned char *in, Docid *out)
504 const unsigned bit_width = *in++ & 0x3f;
505 unsigned num_exceptions = *in++;
507 // Decode the base values.
508 InterleavedBitReader<4> bs0(in + 0 * sizeof(uint32_t), bit_width);
509 InterleavedBitReader<4> bs1(in + 1 * sizeof(uint32_t), bit_width);
510 InterleavedBitReader<4> bs2(in + 2 * sizeof(uint32_t), bit_width);
511 InterleavedBitReader<4> bs3(in + 3 * sizeof(uint32_t), bit_width);
512 for (unsigned i = 0; i < BlockSize / 4; ++i) {
513 out[i * 4 + 0] = bs0.read();
514 out[i * 4 + 1] = bs1.read();
515 out[i * 4 + 2] = bs2.read();
516 out[i * 4 + 3] = bs3.read();
518 in += bytes_for_packed_bits(BlockSize, bit_width);
520 // Decode exceptions.
521 Docid exceptions[BlockSize];
524 for (unsigned i = 0; i < num_exceptions; ++i) {
525 exceptions[i] = read_le<Docid>(in);
529 for (unsigned i = 0; i < num_exceptions; ++i) {
530 in = read_vb(in, &exceptions[i]);
535 for (unsigned i = 0; i < num_exceptions; ++i) {
536 unsigned idx = *in++;
537 out[idx] |= exceptions[i] << bit_width;
541 Docid prev_val = out[-1];
542 for (unsigned i = 0; i < BlockSize; ++i) {
543 out[i] = prev_val = out[i] + prev_val + 1;
549 template<unsigned BlockSize, class Docid>
550 const unsigned char *decode_pfor_vb_interleaved(const unsigned char *in, Docid *out)
552 if constexpr (BlockSize == 128 && sizeof(Docid) == sizeof(uint32_t)) {
553 return decode_pfor_vb_interleaved_128_32(in, out);
555 return decode_pfor_vb_interleaved_generic(in, out);
559 __attribute__((target("default")))
560 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
562 return decode_pfor_vb_interleaved_generic<128>(in, out);
565 // Specialized version for SSE2.
566 __attribute__((target("sse2")))
567 const unsigned char *decode_pfor_vb_interleaved_128_32(const unsigned char *in, uint32_t *out)
569 constexpr unsigned BlockSize = 128;
570 using Docid = uint32_t;
572 const unsigned bit_width = *in++ & 0x3f;
573 unsigned num_exceptions = *in++;
575 // Decode the base values.
576 in = decode_bitmap_sse2<BlockSize, /*OrWithExisting=*/false, /*DeltaDecode=*/false>(in, bit_width, out);
578 // Decode exceptions.
579 Docid exceptions[BlockSize];
582 for (unsigned i = 0; i < num_exceptions; ++i) {
583 exceptions[i] = read_le<Docid>(in);
587 for (unsigned i = 0; i < num_exceptions; ++i) {
588 in = read_vb(in, &exceptions[i]);
593 for (unsigned i = 0; i < num_exceptions; ++i) {
594 unsigned idx = *in++;
595 out[idx] |= exceptions[i] << bit_width;
598 delta_decode_sse2<BlockSize>(out);
610 template<unsigned BlockSize, class Docid>
611 const unsigned char *decode_pfor_delta1(const unsigned char *in, unsigned num, bool interleaved, Docid *out)
616 in = read_baseval(in, out++);
618 for (unsigned i = 1; i < num; i += BlockSize, out += BlockSize) {
619 const unsigned num_this_block = std::min<unsigned>(num - i, BlockSize);
620 switch (in[0] >> 6) {
622 if (interleaved && num_this_block == BlockSize) {
623 dprintf("%d+%d: blocktype=%d (for, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
624 in = decode_for_interleaved<BlockSize>(in, out);
626 dprintf("%d+%d: blocktype=%d (for), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
627 in = decode_for(in, num_this_block, out);
630 case BlockType::PFOR_VB:
631 if (interleaved && num_this_block == BlockSize) {
632 dprintf("%d+%d: blocktype=%d (pfor + vb, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
633 in = decode_pfor_vb_interleaved<BlockSize>(in, out);
635 dprintf("%d+%d: blocktype=%d (pfor + vb), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
636 in = decode_pfor_vb<BlockSize>(in, num_this_block, out);
639 case BlockType::PFOR_BITMAP:
640 if (interleaved && num_this_block == BlockSize) {
641 dprintf("%d+%d: blocktype=%d (pfor + bitmap, interleaved), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
642 in = decode_pfor_bitmap_interleaved<BlockSize>(in, out);
644 dprintf("%d+%d: blocktype=%d (pfor + bitmap), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
645 in = decode_pfor_bitmap(in, num_this_block, out);
648 case BlockType::CONSTANT:
649 dprintf("%d+%d: blocktype=%d (constant), bitwidth=%d\n", i, num_this_block, in[0] >> 6, in[0] & 0x3f);
650 in = decode_constant(in, num_this_block, out);
658 #endif // !defined(_TURBOPFOR_H)