Lemire Dictionary Save

High-performance dictionary coding

Project README

dictionary

High-performance dictionary coding

Suppose you want to compress a large array of values with (relatively) few distinct values. For example, maybe you have 16 distinct 64-bit values. Only four bits are needed to store a value in the range [0,16) using binary packing, so if you have long arrays, it is possible to save 60 bits per value (compress the data by a factor of 16).

We consider the following (simple) form of dictionary coding. We have a dictionary of 64-bit values (could be pointers) stored in an array. In the compression phase, we convert the values to indexes and binary pack them. In the decompression phase, we try to recover the dictionary-coded values as fast as possible.

Dictionary coding is in common use within database systems (e.g., Oracle, Parquet and so forth).

We are going to assume that one has a recent Intel processor for the sake of this experiment.

Core Idea

It is tempting in dictionary coding, to first unpack the indexes to a temporary buffer and then run through it and look-up the values in the dictionary. What if it were possible to decode the indexes and look-up the values in the dictionary in one step? It is possible with vector instructions as long as you have access to a gather instruction. Thankfully, recent commodity x64 processors have such an instruction.

A word on RAM access

There is no slower processor than an idle processor waiting for the memory subsystem.

When working with large data sets, it is tempting to decompress them from RAM to RAM, converting gigabytes of compressed data into (many more) gigabytes of uncompressed data.

If the purpose of compression is to keep more of the data close to the CPU, then this is wasteful.

One should engineer applications so as to work on cache-friendly blocks. For example, if have an array made of billions of values, instead of decoding them all to RAM, and then reading them, it is much better to decode them in small blocks at a time. In fact, ideally, one would prefer not to decode the data at all if possible: working directly over the compressed data would be ideal.

If you must decode gigabytes of data to RAM or to disk, then you should expect to be wasting enormous quantities of CPU cycles.

Usage

make && make test
./decodebenchmark

Experimental results (Skylake, August 24th 2016)

We find that an AVX2 dictionary decoder can be more than twice as fast as a good scalar decoder on a recent Intel processor (Skylake) for modest dictionary sizes. Even with large dictionaries, the AVX2 gather approach is still remarkably faster. See results below. We expect results on older Intel architectures to be less impressive because the vpgather instruction that we use was quite slow in its early incarnations.

The case with large dictionary as implemented here is somewhat pessimistic as it assumes that all values are equally likely. In most instances, a dictionary will have frequent values, more likely to be repeated. This will reduce the number of cache misses.

Also, in practice one might limit the size of the dictionary by horizontal partitions.

$ ./decodebenchmark
For this benchmark, use a recent (Skylake) Intel processor for best results.
Intel processor:  Skylake     compiler version: 5.3.0 20151204        AVX2 is available.
Using array sizes of 8388608 values or 65536 kiB.
testing with dictionary of size 2
Actual dict size: 2
        scalarcodec.uncompress(t,newbuf):  4.00 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.06 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.45 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  1.91 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.15 cycles per decoded value

testing with dictionary of size 4
Actual dict size: 4
        scalarcodec.uncompress(t,newbuf):  3.99 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.06 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.46 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  1.91 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.19 cycles per decoded value

testing with dictionary of size 8
Actual dict size: 8
        scalarcodec.uncompress(t,newbuf):  3.52 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  2.38 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.49 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  1.93 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.17 cycles per decoded value

testing with dictionary of size 16
Actual dict size: 16
        scalarcodec.uncompress(t,newbuf):  4.01 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.08 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.50 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  1.95 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.19 cycles per decoded value

testing with dictionary of size 32
Actual dict size: 32
        scalarcodec.uncompress(t,newbuf):  4.02 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.06 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.51 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  1.96 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.18 cycles per decoded value

testing with dictionary of size 64
Actual dict size: 64
        scalarcodec.uncompress(t,newbuf):  4.02 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.08 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.54 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  1.98 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.17 cycles per decoded value

testing with dictionary of size 128
Actual dict size: 128
        scalarcodec.uncompress(t,newbuf):  3.59 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  2.35 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.55 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  1.99 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.14 cycles per decoded value

testing with dictionary of size 256
Actual dict size: 256
        scalarcodec.uncompress(t,newbuf):  4.03 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.10 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.55 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  2.00 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.22 cycles per decoded value

testing with dictionary of size 512
Actual dict size: 512
        scalarcodec.uncompress(t,newbuf):  4.04 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.11 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.55 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  2.01 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.20 cycles per decoded value

testing with dictionary of size 1024
Actual dict size: 1024
        scalarcodec.uncompress(t,newbuf):  4.04 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.11 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.57 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  2.04 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.18 cycles per decoded value

testing with dictionary of size 2048
Actual dict size: 2048
        scalarcodec.uncompress(t,newbuf):  4.08 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.15 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.67 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  2.05 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.22 cycles per decoded value

testing with dictionary of size 4096
Actual dict size: 4096
        scalarcodec.uncompress(t,newbuf):  4.14 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.33 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.69 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  2.12 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.32 cycles per decoded value

