简介本文关注的是一类常见但不容易高效向量化的问题：输入端可以按向量并行处理，但输出端具有不规则长度或稀疏有效性，需要将有效结果重新排列为连续内存流。COMPACT正是解决这类“稀疏向稠密转换”的关键原语之一。 COMPACT指令的工作机制 COMPACT是ARM SVE中的向量压缩指令，依据谓词寄存器将源向量中被选中的元素按原始顺序连续搬入目标向量的低位，未填充位置清零；其功能类似x86 AVX‑512的COMPRESS指令，常用于条件过滤、稀疏数据压缩、copy_if、向量化筛选等场景。COMPACT具备跨lane数据重排能力，被过滤的元素会影响后续有效元素的目标位置。 COMPACT意为“紧凑”，是ARM SVE中用于“向量压缩”的指令。它根据谓词寄存器中的有效位，将源向量中被选中的元素按原始顺序收集起来，连续放到目标向量的低位lane中，未被填充的位置通常清零。其作用类似于x86 AVX-512中的COMPRESS类指令，常用于条件过滤、稀疏数据压缩、copy_if、向量化筛选等场景。COMPACT Zd.X, Pg, Zn.X 图 1 COMPACT指令的工作机制 COMPACT以谓词寄存器Pg为掩码，对于Zn中由Pg激活的lane，将其整个lane移动到向量的低位，与其他激活的lane紧密排布。基础的SVE支持32bit和64bit元素，演进版本的SVE额外支持8bit和16bit。 COMPACT的一个重要的特点是：它不是普通的逐lane独立运算，而是具有跨lane数据重排能力。某个lane是否被保留，会影响后续所有有效元素最终落到哪个目标lane中。例如前面某个元素被过滤掉，后面的元素就会整体向低位移动。多数向量指令，元素的影响仅限于它所处的lane内部，而COMPACT可以在lane之间传递影响，在变长元素向量化的场景中有重要作用。与x86 COMPRESS的比较 ARM SVE COMPACT与x86 AVX‑512 COMPRESS在核心语义上相同，都是按掩码/谓词选取元素并压缩到低位连续位置。x86采用更指令中心化的设计，提供合并（merge）模式和直接写内存的输出模式，而ARM则倾向于模块化实现，可通过ext、CNT、predicated store等指令组合完成相同功能。尽管编码和编程模型不同，两者最终实现相同的压缩算法。与ARM SVE COMPACT类似，x86 AVX-512支持一批COMPRESS指令，从核心语义上看二者不存在本质差异，ARM SVE的COMPACT与x86 AVX-512的COMPRESS都提供了按谓词/掩码选择元素并压缩到低位连续位置的能力。但在具体ISA暴露的操作形式上，x86 AVX-512 COMPRESS更倾向于为常见操作提供直接的复合指令形式，设计上更加“指令中心化”。ARM SVE COMPACT则更强调与SVE的VLA模型和predicate机制协同使用，设计上更加“模块化”。 x86的指令如下。 ●vpcompress zmm1 \{k\}, zmm2 这条指令额外提供了高位填充元素的处理模式，ARM COMPACT会默认压缩结果的高位清零，而x86支持合并（merge）模式，允许未使用部分保留目标寄存器中的旧值。 ARM平台可以通过ext等指令进行组合操作来实现类似功能。 ●vpcompress [mem] \{k\}, zmm 这条指令额外提供了与内存交互的输出模式，ARM COMPACT会默认将结果存储到向量寄存器中，而x86允许生成的结果直接存储到内存之中。 ARM平台可以通过CNT指令、predicated store指令等方式完成类似的功能。尽管编码差异导致编程模型和最佳代码形态不同，但是COMPRESS与COMPACT最终都能实现相同的“压缩”算法逻辑。与ARM BEXT指令的比较 ARM SVE提供两种压缩指令：COMPACT和BEXT。COMPACT在lane之间进行元素级压缩，根据谓词掩码将活跃的整个元素整体移动到向量低位，具有全局状态依赖；BEXT在每个lane内部按位掩码提取比特并压缩到该lane的低位，各lane独立操作，属于无状态压缩。两者分别适用于跨lane元素筛选和单元素内部位选择的不同场景。除了面向向量元素（lane）进行压缩的COMPACT指令，ARM SVE还提供了一条在比特位（bit）层面进行压缩的指令——位提取（Bit Extract, BEXT）。两者虽同属“压缩”操作，但是作用层面与应用场景不同。BEXT Zd.X, Zn.X, Zm.X 图 1 BEXT执行位压缩操作 BEXT执行位压缩操作，它使用Zm作为位掩码，从源寄存器Zn的每个lane内部选出被激活的比特位，并将这些比特压缩到目标寄存器Zd同一lane的低位。相比之下，COMPACT指令实现的是跨lane元素压缩。它根据谓词寄存器（predicate）的掩码，将整个向量中活跃的整个元素筛选出来，并紧密地排列到向量的起始（低位）地址空间。特性 COMPACT（Lane级压缩） BEXT（Bit级压缩）压缩对象整个向量元素（如一个32位整数、一个浮点数）元素内部的各个比特位操作范围跨lane全局操作。一个lane的保留与否，会影响后续所有lane在结果向量中的最终位置。每个lane内部独立操作。lane 0的掩码和结果不会对lane 1产生任何影响。 BEXT（以及大多数其他向量指令）是“无状态”的，每个lane内部独立处理，lane 0的掩码值不会影响lane 1的结果。而COMPACT指令是“有状态”的，其压缩过程具有全局依赖性，一个lane是否被保留会影响后续所有lane的最终位置，如果lane 0被过滤掉，则后续所有lane的元素都会向低位移动。典型应用场景变长编码香农信源编码定理表明“高频符号用短码、低频符号用长码”的变长编码是逼近熵、实现高效压缩的必由之路，但在SIMD向量化中，各lane产生的变长输出字节长度不统一，导致难以连续写入缓冲区。COMPRESS指令通过将32bit元素重新解释为8bit向量并生成掩码，实现单指令压缩，、而使用COMPACT指令可以将变长的有效部分压缩到一起，可视为“predicate prefix sum + lane permutation”的融合，从而高效解决Varint等变长编码的输出紧凑化问题，相比标量串行存储或基于Kogge‑Stone前缀和的scatter方案更具性能优势。在信息论中，香农信源编码定理说明了依据符号出现概率赋予不同长度编码是逼近熵值H，实现高效压缩的必然途径。“高频符号用短码，低频符号用长码”的策略被广泛应用于霍夫曼编码、算术编码等各类变长编码。然而这类“变长”需求可能导致各并行通道生成的输出字节长度不统一，给SIMD向量化并行实现带来了巨大挑战。 COMPRESS指令在“变长编码”中可以作为一个很重要的数据紧凑化原语，高效解决变长压缩中经常出现的一个核心问题：每个lane产生的输出长度不固定，如何将变长输出数据连续写入输出缓冲区。本文以RPC Protobuf库使用的Varint编码为具体分析对象，其编码特性十分契合这一场景：以32位编码为例，去除5字节特殊处理后，编码结果可能为1/2/3/4字节，被存储在每个lane的低位。例如对下列这组数字编码：7、16383、624485、300、128、2097152、42、16384 使用向量化处理后各个lane中的元素可以编码为：00 00 00 07|00 00 7F FF|00 26 8E E5|00 00 02 AC|00 00 01 80|01 80 80 80|00 00 00 2A|00 01 80 80 而最终生成的编码结果应当为：07|7F FF|26 8E E5|02 AC|01 80|01 80 80 80|2A|01 80 80 如何根据长度压缩并消除中间多余的零字节，成为向量化最后一步的难点。在未使能COMPACT指令时，可能有以下做法： A：移动到标量，通过串行存储解决实现方式较为简单，将元素提取到灵活的标量寄存器，串行存储。存在问题：从向量寄存器搬移数据到通用寄存器会引入搬移开销。此外地址的串行计算和依次存储会产生大量的指令开销。 B：向量计算地址，scatter进行自动覆盖尽管ARM指令集规范中，scatter指令的写入顺序暂未定义，对重合地址的写入行为也属于未定义行为。但是鲲鹏系列处理器的scatter指令存在高lane覆盖低lane的特性，即当scatter store的多个激活lane的写地址重合时，高lane写入的优先级更高，结果等同于先写低lane，后用高lane覆盖。这个特性使得使用scatter存储可以通过覆盖机制处理编码结果的紧密排布。使用scatter的难点在于计算每个存储位置的地址。在串行存储中，这个地址每次会累加编码长度。而scatter方案中需要同时计算所有的累加和，本质上是要快速计算向量的前缀和。向量前缀和可以使用Kogge-Stone算法，这个算法来自快速加法器电路的硬件算法，这个算法通过logN轮移位即可计算前缀和，第i轮右移2^(i-1)位并与移位前的相加。计算8个元素的前缀和，需要进行三轮操作。设初始向量为v0，第一轮计算v1 = v0 + shift_right(v0, 1)；第二轮计算v2 = v1 + shift_right(v1, 2)；第三轮计算v3 = v2 + shift_right(v2, 4)。图 1 计算8个元素的前缀和操作缺点：前缀和计算的利用率不高，32bit 8元素计算前缀和需要三轮移位+add，移位的ext指令由于寄存器限制需要mov，总共需要9条向量指令，总体性能较差。此时适合使用COMPACT进行合并。如图2所示，可以将32bit元素向量reinterpret为8bit元素向量，则原本的每个元素自动被分为4段，通过比较计算后可以构造mask。使用COMPACT指令即可将变长的有效部分压缩到一起。可以视为把“predicate prefix sum + lane permutation”融合为一条语义指令。图 2 32bit元素向量reinterpret为8bit元素向量只需计算掩码加一条compact指令即可完成压缩，后续只需要一次普通存储即可完成变长元素的向量编码。位图提取位图是一种在操作系统内核、内存分配器等高性能数据处理系统中广泛应用的基础数据结构。激活元素提取是位图最常见的操作之一，传统标量代码采用逐位扫描方式，存在循环迭代次数多、分支预测失败率高、无法利用SIMD并行能力等性能瓶颈。COMPACT指令可根据位图生成的predicate一次性提取所有激活元素并压缩到目标向量低位，减少标量依赖链开销，提高向量吞吐性能。其收益与激活元素密度相关：稀疏位图可能更适合lowbit扫描，中高密度位图则更能发挥COMPACT优势。最优方案可结合两种方法，并为全0/全1情况设置快速路径。在操作系统内核、内存分配器、数据库索引、网络报文处理等各类高性能数据处理系统中，位图（Bitmap）是一种应用极为广泛的基础数据结构。位图是一串连续的二进制比特，每个比特与目标元素一一对应，0或1是元素的二元状态标记，如“无效/有效”、“未选中/选中”、“空闲/占用”等；哪一端取0、哪一端取1并无定论，由开发者按后续数据处理的便利性决定。由于具备极致的空间利用率，并原生支持高效的位运算，位图成为大规模状态标记场景中的首选方案。在实际工程落地中，位图的核心操作远不止单点状态查询，激活元素提取是其中最常见的访存模式之一。该操作需要遍历位图中的所有比特位，将所有状态为“激活”的比特位对应的元素索引按顺序提取出来，并连续紧凑地写入目标缓冲区。这类位图提取操作是任务调度、数据过滤、空闲资源分配等上层逻辑的核心基础，其执行效率往往直接决定了整个系统的吞吐与延迟表现。本文以jemalloc内存分配器为例，其在内存片管理（arena_slab）中使用了位图来跟踪内存单元的空闲状态。具体来说，每个内存片被划分为多个大小相同的内存单元并使用位图进行管理，位图中的每一位表示相应内存单元的占用情况：1表示空闲，0表示已分配。当处理内存分配请求时，分配器需要从该位图中提取出内存片中所有空闲单元索引，完成地址计算与占用位标记，该操作的执行速度直接决定了小内存分配的延迟性能。传统标量代码通常采用逐位扫描的朴素方案实现该操作：通过循环结构配合移位、按位与等位运算，依次检查每一位的激活状态；若判定当前位为有效状态，则计算其对应索引并追加写入输出缓冲区。bool bitmap_test(uint64_t* bitmap, int location){ return bitmap[location/64] & (1ll<<(location%64)); } for (int i = 0; i < n; i++) { if (bitmap_test(bitmap, i)) { out[j++] = data[i]; } } 或者采用lowbit函数，利用补码表示中 -x = ~x + 1 的特性，使用公式x & -x位运算快速提取最低位的1。for (size_t w = 0; w < word_count; w++) { uint64_t bits = bitmap[w]; while (bits != 0) { uint64_t lowbit = bits & -bits; unsigned bit_index = __builtin_ctzll(bits); size_t i = w * 64 + bit_index; out[j++] = data[i]; bits ^= lowbit; } } 这种实现逻辑直观易懂，但存在显著的性能瓶颈：循环迭代次数与位图总位数成正比，分支指令密集且分支预测失败率高，同时完全无法利用现代CPU的SIMD并行计算能力，在大位图、高频率调用的场景下，极易成为系统性能的瓶颈。而COMPACT指令可以根据由Bitmap生成的predicate，一次性从向量中提取所有激活元素，并按原始顺序压缩到目标向量的低位连续lane中。随后只需根据激活元素数量将前若干lane连续写出即可。这样可以有效减少标量分支和逐元素搬移开销，且能利用好向量执行资源，提高位图扫描类操作的性能。其伪代码如下。while (i < n) { pred = load_predicate_from_bitmap(bitmap, i); vec = load_vector(data + i); packed = compact(vec, pred); count = popcount(pred); store(out + j, packed, count); j += count; i += vector_length; } COMPACT不能完全消除输出指针的串行性，因为输出流本身仍然是线性生成的。但它将指针更新从“每个active元素一次”降低到“每个向量块一次”，显著缩短了标量依赖链。 COMPACT的收益与active lane密度相关。对于极稀疏位图，lowbit扫描每次只处理激活bit，循环次数等于popcount，可能仍有优势。对于中高密度或分布不规则的位图，COMPACT可以一次处理整个向量块，减少分支和逐元素输出更新，通常更容易发挥向量吞吐优势。最优的写法可以考虑结合使用，并为全0（直接跳过）、全1（全部输出）设置快速路径，中间情况使用COMPACT。总结总结来看，COMPACT的价值在于它提供了跨lane的数据紧凑化能力。对于变长编码，它可以将不同lane中产生的有效字节重新排列为连续输出；对于位图处理，它可以将Bitmap标记的active元素一次性提取为稠密数组。相比标量提取、lowbit扫描或前缀和 + scatter方案，COMPACT可以减少分支、降低输出指针串行更新压力，并避免大量向量到标量的数据搬移。随着SVE版本对B8/B16 COMPACT的支持，ARM在字节级变长数据处理上的向量化路径会更加直接，有望打通一批变长压缩以及位图处理场景的全程向量化路径，带来显著性能提升。