PivCo-Huffman “合并”操作

# PivCo-Huffman “合并”操作 来源：https://fgiesen.wordpress.com/2026/06/21/pivco-huffman-merge-operations/ 有一篇新论文《PivCo-Huffman》（https://arxiv.org/abs/2606.05765）[带注释的HTML版本见此处 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html)]，非常有趣。传统的霍夫曼解码（以及程度稍低的编码）本质上是高度串行的。我们可以通过使用多流（https://fgiesen.wordpress.com/2021/08/30/entropy-coding-in-oodle-data-huffman-coding/）来获得显式的并行性，这在中等数量的流（如4-8个）中通常没有问题。但这种方式不太适合向量化或像GPU这样的宽向量机器：每增加一个流都会在比特流中增加信令开销，而且同时从多个流解码是一种高能耗的收集操作。GPU可以处理收集（尽管分散的数据访问仍然比紧凑的内存访问模式消耗更多周期），但大多数其他设备对极度依赖收集的模式非常不满意。尤其是我们通常的基于表的解码器会立即随之进行另一次收集，尽管这部分更容易修复：规范哈夫曼编码（https://en.wikipedia.org/wiki/Cannonical_Huffman_code）容易实现无表解码（至少对于关键的“长度确定”部分），如果需要的话。这些方法在标量单次解码器中并不特别吸引人，因为单次加载非常便宜；但如果你在处理32宽的向量，做一堆整数运算来节省一次收集就更具吸引力了。 你也可以使用ANS式交织（https://arxiv.org/abs/1402.3392）将许多逻辑比特流转换为单个物理比特流。这正是 GDeflate（https://docs.nvidia.com/cuda/nvcomp/gdeflate.html）所做的，它得到一个具有更多潜在并行性且无需到处收集的比特流。交织解决了“跨内存读取”的问题，并在提供合适设施的GPU和CPU（例如AVX-512的“EXPAND”系列指令，或仅来自相同缓存行的快速收集）上表现出色，但在没有这类硬件支持时则很慢。它还迫使你在比特流定义中选择一个魔法数字（交织因子）。如果太低，像GPU这样的宽向量机器在解码时利用率会很低。如果太高，标量机器根本无法高效解码。更糟的是，适合AVX-512或GPU的数字范围有重叠，但大多数GPU甚至带有AVX-512的CPU能够获得不错利用率的最小交织流数量约为32，而标量或较窄向量机器（具有典型寄存器数量）能够舒适解码的最大数量约为8-16（具体取决于实现方式），介于16和32之间的区域则是一个谁都不满意的泪谷。这就是为什么除了GDeflate之外，这类比特流风格很少见的原因；它本质上依赖于你选择一个魔法数字，这个数字对每个实现都有巨大影响，同时又受到不断变化的硬件细节的影响。是的，NVIDIA GPU已经围绕32个“线程”（更像是SIMD通道）构建了相当长一段时间，每个寄存器32位；但AMD曾经偏爱64（直到几代前主要转向32），Intel GPU设计为8，一些移动GPU过去只做4，而4也是ARM NEON或x86上的SSE4.2所拥有的32位通道数，后来通过AVX2扩展到8。最后，ARM SVE和RISC-V V扩展将其留作实现定义，当模型是运行像SAXPY这样的简单向量数学内核时是一回事，但当物理向量宽度变成一个被固化在持久线格式中的魔法常数（可能持续数十年）时，则完全是另一回事。 关于“这非常串行”这一难题，最后一个主流的流行解决方案是完全暴力破解。从输入中取出大量比特。并行地，从比特0、比特1、比特2、比特3等位置开始解码。对许多连续的候选位置执行此操作。我说的是16个或更多。最终，我们发现从比特0开始的码长是6位。酷！这意味着我们丢弃了在比特偏移1到6处所做的工作，然后查看我们已经在比特6处预解码的码。这个码长是5位，所以我们丢弃了为比特7到10所做的推测工作，发现从比特11开始，另一个码长也是5位。恭喜，我们刚刚以16次工作的代价解码了3个值。这完全可行。信不信由你，如果需要每个周期输出多个值，这实际上是硬件解码此类顺序比特流的首选方法。尤其是使用规范码和不太长的长度限制时，这可以变得相当便宜。在最后追逐要输出的实际值序列是一个潜在的可扩展性问题，但一次3或4个还不算太坏；如果还不够，还有更好的算法来追踪这些链接，能提供更多并行性。简而言之，这是可以做到的，如果你构建专用硬件，效果不错，但你绝不想在通用硬件上用软件来做。我出于好奇实现过它，即使在GPU上，习惯性地丢弃超过80%的工作也不是快速代码的配方，更不用说试图在受功耗限制的电池供电设备上耍这种花招时浪费的能量了。 到目前为止，这就是我们的主要选择：我们可以顺序地一次解码一个，但这无法扩展。我们可以使用多个独立的比特流，理论上这能为我们提供类似线程级或可能指令级并行性，但并行度被固化在比特流中，并增加了一些开销（因为每个解码器线程需要知道从哪里开始）。它也不适合SIMD风格的实现，因为发散的内存访问模式让我们很不爽。我们可以使用交织的比特流，它们具有更好的内存访问局部性，原则上与SIMD和GPU架构很匹配，但需要我们在比特流规范时选择一个魔法数字，这个数字将永远限制我们能获得的解码器并行度，而且如果我们选择的数字足够高以耗尽某些目标硬件的寄存器，也会毁了我们的好日子。即使在同类设备（比如GPU）中，对于这个数字应该是什么也没有任何共识。最后，我们可以耸耸肩，极其挥霍，立即丢弃我们做过的大部分工作。这不是并行性，而是效率低下的并行性。 ### 进入PivCo Marcin Żukowski 的“Pivco-Huffman”则将其翻转。字面意义上的。为了直奔本篇文章的核心，我会快速过一遍，详情请参阅论文。具体来说，假设我们要编码字符串“abracadabra”。构建标准霍夫曼树（这是一个教科书算法，这里不解释）会得到类似这样的图： [ ](https://fgiesen.wordpress.com/wp-content/uploads/2026/06/hufftree-2.png) “abracadabra”的霍夫曼树 通常，为了编码任何符号，你从根开始，发送到达适当叶子需要经过的边的标签。在这个树中，“a”编码为“0”，“b”编码为“100”，“r”编码为“101”，依此类推。我们在继续下一个符号之前完整地发送每个符号。 PivCo-Huffman则概念性地一次性处理整个字符串，将其缓慢地向下推入树中。从根节点开始，我们看到每个包含“a”的位置发送“0”，其他所有位置发送“1”。将字符串对齐，我们可以看到根节点输出的比特： ``` abracadabra 01101010110 ``` 这些比特直接进入我们的输出比特流。根节点的左子树只是“a”叶子，因此每个发送0的位置实际上已经完成。但那些不是“a”的位置尚未完成。让我们找出这些位置以及它们下一步需要采取的步骤： ``` brcdbr 001100 ``` 这些是根节点右子节点输出的比特。一般来说，在每个内部节点，我们将到达此处的符号分区为两个较短的子序列：一个进入左子树，另一个进入右子树。在我们的例子中，继续向左的子序列是“brbr”，而右边的子序列只是“cd”。我们以这种方式进行前序树遍历，直到将所有符号推到叶子。注意，这与使用该树的常规霍夫曼编码发送的比特完全相同，只是顺序不同。 为了解码，我们需要知道比特流中编码了多少个符号，设为N。每个符号都必须经过根节点，因此我们知道根节点的比特串有N位。我们可以计算该比特串中0和1的数量，这告诉我们有多少符号进入左（0）和右（1）子树。然后，递归地，我们可以对这些节点做同样的事情。这让我们能够定位每个节点的比特在最终比特流中的位置，以及有多少符号经过它们。最后，在返回树的路上，既然我们有了子序列的长度，我们就可以在自底向上的合并过程中重建它们可能的内容。例如，取“b”和“r”叶子的父节点。我们知道有4个符号“经过那里”，相应的比特流是“0101”。这意味着在此子树中编码的符号子序列是“brbr”。它的兄弟节点只有两个比特“01”，编码了“cd”。它们的共同父节点是有6个符号的节点，发出我们之前看到的“001100”比特串。我们刚刚计算出，其左（“0”）子树编码的4个符号是“brbr”，右（“1”）子树编码的2个符号是“cd”。这意味着整个节点编码的符号是“brcdbr”。最后，我们继续向上推一层，合并a，就得到了“abracadabra”。 很好，但我们为什么要这样做？这看起来只是常规的霍夫曼编码，只不过是批处理模式外加了额外步骤。答案是，我们将霍夫曼编码转化为一系列顺序列表划分步骤，而将解码转化为一系列列表合并，其中我们不是进行比较，而是通过一个比特流告诉我们从两个列表中的哪一个取下一个元素。常规的霍夫曼*编码*并不那么糟糕，但解码正如上面讨论的那样，是一个极其串行的过程。而这类列表合并则不然：找出要从哪个列表取元素归结为前缀和，这虽然不是微不足道的，但却是我们可以做得很好的一类并行算法（扫描）的原型，并且它不需要比特流针对特定向量宽度（或类似指标）编写。它很容易根据目标机器的能力向上或向下扩展。还有许多其他可能的优化：例如，我展示的树中包含一个针对4个符号“b”、“r”、“c”和“d”的完全二叉树。当然，你*可以*将其编码（或解码）为一系列3个二进制列表划分（或解码器端的合并），但你也可以直接每个符号发送2位并完事。变长到固定字母表的解码（像霍夫曼那样）很棘手，但固定长度到固定字母表的子集则可以轻松并行化。如果我们不想扫描所有这些列表来计算有多少个“1”，我们可以为某些或全部霍夫曼树节点存储这些信息，花费额外的比特，但省去解码器扫描（可能数万比特）的工作。等等。 因此，虽然这个想法的基线标量实现并不有趣，但它正好位于可以很好映射到几乎任何数据并行基础设施的任务子集中——无论是GPU、任何类型的向量指令集，甚至只是线程——这使得它值得一试。并且论文中给出的数字很令人鼓舞，但有个主要警告：主要结果不出意外是在带有AVX-512的x86-64服务器或Apple Silicon CPU上获得的——即非常高端硬件。这对算法的未来是个好兆头，但线格式需要适用于所有人，而不仅仅是最高端目标。因此问题是：这些基本原语能有多便宜？在这篇文章中，我将特别关注自底向上解码器中的“合并”操作。 ### 合并操作 以下是在类Python伪代码中一次合并的样子： ``` def merge(l_list, r_list, bitstream): output = [] l_pos, r_pos = 0, 0 for bit in bitstream: if bit == 0: output.append(l_list[l_pos]) l_pos += 1 else: output.append(r_list[r_pos]) r_pos += 1 return output ``` 仅此而已。这就是我们要处理的。注意，该算法有一个不变式：`l_pos + r_pos` 等于已处理元素（以及已写入输出元素）的数量，因此实际上跟踪两者是多余的。其中一个隐含着另一个。并且 `r_pos` 是迄今为止遇到的所有 `bit` 值的（不包含）前缀和。如上所述，这基本上归结为并行编程101课程中的期中作业问题。这是一个*非常*简单的算法，这对我们来说是好事，因为我们确实需要速度快的东西，而当事情如此直接时，通常有很多不同的方式来实现，我们可以选择当前目标上效果最好的那种。但接下来我们需要比类Python更低层一点的东西。特别是，我们需要选择一些实际数据类型。在下面的内容中，我将假设我们要编码的符号是字节，这既实际相关，也与我之前关于该主题的文章一致。我们的比特流将以明显的方式按位打包。 与像AVX512_VBMI2这样的指令集最直接匹配，它提供了 VPEXPANDB (https://www.felixcloutier.com/x86/vpexpandb:vpexpandw)，这给我们一种字节级别的掩码加载操作，其中活跃的SIMD通道（对应掩码位为1）从连续地址加载，而非活跃通道要么保持不变，要么初始化为零，并且加载地址不会增加。它旨在将稀疏数据加载到向量寄存器中，基本上是我们所需内容的完美匹配。在下面的内容中，我不会使用官方的内联函数名称，因为如果你不习惯的话，这些符号相当吓人，但过程看起来像这样，从伪Python切换到伪C： ```c void merge(uint8* output, const uint8* l_list, const uint8* r_list, const uint8* bits, usize count) { // 以下代码片段都不会处理边界情况，例如最后几个元素，也不会进行任何边界检查。 // 真正的实现绝对需要做这些，但这是针对实际代码，而不是博客文章中的伪代码。你已收到警告。 // AVX-512 每次迭代可以处理64个字节！ for (usize i = 0; i < count; i += 64) { // 掩码中来自 r_list 的元素对应的位被设置（小端顺序自然是合适的） uint64 mask = read64LE(&bits[i / 8]); // 读取 l_list 条目 // 暂时将其他部分初始化为零 uint8x64 result = zero_masked_vexpandb_from_mem(l_list, ~mask); // 读取 r_list 条目 result = masked_vexpandb_from_mem(result, mask, r_list); // 将结果存储到输出缓冲区 vstore(&output[i], result); // 计算人口计数（1位的数量）...