Crate bitpacking [−] [src]

Fast Bitpacking algorithms

This crate is a Rust port of Daniel Lemire's simdcomp C library. It contains different implementation of integers compression via bitpacking. Each implementation requires on a different CPU SIMD instruction set, for state of the art performance.

This crate is used by tantivy.

For instance, with SSE3, you can typically expect more than 4 billions ints per seconds. Check the Benchmark for more accurate details.

Usage

This crate contains different implementation for bitpacking depending on the instruction set available with your processor. The resulting format are not compatible one with each other.

Currently the following are available :

  • scalar: implementation not using any SIMD instruction. A block has a size of 32. This implementation is still more performant naive solutions.
  • SSE3: bitpacking 4 integer at once. (block size of 128). Requires the sse3 feature to be enabled. This feature is enabled by default.
  • AVX: butpacking 8 integers at once. (block size of 256). Delta integration is comparatively expensive. Requires to enable the avx feature.

I recommend using the SSE3 implementation if you are not sure what you are doing and you are targetting x86_64 CPUs that have been produced after 2006.

Make sure to compile with

RUSTFLAGS="-C target-cpu=native"

Examples without delta-encoding

extern crate bitpacking;

use bitpacking::{SSE3BitPacker, BitPacker};

let num_bits: u8 = SSE3BitPacker::num_bits(&my_data);

// A block will be take at most 4 bytes per-integers.
let mut compressed = vec![0u8; 4 * SSE3BitPacker::BLOCK_LEN];

let compressed_len = SSE3BitPacker::compress(&my_data, &mut compressed[..], num_bits);

assert_eq!((num_bits as usize) *  SSE3BitPacker::BLOCK_LEN / 8, compressed_len);

// Decompressing
let mut decompressed = vec![0u32; SSE3BitPacker::BLOCK_LEN];
SSE3BitPacker::decompress(&compressed[..compressed_len], &mut decompressed[..], num_bits);

assert_eq!(&my_data, &decompressed);

Examples with delta-encoding

extern crate bitpacking;

use bitpacking::{SSE3BitPacker, BitPacker};

let num_bits: u8 = SSE3BitPacker::num_bits_sorted(16u32, &my_data);

// A block will be take at most 4 bytes per-integers.
let mut compressed = vec![0u8; 4 * SSE3BitPacker::BLOCK_LEN];

let compressed_len = SSE3BitPacker::compress_sorted(&sorted_array, &mut compressed[..], num_bits);

assert_eq!((num_bits as usize) *  SSE3BitPacker::BLOCK_LEN / 8, compressed_len);

// Decompressing
let mut decompressed = vec![0u32; SSE3BitPacker::BLOCK_LEN];
SSE3BitPacker::decompress(17, &compressed[..compressed_len], &mut decompressed[..], num_bits);

assert_eq!(&sorted_array, &decompressed);

Structs

SSE3BitPacker
ScalarBitPacker

Traits

BitPacker