其他答案提出了各种将单个变量中的值相加的方法(无需解包)。虽然这些方法在吞吐量上表现良好(特别是使用POPCNT),但它们具有很大的延迟,要么是因为长计算链,要么是因为使用高延迟指令。
最好使用普通的加法指令(一次将一对值相加),使用简单的操作如掩码和移位来分割这些值,并使用指令级并行性来高效地完成此操作。同时,在字节中两个中间值的位置提示了一种使用单个64位寄存器而不是内存的表查找变体。所有这些都可以加快计算四个值的总和并仅使用4或5个时钟周期。
原始的表查找方法建议在OP中包含以下步骤:
1. 从内存加载带有四个值的字节(5个时钟周期)
2. 使用查找表计算值的总和(5个时钟周期)
3. 更新指针(1个时钟周期)
64位寄存器查找
以下代码段展示了如何在5个时钟周期内执行第2步,并在保持延迟为5个时钟周期的情况下组合第2步和第3步(可以通过复杂的寻址模式优化到4个时钟周期以进行内存加载):
p += 5 + (*p & 3) + (*p >> 6) +
((0x6543543243213210ull >> (*p & 0x3C)) & 0xF);
这里的常数“5”表示我们跳过当前字节和4个数据字节,这些字节对应于全零长度。该代码片段对应于以下代码(仅限64位):
mov eax, 3Ch
and eax, ebx
mov ecx, 3
and ecx, ebx
shr ebx, 6
add ebx, ecx
mov rcx, 6543543243213210h
shr rcx, eax
and ecx, Fh
add rsi, 5
add rsi, rbx
movzx ebx, [rsi + rcx]
add rsi, rcx
我曾试过使用以下编译器自动生成这段代码:gcc 4.6.3、clang 3.0和icc 12.1.0。前两个都没有做到好的效果,但英特尔的编译器几乎完美地完成了任务。
ROR指令实现快速位域提取
编辑:Nathan的测试揭示了以下方法的问题。Sandy Bridge 上的 ROR 指令使用了两个端口,并与 SHR 指令冲突。因此,这段代码在 Sandy Bridge 上需要多一次时钟,使它不是很有用。可能它在 Ivy Bridge 和 Haswell 上能够按预期执行。
不必将64位寄存器作为查找表来使用技巧。相反,你可以将字节旋转4位,从而将中间两个值放置在第一个和第四个值的位置。然后,你可以以同样的方式处理它们。这种方法至少有一个缺点。C语言中不太容易表示字节旋转。此外,我对这种旋转并不十分确定,因为在旧处理器上,它可能导致部分寄存器停顿。优化手册提示,在 Sandy Bridge 上,如果操作源与目标相同,则可以更新寄存器的一部分,而不会停顿。但我不确定我是否正确地理解了这一点。并且我没有适当的硬件来检查这一点。无论如何,以下是代码(现在可以是32位或64位):
mov ecx, 3
and ecx, ebx
shr ebx, 6
add ebx, ecx
ror al, 4
mov ecx, 3
and ecx, eax
shr eax, 6
add eax, ecx
add esi, 5
add esi, ebx
movzx ebx, [esi+eax]
movzx eax, [esi+eax]
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加载内存以外。 (在Haswell上可以使用广播+添加+收集来完成所有操作,但这不太可能更快)。另外,交替加载数据到一对AVX寄存器应该是有帮助的(以每次迭代处理两个数据块)。这允许部分重叠的一对负载操作,并消除了额外延迟的一半。
从寄存器中解包出正确的字节开始:
vpshufb xmm0, xmm6, xmm0
将四个位域相加:
vpand xmm1, xmm0, [mask_12]
vpand xmm2, xmm0, [mask_34]
vpsrlq xmm2, xmm2, 4
vpshufb xmm1, xmm5, xmm1
vpshufb xmm2, xmm5, xmm2
vpaddb xmm0, xmm1, xmm2
然后更新地址并加载下一个字节向量:
vpaddd xmm4, xmm4, [min_size]
vpaddd xmm4, xmm4, xmm1
vmovd esi, xmm4
vmovd edx, xmm2
vmovdqu xmm6, [esi + edx]
然后再次重复相同的代码,只是使用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位半字节,使用PSRL*移动高半字节,使用两个PSHUFB找到每个半字节的和,并使用PADDB添加两个和。(6 uops)
- 使用PADDB计算链接到下一个四字段字节的“链接”:将常量0x75、0x76等添加到XMM/YMM寄存器的字节中。(1 uop)
- 使用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 uops)
- 使用PSUBB从每个字节中减去16,(仅适用于AVX2)使用VEXTRACTI128将高128位提取到单独的XMM寄存器中。(2 uops)
- 现在预处理完成。我们可以跟随“链接”到下一个16字节数据块中的第一个数据块。这可能需要使用PCMPGTB、PSHUFB、PSUBB和PBLENDVB来完成。但是,如果我们为可能的“链接”值分配范围
0x70 .. 0x80
,一个PSHUFB就可以正确地完成工作(实际上,在AVX2的情况下是一对PSHUFB)。值0x70 .. 0x7F
选择下一个16字节寄存器中的正确字节,而值0x80
将跳过下一个16字节并加载字节0
,这正是所需的。(2 uops, latency = 2 clocks)
这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个时钟周期以下。