c – 如何在单个8位字节中求和四个2位位元？

概述我有四个2位位字段存储在一个字节.因此,每个位域可以表示0,1,2或3.例如,这里是前3个位域为零的4个可能值： 00 00 00 00 = 0 0 0 000 00 00 01 = 0 0 0 100 00 00 10 = 0 0 0 200 00 00 11 = 0 0 0 3 我想要一个有效的方式来总结四个位域.例如： 11 10 01 00 = 3 + 2 + 1 + 0 = 6 现 我有四个2位位字段存储在一个字节.因此,每个位域可以表示0,1,2或3.例如,这里是前3个位域为零的4个可能值：

00 00 00 00 = 0 0 0 000 00 00 01 = 0 0 0 100 00 00 10 = 0 0 0 200 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 = *byted = *byteb = *bytec = *bytelatencylatencya &= maskd >>= 6b >>= 2c >>= 4a += db &= maskc &= maskb += ca += 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,@R_962_5028@ AVX  6 cycles               5 cycles>     X87                    7 cycles               6 cycles >     256-bit AVX            7 cycles               7 cycles

编辑：我认为这是以下的Ira解决方案将会进入周期.我认为还需要5个周期的工作负载.

a = *byteb = *bytelatencylatency latencya &= 0x33b >>= 2b &= 0x33c = aa += bc += ba &= 7c >>= 4a += c

解决方法 其他答案提出了各种方法来加入坐在单个变量中的值(不打包它们).虽然这些方法提供了非常好的吞吐量(特别是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,3Chand eax,ebx              ;clock 1mov ecx,3and ecx,ebx              ;clock 1shr ebx,6                ;clock 1add ebx,ecx              ;clock 2mov rcx,6543543243213210hshr rcx,eax              ;clock 2..3and ecx,Fh               ;clock 4add rsi,5add rsi,rbx              ;clock 3 or 4movzx ebx,[rsi + rcx]    ;clock 5..9add 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,ecx              ;clock 2ror al,4                 ;clock 1mov ecx,eax              ;clock 2shr eax,6                ;clock 2add eax,ecx              ;clock 3add esi,5add esi,ebx              ;clock 3movzx ebx,[esi+eax]      ;clocks 4 .. 8movzx eax,[esi+eax]      ;clocks 4 .. 8add esi,eax

使用AL和AH之间的边界打开位字段

该方法与上一个方法的不同之处仅在于提取两个中间位域的方式.而不是在桑迪桥上昂贵的ROR,而是使用简单的移动.这种移动将AH中的第二位域置于寄存器AL和第三位域中.然后用轮班/面具抽出.像以前的方法一样,这里存在部分寄存器停顿的可能性,现在在两个指令中而不是一个.但是很有可能Sandy BrIDge和较新的处理器可以毫不拖延地执行它们.

mov ecx,ecx              ;clock 2shl eax,4                ;clock 1mov edx,3and dl,ah                ;clock 2shr al,6                 ;clock 2add dl,al                ;clock 3add esi,[esi+edx]      ;clock 4..8movzx eax,[esi+edx]      ;clock 4..8add 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 readyvpand xmm2,[mask_34]   ; clock 2 -- bitfIElds 3,4 (shifted)vpsrlq xmm2,xmm2,4          ; clock 3 -- bitfIElds 3,4 readyvpshufb xmm1,xmm5,xmm1      ; clock 3 -- sum of bitfIElds 1 and 2vpshufb xmm2,xmm2      ; clock 4 -- sum of bitfIElds 3 and 4vpaddb xmm0,xmm1,xmm2       ; clock 5 -- sum of all bitfIElds

然后更新地址并加载下一个字节向量：

vpaddd xmm4,xmm4,[min_size]vpaddd xmm4,xmm1       ; clock 4 -- address + 5 + bitfIElds 1,2vmovd esi,xmm4               ; clock 5..6vmovd edx,xmm2               ; clock 5..6vmovdqu 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个字节数据的时间.

总结

以上是内存溢出为你收集整理的c – 如何在单个8位字节中求和四个2位位元？全部内容，希望文章能够帮你解决c – 如何在单个8位字节中求和四个2位位元？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。