，

Decoding billions of integers per second through vectorization

D. Lemire and L. Boytsov LICEF Research Center, TELUQ, Montreal, QC, Canada Carnegie Mellon University, Pittsburgh, PA, USA

摘要

在许多重要的应用程序例如搜索引擎和关系数据库系统中，数据以整数数组的形式存储。对这些数组进行编码，最重要的是解码会消耗大量的CPU时间。因此研究人员已经做出了巨大的努力来减少与压缩和减压相关的成本，特别的是已经开发出超标量的现代处理器和单指令多数据(SIMD)指令集。我们引入了一种新的向量化方案SIMD-BP128*，这比以前提出的向量化方法有所改进。它的速度几乎是varint-G8IU和PFOR在台式机处理器上最快的方案的两倍，同时SIMD- BP128*每个整数最多节省2位。为了获得更好的压缩效果，我们提出了另一种新的向量化方案SIMD-FastPFOR，其压缩率和最新的Simple-8b相比降低10％之内，但是解码速度快了两倍。

关键字：性能；测量；索引压缩；向量处理

1. 引言

计算机存储设备是一个层次结构，从慢而便宜（磁盘或磁带）到快而昂贵（寄存器或CPU缓存）。在许多情况下，访问较低层次的存储设备会抑制应用程序性能。 以前只有磁盘和磁带被认为是慢速设备。 因此，应用程序开发人员倾向于仅优化磁盘输入/输出。而如今，CPU变得如此快以至于访问主内存已成为许多工作负载的限制因素。数据压缩可以通过减少主存带宽显著提高查询性能。数据压缩有助于将更多的数据加载并保存到存储器中。因此，快速压缩方案可以提高数据库系统和文本检索引擎的性能 。

我们主要研究32位整数序列的压缩技术。最好是大多数整数都很小，因为我们可以通过更紧凑地表示小整数来节省空间，也就是说使用短代码。假设没有一个值大于255，我们可以使用1个字节对每个整数进行编码，从而实现4的压缩比(整数使用未压缩格式的4个字节)。

在关系数据库系统中，列值通过字典编码转换为整数值。为了提高压缩性，我们可以将最频繁的值映射到最小的整数。在文本检索系统中，单词通常由整数文档标识符的排序列表表示(也称为发布列表)。这些标识符通过数据差分转换为小整数。 其他数据库索引也可以类似地存储。

数据差分的主流方法是差分编码(图  1)，而不是存储j将原始数组排序后的数据$(x_1 , x_2 , ...with x_i <= x_{i+1} for all i )$，我们只保留连续元素之间的差异以及初始值：$(x_1, \delta_2= x_2 -x_1,\delta_3=x_3-x_2, ...)$。差异或增量是非负整数，通常比原始整数小得多， 因此它们可以被更有效地压缩。我们可以通过计算前缀和来重建原始数组$(x_j=x_1 + \sum_{i=2}^j\delta_j)$。差分编码也被称为增量编码，不要与Elias delta编码混淆(2.3节)，差分编码的一个缺点是，随机访问位于给定索引处的整数可能需要对几个增量求和，如果需要，我们可以通过将大型数组划分为较小的数组来缓解此问题。

图 1. 使用差分编码和整数压缩算法对整数数组进行编码和解码。 工程师可能会倾向于使用通用压缩工具，例如LZO，Google Snappy，FastLZ，LZ4或gzip， 然而这可能是不明智的。 我们最快的方案比快速通用库如Snappy快一个数量级，同时压缩效果更(第6.5节)，使用基于单指令多数据（SIMD）操作的专用方案压缩这些整数数组可能更可取。Stepanov et al.报告说到他们基于SIMD的varint-G8IU算法的性能比经典的可变字节编码方法（[第2.4节]()）高300％，还表明使用SIMD指令可使解码算法的性能提高50％以上。

表 1 中，给出对32位整数最好的解缩速度报告，单位为百万/秒。我们指出作者是否明确使用了单指令、多数据指令。结果不具有直接可比性，但它们说明了性能的演变。

	Speed	Cycles/int	Fastest scheme	Processor	SIMD
This paper	2300	1.5	SIMD‐BP128*	Core i7 (3.4 GHz)	SSE2
Stepanov et al. (2011)	1512	2.2	varint‐G8IU	Xeon (3.3 GHz)	SSSE3
Anh and Moffat (2010)	1030	2.3	binary packing	Xeon (2.33 GHz)	no
Silvestri and Venturini (2010)	835	—	VSEncoding	Xeon	no
Yan et al. (2009)	1120	2.4	NewPFD	Core 2 (2.66 GHz)	no
Zhang et al. (2008)	890	3.6	PFOR2008	Pentium 4 (3.2 GHz)	no
Zukowski et al. (2006)	1024	2.9	PFOR	Pentium 4 (3 GHz)	no

SIMD，单指令多数据； SSE2，单指令多数据流技术扩展 2； SSSE3，单指令多数据流技术扩展 3。

我们以保守的方式报告自己的速度，(1) 我们的计时基于挂钟时间，而不是常用的CPU时间；(2) 我们的计时包括所有的解码操作，包括前缀和的计算，而其他作者会省略它；(3) 我们报告的基于真实数据可以达到每秒23亿个整数的速度，另外测量一些真实数据的速度甚至达到了25亿以及28亿。

从表 1我们可以看到的另一个结论是，并不是所有的作者都选择使用SIMD指令，尽管PFOR 有几种变体，例如NewPFD和OptPFD ，自Pentium 4和SSE2推出以来，我们首次引入了一种变体，旨在利用可用的向量化指令。 实验结果表明，这种向量化是必要的，我们的SIMD-FastPFOR方案比PFOR的解码速度至少高出30％，同时提供了出色的压缩率$(10％)$。 在一些情况下，SIMD-FastPFOR 是原始PFOR的两倍。

对于大多数方案，前缀总和计算是如此之快，以至于只占运行时间的20％或更少。 但是由于我们的新颖方案要快得多，因此前缀和可以占运行时间的大部分。因此我们不得不尝试更快的替代方法。 我们发现使用SIMD指令的向量化前缀总和可以快两倍。 没有向量化差分编码，我们将无法达到每秒20亿个整数的速度。

从某种意义上说，我们获得的速度提升是直接将高级硬件指令应用于整数编码问题（特别是2001年推出的SSE2）。 但是，说明如何执行此操作并量化所产生的收益是很有启发性的。

2 相关工作

一些最早的整数压缩技术有Golomb coding ，Rice coding以及Elias gamma和delta coding。 近年来已经添加了几种更快的技术，例如Simple系列，binary packing和patched coding。 我们简要回顾一下。

因为我们使用无符号整数，所以我们使用两种表示形式：二进制和一元编码。在这两个系统中，数字仅使用两位数字表示：0和1。二进制表示法是标准的位置以2为基的系统（例如1→1、2→10、3→11）。给定正整数x，二进制表示法要求$log_2（x + 1）$位。计算机通常通过将前导零加到固定的位数来使用二进制数存储无符号整数，例如，使用8位将3写入00000011。用一元编码表示法，我们将数字x表示为$x − 1$个0的序列，后跟数字1（例如1→1、2→01、3→001）。如果数x可以为零，我们可以存储x +1。

2.1 Golomb和Rice编码

