整数压缩算法 TurboPFor

本文讲述整数压缩算法 TurboPFor。

原作者写了个示例，以方便理解：https://github.com/stapelberg/goturbopfor

1 压缩后的格式

以 TurboPFor256 为例，每个 block 包含 256 个整数，最后一个 block 可能不足 256 个整数：

最后一个 block 使用一般的bitpacking，其它 block 使用 SIMD bitpacking。

每个 block 的前 2 个 bit 标识该 block 的类型：

• 11: constant
• 00: bitpacking
• 10: bitpacking with exceptions (bitmap)
• 01: bitpacking with exceptions (variable byte)

需注意，block 中不会存放被编码的数据个数，使用者需要自己知道有多少个数据要被解码，还需要知道应将多少个字节喂给 TurboPFor，所以使用者需要自己额外定一个容器格式。

TurboFor 会自动为每个 block 选择最好的 block 类型。

Constant block

一个 constant block 中记录了一个位宽 <= 32 的值。

• 第 1 个字节的后 6 位存储 constant 的位宽
• 后面的字节存储 constant

例如调用 decode(input, 3, output)，其中 input 如下所示：

可以看到被解码的数据的位宽是 32，所以读取随后的 4 个 block，采用小端方式得到数字的二进制形式为 10111000-10010001-00100110-00110110， 其十六进制格式为 0xB8912636。因为 decode() 的第 2 个参数是 3，可知是 3 个 0xB8912636 被压缩了，所以解压后得到 output = {0xB8912636, 0xB8912636, 0xB8912636}

Bitpacking block

第 1 个 bitpacking block 指定了位宽 <= 32，随后跟着的是被压缩的数据。

• 第 1 个字节的后 6 位存储 value 的位宽
• 后面的字节存储 n 个 value

每个值都是小端方式存储，例如位宽是 3，那么 110，110，000 拼接后会变成 000110110

Bitpacking with exceptions (bitmap) block

如果大部分数字都可以用 3 bit 表示，但是只有少量数字用 8 bit 表示，那么就可以将数据分为两部分：value 和 exception。

假如压缩了 n 个数据

• 第 1 个字节的后 6 位存储 value 的位宽
• 第 2 个字节存储 exception 的位宽
• 接下来的 n 个 bit 是 exception map，如果第 i 个数字 exception 和 value 的拼接，那么第 i 个 bit 为 1，假如 bit 为 1 的个数是 m
• 接下来是 m 个 exception
• 接下来是 n 个 value

如下例子中，在解码第 3 个整数 out2(000b) 时，还需要与 exception ex0(10110b) 结合到一起，因为在 bitmap 中第 3 位是 1，最终得到 10110000b。

exception 的数量可通过统计 bitmap 中 1 的数量得到，统计的方法可参考 popcount instruction。

Bitpacking with exceptions (variable byte)

如果 exception 的位宽不统一，就使用 variable byte 编码。

假如压缩了 n 个数据

• 第 1 个字节的后 6 位存储 value 的位宽
• 第 2 个字节存储 exception 的数量 m
• 从第 3 个字节起，存储 n 个 value
• 接下来存储 m 个 exception
• 接下来存储 exception 的下标 i，说明当前 exception 可以与第 i 个 value 拼接成一个数字

2 解码变长字节

第一个字节 b[0] 用来存储区分范围

• [0 - 176]：值是 b[0] 0 -- 10110000
• [177 - 240]：14 bit 的值，其中高 6 bit 位于 b[0]，低 8 bit 位于 b[1] 0 -- 11110000
• [241 - 248]：19 bit 的值，其中高 3 bit 位于 b[0]，b[1] 和 b[2] 存储低 16 bit 11110001 -- 11111000
• [249 - 255] ：32 bit 的值，存储在 b[1], b[2], b[3]，也有可能会有 b[4] 11111001 -- 11111111

值的存储空间：

• [0 - 176]：1 byte 0 -- 10110000
• [177—16560]：2 byte，高 6 bit 会加到 177 10110001 -- 1000000-10110000
• [16561—540848]：3 byte，高 3 bit 加到 241 1000000-10110001 -- 1000-01000000-10110000
• [540849—16777215] ：4 byte，0 会加到 249 1000-01000000-10110001 -- 11111111-11111111-11111111
• [16777216—4294967295] ：5 byte，1 加到 249 1-00000000-00000000-00000000 -- 11111111-11111111-11111111-11111111

3 解码：bitpacking

一般的 bitpacking

整数按照顺序存储，例如，bitpack 3 bit 的整数：

SIMD bitpacking (256v32)

SIMD bitpacking 会一次性处理 8 个小端序的 uint32：

4 TurboPFor-Integer-Compression

源码：TurboPFor-Integer-Compression

所有的编解码函数定义都可以位于 include/ic.h，实现部分位于 lib/vp4c.c 和 lib/vp4d.c，是使用宏实现的。例如对于 size_t p4nd1enc128v32(uint32_t *__restrict in, size_t n, unsigned char *__restrict out);，无法直接通过函数名直接搜到其实现，需通过如下方式拼接得到函数名。

在 vp4c.c 中可以看到如下函数：

size_t T2(P4NENC, USIZE)(uint_t *__restrict in, size_t n, unsigned char *__restrict out) {
    ...
}

其中，T2 在 lib/include_/conf.h 中定义如下：

#define T2_(_x_, _y_) _x_##_y_
#define T2(_x_, _y_) T2_(_x_,_y_)

仅仅用于拼接两个字符串。

P4NENC 和 USIZE 在 lib/vp4c.c 中定义如下：

#define  P4NENC    p4ndenc128v
#define USIZE 32

进行宏替换 T2(P4NENC, USIZE) --> p4ndenc128v32 后就得到了函数名。

也可以使用 cpp vp4c.c > cp4c.i 得到宏扩展后的文件，不过如果有的宏的符号没找到的话，扩展后会缺失。

参考

TurboPFor: an analysis (2019)