其他答案提出了各种方法来将位于单个变量中的值加在一起（无需解包）。虽然这些方法提供了相当好的吞吐量（特别是 POPCNT），但它们具有很大的延迟——要么是因为计算链长，要么是因为使用了高延迟指令。
最好使用普通的加法指令（一次将一对值相加），使用掩码和移位之类的简单操作将这些值彼此分开，并使用指令级并行性来有效地做到这一点。此外，字节中两个中间值的位置暗示了使用单个 64 位寄存器而不是内存的表查找变体。所有这一切都可以加快计算四个总和的速度，并且只使用 4 或 5 个时钟。
OP中建议的原始表查找方法可能包括以下步骤：
- 从内存中加载具有四个值的字节（5 个时钟）
- 使用查找表计算值的总和（5 个时钟）
- 更新指针（1 个时钟）
64位寄存器查找
以下代码片段显示了如何在 5 个时钟内执行步骤 #2，并结合步骤 #2 和 #3 将延迟仍保持在 5 个时钟（可以优化为 4 个时钟，具有复杂寻址模式以用于内存负载）：
p += 5 + (*p & 3) + (*p >> 6) +
((0x6543543243213210ull >> (*p & 0x3C)) & 0xF);
这里常量“5”意味着我们跳过当前字节的长度以及对应于全零长度的 4 个数据字节。此代码段对应于以下代码（仅限 64 位）：
mov eax, 3Ch
and eax, ebx ;clock 1
mov ecx, 3
and ecx, ebx ;clock 1
shr ebx, 6 ;clock 1
add ebx, ecx ;clock 2
mov rcx, 6543543243213210h
shr rcx, eax ;clock 2..3
and ecx, Fh ;clock 4
add rsi, 5
add rsi, rbx ;clock 3 or 4
movzx ebx, [rsi + rcx] ;clock 5..9
add rsi, rcx
我尝试使用以下编译器自动生成此代码：gcc 4.6.3、clang 3.0、icc 12.1.0。前两个没有做任何好事。但英特尔的编译器几乎完美地完成了这项工作。
使用 ROR 指令快速提取位域
编辑：内森的测试揭示了以下方法的问题。Sandy Bridge 上的 ROR 指令使用两个端口，与 SHR 指令冲突。所以这段代码在 Sandy Bridge 上还需要 1 个时钟，这使得它不是很有用。可能它会在 Ivy Bridge 和 Haswell 上按预期工作。
没有必要使用 64 位寄存器的技巧作为查找表。相反，您可以将字节旋转 4 位，将两个中间值放置到第一个和第四个值的位置。然后你可以用同样的方式处理它们。这种方法至少有一个缺点。在 C 中表达字节旋转并不容易。我也不太确定这种旋转，因为在旧处理器上它可能会导致部分寄存器停顿。优化手册提示，对于 Sandy Bridge，如果操作源与目标相同，我们可以更新部分寄存器，而无需停顿。但我不确定我是否理解正确。而且我没有合适的硬件来检查这一点。无论如何，这是代码（现在它可能是 32 位或 64 位）：
mov ecx, 3
and ecx, ebx ;clock 1
shr ebx, 6 ;clock 1
add ebx, ecx ;clock 2
ror al, 4 ;clock 1
mov ecx, 3
and ecx, eax ;clock 2
shr eax, 6 ;clock 2
add eax, ecx ;clock 3
add esi, 5
add esi, ebx ;clock 3
movzx ebx, [esi+eax] ;clocks 4 .. 8
movzx eax, [esi+eax] ;clocks 4 .. 8
add esi, eax
使用 AL 和 AH 之间的边界来解包位域
此方法与前一种方法的不同之处仅在于提取两个中间位域的方式。代替在 Sandy Bridge 上昂贵的 ROR，使用了简单的班次。此移位将第二个位域定位在寄存器 AL 中，将第三个位域 - 定位在 AH 中。然后用移位/掩码提取它们。和之前的方法一样，这里有部分寄存器停顿的可能性，现在是两条指令而不是一条。但很可能 Sandy Bridge 和更新的处理器可以毫不拖延地执行它们。
mov ecx, 3
and ecx, ebx ;clock 1
shr ebx, 6 ;clock 1
add ebx, ecx ;clock 2
shl eax, 4 ;clock 1
mov edx, 3
and dl, ah ;clock 2
shr al, 6 ;clock 2
add dl, al ;clock 3
add esi, 5
add esi, ebx ;clock 3
movzx ebx, [esi+edx] ;clock 4..8
movzx eax, [esi+edx] ;clock 4..8
add esi, edx
并行加载和计算总和
也没有必要加载 4 个长度的字节并按顺序计算总和。您可以并行执行所有这些操作。四个之和只有 13 个值。如果您的数据是可压缩的，那么您很少会看到这个总和大于 7。这意味着您可以将前 8 个最可能的字节加载到 64 位寄存器，而不是加载单个字节。你可以在计算四者的总和之前做到这一点。在计算总和时加载 8 个值。然后，您只需使用移位和掩码从该寄存器中获得正确的值。这个想法可以与任何计算总和的方法一起使用。这里它与简单的表查找一起使用：
typedef unsigned long long ull;
ull four_lengths = *p;
for (...)
{
ull preload = *((ull*)(p + 5));
unsigned sum = table[four_lengths];
p += 5 + sum;
if (sum > 7)
four_lengths = *p;
else
four_lengths = (preload >> (sum*8)) & 15;
}
使用正确的汇编代码，这只会给延迟增加 2 个时钟：移位和掩码。这提供了 7 个时钟（但仅限于可压缩数据）。
如果将查表更改为计算，您可能会得到只有 6 个时钟的循环延迟：4 个用于将值相加并更新指针，2 个用于移位和掩码。有趣的是，在这种情况下，循环延迟仅由计算确定，而不取决于内存加载的延迟。
并行加载和计算总和（确定性方法）
可以以确定性方式进行并行执行加载和求和。加载两个 64 位寄存器，然后使用 CMP+CMOV 选择其中一个是一种可能性，但与顺序计算相比，它不会提高性能。其他可能性是使用 128 位寄存器和 AVX。在 128 位寄存器和 GPR/内存之间迁移数据会增加大量延迟（但如果我们每次迭代处理两个数据块，则可能会消除一半的延迟）。此外，我们需要对 AVX 寄存器使用字节对齐的内存加载（这也会增加循环延迟）。
这个想法是在 AVX 中执行所有计算，除了应该从 GPR 完成的内存加载。（有一种替代方法可以在 AVX 中执行所有操作并在 Haswell 上使用广播+添加+收集，但它不太可能更快）。此外，将数据加载到一对 AVX 寄存器（每次迭代处理两个数据块）应该是有帮助的。这允许成对的加载操作部分重叠并抵消一半的额外延迟。
从从寄存器中解压缩正确的字节开始：
vpshufb xmm0, xmm6, xmm0 ; clock 1
将四个位域相加：
vpand xmm1, xmm0, [mask_12] ; clock 2 -- bitfields 1,2 ready
vpand xmm2, xmm0, [mask_34] ; clock 2 -- bitfields 3,4 (shifted)
vpsrlq xmm2, xmm2, 4 ; clock 3 -- bitfields 3,4 ready
vpshufb xmm1, xmm5, xmm1 ; clock 3 -- sum of bitfields 1 and 2
vpshufb xmm2, xmm5, xmm2 ; clock 4 -- sum of bitfields 3 and 4
vpaddb xmm0, xmm1, xmm2 ; clock 5 -- sum of all bitfields
然后更新地址并加载下一个字节向量：
vpaddd xmm4, xmm4, [min_size]
vpaddd xmm4, xmm4, xmm1 ; clock 4 -- address + 5 + bitfields 1,2
vmovd esi, xmm4 ; clock 5..6
vmovd edx, xmm2 ; clock 5..6
vmovdqu xmm6, [esi + edx] ; clock 7..12
然后再次重复相同的代码，只使用xmm7而不是xmm6。xmm6加载时我们可以处理xmm7.
这段代码使用了几个常量：
min_size = 5, 0, 0, ...
mask_12 = 0x0F, 0, 0, ...
mask_34 = 0xF0, 0, 0, ...
xmm5 = lookup table to add together two 2-bit values
如此处所述实现的循环需要 12 个时钟来完成并一次“跳转”两个数据块。这意味着每个数据块有 6 个周期。这个数字可能过于乐观了。我不太确定 MOVD 只需要 2 个时钟。此外，还不清楚执行未对齐内存加载的 MOVDQU 指令的延迟是多少。我怀疑当数据跨越缓存线边界时 MOVDQU 具有非常高的延迟。我想这意味着平均增加 1 个延迟时钟。因此，每个数据块大约 7 个周期是更现实的估计。
使用蛮力
每次迭代只跳转一个或两个数据块很方便，但不会充分利用现代处理器的资源。经过一些预处理后，我们可以实现直接跳转到下一个对齐的 16 字节数据中的第一个数据块。预处理应该读取数据，计算每个字节的四个字段的总和，使用这个总和计算到下一个四字节字段的“链接”，最后沿着这些“链接”到下一个对齐的 16 字节块. 所有这些计算都是独立的，可以使用 SSE/AVX 指令集以任何顺序计算。AVX2 的预处理速度会快两倍。
- 使用 MOVDQA 加载 16 或 32 字节的数据块。
- 将每个字节的 4 个位域相加。为此，使用两条 PAND 指令提取高 4 位和低 4 位半字节，使用 PSRL* 移动高半字节，使用两个 PSHUFB 求每个半字节的总和，并使用 PADDB 将两个总和相加。（6 微秒）
- 使用 PADDB 计算到下一个四字段字节的“链接”：将常量 0x75、0x76、... 添加到 XMM/YMM 寄存器的字节。(1 微升)
- 按照 PSHUFB 和 PMAXUB 的“链接”（PMAXUB 更昂贵的替代品是 PCMPGTB 和 PBLENDVB 的组合）。
VPSHUFB ymm1, ymm2, ymm2几乎所有的工作。它将“越界”值替换为零。然后VPMAXUB ymm2, ymm1, ymm2恢复原始“链接”来代替这些零。两次迭代就足够了。每次迭代后，每个“链接”的距离都是两倍大，所以我们只需要 log(longest_chain_length) 次迭代。例如，最长的链 0->5->10->15->X 一步压缩为 0->10->X，两步压缩为 0->X。（4 微指令）
- 使用 PSUBB 从每个字节中减去 16，并且（仅适用于 AVX2）使用 VEXTRACTI128 将高 128 位提取到单独的 XMM 寄存器中。（2 微秒）
- 现在预处理已经完成。我们可以跟随“链接”到下一个 16 字节数据中的第一个数据块。这可以通过 PCMPGTB、PSHUFB、PSUBB 和 PBLENDVB 完成。但是，如果我们
0x70 .. 0x80为可能的“链接”值分配范围，则单个 PSHUFB 将正常工作（实际上是一对 PSHUFB，在 AVX2 的情况下）。值0x70 .. 0x7F从下一个 16 字节寄存器中选择正确的字节，而值0x80将跳过下一个 16 字节并加载字节0，这正是需要的。（2 微指令，延迟 = 2 个时钟）
这 6 个步骤的说明不需要按顺序排列。例如，第 5 步和第 2 步的说明可能彼此相邻。每个步骤的指令应处理流水线不同阶段的 16/32 字节块，如下所示：步骤 1 处理块i，步骤 2 处理块i-1，步骤 3,4 处理块i-2等。
整个循环的延迟可能是 2 个时钟（每 32 字节数据）。但这里的限制因素是吞吐量，而不是延迟。当使用 AVX2 时，我们需要执行 15 个微指令，这意味着 5 个时钟。如果数据不可压缩且数据块很大，则每个数据块大约需要 3 个时钟。如果数据是可压缩的并且数据块很小，这会为每个数据块提供大约 1 个时钟。（但由于 MOVDQA 延迟是 6 个时钟，为了每 32 个字节获得 5 个时钟，我们需要两个重叠加载并在每个循环中处理两倍的数据）。
预处理步骤独立于步骤#6。所以它们可能在不同的线程中执行。这可能会将每 32 字节数据的时间减少到 5 个时钟以下。