git.sesse.net Git - plocate/blob - turbopfor-encode.h

   1 #ifndef _TURBOPFOR_ENCODE_H
   2 #define _TURBOPFOR_ENCODE_H
   3
   4 // Much like turbopfor.h (and shares all of the same caveats), except this is
   5 // for encoding. It is _much_ slower than the reference implementation, but we
   6 // encode only during build, and most time in build is spent in other things
   7 // than encoding posting lists, so it only costs ~5-10% overall. Does not use
   8 // any special character sets, and generally isn't optimized at all.
   9 //
  10 // It encodes about 0.01% denser than the reference encoder (averaged over
  11 // a real plocate corpus), probably since it has a slower but more precise
  12 // method for estimating the cost of a PFOR + varbyte block.
  13
  14 #include "turbopfor-common.h"
  15
  16 #include <assert.h>
  17 #include <limits.h>
  18 #include <stdint.h>
  19
  20 template<class Docid>
  21 void write_le(Docid val, void *out)
  22 {
  23         if constexpr (sizeof(Docid) == 8) {
  24                 val = htole64(val);
  25         } else if constexpr (sizeof(Docid) == 4) {
  26                 val = htole32(val);
  27         } else if constexpr (sizeof(Docid) == 2) {
  28                 val = htole16(val);
  29         } else if constexpr (sizeof(Docid) == 1) {
  30                 val = val;
  31         } else {
  32                 assert(false);
  33         }
  34         memcpy(out, &val, sizeof(val));
  35 }
  36
  37 // Corresponds to read_baseval.
  38 template<class Docid>
  39 unsigned char *write_baseval(Docid in, unsigned char *out)
  40 {
  41         if (in < 128) {
  42                 *out = in;
  43                 return out + 1;
  44         } else if (in < 0x4000) {
  45                 out[0] = (in >> 8) | 0x80;
  46                 out[1] = in & 0xff;
  47                 return out + 2;
  48         } else if (in < 0x200000) {
  49                 out[0] = (in >> 16) | 0xc0;
  50                 out[1] = in & 0xff;
  51                 out[2] = (in >> 8) & 0xff;
  52                 return out + 3;
  53         } else {
  54                 assert(false);  // Not implemented.
  55         }
  56 }
  57
  58 // Writes a varbyte-encoded exception.
  59 template<class Docid>
  60 unsigned char *write_vb(Docid val, unsigned char *out)
  61 {
  62         if (val <= 176) {
  63                 *out++ = val;
  64                 return out;
  65         } else if (val <= 16560) {
  66                 val -= 177;
  67                 *out++ = (val >> 8) + 177;
  68                 *out++ = val & 0xff;
  69                 return out;
  70         } else if (val <= 540848) {
  71                 val -= 16561;
  72                 *out = (val >> 16) + 241;
  73                 write_le<uint16_t>(val & 0xffff, out + 1);
  74                 return out + 3;
  75         } else if (val <= 16777215) {
  76                 *out = 249;
  77                 write_le<uint32_t>(val, out + 1);
  78                 return out + 4;
  79         } else {
  80                 *out = 250;
  81                 write_le<uint32_t>(val, out + 1);
  82                 return out + 5;
  83         }
  84 }
  85
  86 template<class Docid>
  87 inline unsigned num_bits(Docid x)
  88 {
  89         if (x == 0) {
  90                 return 0;
  91         } else {
  92                 return sizeof(Docid) * CHAR_BIT - __builtin_clz(x);
  93         }
  94 }
  95
  96 struct BitWriter {
  97 public:
  98         BitWriter(unsigned char *out, unsigned bits)
  99                 : out(out), bits(bits) {}
 100         void write(uint32_t val)
 101         {
 102                 cur_val |= val << bits_used;
 103                 write_le<uint32_t>(cur_val, out);
 104
 105                 bits_used += bits;
 106                 cur_val >>= (bits_used / 8) * 8;
 107                 out += bits_used / 8;
 108                 bits_used %= 8;
 109         }
 110
 111 private:
 112         unsigned char *out;
 113         const unsigned bits;
 114         unsigned bits_used = 0;
 115         unsigned cur_val = 0;
 116 };
 117
 118 template<unsigned NumStreams>
 119 struct InterleavedBitWriter {
 120 public:
 121         InterleavedBitWriter(unsigned char *out, unsigned bits)
 122                 : out(out), bits(bits) {}
 123         void write(uint32_t val)
 124         {
 125                 cur_val |= uint64_t(val) << bits_used;
 126                 if (bits_used + bits >= 32) {
 127                         write_le<uint32_t>(cur_val & 0xffffffff, out);
 128                         out += Stride;
 129                         cur_val >>= 32;
 130                         bits_used -= 32;  // Underflow, but will be fixed below.
 131                 }
 132                 write_le<uint32_t>(cur_val, out);
 133                 bits_used += bits;
 134         }
 135
 136 private:
 137         static constexpr unsigned Stride = NumStreams * sizeof(uint32_t);
 138         unsigned char *out;
 139         const unsigned bits;
 140         unsigned bits_used = 0;
 141         uint64_t cur_val = 0;
 142 };
 143
 144 // Bitpacks a set of values (making sure the top bits are lopped off).
 145 // If interleaved is set, makes SSE2-compatible interleaving (this is
 146 // only allowed for full blocks).
 147 template<class Docid>
 148 unsigned char *encode_bitmap(const Docid *in, unsigned num, unsigned bit_width, bool interleaved, unsigned char *out)
 149 {
 150         unsigned mask = mask_for_bits(bit_width);
 151         if (interleaved) {
 152                 InterleavedBitWriter<4> bs0(out + 0 * sizeof(uint32_t), bit_width);
 153                 InterleavedBitWriter<4> bs1(out + 1 * sizeof(uint32_t), bit_width);
 154                 InterleavedBitWriter<4> bs2(out + 2 * sizeof(uint32_t), bit_width);
 155                 InterleavedBitWriter<4> bs3(out + 3 * sizeof(uint32_t), bit_width);
 156                 assert(num % 4 == 0);
 157                 for (unsigned i = 0; i < num / 4; ++i) {
 158                         bs0.write(in[i * 4 + 0] & mask);
 159                         bs1.write(in[i * 4 + 1] & mask);
 160                         bs2.write(in[i * 4 + 2] & mask);
 161                         bs3.write(in[i * 4 + 3] & mask);
 162                 }
 163         } else {
 164                 BitWriter bs(out, bit_width);
 165                 for (unsigned i = 0; i < num; ++i) {
 166                         bs.write(in[i] & mask);
 167                 }
 168         }
 169         return out + bytes_for_packed_bits(num, bit_width);
 170 }
 171
 172 // See decode_for() for the format.
 173 template<class Docid>
 174 unsigned char *encode_for(const Docid *in, unsigned num, unsigned bit_width, bool interleaved, unsigned char *out)
 175 {
 176         return encode_bitmap(in, num, bit_width, interleaved, out);
 177 }
 178
 179 // See decode_pfor_bitmap() for the format.
 180 template<class Docid>
 181 unsigned char *encode_pfor_bitmap(const Docid *in, unsigned num, unsigned bit_width, unsigned exception_bit_width, bool interleaved, unsigned char *out)
 182 {
 183         *out++ = exception_bit_width;
 184
 185         // Bitmap of exceptions.
 186         {
 187                 BitWriter bs(out, 1);
 188                 for (unsigned i = 0; i < num; ++i) {
 189                         bs.write((in[i] >> bit_width) != 0);
 190                 }
 191                 out += bytes_for_packed_bits(num, 1);
 192         }
 193
 194         // Exceptions.
 195         {
 196                 BitWriter bs(out, exception_bit_width);
 197                 unsigned num_exceptions = 0;
 198                 for (unsigned i = 0; i < num; ++i) {
 199                         if ((in[i] >> bit_width) != 0) {
 200                                 bs.write(in[i] >> bit_width);
 201                                 ++num_exceptions;
 202                         }
 203                 }
 204                 out += bytes_for_packed_bits(num_exceptions, exception_bit_width);
 205         }
 206
 207         // Base values.
 208         out = encode_bitmap(in, num, bit_width, interleaved, out);
 209
 210         return out;
 211 }
 212
 213 // See decode_pfor_vb() for the format.
 214 template<class Docid>
 215 unsigned char *encode_pfor_vb(const Docid *in, unsigned num, unsigned bit_width, bool interleaved, unsigned char *out)
 216 {
 217         unsigned num_exceptions = 0;
 218         for (unsigned i = 0; i < num; ++i) {
 219                 if ((in[i] >> bit_width) != 0) {
 220                         ++num_exceptions;
 221                 }
 222         }
 223         *out++ = num_exceptions;
 224
 225         // Base values.
 226         out = encode_bitmap(in, num, bit_width, interleaved, out);
 227
 228         // Exceptions.
 229         for (unsigned i = 0; i < num; ++i) {
 230                 unsigned val = in[i] >> bit_width;
 231                 if (val != 0) {
 232                         out = write_vb(val, out);
 233                 }
 234         }
 235
 236         // Exception indexes.
 237         for (unsigned i = 0; i < num; ++i) {
 238                 unsigned val = in[i] >> bit_width;
 239                 if (val != 0) {
 240                         *out++ = i;
 241                 }
 242         }
 243
 244         return out;
 245 }
 246
 247 // Find out which block type would be the smallest for the given data.
 248 template<class Docid>
 249 BlockType decide_block_type(const Docid *in, unsigned num, unsigned *bit_width, unsigned *exception_bit_width)
 250 {
 251         // Check if the block is constant.
 252         bool constant = true;
 253         for (unsigned i = 1; i < num; ++i) {
 254                 if (in[i] != in[0]) {
 255                         constant = false;
 256                         break;
 257                 }
 258         }
 259         if (constant) {
 260                 *bit_width = num_bits(in[0]);
 261                 return BlockType::CONSTANT;
 262         }
 263
 264         // Build up a histogram of bit sizes.
 265         unsigned histogram[sizeof(Docid) * CHAR_BIT + 1] = { 0 };
 266         unsigned max_bits = 0;
 267         for (unsigned i = 0; i < num; ++i) {
 268                 unsigned bits = num_bits(in[i]);
 269                 ++histogram[bits];
 270                 max_bits = std::max(max_bits, bits);
 271         }
 272
 273         // Straight-up FOR.
 274         unsigned best_cost = bytes_for_packed_bits(num, max_bits);
 275         unsigned best_bit_width = max_bits;
 276
 277         // Try PFOR with bitmap exceptions.
 278         const unsigned bitmap_cost = bytes_for_packed_bits(num, 1);
 279         unsigned num_exceptions = 0;
 280         for (unsigned exception_bit_width = 1; exception_bit_width <= max_bits; ++exception_bit_width) {
 281                 unsigned test_bit_width = max_bits - exception_bit_width;
 282                 num_exceptions += histogram[test_bit_width + 1];
 283
 284                 // 1 byte for signaling exception bit width, then the bitmap,
 285                 // then the base values, then the exceptions.
 286                 unsigned cost = 1 + bitmap_cost + bytes_for_packed_bits(num, test_bit_width) +
 287                         bytes_for_packed_bits(num_exceptions, exception_bit_width);
 288                 if (cost < best_cost) {
 289                         best_cost = cost;
 290                         best_bit_width = test_bit_width;
 291                 }
 292         }
 293
 294         // Try PFOR with varbyte exceptions.
 295         bool best_is_varbyte = false;
 296         for (unsigned test_bit_width = 0; test_bit_width < max_bits; ++test_bit_width) {
 297                 // 1 byte for signaling number of exceptions, plus the base values,
 298                 // and then we count up the varbytes and indexes. (This is precise
 299                 // but very slow.)
 300                 unsigned cost = 1 + bytes_for_packed_bits(num, test_bit_width);
 301                 for (unsigned i = 0; i < num && cost < best_cost; ++i) {
 302                         unsigned val = in[i] >> test_bit_width;
 303                         if (val == 0) {
 304                                 // Not stored, and then also no index.
 305                         } else if (val <= 176) {
 306                                 cost += 2;
 307                         } else if (val <= 16560) {
 308                                 cost += 3;
 309                         } else if (val <= 540848) {
 310                                 cost += 4;
 311                         } else if (val <= 16777215) {
 312                                 cost += 5;
 313                         } else {
 314                                 cost += 6;
 315                         }
 316                 }
 317                 if (cost < best_cost) {
 318                         best_cost = cost;
 319                         best_bit_width = test_bit_width;
 320                         best_is_varbyte = true;
 321                 }
 322         }
 323
 324         // TODO: Consider the last-resort option of just raw storage (255).
 325
 326         if (best_is_varbyte) {
 327                 *bit_width = best_bit_width;
 328                 return BlockType::PFOR_VB;
 329         } else if (best_bit_width == max_bits) {
 330                 *bit_width = max_bits;
 331                 return BlockType::FOR;
 332         } else {
 333                 *bit_width = best_bit_width;
 334                 *exception_bit_width = max_bits - best_bit_width;
 335                 return BlockType::PFOR_BITMAP;
 336         }
 337 }
 338
 339 // The basic entry point. Takes one block of integers (which already must
 340 // be delta-minus-1-encoded) and packs it into TurboPFor format.
 341 // interleaved corresponds to the interleaved parameter in decode_pfor_delta1()
 342 // or the “128v” infix in the reference code's function names; such formats
 343 // are much faster to decode, so for full blocks, you probably want it.
 344 // The interleaved flag isn't stored anywhere; it's implicit whether you
 345 // want to use it for full blocks or not.
 346 //
 347 // The first value must already be written using write_baseval() (so the delta
 348 // coding starts from the second value). Returns the end of the string.
 349 // May write 4 bytes past the end.
 350 template<unsigned BlockSize, class Docid>
 351 unsigned char *encode_pfor_single_block(const Docid *in, unsigned num, bool interleaved, unsigned char *out)
 352 {
 353         assert(num > 0);
 354         if (interleaved) {
 355                 assert(num == BlockSize);
 356         }
 357
 358         unsigned bit_width, exception_bit_width;
 359         BlockType block_type = decide_block_type(in, num, &bit_width, &exception_bit_width);
 360         *out++ = (block_type << 6) | bit_width;
 361
 362         switch (block_type) {
 363         case BlockType::CONSTANT: {
 364                 unsigned bit_width = num_bits(in[0]);
 365                 write_le<Docid>(in[0], out);
 366                 return out + div_round_up(bit_width, 8);
 367         }
 368         case BlockType::FOR:
 369                 return encode_for(in, num, bit_width, interleaved, out);
 370         case BlockType::PFOR_BITMAP:
 371                 return encode_pfor_bitmap(in, num, bit_width, exception_bit_width, interleaved, out);
 372         case BlockType::PFOR_VB:
 373                 return encode_pfor_vb(in, num, bit_width, interleaved, out);
 374         default:
 375                 assert(false);
 376         }
 377 }
 378
 379 #endif  // !defined(_TURBOPFOR_ENCODE_H)