1

继我之前的两个问题之后，如何提高 64 位 C/intel 汇编程序的内存性能/数据局部性和使用 C/Intel 汇编，测试 128 字节内存块是否包含全零的最快方法是什么？，我进一步将这些问题中提到的测试程序的运行时间从 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 字节块是零，而不是我上次错误报告的 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 仍然会报告一些相当大的数字，如下所示。

我分析了一个更现实的测试，其中八个同时运行的线程在不同的范围内运行。内部循环检查零块的 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

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

4

2 回答 2

2

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

除此之外，只能考虑通过 recursive 减少位集来计算位图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依赖项和分支。

于 2013-03-12T13:08:55.817 回答
0

对于 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
于 2013-03-10T06:11:58.727 回答