00 00 00 00 = 0 0 0 0 00 00 00 01 = 0 0 0 1 00 00 00 10 = 0 0 0 2 00 00 00 11 = 0 0 0 3
我想要一个有效的方式来总结四个位域.例如：
11 10 01 00 = 3 + 2 + 1 + 0 = 6
现代Intel x64 cpu上的8位查询表需要4个周期才能从L1返回答案.似乎应该有一些方法来比较快地计算答案. 3个循环给出6-12个简单位操作的空间.作为起始者,简单的面具和移位看起来像在Sandy Bridge上需要5个周期：
假设位字段为：d c b a,该掩码为：00 00 00 11
在Ira的帮助下澄清：这假设a,b,c和d是相同的,并且都被设置为初始字节.奇怪的是,我想我可以免费做这个.由于每个周期可以做2次加载,而不是加载一次,所以我可以加载四次：第一个周期的a和d,第二个周期的b和c.第二个负载将延迟一个周期,但直到第二个周期才需要它们.下面的拆分代表如何将事件分解成单独的循环.
a = *byte d = *byte b = *byte c = *byte latency latency a &= mask d >>= 6 b >>= 2 c >>= 4 a += d b &= mask c &= mask b += c a += b
为了使逻辑更容易,对于位字段的不同编码实际上是很好的,只要它适合单个字节,并以某种方式与该方案一对一映射.掉落到装配也很好.目前的目标是桑迪大桥,但是对于哈斯韦尔或以上的目标来说也是如此.
应用和动机：我试图使一个开源变量位解压缩例程更快.每个位域表示随后的四个整数中的每一个的压缩长度.我需要这个总和来知道我需要跳转到下一组4个字节.当前的循环需要10个循环,其中5个循环进行了我正在尝试避免的查找.削减一个周期将会改善10％.
编辑：本来我说“8个循环”,但是如Evgeny所指出的那样我错了.正如Evgeny指出的,唯一的时间是间接的4周期负载是从系统内存的第2K加载而不使用索引寄存器.正确的延迟清单可以在Intel Architecture Optimization Manual第2.12节中找到
> Data Type (Base + Offset) > 2048 (Base + Offset) < 2048 > Base + Index [+ Offset] > Integer 5 cycles 4 cycles > MMX,SSE,128-bit AVX 6 cycles 5 cycles > X87 7 cycles 6 cycles > 256-bit AVX 7 cycles 7 cycles
编辑：我认为这是以下的Ira解决方案将会进入周期.我认为还需要5个周期的工作负载.
a = *byte b = *byte latency latency latency a &= 0x33 b >>= 2 b &= 0x33 c = a a += b c += b a &= 7 c >>= 4 a += c
解决方法
使用正常的加法指令(一次添加一对值)可能会更好一些,使用像掩码和移位这样的简单操作将这些值彼此分离,并使用指令级并行来高效地执行此操作.此外,字节中两个中间值的位置提示使用单个64位寄存器而不是内存的表查找变体.所有这些都可以加快四个和的总和的计算,只能使用4或5个时钟.
>从存储器(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.前两个人没有做任何事情.但英特尔的编译器几乎完成了这项工作.
编辑：Nathan的测试揭示了以下方法的问题. Sandy Bridge的ROR指令使用两个端口并与SHR指令冲突.所以这个代码在Sandy Bridge上需要更多的时钟,这使得它不是很有用.它可能会像Ivy Bridge和Haswell那样工作.
没有必要使用64位寄存器的技巧作为查找表.相反,您只需将字节旋转4位,将两个中间值放置在第一个和第四个值的位置.那么你可以以相同的方式处理它们.这种方法至少有一个缺点.在C中表达字节旋转并不容易.另外我不太确定这个旋转,因为在较旧的处理器上可能会导致部分寄存器停止.优化手册提示,对于Sandy Bridge,如果操作源与目的地相同,则可以更新部分寄存器,而无需停止.但我不知道我是否明白了.我没有正确的硬件来检查这个.无论如何,这里是代码(现在可能是32位或64位)：
mov ecx,ecx ;clock 2 ror al,4 ;clock 1 mov 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之间的边界打开位字段
该方法与上一个方法的不同之处仅在于提取两个中间位域的方式.而不是在桑迪桥上昂贵的ROR,而是使用简单的移动.这种移动将AH中的第二位域置于寄存器AL和第三位域中.然后用轮班/面具抽出.像以前的方法一样,这里存在部分寄存器停顿的可能性,现在在两个指令中而不是一个.但是很有可能Sandy Bridge和较新的处理器可以毫不拖延地执行它们.
mov ecx,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,[esi+edx] ;clock 4..8 movzx eax,[esi+edx] ;clock 4..8 add esi,edx
并行加载和计算和
也不需要加载4个长度的字节并顺序地计算和.您可以并行执行所有这些操作.四个总和只有13个值.如果您的数据是可压缩的,那么很少会看到这个总和大于7.这意味着不是加载一个字节,您可以将前8个最可能的字节加载到64位寄存器.而且你可以比计算总和的时间早.在计算和时加载8个值.然后,您只需使用shift和mask从该寄存器获取正确的值.这个想法可以与用于计算和的任何方法一起使用.这里使用简单的表查找：
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个时钟延迟：shift和mask.其中有7个时钟(但仅在可压缩数据上).
如果将表查找更改为计算,则可能会获得只有6个时钟的循环延迟：4将值添加到一起并更新指针,对于shift和mask可以使用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,[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,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,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,... mask_12 = 0x0F,... mask_34 = 0xF0,... 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点)
>使用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)将高128位提取到具有VEXTRACTI128的单独XMM寄存器. (2个小时)
>现在预处理完成.我们可以在下一个16字节的数据块中跟随第一个数据块的“链接”.这可以用PCMPGTB,PSHUFB,PSUBB和PBLENDVB完成.但是,如果为可能的“链接”值分配范围0x70 .. 0x80,则单个PSHUFB将正常工作(实际上是一对PSHUFB,在AVX2的情况下).值0x70 .. 0x7F从下一个16字节寄存器中选择正确的字节,而值0x80将跳过下一个16字节并加载字节0,这正是所需要的. (2 uops,等待时间= 2个时钟)
这6个步骤的说明不需要按顺序排列.例如,步骤5和2的指令可以彼此相邻.每个步骤的指令应该处理不同流水线段的16/32字节块,如下所示：步骤1处理块i,步骤2处理块i-1,步骤3,4处理块i-2等.
整个循环的延迟可能是2个时钟(每32个字节的数据).但是这里的限制因素是吞吐量,而不是延迟.当使用AVX2时,我们需要执行15个uops,这意味着5个时钟.如果数据不可压缩且数据块较大,则每个数据块约3个时钟.如果数据是可压缩的并且数据块很小,则每个数据块大约1个时钟. (但是由于MOVDQA延迟为6个时钟,要获得每32个字节5个时钟,我们需要两个重叠的负载,并在每个循环中处理两倍的数据).
预处理步骤与步骤#6无关.所以它们可以在不同的线程中执行.这可能会减少5个时钟以下每32个字节数据的时间.