testing with dictionary of size 8192
Actual dict size: 8192
        scalarcodec.uncompress(t,newbuf):  4.35 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.65 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  3.85 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  2.28 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  1.67 cycles per decoded value

testing with dictionary of size 16384
Actual dict size: 16384
        scalarcodec.uncompress(t,newbuf):  4.51 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.95 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  4.07 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  2.55 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  2.12 cycles per decoded value

testing with dictionary of size 32768
Actual dict size: 32768
        scalarcodec.uncompress(t,newbuf):  4.88 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  3.84 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  4.89 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.52 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.02 cycles per decoded value

testing with dictionary of size 65536
Actual dict size: 65536
        scalarcodec.uncompress(t,newbuf):  7.14 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  5.47 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.68 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  5.18 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  4.53 cycles per decoded value

testing with dictionary of size 131072
Actual dict size: 131072
        scalarcodec.uncompress(t,newbuf):  7.96 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  6.05 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  7.53 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  6.01 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  5.43 cycles per decoded value

testing with dictionary of size 262144
Actual dict size: 262144
        scalarcodec.uncompress(t,newbuf):  8.30 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  6.35 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  8.08 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  6.46 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  5.66 cycles per decoded value

testing with dictionary of size 524288
Actual dict size: 524288
        scalarcodec.uncompress(t,newbuf):  8.48 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  6.39 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  8.09 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  6.44 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  5.83 cycles per decoded value

testing with dictionary of size 1048576
Actual dict size: 1048235
        scalarcodec.uncompress(t,newbuf):  11.85 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  10.53 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  11.65 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  8.47 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  8.07 cycles per decoded value

Experimental results (Knights Landing, August 24th 2016)

We find that an AVX-512 dictionary decoder can be than twice as fast as an AVX dictionary decoder which is in turn twice as fast as a scalar decoder on a recent Intel processor (Knights Landing) for modest dictionary sizes. The case with large dictionary as implemented here is somewhat pessimistic as it assumes that all values are equally likely.

$ ./decodebenchmark
For this benchmark, use a recent (Skylake) Intel processor for best results.
Intel processor:  UNKNOWN     compiler version: 5.3.0        AVX2 is available.
Using array sizes of 8388608 values or 65536 kiB.
testing with dictionary of size 2
Actual dict size: 2
        scalarcodec.uncompress(t,newbuf):  7.75 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.39 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.26 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.22 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.06 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.48 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.14 cycles per decoded value

testing with dictionary of size 4
Actual dict size: 4
        scalarcodec.uncompress(t,newbuf):  7.83 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.49 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.35 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.23 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.10 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.49 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.21 cycles per decoded value

testing with dictionary of size 8
Actual dict size: 8
        scalarcodec.uncompress(t,newbuf):  7.27 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  6.99 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.17 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.23 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.10 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.59 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.25 cycles per decoded value

testing with dictionary of size 16
Actual dict size: 16
        scalarcodec.uncompress(t,newbuf):  7.98 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.65 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.32 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.23 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.16 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.68 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.34 cycles per decoded value

testing with dictionary of size 32
Actual dict size: 32
        scalarcodec.uncompress(t,newbuf):  7.92 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.63 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.27 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.23 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.19 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.65 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.43 cycles per decoded value

testing with dictionary of size 64
Actual dict size: 64
        scalarcodec.uncompress(t,newbuf):  8.05 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.76 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.32 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.31 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.25 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.85 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.66 cycles per decoded value

testing with dictionary of size 128
Actual dict size: 128
        scalarcodec.uncompress(t,newbuf):  6.64 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  6.36 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.19 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.34 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.28 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.83 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.57 cycles per decoded value

testing with dictionary of size 256
Actual dict size: 256
        scalarcodec.uncompress(t,newbuf):  8.07 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.87 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.39 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.39 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.35 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  1.95 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.69 cycles per decoded value

testing with dictionary of size 512
Actual dict size: 512
        scalarcodec.uncompress(t,newbuf):  8.07 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.87 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.32 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.52 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.48 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  2.04 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.76 cycles per decoded value

testing with dictionary of size 1024
Actual dict size: 1024
        scalarcodec.uncompress(t,newbuf):  8.22 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.97 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.43 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.63 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.57 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  2.05 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.83 cycles per decoded value

testing with dictionary of size 2048
Actual dict size: 2048
        scalarcodec.uncompress(t,newbuf):  7.97 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  7.69 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.37 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.76 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.64 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  2.11 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  1.91 cycles per decoded value

testing with dictionary of size 4096
Actual dict size: 4096
        scalarcodec.uncompress(t,newbuf):  8.53 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  8.20 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.67 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.58 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.56 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  2.55 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  2.35 cycles per decoded value

testing with dictionary of size 8192
Actual dict size: 8192
        scalarcodec.uncompress(t,newbuf):  8.66 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  8.27 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.79 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.92 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.86 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  2.80 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  2.54 cycles per decoded value

