c - 使用 C/Intel 汇编，测试 128 字节内存块是否包含全零的最快方法是什么？

Question

继续我的第一个问题，我正在尝试优化通过 VTune 分析 64 位 C 程序发现的内存热点。

特别是，我想找到最快的方法来测试 128 字节的内存块是否包含全零。您可以为内存块假设任何所需的内存对齐方式；我使用了 64 字节对齐。

我使用的 PC 配备 Intel Ivy Bridge Core i7 3770 处理器、32 GB 内存和 Microsoft vs2010 C 编译器的免费版本。

我的第一次尝试是:

const char* bytevecM;    // 4 GB block of memory, 64-byte aligned
size_t* psz;             // size_t is 64-bits
// ...
// "m7 & 0xffffff80" selects the 128 byte block to test for all zeros
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;
// ...

相应程序集的 VTune 分析如下:

cmp    qword ptr [rax],      0x0       0.171s
jnz    0x14000222                     42.426s
cmp    qword ptr [rax+0x8],  0x0       0.498s
jnz    0x14000222                      0.358s
cmp    qword ptr [rax+0x10], 0x0       0.124s
jnz    0x14000222                      0.031s
cmp    qword ptr [rax+0x18], 0x0       0.171s
jnz    0x14000222                      0.031s
cmp    qword ptr [rax+0x20], 0x0       0.233s
jnz    0x14000222                      0.560s
cmp    qword ptr [rax+0x28], 0x0       0.498s
jnz    0x14000222                      0.358s
cmp    qword ptr [rax+0x30], 0x0       0.140s
jnz    0x14000222
cmp    qword ptr [rax+0x38], 0x0       0.124s
jnz    0x14000222
cmp    qword ptr [rax+0x40], 0x0       0.156s
jnz    0x14000222                      2.550s
cmp    qword ptr [rax+0x48], 0x0       0.109s
jnz    0x14000222                      0.124s
cmp    qword ptr [rax+0x50], 0x0       0.078s
jnz    0x14000222                      0.016s
cmp    qword ptr [rax+0x58], 0x0       0.078s
jnz    0x14000222                      0.062s
cmp    qword ptr [rax+0x60], 0x0       0.093s
jnz    0x14000222                      0.467s
cmp    qword ptr [rax+0x68], 0x0       0.047s
jnz    0x14000222                      0.016s
cmp    qword ptr [rax+0x70], 0x0       0.109s
jnz    0x14000222                      0.047s
cmp    qword ptr [rax+0x78], 0x0       0.093s
jnz    0x14000222                      0.016s

我能够通过英特尔内部函数对此进行改进:

const char* bytevecM;                        // 4 GB block of memory
__m128i* psz;                                // __m128i is 128-bits
__m128i one = _mm_set1_epi32(0xffffffff);    // all bits one
// ...
psz = (__m128i*)&bytevecM[(unsigned int)m7 & 0xffffff80];
if (_mm_testz_si128(psz[0], one) && _mm_testz_si128(psz[1], one)
&&  _mm_testz_si128(psz[2], one) && _mm_testz_si128(psz[3], one)
&&  _mm_testz_si128(psz[4], one) && _mm_testz_si128(psz[5], one)
&&  _mm_testz_si128(psz[6], one) && _mm_testz_si128(psz[7], one)) continue;
// ...

相应程序集的 VTune 分析如下:

movdqa xmm0, xmmword ptr [rax]         0.218s
ptest  xmm0, xmm2                     35.425s
jnz    0x14000ddd                      0.700s
movdqa xmm0, xmmword ptr [rax+0x10]    0.124s
ptest  xmm0, xmm2                      0.078s
jnz    0x14000ddd                      0.218s
movdqa xmm0, xmmword ptr [rax+0x20]    0.155s
ptest  xmm0, xmm2                      0.498s
jnz    0x14000ddd                      0.296s
movdqa xmm0, xmmword ptr [rax+0x30]    0.187s
ptest  xmm0, xmm2                      0.031s
jnz    0x14000ddd
movdqa xmm0, xmmword ptr [rax+0x40]    0.093s
ptest  xmm0, xmm2                      2.162s
jnz    0x14000ddd                      0.280s
movdqa xmm0, xmmword ptr [rax+0x50]    0.109s
ptest  xmm0, xmm2                      0.031s
jnz    0x14000ddd                      0.124s
movdqa xmm0, xmmword ptr [rax+0x60]    0.109s
ptest  xmm0, xmm2                      0.404s
jnz    0x14000ddd                      0.124s
movdqa xmm0, xmmword ptr [rax+0x70]    0.093s
ptest  xmm0, xmm2                      0.078s
jnz    0x14000ddd                      0.016s

