c - 使用 C/Intel 程序集寻求最大位图(又名位数组)性能

Question

继我之前的两个问题之后，How to improve memory performance/data locality of 64-bit C/intel assembly program和 Using C/Intel assembly, what is the fastest way to test if a 128-byte memory block contains all zeros? , 我进一步将这些问题中提到的测试程序的运行时间从 150 秒减少到 62 秒，我将在下面描述。

64 位程序有五个 4 GB 的查找表(bytevecM、bytevecD、bytevecC、bytevecL、bytevecX)。为了减少缓存未命中的(大量)数量，我在上一个问题中进行了分析，我添加了五个 4 MB 位图，每个查找表一个。

这是原始的内部循环:

psz = (size_t*)&bytevecM[(unsigned int)m7 & 0xffffff80];
if (psz[0]  == 0 && psz[1]  == 0
&&  psz[2]  == 0 && psz[3]  == 0
&&  psz[4]  == 0 && psz[5]  == 0
&&  psz[6]  == 0 && psz[7]  == 0
&&  psz[8]  == 0 && psz[9]  == 0
&&  psz[10] == 0 && psz[11] == 0
&&  psz[12] == 0 && psz[13] == 0
&&  psz[14] == 0 && psz[15] == 0) continue;
// ... rinse and repeat for bytevecD, bytevecC, bytevecL, bytevecX

// expensive inner loop that scans 128 byte chunks from the 4 GB lookup tables...

这个简单的“预检查”背后的想法是，如果所有 128 个字节都为零，则避免昂贵的内部循环。然而，分析表明，由于大量缓存未命中，此预检查是主要瓶颈，如上次所讨论的那样。所以我创建了一个 4 MB 的位图来进行预检查。 (顺便说一句，大约 36% 的 128 字节 block 为零，而不是我上次错误报告的 98%)。

这是我用来从 4 GB 查找表创建 4 MB 位图的代码:

// Last chunk index (bitmap size=((LAST_CHUNK_IDX+1)>>3)=4,194,304 bytes)
#define LAST_CHUNK_IDX      33554431
void make_bitmap(
   const unsigned char* bytevec,  // in:  byte vector
   unsigned char* bitvec          // out: bitmap
)
{
   unsigned int uu;
   unsigned int ucnt = 0;
   unsigned int byte;
   unsigned int bit;
   const size_t* psz;
   for (uu = 0; uu <= LAST_CHUNK_IDX; ++uu)
   {
      psz = (size_t*)&bytevec[uu << 7];
      if (psz[0]  == 0 && psz[1]  == 0
      &&  psz[2]  == 0 && psz[3]  == 0
      &&  psz[4]  == 0 && psz[5]  == 0
      &&  psz[6]  == 0 && psz[7]  == 0
      &&  psz[8]  == 0 && psz[9]  == 0
      &&  psz[10] == 0 && psz[11] == 0
      &&  psz[12] == 0 && psz[13] == 0
      &&  psz[14] == 0 && psz[15] == 0) continue;
      ++ucnt;
      byte = uu >> 3;
      bit  = (uu & 7);
      bitvec[byte] |= (1 << bit);
   }
   printf("ucnt=%u hits from %u\n", ucnt, LAST_CHUNK_IDX+1);
}

欢迎就更好的方法提出建议。

通过上述函数创建的位图，然后我将“预检查”更改为使用 4 MB 位图，而不是 4 GB 查找表，如下所示:

if ( (bitvecM[m7 >> 10] & (1 << ((m7 >> 7) & 7))) == 0 ) continue;
// ... rinse and repeat for bitvecD, bitvecC, bitvecL, bitvecX

// expensive inner loop that scans 128 byte chunks from the 4 GB lookup tables...

这是“成功的”，因为在简单的单线程情况下，运行时间从 150 秒减少到 62 秒。但是，VTune 仍然会报告一些相当大的数字，如下所示。

我分析了一个更真实的测试，其中八个同时线程在不同范围内运行。内循环检查零 block 的 VTune 输出如下所示:

> m7 = (unsigned int)( (m6 ^ q7) * H_PRIME );
> if ( (bitvecM[m7 >> 10] & (1 << ((m7 >> 7) & 7))) == 0 ) continue;

0x1400025c7  Block 15:
mov   eax, r15d                    1.058s
mov   edx, ebx                     0.109s
xor   eax, ecx                     0.777s
imul  eax, eax, 0xf4243            1.088s
mov   r9d, eax                     3.369s
shr   eax, 0x7                     0.123s
and   eax, 0x7                     1.306s
movzx ecx, al                      1.319s
mov   eax, r9d                     0.156s
shr   rax, 0xa                     0.248s
shl   edx, cl                      1.321s
test  byte ptr [rax+r10*1], dl     1.832s
jz    0x140007670                  2.037s

> d7 = (unsigned int)( (s6.m128i_i32[0] ^ q7) * H_PRIME );
> if ( (bitvecD[d7 >> 10] & (1 << ((d7 >> 7) & 7))) == 0 ) continue;

0x1400025f3  Block 16:
mov   eax, dword ptr [rsp+0x30]  104.983s
mov   edx, ebx                     1.663s
xor   eax, r15d                    0.062s
imul  eax, eax, 0xf4243            0.513s
mov   edi, eax                     1.172s
shr   eax, 0x7                     0.140s
and   eax, 0x7                     0.062s
movzx ecx, al                      0.575s
mov   eax, edi                     0.689s
shr   rax, 0xa                     0.016s
shl   edx, cl                      0.108s
test  byte ptr [rax+r11*1], dl     1.591s
jz    0x140007670                  1.087s

