快速位打包算法

此crate是 Daniel Lemire 的 simdcomp C 库的 Rust 版本。

它可以压缩/解压缩

• 小整数的序列
• 递增整数的序列

⭐ 它很快。每秒可处理超过 40 亿个整数。

如何编译？

bitpacking 在稳定 Rust 上编译，但需要 rust > 1.27 才能编译。

只需将其添加到您的 Cargo.toml

bitpacking = "0.5"

对于某些位打包风格和某些平台，位打包 crate 可能会从特定的 simd 指令集受益。

在这种情况下，它将始终提供替代的标量实现，并在运行时回退到标量实现。

换句话说，您无需进行任何配置。您的程序将正确运行，并且以 CPU 可用的最快速度运行。

文档

参考文档

什么是位打包？

传统的压缩方案，如 LZ4，并不能有效地解决这个问题。相反，有不同系列的解决方案。

其中最直接和最有效的一种是 bitpacking

• 整数首先被分组到大小恒定的块中（例如，使用 SSE2 实现时为 128）。
• 如果没有隐式地计算，则计算表示所有整数所需的最小位数 b。换句话说，最小的 b 使得块中的所有整数严格小于 2^b。
• 然后，位打包表示就是一些变体，它将整数连接起来，限制在它们的最低 b-位。

例如，假设一个大小为 4 的块，当编码 4, 9, 3, 2。假设块中的最大值为 9，b = 4。所有值将按如下方式编码到 4 位。

因此，该块中的每个整数只需要 4 位。

选择 BitPacker1x、BitPacker4x 和 BitPacker8x。

⚠️ BitPacker1x、BitPacker4x 和 BitPacker8x 产生不同的格式，它们彼此不兼容。

BitPacker4x 和 BitPacker8x 分别设计用于利用 SSE3 和 AVX2 指令。

如果运行 CPU 上没有这些指令集，将在运行时安全地回退到这些格式的标量实现。

👌 如果您不确定，我建议使用 BitPacker4x。

BitPacker1x

BitPacker1x 是您期望的位打包器。整数在 b 位上的表示只是依次连接。一个块必须包含 32 个整数。

BitPacker4x

BitPacker4x 的位排序按 4 个整数的层进行。这为利用 SSE3 指令编码和解码流提供了机会。一个块必须包含 128 个整数。

BitPacker8x

BitPacker8x 的位排序按 8 个整数的层进行。这为利用 AVX2 指令编码和解码流提供了机会。一个块必须包含 256 个整数。

压缩小整数

extern crate bitpacking;

use bitpacking::{BitPacker4x, BitPacker};


// Detects if `SSE3` is available on the current computed
// and uses the best available implementation accordingly.
let bitpacker = BitPacker4x::new();

// Computes the number of bits used for each integers in the blocks.
// my_data is assumed to have a len of 128 for `BitPacker4x`.
let num_bits: u8 = bitpacker.num_bits(&my_data);

// The compressed array will take exactly `num_bits * BitPacker4x::BLOCK_LEN / 8`.
// But it is ok to have an output with a different len as long as it is larger
// than this.
let mut compressed = vec![0u8; 4 * BitPacker4x::BLOCK_LEN];

// Compress returns the len.
let compressed_len = bitpacker.compress(&my_data, &mut compressed[..], num_bits);
assert_eq!((num_bits as usize) *  BitPacker4x::BLOCK_LEN / 8, compressed_len);

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

assert_eq!(&my_data, &decompressed);

基准测试

以下基准测试在我的笔记本电脑 CPU 上的一个线程上运行：Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz。

您可以通过运行以下命令在您的硬件上获得准确的数据。

cargo bench

BitPacker1x

BitPacker4x（假设可用 SSE3 指令）

BitPacker8x（假设可用 AVX2 指令）

参考

• SIMD 压缩和排序整数交集

您可能还想查看的其他 crate

• stream vbyte Stream-VByte 实现
• mayda 使用相同算法的另一个 crate 实现。