如您所见，汇编指令更少，而且该版本在时序测试中进一步证明速度更快。

由于我在 Intel SSE/AVX 指令领域相当薄弱，我欢迎就如何更好地使用它们来加速此代码提出建议。

虽然我搜索了数百个可用的内在函数，但我可能错过了理想的内在函数。特别是，我无法有效地使用 _mm_cmpeq_epi64();我寻找了这个内在函数的“不相等”版本(它似乎更适合这个问题)，但没有找到答案。虽然下面的代码“有效”:

if (_mm_testz_si128(_mm_andnot_si128(_mm_cmpeq_epi64(psz[7], _mm_andnot_si128(_mm_cmpeq_epi64(psz[6], _mm_andnot_si128(_mm_cmpeq_epi64(psz[5], _mm_andnot_si128(_mm_cmpeq_epi64(psz[4], _mm_andnot_si128(_mm_cmpeq_epi64(psz[3], _mm_andnot_si128(_mm_cmpeq_epi64(psz[2], _mm_andnot_si128(_mm_cmpeq_epi64(psz[1], _mm_andnot_si128(_mm_cmpeq_epi64(psz[0], zero), one)), one)), one)), one)), one)), one)), one)), one), one)) continue;

它几乎不可读，而且(不出所料)被证明比上面给出的两个版本慢得多。我确信必须有一种更优雅的方式来使用 _mm_cmpeq_epi64() 并欢迎就如何实现这一点提出建议。

除了使用 C 中的内在函数外，还欢迎针对此问题使用原始英特尔汇编语言解决方案。

Answer 1

正如其他人指出的那样，主要问题是您正在检查的 128 字节数据缺少数据缓存和/或 TLB并转到 DRAM，这很慢。 VTune 告诉您这一点

cmp    qword ptr [rax],      0x0       0.171s
jnz    0x14000222                     42.426s

你在半路上有另一个更小的热点

cmp    qword ptr [rax+0x40], 0x0       0.156s
jnz    0x14000222                      2.550s

占 JNZ 指令的那 42.4 + 2.5 秒实际上是由于先前从内存加载造成的停顿……在您分析程序的时间里，处理器总共有 45 秒无所事事……等待动态随机存取存储器。

你可能会问半路上的第二个热点是什么。好吧，你正在访问 128 字节，缓存行是 64 字节，CPU 一读取前 64 字节就开始为你预取……但是你没有对前 64 字节做足够的工作来完全重叠进入内存的延迟。

Ivy Bridge 的内存带宽非常高(这取决于您的系统，但我猜超过 10 GB/秒)。您的内存块是 4GB，如果您按顺序访问它并让 CPU 提前为您预取数据，您应该能够在不到 1 秒的时间内通过它。

我的猜测是您通过以非连续方式访问 128 字节 block 来阻止 CPU 数据预取器。

将您的访问模式更改为顺序访问模式，您会惊讶于它的运行速度有多快。然后您可以考虑下一级优化，这将确保分支预测正常运行。

要考虑的另一件事是TLB 未命中。这些都是昂贵的，尤其是在 64 位系统中。与其使用 4KB 页面，不如考虑使用 2MB huge pages。请参阅此链接了解 Windows 对这些的支持:Large-Page Support (Windows)

如果您必须以某种随机方式访问 4GB 数据，但您提前知道 m7 值(您的索引)的序列，那么您可以流水线在你使用之前显式地获取内存(它需要在你使用它之前几个 100 个 CPU 周期才能有效)。见

• _mm_prefetch
• usage of "_mm_prefetch(...)"
• MM_PREFETCH

这里有一些链接可能对内存优化主题有帮助

What Every Programmer Should Know About Memory by Ulrich Drepper

http://www.akkadia.org/drepper/cpumemory.pdf

机器架构:您的编程语言从未告诉您的事情，作者 Herb Sutter

http://www.gotw.ca/publications/concurrency-ddj.htm

http://nwcpp.org/static/talks/2007/Machine_Architecture_-_NWCPP.pdf

http://video.google.com/videoplay?docid=-4714369049736584770#