> c7 = (unsigned int)( (s6.m128i_i32[1] ^ q7) * H_PRIME );
> if ( (bitvecC[c7 >> 10] & (1 << ((c7 >> 7) & 7))) == 0 ) continue;

0x14000261f  Block 17:
mov   eax, dword ptr [rsp+0x34]   75.863s
mov   edx, 0x1                     1.097s
xor   eax, r15d                    0.031s
imul  eax, eax, 0xf4243            0.265s
mov   ebx, eax                     0.512s
shr   eax, 0x7                     0.016s
and   eax, 0x7                     0.233s
movzx ecx, al                      0.233s
mov   eax, ebx                     0.279s
shl   edx, cl                      0.109s
mov   rcx, qword ptr [rsp+0x58]    0.652s
shr   rax, 0xa                     0.171s
movzx ecx, byte ptr [rax+rcx*1]    0.126s
test  cl, dl                      77.918s
jz    0x140007667

> l7 = (unsigned int)( (s6.m128i_i32[2] ^ q7) * H_PRIME );
> if ( (bitvecL[l7 >> 10] & (1 << ((l7 >> 7) & 7))) == 0 ) continue;

0x140002655  Block 18:
mov   eax, dword ptr [rsp+0x38]    0.980s
mov   edx, 0x1                     0.794s
xor   eax, r15d                    0.062s
imul  eax, eax, 0xf4243            0.187s
mov   r11d, eax                    0.278s
shr   eax, 0x7                     0.062s
and   eax, 0x7                     0.218s
movzx ecx, al                      0.218s
mov   eax, r11d                    0.186s
shl   edx, cl                      0.031s
mov   rcx, qword ptr [rsp+0x50]    0.373s
shr   rax, 0xa                     0.233s
movzx ecx, byte ptr [rax+rcx*1]    0.047s
test  cl, dl                      55.060s
jz    0x14000765e

除此之外，大量时间(令我感到困惑)归因于此行:

> for (q6 = 1; q6 < 128; ++q6) {

0x1400075a1  Block 779:
inc   edx                          0.124s
mov   dword ptr [rsp+0x10], edx
cmp   edx, 0x80                    0.031s
jl    0x140002574
mov   ecx, dword ptr [rsp+0x4]
mov   ebx, dword ptr [rsp+0x48]
...
0x140007575 Block 772:
mov   edx, dword ptr [rsp+0x10]    0.699s
...
0x14000765e  Block 789  (note: jz in l7 section above jumps here if zero):
mov   edx, dword ptr [rsp+0x10]    1.169s
jmp   0x14000757e                  0.791s
0x140007667  Block 790 (note: jz in c7 section above jumps here if zero):
mov   edx, dword ptr [rsp+0x10]    2.261s
jmp   0x140007583                  1.461s
0x140007670  Block 791 (note: jz in m7/d7 section above jumps here if zero):
mov   edx, dword ptr [rsp+0x10]  108.355s
jmp   0x140007588                  6.922s

我不完全理解上面 VTune 输出中的大数字。如果有人能更清楚地说明这些数字，我会洗耳恭听。

在我看来，我的 5 个 4 MB 位图比我的 Core i7 3770 处理器能够装入其 8 MB L3 缓存的容量大，导致许多缓存未命中(尽管比以前少得多)。如果我的 CPU 有一个 30 MB 的 L3 缓存(就像即将推出的 Ivy Bridge-E 那样)，我推测这个程序会运行得更快 很多 因为所有五个位图都可以轻松地放入 L3 缓存中。是吗？

此外，由于测试位图的代码，即:

m7 = (unsigned int)( (m6 ^ q7) * H_PRIME );
bitvecM[m7 >> 10] & (1 << ((m7 >> 7) & 7))) == 0

现在在内循环中出现了五次，非常欢迎任何加速这段代码的建议。

Answer 1

在循环的核心位中，使用 _bittest() MSVC 内在位图检查结合了 shl/test 组合编译器创建单个指令(在 SandyBridge 上)没有延迟/吞吐量损失，即它应该减少几个周期。

除此之外，只能考虑通过递归 POR 映射减少位集来计算位图，作为可能值得基准测试的零测试的变体:

for (int i = 0; i < MAX_IDX; i++) {
   __m128i v[8];
   __m128i* ptr = ...[i << ...];

   v[0] = _mm_load_si128(ptr[0]);
   v[1] = _mm_load_si128(ptr[1]);
   v[2] = _mm_load_si128(ptr[2]);
   v[3] = _mm_load_si128(ptr[3]);
   v[4] = _mm_load_si128(ptr[4]);
   v[5] = _mm_load_si128(ptr[5]);
   v[6] = _mm_load_si128(ptr[6]);
   v[7] = _mm_load_si128(ptr[7]);
   v[0] = _mm_or_si128(v[0], v[1]);
   v[2] = _mm_or_si128(v[2], v[3]);
   v[4] = _mm_or_si128(v[4], v[5]);
   v[6] = _mm_or_si128(v[6], v[7]);

   v[0] = _mm_or_si128(v[0], v[2]);
   v[2] = _mm_or_si128(v[4], v[6]);

   v[0] = _mm_or_si128(v[0], v[2]);

   if (_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_setzero_si128(), v[0]))) {
       // the contents aren't all zero
   }
   ...
}

在这一点上，纯加载/累积-OR/提取掩码可能比 SSE4.2 PTEST 的紧密循环更好，因为没有 flags 依赖且没有分支。