testing with dictionary of size 16384
Actual dict size: 16384
        scalarcodec.uncompress(t,newbuf):  8.85 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  8.55 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.95 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  4.05 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.87 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  3.14 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  2.96 cycles per decoded value

testing with dictionary of size 32768
Actual dict size: 32768
        scalarcodec.uncompress(t,newbuf):  6.75 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  6.81 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  6.94 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  3.68 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  3.58 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  3.41 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  3.24 cycles per decoded value

testing with dictionary of size 65536
Actual dict size: 65536
        scalarcodec.uncompress(t,newbuf):  11.75 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  13.76 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  9.64 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  5.29 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  5.50 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  4.54 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  4.66 cycles per decoded value

testing with dictionary of size 131072
Actual dict size: 131072
        scalarcodec.uncompress(t,newbuf):  19.07 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  19.53 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  17.02 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  11.02 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  11.01 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  8.03 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  8.01 cycles per decoded value

testing with dictionary of size 262144
Actual dict size: 262144
        scalarcodec.uncompress(t,newbuf):  22.84 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  23.12 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  20.63 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  16.57 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  16.45 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  13.68 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  13.69 cycles per decoded value

testing with dictionary of size 524288
Actual dict size: 524288
        scalarcodec.uncompress(t,newbuf):  22.34 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  22.54 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  20.36 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  16.30 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  16.34 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  14.91 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  14.94 cycles per decoded value

testing with dictionary of size 1048576
Actual dict size: 1048235
        scalarcodec.uncompress(t,newbuf):  21.93 cycles per decoded value
   decodetocache(&sc, &t,newbuf,bufsize):  22.11 cycles per decoded value
           avxcodec.uncompress(t,newbuf):  19.91 cycles per decoded value
  AVXDictCODEC::fastuncompress(t,newbuf):  16.33 cycles per decoded value
     AVXdecodetocache(&t,newbuf,bufsize):  16.30 cycles per decoded value
AVX512DictCODEC::fastuncompress(t,newbuf):  15.32 cycles per decoded value
  AVX512decodetocache(&t,newbuf,bufsize):  15.31 cycles per decoded value

Limitations

We support just one dictionary. In practice, one might want to use horizontal partitions.
We do not have a realistic usage of the dictionary values (we use a uniform distribution).
For simplicity, we assume that the dictionary is made of 64-bit words. It is hard-coded in the code, but not a fundamental limitation: the code would be faster with smaller words.
This code is not meant to be use in production. It is a demo.
This code makes up its own convenient format. It is not meant to plug as-is into an existing framework.
We assume that the arrays are large. If you have tiny arrays... well...
We effectively measure steady-state throughput. So we ignore costs such as loading up the dictionary in CPU cache.

Authors

Daniel Lemire and Eric Daniel (motivated by parquet-cpp)

Other relevant libraries

SIMDCompressionAndIntersection: A C++ library to compress and intersect sorted lists of integers using SIMD instructions https://github.com/lemire/SIMDCompressionAndIntersect
The FastPFOR C++ library : Fast integer compression https://github.com/lemire/FastPFor
LittleIntPacker: C library to pack and unpack short arrays of integers as fast as possible https://github.com/lemire/LittleIntPacker
The SIMDComp library: A simple C library for compressing lists of integers using binary packing https://github.com/lemire/simdcomp
StreamVByte: Fast integer compression in C using the StreamVByte codec https://github.com/lemire/streamvbyte
MaskedVByte: Fast decoder for VByte-compressed integers https://github.com/lemire/MaskedVByte
CSharpFastPFOR: A C# integer compression library https://github.com/Genbox/CSharpFastPFOR
JavaFastPFOR: A java integer compression library https://github.com/lemire/JavaFastPFOR
Encoding: Integer Compression Libraries for Go https://github.com/zhenjl/encoding
FrameOfReference is a C++ library dedicated to frame-of-reference (FOR) compression: https://github.com/lemire/FrameOfReference
libvbyte: A fast implementation for varbyte 32bit/64bit integer compression https://github.com/cruppstahl/libvbyte
TurboPFor is a C library that offers lots of interesting optimizations. Well worth checking! (GPL license) https://github.com/powturbo/TurboPFor
Oroch is a C++ library that offers a usable API (MIT license) https://github.com/ademakov/Oroch

Open Source Agenda is not affiliated with "Lemire Dictionary" Project. README Source: lemire/dictionary

Stars

100

Open Issues

Last Commit

7 years ago

Repository

lemire/dictionary

License

Apache-2.0

Open Source Agenda Badge

<a href="https://www.opensourceagenda.com/projects/lemire-dictionary"><img src="https://www.opensourceagenda.com/projects/lemire-dictionary/reviews/badge.svg" alt="Open Source Agenda"></a>

Submit Review Review Your Favorite Project

Submit Resource Articles, Courses, Videos

Submit Article Submit a post to our blog

From the blog

Dec 11, 2022

How to Choose Which Programming Language to Learn First?

From the blog

Dec 11, 2022