使用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位程序有5个4GB的查找表(bytevecM、bytevecD、bytevecC、bytevecL、bytevecX).为了减少缓存丢失的数量(在上一个问题中进行了分析)，我添加了5个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个字节都为零，则避免使用昂贵的内循环。然而，正如上次讨论的那样，分析显示，由于大量缓存未命中，这种预检查是主要的瓶颈。所以我创建了一个4MB的位图来做预检查。(顺便说一句，128个字节块中约有36%为零，而不是我上次错误报道的98% )。

下面是用于从4GB查找表创建4MB位图的代码：

// 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);
}

关于更好的方法的建议是值得欢迎的。

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

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仍然报告了一些相当大的数字，如下所示。

我分析了一个更真实的测试，八个同时运行在不同范围的线程。零块内环检查的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的位图比我的核心i7 3770处理器能容纳到它的8MB L3缓存大，导致许多缓存丢失(尽管比以前少得多)。如果我的CPU有一个30 MB的L3缓存(就像即将到来的常春藤桥E那样)，我推测这个程序会运行得更快，因为所有五个位图都能很好地适应L3缓存。是那么回事吗？

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

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

现在在内部循环中出现了五次，任何关于加速这个代码的建议都是非常受欢迎的。

Answer 1

在循环的核心位内，使用位图检查所固有的_bittest() MSVC将编译器创建的shl/test组合组合成一个指令，没有延迟/吞吐量损失，也就是说，它应该减少几个周期。

除此之外，只能考虑通过递归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
   }
   ...
}

此时，纯load /累加-OR/提取掩码可能比SSE4.2 PTEST的紧循环更好，因为不存在flags依赖和分支。

Answer 2

对于128字节的缓冲区，使用较大的整数进行比较.

unsigned char cbuf[128];
unsigned long long *lbuf = cbuf;
int i;
for (i=0; i < 128/sizeof(long long); i++) {
    if (lbuf[i]) return false; // something not a zero
}
return true; // all zero