c - 如何将四个 2 位位域求和到一个 8 位字节中？

Question

我有四个 2 位位域存储在一个字节中。因此，每个位域可以表示 0、1、2 或 3。例如，以下是前 3 个位域为零的 4 个可能值:

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 次加载，因此我可以只加载四次，而不是加载 byte 一次:第一次加载 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

对位字段进行不同的编码以使逻辑更容易实际上是可以的，只要它适合单个字节并以某种方式与此方案一对一映射即可。下降到装配也很好。当前目标是 Sandy Bridge，但目标 Haswell 或更高版本也可以。

应用和动机:我正在尝试使开源变量位解压缩例程运行得更快。每个位域表示后面的四个整数中每一个的压缩长度。我需要总和才能知道需要跳转多少字节才能到达下一组四个字节。当前循环需要 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 

Answer 1

内置 POPCOUNT 指令有帮助吗？

n = POPCOUNT(byte&0x55);
n+= 2*POPCOUNT(byte&0xAA)

或者也许

  word = byte + ((byte&0xAA) << 8);
  n = POPCOUNT(word);

不确定总时间。 This discussion说 popcount 有 3 个周期延迟，1 个吞吐量。

<小时/>

更新:
我可能遗漏了一些关于如何运行 IACA 的重要事实，但在 12-11 吞吐量范围内进行了一些实验后，我编译了以下内容:

 uint32_t decodeFast(uint8_t *in, size_t count) {
  uint64_t key1 = *in;
  uint64_t key2;
  size_t adv;
  while (count--){
     IACA_START;
     key2=key1&0xAA;
     in+= __builtin_popcount(key1);
     adv= __builtin_popcount(key2);
     in+=adv+4;
     key1=*in;
  }
  IACA_END;
  return key1;
}

与gcc -std=c99 -msse4 -m64 -O3 test.c

并获得3.55个周期!？!:

Block Throughput: 3.55 Cycles       Throughput Bottleneck: InterIteration
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |    |
---------------------------------------------------------------------
|   1    |           | 1.0 |           |           |     |     |    | popcnt edx,eax
|   1    | 0.9       |     |           |           |     | 0.1 | CP | and eax,0x55 
|   1    |           | 1.0 |           |           |     |     | CP | popcnt eax,eax
|   1    | 0.8       |     |           |           |     | 0.2 |    | movsxd rdx,edx
|   1    | 0.6       |     |           |           |     | 0.4 |    | add rdi, rdx
|   1    | 0.1       | 0.1 |           |           |     | 0.9 | CP | cdqe 
|   1    | 0.2       | 0.3 |           |           |     | 0.6 |    | sub rsi, 1
|   1    | 0.2       | 0.8 |           |           |     |     | CP | lea rdi,[rdi+rax+4] 
|   1    |           |     | 0.5   0.5 | 0.5   0.5 |     |     | CP | movzx eax,[rdi]
|   1    |           |     |           |           |     | 1.0 |    | jnz 0xffff

<小时/>

另外两个想法

可能的微优化，用 2 条指令求和

total=0;
PDEP(vals,0x03030303,*in);  #expands the niblets into bytes
PSADBW(total,vals) #total:= sum of abs(0-byte) for each byte in vals

每个延迟据说是 3，所以这可能没有帮助。也许按字节求和加法可以用简单的移位和加法来代替 AX=total+total>>16; ADD AL,AH

宏观优化:
您提到使用 key 作为对随机指令表的查找。为什么不将到下一个键的距离与随机播放指令一起存储呢？要么存储一个更大的表，要么可能将 4 位长度压缩到 shuffle key 的未使用的位 3-6 中，但代价是需要一个掩码来提取它。