在Golomb编码中，给定一个固定参数b和一个正整数v被压缩$v/b$的商使用一元编码，余数r=v % b​使用二进制编码，当b选择为2的幂时，所得算法称为Ricecoding。可以通过假设整数遵循已知分布来最佳地选择参数b[。

不幸的是，Golomb和Rice要比variable byte慢很多，达不到我们每秒解码数十亿个整数的目标。

2.2. Interpolative coding

如果速度不是问题，但是希望对排序后的数组进行高压缩，则Interpolative coding可能会很有吸引力。在此方案中，我们首先以最小的形式存储最小值和最大值$x_1$和$x_n$。然后将中间的值以二进制形式存储，这是因为该值必一定x 1，x n）范围内。如果$x_1 = 16$且$x _n$ = 31，我们知道对于x之间的任何值，差$x−x_1$是从0到15。因此，我们可以仅使用4位对这种差异进行编码。然后递归地重复该技术。不幸的是它比Golomb编码还慢[。

2.3. Elias gamma and delta coding

一个Elias gamma码[][][有两部分组成，第一部分以一元编码，即以二进制$log_2（x + 1)$存储正整数所需的最少位数。 第二部分以二进制表示形式的整数去除最高有效位。 如果整数等于1，则第二部分为空。例如1→1、2→01 0、3→01 1、4→001 00、5→001 01。如果整数可以为零，我们可以将其值编码为+1。

随着数字变大，Elias gamma coding变得低效。 为了更好地压缩，Elias delta对Elias gamma的第一部分的数字在进行一次Elias gamma ，而第二部分则采用二进制表示法进行编码。 例如要使用Elias delta码对数字8进行编码，我们首先将4 =$log_2（8 + 1）$存储为001 00，然后我们可以存储除最高有效位以外的所有位。 最终结果为001 00 000。

然而variable  byte的速度是Elias gamma和delta的两倍。Golomb和Elias gamma无法达到我们每秒压缩数十亿个整数的目标。

2.3.1 k-gamma

Schlegel等提出了一种更适合当前处理器的Elias-gamma版本。为了简化向量化，使用相同的位数将数据存储在k个整数的块中，其中k∈{2,4}。 此方法类似于第2.6节中描述的二进制打包。

与常规Elias gamma 一样，对于k个整数使用相同的位数，我们使用一元代码来存储此位数的值。使用与第4节相同的向量化布局（称为垂直或交错）存储 Elias gamma代码的二进制部分。 在解压缩期间，我们以k个整数为一组解码整数。 对于每个组，我们首先检索二进制长度。 然后我们使用类似于第4节中描述的快速位拆包技术的一系列掩码和移位操作对组元素进行解码。此步骤不需要分支。

2.4 可变字节和面向字节的编码

可变字节是一种流行的技术，它以许多名称（v-byte, variable-byte , var-byte, vbyte , varint, VInt, VB , 以及Escaping ）。据我们所知，由Thiel 和 Heaps在1972年首次提出的。可变字节以字节为单位对数据进行编码：它使用低7位存储数据，而第八位用作代码长度的隐式指示。例如：

• $[0,2^7)$中的整数使用1个字节写入，低7位用于存储整数的二进制表示，第八位设置为0。

• 在整数$[2^7，2^{14})$，使用2个字节写入，第一个字节的8位被设置为2，而第二个字节的第八个bit置为0，其余的14位被用于存储二进制整数的表示形式。

举一个具体的例子，数字200以二进制表示法写为11001000。可变字节将使用16位将其编码为1 0000001 0 1001000。解码时，字节依次读取：如果第八位为1，则丢弃该第八位；每当第八位为0时，我们就输出一个新的整数。

尽管可变字节很少能最佳地压缩数据，但它相当有效。在我们的测试中，可变字节编码数据的速度是大多数替代方法的三倍。此外当数据不可高度压缩时，它可以更简约方案的压缩率。

Stepanov et al.将可变字节编码概括为一系列面向字节的编码。 它们的主要特征是一个编码后的字节中8个位来自一个整数， 当可变字节每字节使用1位作为描述符时，有替代方案例如，varint-G8IU和varint-GB将所有描述符重组为一个字节。 这样的替代布局使得同时解码多个整数更加容易。一种类似的将描述符放在控制字中的方法被用来加速Lempel-Ziv算法的变体。

例如varint-GB使用一个字节描述4个整数，一个整数使用2bit来表示。假设我们要存储整数$2^{15}，2^{23}，2^7$和$2^{31}$。在通常的二进制表示法中，我们将分别使用2、3、1和4个字节。如果我们假设每个数字都是使用非零字节数编码的，那么我们可以将序列存储为1、2、0、3。这4个整数中的每一个都可以使用2位来写入。我们可以将它们打包成一个字节01、10、00和11。在此字节之后，我们使用$2 + 3 + 1 + 4 = 10$个字节写入整数值。

varint-GB使用单个描述符对4个整数进行编码，而varint-G8IU对8 byte使用一个描述符，这8个字节组可以存储2到8个整数。1 byte的描述符放在8 byte前面，每当描述符位设置为0时，相应的字节就是整数的结尾。比如四个整数$2^{15}、2^{23}、2^7$和$2^{31}$，只能将前三个整数存储到单个8字节组中，这些整数分别使用2、3和1个字节，描述符字节以二进制表示为11001101。描述符的前两位（01）告诉我们，第一个整数使用2个字节。接下来的三位（011）表示第二个整数需要3个字节。由于第三个整数使用单个字节，因此描述符的下一个位将为0。在此模型中无法使用后两个字节，因此我们将后两位设置为1。

在最新的x86处理器上，可以使用SSSE3混选指令pshufb有效地解压varint-G8IU压缩的整数。此操作选择性的将源16 byte向量复制到目标16 byte缓冲区的指定位置，并将选定的元素替换为零。混选(shuffle)这个名称用词不当，因为某些源字节可以省略，而一些源字节可以多次复制到多个不同的位置。该操作采用两个16向量（16×8位＝ 128位），第一个向量的字节将被混选到输出向量，而第二个向量用作混选掩码。混选掩码中的每个字节确定源向量中的一个值将输出到目标向量中的相应位置。如果该位置字节的值大于127，则目标字节的对应位置将置零。

在图2中，我们说明了varint-G8IU的解码算法的一个步骤。我们假定已经检索了描述符字节，该描述符字节存储三个整数$2^{15}、2^{23}、2^7$所需的2、3、1进行了编码。描述符字节用于为pshufb获得适当的混选掩码。该掩码定义了编码的操作序列，该操作序列将字节从源复制到目标缓冲区，或用零填充目标特定的缓冲区字节。所有这些字节操作都以以下方式并行执行

• 第一个整数使用2个字节，这两个字节均被复制到目标缓冲区的0-1字节。目标缓冲区的2–3字节被置零。

• 同样，我们将源缓冲区的字节2–4复制到目标缓冲区的4–6字节。目标缓冲区的7字节被置零。

• 最后一个整数仅使用一个5字节，我们将此字节的值复制到8字节，9-11字节置零。

• 目标缓冲区的字节12-15当前未使用，将由后续的解码步骤填充。在当前步骤中，我们可以使用任意值

图 2. 使用混选指令同时解码方案varint-G8IU中的三个整数的示例。 整数$2^{15}、2^{23}和2^7$被压缩到8字节的块中，其中2字节未使用。 字节值由十六进制数展示，源16字节缓冲区复制目标16字节缓冲区或将其填充为零。 箭头指示将源缓冲区的哪些字节复制到目标缓冲区，以及它们在源缓冲区和目标缓冲区中的位置。

我们不知道Google是否使用SIMD指令实现了varint-GB。但是，Schlegel等和Popov描述了pshufb指令加速varint-GB方案的解码的方案，Schlegel等人将其称 four‐wise null suppression。

Stepanov等[发现varint-G8IU的压缩比基于SIMD的varint-GB速度快20％。 与普通可变字节相比varint-G8IU的压缩率稍差10％，但快了2-3倍。

2.5 Simple系列

可变字节采用固定的输入长度并产生可变长度的输出，而Simple系列在每一步都输出固定数量的bit来处理不定长输入。但是与varint-G8IU不同，Simple系列的方案不是面向字节的。它们可能在高度可压缩的数组上表现更好。例如它们可以将{0,1}中的数字序列压缩为1bit / int。

64位处理器上最有竞争力的简单方案是Simple-8b 。它输出64位，每个64位的前4位是用于指示编码的模式选择器。其余的60位用于保留数据。每个整数使用相同数量的位b来存储。Simple-8b有两种编码零序列的方案和14种编码正整数序列的方案。例如：

• 选择器0或1分别代表包含240和120个零的序列。在这种情况下，将忽略60个数据位。
• 选择器2对应于b =1。这使我们可以存储60个{0,1}整数，这些整数压缩在一个bit中
• 选择器3对应于b = 2，并允许将30个[0,3]的整数，每个整数放入2个bit

依此类推见表  2，选择器的值越大，b越大，60个位容纳的整数越少。在编码过程中，我们会依次尝试从值0开始的选择器。也就是说我们会贪婪地尝试在下一个64位字中容纳尽可能多的整数。

表2. Simple-8b方案的编码模式。1个到240个整数用一个64位字编码。

Selector value	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Integers coded	240	120	60	30	20	15	12	10	8	7	6	5	4	3	2	1
Bits/int	0	0	1	2	3	4	5	6	7	8	10	12	15	20	30	60

比如其他方案Simple-9和Simple-16使用32位。尽管这些方案有时可能会压缩得更好，但它们通常较慢。因此我们在实验中省略了它们。与Simple-8b可以在$[0,2^{60}）$中编码整数不同，Simple-9和Simple-16被限制为$[0,2^{28}）$中的整数。

尽管Simple-8b在编码过程中不如可变字节快，但仍比许多替代方法快。因为可以高效地执行解码步骤在获得比可变字节更好的压缩率的同时，我们还可以获得良好的解码速度。

2.6 Binary packing

Binary packing与来自 Goldstein et al. 的frame‐of‐reference (FOR)以及来自Ng 和 Ravishankar的tuple differential coding技术密切相关。在Binary packing中，大整数数组被划分为块（如128个整数位一个块）。 首先计算块中的值范围，然后参考范围值写入块中的所有差值。如果块中的值是[1000,1127]范围内的整数，则它们可以对每个整数使用7个bit进行编码($log_2（1127 + 1 − 1000）= 7$)，存储的每个值与1000的偏移量。此外还需要存储块长度、7和1000用于解码。

Anh和Moffat称Binary packing为Packed Binary，而Delbru 等人称128‐integer binary packing FOR 和 32‐integer binary‐packing AFOR‐1。

2.7 变长的Binary packing

确定Binary packing 的存储成本有三个因素：

• 以二进制表示法存储最大数值所需的位数b，

• 块长度B

• 每块的固定开销 κ。

一个块的总存储成本为bB +  κ。Binary packing使用固定长度的块如B = 32或B = 128。我们可以动态改变块的长度以提高压缩率。这给每个块增加了很小的开销，因为我们不仅需要存储相应的位宽b，还需要存储块长度B。然后我们遇到了一个常规的优化问题：必须将数组划分为多个块，以使总存储成本降至最低。每个块的成本仍然是bB +  κ，但是块长度B可能在一个块之间变化。

块长的动态选择首先由Deveaux 等人提出。 他们使用了自上而下和自下而上的启发式方法压缩率提升了(15–30)％

Delbru等也实现了两个这样的自适应解决方案，AFOR-2和AFOR-3。AFOR-2选择长度为8、16和32的块，而AFOR-3在有连续整数的情况下增加了特殊处理。为了确定最佳的块配置，他们选择32个整数并尝试各种配置（1个32整数的块，2个16整数的块等）。他们保持配置最小化存储成本。实际上他们将贪婪方法应用于存储最小化问题。

Silvestri和Venturini 提出了两个可变长度方案，我们选择了它们的最快版本称为VSEncoding。VSEncoding优化了块长度使用动态编程对长度为1–14、16和32的块进行优化。也就是说，给定数组中每个整数的整数对数，VSEncoding会找到一个分区，真正将总存储成本降至最低。我们希望VSEncoding提供比AFOR-2和AFOR-3更高的压缩率。

2.8 Patched coding(修补编码)

Binary packing 有时可能压缩效果不好。 例如整数1、4、255、4、3、12、101可以使用8位的二进制存储形式存储。 但是具有一个较大值的相同序列例如1、4、255、4、3、12、4294967295不再那么可压缩，至少需要32位/ int。为了解决这个问题，Zukowski等人提出Patched，我们使用b个bit存储大部分整数，当一些整数大于或等于$2^b$时，把这些异常数存储在单独的位置。他们这种方法为PFOR，当使用差分编码时，也会称为PFD 、PFor或PForDelta。

我们从将输入数组划分为具有固定大小（例如32MB）的子数组开始。将每个这样的子数组称为页。PFOR中的整个页使用一个bit长度即b，为了确定编码期间的最佳b，在页外创建最多$2^{16}$个整数的样本。然后测试各种位宽度，直到获得最佳压缩率。在实践中为了加快计算速度，我们可以构建直方图，记录给定整数所需要的位数$（log_2（x + 1））$。

一个页以128个整数的块进行编码，一个页有一个的异常数组。当整数的值为正常的值时，将该值编码为b个bit。如果是异常值时，则将下一个异常值的偏移量写入b个bit。偏移量是下一个异常的索引与当前异常的索引之间的差减一，我们将整数值和偏移量存储在同一数组中。如下列数组：

10, 10, 1, 10, 100110, 10, 1, 11, 10, 100000, 10, 110100…

假设位宽b = 3，那么在位置4,9,11为异常值，偏移量为9-4-1 = 4,11-9-1 = 1。 用二进制表示4→100和1→1，因此我们将存储结果如下

0,10,1,10,100,10,1,11,10,1,10…

在每个压缩的块之前是一个包含两个标记的32位。 第一个标记指示第一个异常在块中的位置，在我们的示例中为4。第二个标记指示该块第一个异常值在异常数组中的位置。

我们首先读取第一个异常的位置， 然后转到该位置找到偏移量，从而可以获取下一个异常的位置。如果位宽b太小而无法存储偏移量值，也就是说，如果偏移量大于或等于$2^b$，则我们额外创建强制的异常来链接异常。

当异常过多时，这些异常表可能会溢出，因此有必要启动新页，Zukowski使用的页大小为32MB。 在我们自己的实验中，我们将大型数组划长度为$2^{16}$的整数数组（第6.2节），实际我们使用的是单个页。PFOR 不压缩异常值。 为了提高压缩率，Zhang等人建议使用8位、16位或32位存储异常值。 我们实施了这种方法此后称为PFOR2008）

表3.Patched coding概述，PFOR和PFOR2008强制产生异常，并且每页使用单个位宽b。 NewPFD和OptPFD逐块存储异常。 我们实现了所有方案，每个块具有128个整数，并且页大小至少为$2^{16}$个整数。

	Compulsory	Bit width	Exceptions	Compressed exceptions
PFOR	Yes	Per page	Per page	No
PFOR2008	Yes	Per page	Per page	8, 16, 32 bits
NewPFD/OptPFD	No	Per block	Per block	Simple‐16
FastPFOR [Section 5]	No	Per block	Per page	Binary packing
SIMD‐FastPFOR ([Section 5]	No	Per block	Per page	Vectorized bin. Pack.
SimplePFOR [Section 5]	No	Per block	Per page	Simple‐8b

2.8 1 NewPFD和OptPFD

PFOR和PFOR2008的压缩率相对适中。 我们发现在32个整数的块上，它们的性能比Binary packing差。 为了获得更好的压缩，Yang 等人提出了两个新方案，称为NewPFD和OptPFD。 NewPFD有时被称为NewPFOR 44/45，而OptPFD也被称为OPT-P4D24。它们不是使用每页相同的位宽b，而是使用每块(128个整数)相同的位宽。 避免强制性异常的浪费，也是将异常偏移量存储在块中，而是存储异常整数值的低b位。 给定以下数组：

10, 10, 1, 10, 100110, 10, 1, 11, 10, 100000, 10, 110100…

并且宽度b为3，将压缩为：

10,10,1,10,110,10,1,11,10,0,10,100…

异常值的高32-b位，即在示例中为100,100,110…以及它们的位置放入异常数组中，并使用Simple-16压缩。每个块前面都有一个32位，用于存储位宽b、异常数和异常数据压缩后的长度。NewPFD通过以使不超过10％的整数为异常的方式来决定b，OptPFD选择b的值以最大化压缩率。 为了加快处理速度，建议在0-16、20和32的整数值中选择位宽。

Ao 等人也提出了一个称为ParaPFD的PFOR版本。 尽管它的压缩效率比NewPFD或PFOR差，但它是为在图形处理单元上快速执行而设计的。

3. 快速差分编码和解码

我们认为所有方案在实验上都基于32位无符号整数的差分编码。 差异或增量的计算通常被认为是微不足道的操作，其仅占总解码时间的可忽略部分。 因此作者没有讨论它。 但是根据我们的经验，差分解码的直接实现可能比小整数的解压缩慢四倍。

我们已经实现并评估了两种差分的方法：

1. 标准形式的差分编码很简单，在编码过程中每个值仅需一个减法$（δ_i= x_i-x_{i-1}）$，在解码期间每个值只需一个加法即可有效地计算前缀和$（x_i =δ_i+ x_{i-1}）$。
2. 向量化的差分编码使前四个元素保持不变。对剩余每个元素索引为$i$，减去索引为$i-4$的元素：$δ_i= x_i-x_{i-4}$。换句话说，原始数组$（x_1,x_2,...）$转换为$（x_1,x_2,x_3，x_4,δ_5= x_5-x_1,δ_6= x_6-x_2,δ_7= x_7-x_3,δ_8= x_8-x_4, …）$ 这种方法的优点是我们可以使用一个SIMD操作来计算四个差值。 此操作对两个四个元素的向量执行逐个元素的减法。 解码部分是对称的，$x_i =δ_i+ x_{i-4}$同样，我们可以使用单个SIMD指令同时执行四个加法。

使用标准差分解码，即展开循环计算前缀和。我们可达到20亿个整数/s或1.7cycle / int的速度。同时我们实现了差分编码的向量化版本。速度能达到50亿/s。但是这是有代价的，向量化的差分通常以向前第四个元素进行差分甚至更长。这将导致存储成本平均增加2位（表5）。

为了防止内存带宽成为的瓶颈，我们更喜欢计算差分编码和解码。我们从最大索引开始，以递减的索引顺序计算增量。例如，给定整数1,4,13，我们首先计算13和4之间的差，我们将它们存储在最后一个位置（1,4,9），然后计算4和1之间的差，我们将它们存储在第二个位置（1、3、9）。解码则相反，从数组头部开始，差分解码以递增的顺序进行。从1,3,9开始，我们首先将1和3相加，我们将其存储在第二个位置（1,4,9），然后将4和9相加，我们将其存储在最后一个位置（1,4,13）。我们的实现需要两次遍历：一次通过其压缩格式重建增量，另一次通过计算前缀和（第6.2节）。为了提高数据的局部性并减少高速缓存未命中，将包含超过$2^{16}$个整数$（2^{16}×4B = 256KB）$的数组分解为较小的数组，并分别对每个数组进行解压缩。使用综合数据进行的实验表明，通过分解数组来高速缓存命中，可以在不降低压缩效率的情况下，对某些方案的解码速度进行近乎显着的改善。

4. 快速位解包

位打包是在$[0,2^ b）$中使用每个b位对小整数进行编码的过程，b可以是任意的，而不仅仅是8,16,32或64。每个数字都是使用正好是b 位写入的。固定大小为b的位接在一起成为一个位串，该位串可以跨越多个32位字。如果某个整数太小而无法使用所有b 位，则将其填充为零。

诸如C和C ++之类的语言支持通过位字段进行位打包的概念。图3给出了两个具有位字段的C / C ++结构的示例  。本示例中的每个结构都存储八个小整数。结构Fields4_8使用4位/整数（b = 4），而结构Fields5_8使用5位/整数（b = 5）。

图3. 在C / C ++中，两个结构体有8个整数。左面中的整数使用4位字段，而右面中的整数使用5位字段。

假设这些结构中的位字段紧凑地存储，即没有间隙，并且保留了位字段的顺序，则将八个整数存储在内存中，如图4所示  。如果未使用任何位，则它们的值可以是任意的。图4左面的所有小整数正好是32位字。但是右侧整数需要两个32位字，其中24位仍未使用（这些位可以是任意的）。 第七个整数的字段越过32位的边界：前2位使用第一个单词的30-31位，而其余3位使用第二个单词的0-2位。
图 4.

不幸的是，语言的实现没有要求确保数据全部打包，例如，C语言规范指是将不合适的位字段放入下一单元或者相邻单元重叠。最重要的是，他们不必提供最佳快速的装箱和拆箱程序。 因此，我们按照Zukowski等人的建议使用自己的程序实现了位打包和拆包。在图5中，我们假定这些字段的布局如图4所示，给出了此类过程的C / C ++实现，打包过程可以类似地实现，为简化说明起见我们省略了它们。

图5.通过两个过程来解包八个位打包的整数。 程序unpack4_8适用于b = 4，而程序unpack5_8适用于b = 5。1. 整数紧密堆积，即没有间隙。2.打包表示使用整个32位字，未使用位的值未定义。

在某些情况下，即使某些整数大于$2^b-1$（第2.8节），我们也使用位打包。实际上我们只打包 这些整数的前b位，这可以通过对每个整数与掩码$2^b-1$的逐位逻辑和运算来实现。这些额外的步骤减慢了位打包的速度（第6.3节）。

unpack4_8解码八个4位整数的过程中，由于这些整数紧密包装在一起，因此它们仅占据一个32位字。假设此字已经加载到寄存器中，则最多可以使用四个简单的操作（移位，掩码，存储和指针增量）提取每个整数。，因为它不涉及任何分支所以拆包很有效。

unpack5_8解码八个5位整数的情况稍微复杂，因为压缩表示形式使用两个单词，第七个整数的字段越过单词边界。此整数的前(低)两个位存储在第一个字中，而其余三个位存储在第二个字中。解码不涉及任何分支，并且大多数整数是使用四个简单的操作提取的。

unpack4_8和unpack5_8只是示例。每个位宽度(不仅是4和5)都需要单独的过程。

unpack4_8和unpack5_8解码在标量32位值上进行，提高解码的性能的有效方法是向量化。考虑图5中的清单，并假设in和out是指向m组元素向量的指针，而不是标量。假设标量运算符（移位，赋值和按位逻辑运算）已向量化。对所有m组向量元素同时进行逐位移位。 然后一次对unpack5_8或unpack4_8的调用将解码m×8而不是仅解码八个整数。

最近x86处理器已经SIMD上的四个32位整数向量进行操作的指令（m= 4）。我们可以使用这些指令来达到更好的解码速度。 图[6]给出了b = 5的 向量化数据布局。整数以循环方式在4个32位字的序列中划分。当一系列四个字溢出时，数据将溢出到下一个32位整数系列中。在此示例中，前24个整数存储在前四个字中，整数25–28的一部分在第一个字系列中，另一部分在第二个字系列中，其余的整数29–32存储在第二个字系列中图[6]的第二行 。注：32位称为一个字(原文用word)。

图6

可以使用unpack5_8的向量化版本来处理这些数据，该过程是通过用相应的SIMD指令替换标量运算获得。借助Microsoft，Intel或GNU GCC编译器，我们几乎可以通过将每个C运算符替换为等效的SSE2内在函数，从标量过程转换为矢量化过程：

• 按位逻辑和（＆）变为_mm_and_si128
• 右移（>>）变为_mm_srli_epi32
• 左移（<<）变为_mm_slli_epi32

图7.

将图5的过程unpack5_8与图7的过程SIMDunpack5_8进行比较内在函数的作用与C运算符相同。除了它操作4个整数的向量而不是单个整数。例如，函数_mm_srli_epi32一次移位四个整数。函数_mm_load_si128和_mm_store_si128数据从内存加载寄存器和将寄存器的内容写入内存，函数_mm_set1_epi32创建一个由四个整数组成的向量，该向量用一个整数初始化（例如31变为31,31,31,31）。

在向量化过程的开始，指针指向图6中第1行中显示的第一个128位数据块，第一个移位和掩码操作一次提取了四个小整数。 然后使用单个128位SIMD存储操作将这些整数写入目标缓冲区。 重复移位和掩码操作，直到我们提取前24个数字和整数25-28的前两位。 此时增加指针，并将下一个128位块加载到寄存器中。 使用附加的掩码操作，它将提取整数25-28的剩余3位。 这些位与已经获得的前2个位组合（对于每个25-28中的整数）。 最后我们存储整数25-28，并通过提取数字29-32完成对第二个128位块的处理。

我们的向量化数据布局是交错的。也就是说，前四个整数（图6中的Int 1，Int 2，Int 3和Int 4）被打包到四个不同的32位字。第一个整数紧邻第五个整数（Int 5）。 Schlegel等被称之为垂直模型。同样我们可以将整数按顺序打包的，比如Int1,Int 2,Int3和Int4存储在同一32位字中。 Schlegel等称之为水平模型，由Willhalm等人使用。在他们的方案中，解码依赖于SSSE3混选操作指令pshufb（例如varint-G8IU）。 在确定该块中整数的位宽b之后，一个解码操作通常包括以下步骤：

1. 将数据加载到源16字节缓冲区中（此步骤可能需要16字节对齐）。

2. 在目标缓冲区的四个32位字中分配三或四个存储在源缓冲区中的整数。 图8（针对5位整数）说明了此步骤，该步骤需要加载混选掩码。 请注意与varint-G8IU不同，源缓冲区中的整数不一定按字节边界对齐（除非b为8,16或32）。 因此在随机操作之后，复制目标缓冲区的整数可能未在32位字的边界上对齐，并且32位字可能包含一些额外的位，这些位不属于感兴趣的整数 。

3. 对齐整数可能需要向右移动几个整数，由于x86平台当前缺少具有四个不同移位量的SIMD移位，

   这一步是通过两个操作来模拟的：使用SSE4.1指令集将SIMD乘以四个不同的整数，然后进行向量化右移。

4. 不感兴趣整数的位归零。这需要进行掩码操作。

5. 存储目标缓冲区。

图8.同时解码存储在水平布局中的四个5位整数的步骤（与图6的垂直数据布局相反）。使用混选操作pshufb将这些整数复制到四个32位字中。源缓冲区和目标缓冲区中的位置由箭头指示。曲线线用于表示跨源缓冲区中字节边界的整数。因此，它们仅被部分复制。粗体零值表示由混选指令清零的字节。请注意某些源字节已复制到多个位置。

总体而言，Willhalm 等的水平位打包需要SSE4.1，而使用垂直布局的有效位打包仅需要SSE2。

我们在第6.3节中比较了实验中的垂直和水平位打包。

5. 新方案：SIMD‐FASTPFOR，FASTPFOR和SIMPLEPFOR

Patched 将压缩数组分解成页，页会分成128个整数的小块。原始的Patched方案（PFOR）以每页为单位存储异常值，而新的替代方案NewPFD和OptPFD以每块为基础存储异常（表3）。同样PFOR为整个页面选择单个位宽，而NewPFD和OptPFD可以为每个块选择单独的位宽。

最终结果是NewPFD的压缩率比PFOR更好，但PFOR的压缩比NewPFD快。我们希望一种与NewPFD一样压缩率的方案，但要具有PFOR的速度。为此我们提出了两个新方案：FastPFOR和SimplePFOR。 FastPFOR和SimplePFOR不会以每块为单位压缩异常，而是以每页为基础存储异常，这与PFOR相似，并且像NewPFD和OptPFD，它们为每个块选择一个新的位宽。

为了解释FastPFOR和SimplePFOR，我们考虑一个示例。 为了简单起见，我们仅使用16个整数进行编码。 这些数字用二进制表示为：

10, 10, 1, 10, 100110, 10, 1, 11, 10, 100000, 10, 110100, 10, 11, 11, 1.

这些整数最大位数为6。因此，我们可以使用6位/int加上一些额外的信息来存储全部数据。但是按照Patched编码的思想，允许例外可能会做得更好。假设我们使用一个字节存储任何异常的位置，在我们的实现中，我们使用128个整数的块，因此这不是浪费的选择。

因此实际选择的b一定小于等于6，也就是说如果一个整数的位数大于b，则我们需要额外存储$6 −  b$位作为异常，而不是$32 - b$。我们建议使用最大位宽度和b的差来估计存储异常的成本。这是一种启发式方法。因为我们使用8位存储异常位置，所以我们估计存储每个异常的成本为$8 +（6 - b）= 14-b$ 位。我们要选择b使得$b ×16 +（14 −  b）×  c$最小，在我们的实现中，我们存储128个整数的块，因此公式为$b ×128 +（14 −  b）×  c）$。

在给定的整数块中，我们仍然需要根据位宽b计算异常数c。我们也建立一个直方图，告诉我们给定位宽有多少个整数。 在软件中，可以将其实现为33个整数的数组：每个整数从0到32的一个整数。 创建直方图需要计算每个要编码的整数对数$log_2(x + 1)$。从该直方图中，我们只需尝试每个可能的b值，就可以快速确定使期望存储量最小的b值。从我们的数据来看，我们有3个整数使用1个位，10个整数使用2个位，而3个整数使用6个位。如果我们将b = 1，则异常数c = 13；对于b = 2，则c = 3；对于b = 6，c = 0。相应的成本$（b×16 +（14-b）×c）$为185,68和96。在这种情况下，我们选择b = 2，因此我们有三个异常（100110,100000,110100）。

压缩页以32位整数开头。最初32位整数未初始化我们稍后再返回。 接下来我们首先存储值本身，异常值只能存储低b位。 在我们的示例中，与该块相对应的数据是

10, 10, 1, 10, 10, 10, 1, 11, 10, 00, 10, 00, 10, 11, 11, 1.

这些整数的值被连续存储，一个块接另一个块（图9）。不同的块可能使用不同的b值，但是由于128×b总是可以被32整除，因此给定块的数据部分可以存储在32位对齐的内存地址中。

图9.SimplePFOR和FastPFOR方案压缩页的布局。我们只给出一个16整数块的数字，但一个页包含数百个块。 每个页面的开头包含每个块的数据。然后是包含元数据的字节数组。在页的最后，我们以压缩形式存储异常值。

在压缩页的编码过程中，我们写入一个临时字节数组。字节数组包含不同类型的信息。对于每个块，我们存储为每个分配的位数即b，以及最大数的位数。 如果最大位数大于b，则我们存储一个指示异常数的计数器c。我们还将异常数的位置在[0,127]中存储为整数。与诸如NewPFD或OptPFD之类的方案相比，我们不尝试压缩这些数字，而只是简单地使用一个字节存储它们。当页的所有整数均已处理并进行位打包后，临时字节数组将在压缩块之后存储，并在其前面写入该字节数组的长度占32位，并且我们用零填充字节数组，以便字节数可被4整除（允许32位内存对齐）。然后我们返回到压缩页的开头，在该处我们留下了一个未初始化的32位整数，并在其中写入了字节数组在压缩页内的偏移量。这确保了在解码期间我们可以立即定位字节数组。

在我们的示例中，我们使用b = 2分别写入16个整数占用4 bytes。 在字节数组中，我们存储以下内容：

1. 使用一个字节保存为每个整数分配的位数b = 2；
2. 使用一个字节保存最大位宽6；
3. 异常数c = 3使用1 byte；
4. 异常的位置（4,9,11），每个使用1byte。

因此对于此块，我们使用3 + 4 + 3 = 10字节

最后我们必须存储每个异常的高4位（6-b）：1001、1000和1101。它们存储在字节数组之后。由于字节数组的偏移量在页的开头，并且由于字节数组存储其自身的长度，因此我们可以在解码期间快速定位异常。 异常以压缩形式每页存储。 这与诸如OptPFD和NewPFD之类的方案相反，后者以每个块为单位存储异常，并与异常数据交织。

SimplePFOR和FastPFOR在压缩异常值的高位方式上有所不同：

• 在SimplePFOR方案中，我们将所有这些值（如1001、1000、1101等）收集到一个32位数组中，然后使用Simple-8b对其进行压缩。每个压缩页面仅使用一次Simple-8b压缩。

• 在FastPFOR方案中，我们将异常存储在32个数组之一中，每个可能的位宽从1到32的一个。在对块进行编码时，最大位宽与b之差决定了将异常存储在哪个数组中。然后使用相应的位宽对32个数组中的每个数组进行位打包。并对数组进行填充以使它们的长度是32的倍数。

  在我们的示例中，对应于异常的高位（1001,1000,1101）的三个值将存储在第四个数组中，并使用4个位/值打包。

  实践中我们将32个数组存储如下，我们从一个32位的bitset开始，该bitset的每个位对应一个数组，如果数组不为空，则该位设置为true，否则为false。然后将按顺序存储所有非空位打包数组。每个位打包的数组前面都有一个32位计数器指示其长度。

在所有其他方面，SimplePFOR和FastPFOR是相同的。

即使它们是为提高速度而设计的，这些方案仍可提供不错的压缩效果。假设我们可以仅使用4个位来压缩示例中三个异常的最高位（1001,1000,1101）。仅对于此块我们就使用32位的块数据，字节数组中的48位的位加上12位的异常值。总共为92位来存储16个整数，达到5.75bit/ int。这比以最大整数的位宽(6)存储更好。在我们的实现中，我们使用128个整数的块而不是16可以达到更好的效果。

在解码期间，首先对异常进行批量解码。为了确保我们不会占用过多的CPU缓存，我们以$2^{16}$个整数的页处理。然后我们解压整数并在每个块的基础上应用修补。异常位置不需要任何特定的解码，它们逐字节读取。

尽管SimplePFOR和FastPFOR在设计上与NewPFD和OptPFD类似，但我们发现它们提供了更好的编码和解码速度。在我们的测试（第6节）中，FastPFOR和SimplePFOR编码整数的速度大约是NewPFD的两倍。这表明批量压缩异常的速度更快。

我们还设计了一种新方案SIMD-FastPFOR，它与FastPFOR相同，除了它的打包依赖于向量化的位打包，用于整数块和异常值的高位。压缩率略有下降，原因有两个：

1. 填充32个异常数组，以便它们的长度是128的倍数，而不是32的倍数。
2. 我们在存储位打包数据之前插入一些填充，以便保留在128位边界上的对齐方式。

这种填充增加了大约0.3-0.4bits / int的开销（表5）。

6. 实验

我们实验的目的是评估最著名的整数编码方法。第6.4节中的第一个测试系列基于Anh和Moffat 23：ClusterData和Uniform首次提出的综合数据集。 它们的优点是可以快速实施，从而有助于重现性。 我们在6.5节中结果基于文本检索会议（TREC）集合ClueWeb09和GOV2的大型真实数据集。

6.1 硬件

我们在配备IntelCore®i7®2600（3.40GHz，L3CPU缓存8192KB）和16GB RAM的Linux服务器上进行了实验。在具有双通道的DDR-31333 RAM的传输速率为≈≈20,000MB / s或每秒5300mis的32位整数。 根据我们的测试，它可以使用C函数memcpy以2270mis的速率复制数组。

6.2软件

我们使用GNU GCC 4.7C ++实现了算法。使用优化标志‐O3。因为varint-G8IU方案需要SSSE3指令，所以我们必须添加标志mssse3。在编译我们的Willhalm等人的实现位解包时，我们必须使用标志msse4.1，因为它需要SSE4指令。我们的完整源代码可在线获得。

和Stepanov等一样， 我们基于挂钟时间和内存处理来计算速度。挂钟时间包括差分编码和解码所需的时间。在我们的测试过程中，我们不会在磁盘上检索或存储数据。当它们保存在磁盘上时，每秒不可能解码数十亿个整数。

包含超过$2^{16}$个整数（256KB）的数组被分解为较小的块。每个块被解码遍历两次。在第一遍中我们解压增量并使用32位字存储每个增量值。在第二遍中，我们对前缀总和进行就地计算。如第3节所述，这种方法极大地改善了数据局部性，并极大地提高了最快方案的解码速度。

我们对VSEncoding，NewPFD和OptPFD的实现基于Silvestri和Venturini 发布的软件。 他们报告说到已对OptPFD原始作者提供的实现进行了验证。我们实现了Stepanov等人的varint-G8IU和Anh和Moffat的Simple-8b。为最大程度地减少分支，我们使用C ++ switch case 实现了Simple-8b，为每个选择器值使用一个函数而不是单个函数，，因为循环展开可消除分支，Anh和Moffat[将这种优化称为批量拆包。我们还实现了Zukowski等人的原始PFOR方案，以及Zhang等人的后续产品PFOR2008.Zukowski在PFOR和PFOR-Delta之间进行了区分：我们有效地使用FOR-Delta，因为我们将PFOR应用于增量。

只要我们不跨越64字节的缓存行，最近的Intel处理器上读写未对齐数据的速度就可以与读写对齐的数据一样快。但是当使用常规二进制打包时，我们仍然希望在32位边界上对齐数据。 每个由32位打包整数组成的块的前面都应有一个描述符，该描述符存储该块中整数的位宽（b）。 块使用的位数始终可以被32整除。因此为了使块在32位边界上对齐，我们将块和相应的描述符分组为元块，每个元块包含四个连续的块。 一个元块之前是一个32位描述符，该描述符组合了4位宽度b（8位/宽度）。 我们将此方案称为BP32。 我们还尝试了使用较少整数（8个整数和16个整数）的二进制压缩版本。 由于这些版本较慢，因此我们在实验中将其省略。

我们还实现了基于128个整数的块上进行向量化二进制打包，以下称为SIMD-BP128。与常规二进制打包相似，使用向量化二进制打包时，我们希望使块在128位边界上对齐。 为此我们将16个块2048个整数分组为元块。像在BP32中一样，元块的编码表示形式之前是一个128位的描述符字保存位宽（8 bits / fwidth）。

总而言之，我们的二进制打包方案的格式如下：

• SIMD-BP128组合了16个128整数的块，而BP32组合了4个32整数的块。
• SIMD-BP128采用垂直向量化位打包，而BP32则依赖第4节中所述的常规位打包。

诸如BP32和SIMD-BP128之类的许多方案都要求在编码过程中计算整数对数。 如果天真地执行此步骤，则将占用大部分运行时间：整数对数的计算比诸如移位或加法之类的快速运算要慢。我们发现最好在x86平台上使用位扫描反向（bsr）汇编指令（因为只要x> 0，它相当于$log_2(x + 1)− 1)$。

对于二进制打包方案，我们必须在编码过程中确定整数的最大对数$max_i(log_2(x_i + 1))$。我们不在每个整数上计算一个对数，而是所有整数进行按位逻辑运算，然后计算结果的整数对数。由于以下等式，此快捷方式是可能的：$max_i(log_2(xi + 1))=log_2(∨i(xi + 1))$其中∨指的是按位逻辑或。

还有一些方案将数据压缩为固定长度的块（如128个整数），如Zhang等人所述，我们使用变量字节压缩其余部分。在我们的测试中，大多测试数组都比块长度大，因此替换可变字节的方案几乎没有差别。

报告速度以32位为单位。Stepanov等报告其最佳方案varint-G8IU在TREC GOV2数据集的速度为1059mis。我们获得了类似的速度（1300mis）。

VSEncoding，FastPFOR和SimplePFOR在压缩和解压缩期间使用与数组大小成比例的缓冲区。VSEncoding使用超过256KB的持久缓冲区，我们使用略大于64KB的持久缓冲区实现了SIMD-FastPFOR，FastPFOR和SimplePFOR。PFOR，PFOR2008，NewPFD和OptPFD是使用与块大小成比例的持久性缓冲区，每种方案使用的持久性缓冲区内存少于512KB。 PFOR和PFOR2008都使用216个整数或256KB的页面。在压缩期间，PFOR，PFOR2008，SIMD-FastPFOR，FastPFOR和SimplePFOR使用缓冲区存储异常。这些缓冲区受页面大小的限制，并且在对数组进行解码或编码后会立即释放它们。

VSEncoding在实现位解包过程中通过汇编使用了一些SSE2指令。Varint-G8IU通过SIMD内在函数明确使用了SSSE3指令，而SIMD-FastPFOR和SIMD-BP128类似地使用SSE2固有功能。尽管我们测试了所有方案的向量化差分编码，但我们仅报告了明确使用SIMD指令（SIMD-FastPFOR，SIMD-BP128和varint-G8IU）的方案的结果。为确保快速向量处理，我们将所有初始指针对齐16字节边界。

6.3 计算位打包

正如Zukowski等人最初提出的，我们使用手动调整的函数实现了位打包。给定位宽b，将K个无符号32位整数序列编码到$Kb∕32$个整数。 在我们的测试中，常规版本使用K = 32，向量化版本使用K = 128。

图10展示了使用32个整数块来打包和解包整数的速度。在一些方案中，已知所有整数均不大于$2^b -1$，而在Patched方案中则存在异常，即大于或等于$2^b-1$的整数。在后一种情况下，我们通过应用掩码强制整数小于$2^b$。此操作会减慢压缩速度。

图10.用于位打包和拆包的墙上时钟速度，单位每秒数百万个整数。我们使用小型数组(256KB)来最大程度地减少缓存丢失。当按照patched方案的要求打包不一定适合b位的整数时，我们必须应用一个掩码操作，该操作会使打包速度降低多达30％。(a)优化但可移植的C ++；(b)使用SSE2指令向量化；©向量化/非向量化比。

当位数很少时，我们可以更快地打包和解包，因为需要从RAM检索的数据更少。当位宽度为4,8,16,24或32时，我们可以更快地打包和解包。尤其是位宽度为8和16的打包和解包特别快。

如在图10(b)所示，向量化版本的速度大约是标量版本的两倍。我们可以以6000mis的速率解压缩位宽为8或更小的整数。但是，它带有隐式约束即整数必须以至少128个整数的块进行打包和解包。当位宽为8或16时，打包会稍微快一点。

在图10（b）中，我们报告了Willhalm等人（第4节）描述的使用水平数据布局时的拆包速度。当位宽在16到26之间时，垂直和水平技术的速度相同。对于较小的位宽（<8）或较大的位（bit> 27），我们的基于垂直布局的方法更可取，因为它的速度提高了70％。因此我们所有整数编码方案都是使用垂直布局来实现的。

我们还尝试了打包较少的整数（K = 8或K = 16）的情况。但是它比较慢，并且有几位未使用((Kb ∕32)32-Kb）。

6.4 综合数据集

我们使用了Anh和Moffat 的ClusterData和Uniform模型。这些模型会生成一组不同的整数，我们将这些整数按排序顺序保留。在Uniform模型中，整数遵循均匀分布，而在ClusterData模型中，整数值倾向于聚类。也就是说，我们更有可能具有相似值的长序列。ClusterData模型的目标是模拟实际中遇到的更实际的数据。我们期望从ClusterData模型获得的数据更具可压缩性。

我们使用ClusterData和Uniform模型生成了$[0,2^{29}）$范围内的随机整数数据集。在第一遍中，我们生成了$2^{10}$个 短数组， 每个数组包含$2^{15}$个整数。因此数组内连续整数之间的平均差为$2^{29-15} = 2^{14}$。我们希望压缩后的数据至少使用14bits / int。在第二遍中，我们生成了一个由$2^{25}$个 整数组成的长数组。在这种情况下，连续整数之间的平均距离为$2 ^4$：我们期望压缩数据至少使用4bits / int。

结果在表4中给出，名称带有⋆的方案，例如SIMD‐FastPFOR⋆，使用向量化差分编码。 在短数组中，我们看到的压缩很少。 可变字节和更节省空间的替代方法FastPFOR之间的压缩效率差异也相对较小。但是速度差异很大，解码速度范围从可变字节的220mis到SIMD-BP128的2500mis。

表4.综合数据集每秒的编码和解码速度，以百万个整数为单位，以及每个32位整数的位数， 结果用两位有效数字给出。 名称为⋆的方案使用向量化差分编码。

	(a) ClusterData: short arrays			(b) Uniform: short arrays
Coding	Decoding	Bits/int	Bits/int	Coding	Decoding	Bits/int
SIMD‐BP128⋆	1700	2500	17	1600	2000	18
SIMD‐FastPFOR⋆	380	2000	16	360	1800	18
SIMD‐BP128	1000	1800	16	1100	1600	17
SIMD‐FastPFOR	300	1400	15	330	1400	16
PFOR	350	1200	18	370	1400	17
PFOR2008	280	1200	18	280	1400	17
SimplePFOR	300	1100	15	330	1200	16
FastPFOR	300	1100	15	330	1200	16
BP32	790	1100	15	840	1200	17
NewPFD	66	1100	16	64	1300	17
varint‐G8IU⋆	160	910	23	140	650	25
varint‐G8IU	150	860	18	170	870	18
VSEncoding	10	720	16	10	690	18
Simple‐8b	260	690	16	260	540	18
OptPFD	5.1	660	15	4.6	1100	17
Variable byte	300	270	17	240	220	19

	© ClusterData: long arrays			(d) Uniform: long arrays
Coding	Decoding	Bits/int	Bits/int	Coding	Decoding	Bits/int
SIMD‐BP128⋆	1800	2800	7.0	1900	2600	8.0
SIMD‐FastPFOR⋆	440	2400	6.8	380	2200	7.6
SIMD‐BP128	1100	1900	6.0	1100	1800	7.0
SIMD‐FastPFOR	320	1600	5.4	340	1600	6.4
varint‐G8IU⋆	270	1600	9.1	270	1600	9.0
PFOR	360	1300	6.1	360	1300	7.3
PFOR2008	280	1300	6.1	280	1300	7.3
BP32	840	1300	5.8	810	1200	6.7
FastPFOR	320	1200	5.4	330	1200	6.3
SimplePFOR	320	1200	5.3	330	1200	6.3
varint‐G8IU	230	1300	9.0	230	1300	9.0
NewPFD	120	970	5.5	110	1000	6.5
Simple‐8b	360	890	5.6	370	940	6.4
VSEncoding	9.8	790	6.4	9.9	790	7.2
OptPFD	17	750	5.4	15	740	6.2
Variable byte	880	830	8.1	930	860	8.0

对于长数组，压缩率之间存在较大差异。 压缩率最佳的方案是SIMD-FastPFOR，FastPFOR，SimplePFOR，Simple-8b和OptPFD。 其中就解码速度而言，SIMD-FastPFOR无疑是赢家。 OptPFD的良好压缩比是有代价的，它具有最差的编码速度之一。 实际上它在编码过程中比SIMD-FastPFOR慢20-50倍。

尽管它们在实现上有显着差异，但是FastPFOR，SimplePFOR和SIMD-FastPFOR具有同样好的压缩率。 这三种方案的解码速度都差不多，但是SIMD-FastPFOR解码整数的速度比FastPFOR和SimplePFOR快得多。

通常编码速度会有很大差异，但是二进制打包方案是最快的，尤其是对它们进行向量化处理时。 更好的实现可能有助于缩小这一差距。

使用向量化差分编码的SIMD-BP128版本（SIMD-BP128⋆）在解码期间始终比任何其他替代方案快400 毫秒。尽管它并不总是提供最佳的压缩率，但始终与可变字节的压缩率匹配。

使用向量化差分编码和常规差分编码之间的差异可能高达2位/整数。但是通常差异小于2位。例如，SIMD-BP128 ⋆当SIMD-BP128相比仅使用约每整一个额外的位。二进制打包的成本由一个块中的最大增量决定，将δ的平均大小增加四倍不一定会导致预期的最大整数增加四倍（以128个δ为一组）。

与我们的新方案相比，varint-G8IU的性能令人印象深刻。但是varint-G8IU比可变字节快60％，同时提供类似的压缩效率。尽管Simple-8b的压缩效率更高，但它也比Simple-8b更快。向量差分编码varint-G8IU版本⋆与普通版本varint-G8IU相比，短数组压缩较差。但是在长数组，varint-G8IU ⋆是更快（从1300个MIS到1600个MIS），而压缩率一样。

PFOR和PFOR2008之间没有什么区别，只是PFOR提供了明显更快的编码速度。在从文献中获取的所有方案中，PFOR和PFOR2008在这些测试中具有最佳的解码速度，它们对所有块使用单个位宽，在压缩开始时确定一次。但是它们在所有指标（编码速度，解码速度和压缩率）中都由SIMD-BP128和SIMD-FastPFOR主导。

为了进行比较，我们测试了Google Snappy（版本1.0.5）作为增量压缩技术。Google Snappy是Google内部在其数据库引擎免费使用的库。我们认为，它与其他快速通用压缩库如zlib或LZO更具有竞争力。对于较短的ClusterData阵列，我们获得了340mis的解码速度，几乎没有压缩（29bits/int）。对于长的ClusterData数组，我们获得了200mis和14bits / int的解码效果。总体而言，Google Snappy的压缩率约为SIMD-BP128⋆的一半，而速度却慢了一个数量级。

7 讨论

我们发现二进制打包既快速又节省空间。向量化二进制打包（SIMD-BP128⋆）是我们最快的方案。尽管与Simple-8b相比，它的压缩效率较低，但在解码过程中它的速度要快三倍以上。此外在最坏的情况下，较慢的二进制打包方案（BP32）与具有最佳压缩率（OptPFD）的修补方案相比，仅产生约1.2位/整数的成本，而解码速度几乎与最快的修补方案PFOR一样。

但是只有极少数的作者在最近的文献中考虑了二进制打包方案或其向量化变体：

• Delbru 等[报告了类似于BP32的二进制打包方案，取得了良好的结果。在他们的实验中，它超越了Simple-8b以及修补方案PFOR2008。

• Anh和Moffat也使用二进制打包方案取得不错的结果，在他们的测试中，它的解码速度比Simple-8b或PFOR2008至少快50％。成本是他们的二进制打包方案压缩率较差。

• Schlegel 等提出了类似于SIMD-BP128的方案。该方案（称为ķ -gamma）采用了垂直数据布局来存储整数，比如我们SIMD-BP128和SIMD-FastPFOR方案。它本质上将二进制压缩应用于一小整数块（最多四个元素）。从我们的初步实验中，我们了解到在小组中解码整数效率不高。Schlegel 等人的结果也证明了这一点。它们的最快解码速度不包括写回RAM仅为1600mis（Core i7-920，2.67GHz）。

• Willhalm 等使用向量化二进制打包，例如我们的SIMD-BP128，但是使用了水平数据布局而不是我们的垂直布局。解码算法依赖于混选指令pshufb。我们的实验结果表明，基于垂直布局的方法可能是更好的选择（图10.(a))。在垂直布局上实现位拆包的实现有时比在水平布局上实现要快50％至70％。

  这种性能比较取决于我们软件的质量。然而，我们重新实现的速度与Willhalm 等人最初报告的速度相当[，他们报告了接近3300mis的速度，位宽为6。相比之下，使用我们的算法实现，对于相同的位宽，最新的CPU体系结构我们获得了高于4800mis的速度，而在更高的速度下，时钟速度提高了20％。

  Willhalm 等人描述的方法。在具有用于同时将几个值按不同的偏移量移位的指令（例如，vpsrld AVX2指令）的平台上，它可能更具竞争力。确实这必须通过乘以2的幂再乘以移位来模拟。

向量化的位打包方案非常有效，它们以4000-8500mis的速度编码/解码整数。因此增量和前缀和的计算可能成为主要瓶颈。可以通过对这些操作进行向量化来消除此瓶颈（尽管在本例中以较差的压缩比为代价）。我们在文献中还没有遇到过这种方法，也许是因为对于较慢的方案，前缀总和的计算只占总运行时间的一小部分。在我们的实现中，为了简化比较，我们将差分解码与数据解压缩分开了：在某些情况下，集成方法的速度可能快两倍。此外通过更好的向量化算法，我们也许可以提高解码速度和压缩率。数据差异可能还有其他选择。

在我们的结果中，二进制打包方案（SIMD-BP128）比原始打包编码方案（PFOR）在三个指标上都得到了优化。同样较新的快速修补方案NewPFD通常优于另一种二进制打包方案（BP32）。的确尽管在实际数据上NewPFD的压缩率高出6％，但NewPFD比BP32慢至少20％。如果我们停止在那里的研究，我们可能会得出结论，当解码速度是台式机处理器的最重要特征时，修补编码不是可行的解决方案。但是我们设计了一种新的向量化修补方案SIMD-FastPFOR。它表明如果使用SIMD指令，修补程序仍然是富有成效的策略。确实它比基于SIMD的varint-G8IU更快，同时提供了更好的压缩率（至少35％）。在真实数据上，SIMD-FastPFOR在两个关键指标上优于BP32：解码速度和压缩率。

将来，我们可能期望由商用CPU支持的SIMD操作的种类以及内存速度的增加。这些未来的改进可以使我们的向量化方案比标量方案更快。但是这些增加意味着最块大小的增加。当我们增加二进制打包中的块的大小时，如果存在异常值，也会使它们的空间效率降低。考虑到BP32比SIMD-BP128在空间效率上要高得多。

值得庆幸的是，大块的离群值问题可以通过修补来解决。的确即使OptPFD使用与SIMD-BP128相同的块大小，也可以提供更好的压缩效果。因此对于能够处理更大向量的未来计算机而言，修补方案可能比当前计算机更有用。

尽管我们的工作集中在解码速度上，但仍有望以压缩形式直接处理数据，理想情况下是使用向量化。我们期望在概念上更简单的方案SIMD-BP128可能会比相对复杂的方案SIMD-FastPFOR具有优势。

许多最快的方案都使用相对较大的块（128个整数），这些块可一次全部解码。但是并非所有查询都需要解码整个数组。
例如考虑排序数组之间的交点的计算。 有时使用随机访问会更有效，尤其是在处理长度差异很大的数组时。如果数据存储在相对较大的压缩块中，随机访问的粒度可能会降低。因此我们可能最终不得不扫描比所需更多的整数。 但是由128个整数组成的块可能不一定会妨碍良好的性能。 实际上Schlegel等人使用最多65536整数的块进行向量化，从而将相交的计算速度提高了五倍。

8 结论

我们提供了新的方案，其速度是文献中以前最好的方案的两倍，同时提供了竞争性的压缩率和编码速度。几乎所有步骤包括差分解码都是通过的矢量化实现的。为了实现高速压缩比和竞争压缩比，我们引入了一种新的修补方案SIMD-FastPFOR，该方案以允许向量化的方式存储异常。

将来，我们可能会寻求在更多不同的体系结构上推广我们的结果，并在速度和压缩比之间进行更大范围的权衡。实际上大多数商用处理器都支持向量化处理（例如Intel，AMD，PowerPC，ARM）。我们可能还想考虑自适应方案，这些方案在数据更可压缩时会更主动地进行压缩，否则会针对速度进行优化。例如对于压缩率较低的数组，可以使用varint-G8IU这样的方案，对于压缩率较高的阵列，可以使用SIMD-BP128这样的方案。还可以使用工作负载感知的压缩，可以优化频繁访问数组以提高解码速度，从而可以优化最不频繁访问的数据以提高压缩效率。最后，我们应该考虑的不仅仅是32位整数。例如，一些流行的搜索引擎如支持64位文档标识符。我们可能会考虑一种类似于Schlegel等人的方法将32位整数块分解为16位整数块。

译者注：由于第6.5节中大幅用来评估真测试实环境的数据，本文省略掉这一部分，但不影响阅读以及理解。最后由于水平有限，如发现任何纰漏，还望指出。

原文链接：https://onlinelibrary.wiley.com/doi/full/10.1002/spe.2203#spe2203-fig-0005