Zigzag 解码与 AVX-512：SIMD 优化的两种路径

背景

在现代图形处理和网格数据处理中，meshoptimizer 等库经常需要对顶点数据进行解码以加速处理。近期，作者在优化 meshoptimizer 中的 AVX-512 顶点解码性能时，探索了两种未最终采用但颇具启发性的优化技术。这些优化触及了 AVX-512 指令集中两个较新的特性，并共同指向同一个核心问题：如何高效地解码 Zigzag 编码的整数。

Zigzag 编码是一种常用于变长整数编码（如 VByte/LEB128）前的预处理步骤。当数据经过差分编码（Delta Encoding）后，相邻值的差异通常很小，但符号不可预测。Zigzag 编码将符号位移至最低位，使得正数变为偶数，负数变为奇数，从而让小幅度差异（无论正负）都映射为较小的无符号整数，便于后续压缩。

核心内容

Zigzag 编码与解码原理

假设有一组经过差分编码得到的有符号整数，其绝对值较小但符号随机。若直接使用二进制补码存储，小数值可能占用较多高位比特，不利于变长编码。Zigzag 编码通过以下规则转换值 $v$：

• 正数 $v$ 编码为 $2v$
• 负数 $v$ 编码为 $2(-v) - 1$ （即 $2(\sim v) + 1$）

例如：$0 \to 0$, $-1 \to 1$, $1 \to 2$, $-2 \to 3$, $2 \to 4$。 这种映射使得符号位变成了最低有效位（LSB），幅度位右移了一位。

解码 Zigzag 编码的值 $v$ 有两种常见方式：

1. 分支版本：

   (v & 1) == 0 ? (v >> 1) : ~(v >> 1)
   

2. 无分支版本（Branchless）：

   (v >> 1) ^ -(v & 1)
   

   无分支版本的原理是：-(v & 1) 在 $v$ 为偶数时为 0，在 $v$ 为奇数时为全 1 掩码（即 -1）。与 $(v >> 1)$ 进行异或操作，若掩码为 0 则保持不变，若为全 1 则按位取反。这等效于上述三元表达式。

传统 SIMD 解码实现

将无分支解码公式直接映射到 SIMD 指令集非常直观。以 SSE2 处理 32 位整数为例：

__m128i xs = _mm_and_si128(v, _mm_set1_epi32(1)); // 提取符号位
__m128i xl = _mm_sub_epi32(_mm_setzero_si128(), xs); // 取反：0 - xs
__m128i xr = _mm_srli_epi32(v, 1); // 右移一位
return _mm_xor_si128(xl, xr); // 异或合并

对应的汇编指令及延迟分析（基于 Zen 4 架构）：

• vpsrld xmm1, xmm0, 1：移位，延迟 1 周期。
• vpandq xmm0, xmm0, xmm2：与操作，延迟 1 周期，不依赖移位结果。
• vpsubd xmm0, xmm3, xmm0：减法，延迟 1 周期，不依赖前两者。
• vpxorq xmm0, xmm0, xmm1：异或，延迟 1 周期，依赖移位和与/减的结果。

由于 vpandq 不依赖 vpsrld，这 4 条指令的累积延迟仅为 3 个周期。

优化路径一：利用 AVX-512 掩码（Masks）

AVX-512 引入了执行掩码（Execution Masks/Predication），允许根据掩码条件性地执行指令。我们可以尝试直接编译带有分支逻辑的代码，而不是依赖算术技巧。

分支逻辑伪代码：

sign = v & 1
mask = sign != 0
res = v >> 1
(predicated by mask) res = ~res

在 AVX-512 中，由于没有直接的按位取反指令，可以使用异或 -1 来模拟。初步实现如下：

__m128i xs = _mm_and_si128(v, _mm_set1_epi32(1));
__mmask8 m = _mm_cmp_epi32_mask(xs, _mm_setzero_si128(), _MM_CMPINT_NE);
__m128i x = _mm_srli_epi32(v, 1);
return _mm_mask_xor_epi32(x, m, x, _mm_set1_epi32(-1));

进一步优化： 上述代码中，_mm_and_si128 的结果用于生成掩码。AVX-512 提供了专用的 _mm_test_epi32_mask 指令，它执行 AND 操作并将结果与 0 比较，直接生成掩码（类似标量 TEST 指令）。优化后的代码：

__mmask8 m = _mm_test_epi32_mask(v, _mm_set1_epi32(1));
__m128i x = _mm_srli_epi32(v, 1);
return _mm_mask_xor_epi32(x, m, x, _mm_set1_epi32(-1));

对应的汇编仅三条指令：

1. vptestmd k1, xmm1, xmm3：测试并生成掩码。
2. vpsrld xmm0, xmm1, 1：移位。
3. vpxord xmm0{k1}, xmm0, xmm2：条件异或。

宽度限制与变通： AVX-512 的掩码异或（_mm_mask_xor_epi32）仅支持 32 位整数，不支持 8 或 16 位。对于 16 位整数，可以使用条件减法 _mm_mask_sub_epi16 来模拟取反（因为 $-1 - x = \sim x$）：

__mmask8 m = _mm_test_epi16_mask(v, _mm_set1_epi16(1));
__m128i x = _mm_srli_epi16(v, 1);
return _mm_mask_sub_epi16(x, m, _mm_set1_epi16(-1), x);

性能对比：掩码是否更快？

虽然指令数从 4 条减少到 3 条，但性能提升取决于具体场景。在 Zen 4 架构上：

• 掩码执行本身（如带掩码的 vpxor 或 vpsub）延迟和吞吐量与无掩码版本相同。
• 然而，vptestmd 的延迟为 3 个周期。
• 条件异或/减法指令依赖于移位结果，而移位指令不依赖于测试指令。

因此，关键路径的总延迟为：vptestmd (3 cycles) + vpsrld (1 cycle) + 条件操作 (1 cycle) = 5 个周期？ 注：原文指出累积延迟为 4 个周期，比原始版本的 3 个周期多 1 个周期。

这意味着在**延迟敏感（Latency-bound）**的场景下，这种基于掩码的优化反而更慢。

关键要点

• Zigzag 解码本质：将符号位移至最低位，使小幅度差值映射