15

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

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

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

我的第一次尝试是：

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

我能够通过 Intel instrinsics 对此进行改进：

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

如您所见，汇编指令较少，并且此版本进一步证明在时序测试中更快。

由于我在英特尔 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 中的内部函数外，还欢迎针对此问题的原始英特尔汇编语言解决方案。

4

6 回答 6

14

正如其他人指出的那样，主要问题是您正在检查的 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 秒……在 DRAM 上等待。

您可能会问中途的第二个热点是什么。好吧，您正在访问 128 字节并且缓存行是 64 字节，CPU 在读取前 64 字节后就开始为您预取......但是您没有对前 64 字节做足够的工作完全重叠进入内存的延迟。

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

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

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

要考虑的另一件事是TLB misses。这些成本很高，尤其是在 64 位系统中。而不是使用 4KB 页面考虑使用 2MB huge pages。请参阅此链接以了解 Windows 对这些内容的支持：大页面支持 (Windows)

如果您必须以某种随机的方式访问 4GB 数据，但您提前知道m7值的序列（您的索引），那么您可以pipeline在使用之前显式获取内存（它需要提前几个 100 个 CPU 周期）您将使用它来有效）。看

以下是一些可能对内存优化主题有帮助的链接

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#

于 2013-03-02T15:51:56.610 回答
5

抱歉，我没有足够的评论声誉。
如果您使用以下内容作为测试会发生什么？

if( (psz[0]  | psz[1]  | psz[2]  | psz[3]  |
     psz[4]  | psz[5]  | psz[6]  | psz[7]  |
     psz[8]  | psz[9]  | psz[10] | psz[11] |
     psz[12] | psz[13] | psz[14] | psz[15] ) == 0) continue;

不幸的是，我没有用于编译它的 64 位系统，而且我不熟悉编译器对 c 代码的确切作用，但在我看来，二进制文件或比单独的 == 比较更快. 我也不知道 Intel 内在函数是什么，但可以以类似于您已经完成的方式优化上述代码。
我希望我的回答有帮助。
马斯

于 2013-03-02T08:22:43.743 回答
2

在 98% 的 128 字节块全为零时，您平均每 4K 页不到一个非零字节。对于稀疏的数组，您是否尝试将其存储为稀疏数组？您将节省大量内存和随之而来的缓存未命中延迟；如果一个普通的 std::map 结果更快，我不会感到惊讶。

于 2013-03-02T17:09:23.560 回答
2

您是否考虑过英特尔字符串扫描指令？这些往往具有非常高的数据速率，并且处理器知道数据访问是顺序的。

     mov      rdi, <blockaddress>
     cld
     xor      rax, rax
     mov      rcx, 128/8
     repe     scasq
     jne      ...

这无助于您的数据不在缓存中的问题。如果您提前知道要考虑哪个块，您可以使用 Intel 的预取指令来解决这个问题。请参阅http://software.intel.com/en-us/articles/use-software-data-prefetch-on-32-bit-intel-architecture

[编辑代码以整合评论中指出的小问题]

于 2013-03-02T17:19:38.717 回答
1

感谢您迄今为止收到的出色提示。

我相信 Mmarss 的“mega or”方法会提高性能，因为它生成的汇编语言指令更少。然而，当我运行我的基准程序时，我原来的笨拙 && 解决方案需要 163 秒，而我原来笨拙的英特尔 instrinsics 解决方案需要 145 秒（这两个在我原来的帖子中有描述）。

为了完整起见，这里是我用于“mega or”方法的 C 代码：

if ((psz[0]  | psz[1]  | psz[2]  | psz[3]
|    psz[4]  | psz[5]  | psz[6]  | psz[7]
|    psz[8]  | psz[9]  | psz[10] | psz[11]
|    psz[12] | psz[13] | psz[14] | psz[15]) == 0) continue;

VTune 程序集是：

mov    rax, qword ptr [rcx+0x78]    0.155s
or     rax, qword ptr [rcx+0x70]   80.972s
or     rax, qword ptr [rcx+0x68]    1.292s
or     rax, qword ptr [rcx+0x60]    0.311s
or     rax, qword ptr [rcx+0x58]    0.249s
or     rax, qword ptr [rcx+0x50]    1.229s
or     rax, qword ptr [rcx+0x48]    0.187s
or     rax, qword ptr [rcx+0x40]    0.233s
or     rax, qword ptr [rcx+0x38]    0.218s
or     rax, qword ptr [rcx+0x30]    1.742s
or     rax, qword ptr [rcx+0x28]    0.529s
or     rax, qword ptr [rcx+0x20]    0.233s
or     rax, qword ptr [rcx+0x18]    0.187s
or     rax, qword ptr [rcx+0x10]    1.244s
or     rax, qword ptr [rcx+0x8]     0.155s
or     rax, qword ptr [rcx]         0.124s
jz     0x1400070b9                  0.342s

然后，我尝试通过以下方式将“大或”的想法翻译成英特尔的内在学：

__m128i tt7;
// ...
tt7 = _mm_or_si128(_mm_or_si128(_mm_or_si128(psz[0], psz[1]),
      _mm_or_si128(psz[2], psz[3])),
      _mm_or_si128(_mm_or_si128(psz[4], psz[5]),
      _mm_or_si128(psz[6], psz[7])));
if ( (tt7.m128i_i64[0] | tt7.m128i_i64[1]) == 0) continue;

虽然结果也更慢，需要 155 秒。它的 VTune 组件是：

movdqa xmm2, xmmword ptr [rax]         0.047s
movdqa xmm0, xmmword ptr [rax+0x20]   75.461s
movdqa xmm1, xmmword ptr [rax+0x40]    2.567s
por    xmm0, xmmword ptr [rax+0x30]    1.867s
por    xmm2, xmmword ptr [rax+0x10]    0.078s
por    xmm1, xmmword ptr [rax+0x50]    0.047s
por    xmm2, xmm0                      0.684s
movdqa xmm0, xmmword ptr [rax+0x60]    0.093s
por    xmm0, xmmword ptr [rax+0x70]    1.214s
por    xmm1, xmm0                      0.420s
por    xmm2, xmm1                      0.109s
movdqa xmmword ptr tt7$[rsp], xmm2     0.140s
mov    rax, qword ptr [rsp+0x28]       0.233s
or     rax, qword ptr [rsp+0x20]       1.027s
jz     0x1400070e2                     0.498s

上面的英特尔内在方法非常粗糙。欢迎提出改进建议。

这再次表明测量的重要性。几乎每次我都猜到哪个会更快我错了。也就是说，只要你仔细衡量每一个变化，你就不会变得更糟，只会变得更好。虽然我倒退（如上）的次数多于前进，但在过去的一周里，我已经能够将小测试程序的运行时间从 221 秒减少到 145 秒。鉴于真正的程序将运行几个月，这将节省几天。

于 2013-03-02T11:56:32.007 回答
0

建议：将您的阵列对齐到 128B，因此空间预取器将始终希望填充正确的高速缓存行以形成一对 128B 的高速缓存行。 英特尔优化手册，第 2-30 页（PDF 第 60 页），描述了 Sandybridge/Ivybridge：

空间预取器：此预取器力求使用将其完成为 128 字节对齐块的对线来完成提取到 L2 高速缓存的每个高速缓存行。

由于您的阵列仅与 64B 对齐，读取 128B 可以触及两对缓存线，导致 L2 空间预取器为您可能永远不会使用的数据发出更多负载。

您的答案有正确的想法：或将块与向量一起，然后测试它是否为全零。使用单个分支可能比每 8 个字节单独分支更好。

但是您测试向量的策略很糟糕：不要存储它然后标量加载+或两半。这是SSE4 PTEST的完美用例，它让我们避免了通常的pcmpeqb / pmovmskb情况：

ptest   xmm0,xmm0      ; 2 uops, and Agner Fog lists it as 1c latency for SnB/IvB, but this is probably bogus.  2c is more likely
jz    vector_is_all_zero
; 3 uops, but shorter latency and smaller code-size than pmovmskb

通常，分支可以很好地预测，生成其标志输入的延迟并不重要。但在这种情况下，主要瓶颈是分支错误预测。因此，花更多的微指令（如有必要）来减少延迟可能是值得的。

我不确定在加载第二个缓存行之前测试第一个缓存行是否更好，以防您找到一个非零字节而不会遭受第二个缓存未命中。空间预取器无法立即加载第二个缓存行，因此可能会在加载第二个 64B 缓存行之前尝试提前退出，除非这会导致大量额外的分支错误预测。

所以我可能会这样做：

allzero_128B(const char *buf)
{
    const __m128i *buf128 = (const __m128i*)buf;  // dereferencing produces 128b aligned-load instructions

    __m128i or0 = _mm_or_si128(buf[0], buf[2]);
    __m128i or2 = _mm_or_si128(buf[1], buf[3]);
    __m128i first64 = _mm_or_si128(or0, or2);
    // A chain of load + 3 OR instructions would be fewer fused-domain uops
    //  than load+or, load+or, or(xmm,xmm).  But resolving the branch faster is probably the most important thing.

    if (_mm_testz_si128(first64, first64)
        return 0;

    __m128i or4 = _mm_or_si128(buf[4], buf[6]);
    __m128i or6 = _mm_or_si128(buf[5], buf[7]);
    __m128i first64 = _mm_or_si128(or4, or6);


}

在 IvyBrige 上，使用 256b AVX 操作并没有什么好处。Vector-FP 256b VORPS ymm 每个 uop 的工作量是原来的两倍，但仅在端口 5 上运行。（POR xmm 在 p015 上运行）。256b 加载作为两个 128b 一半完成，但它们仍然只有 1 uop。

我看不到使用单个 CMPEQPS 来检查 256b 向量是否为全零的方法。+0.0 比较等于 -0.0，因此符号位位置的 1 位在与零的比较中不会被检测到。我也不认为任何 CMPPS 谓词都有帮助，因为它们都没有实现比较 -0.0 与 +0.0 不同的处理方式。（有关浮点相等性的更多信息，请参阅SIMD 指令以进行浮点相等性比较（NaN == NaN））。

; First 32B arrives in L1D (and load buffers) on cycle n
vmovaps  ymm0,   [rdi+64]              ; ready on cycle n+1  (256b loads take 2 cycles)
vorps    ymm0,   ymm0, [rdi+96]        ; ready on cycle n+3  (the load uop is executing on cycles n+1 and n+2)
vextractf128 xmm1, ymm0, 1           ; 2c latency on IvB, 3c on Haswell
                                     ; xmm1 ready on cycle n+5
vpor     xmm0,   xmm0, xmm1          ; ready on n+6 (should be no bypass delay for a shuffle (vextractf128) -> integer booleans)
vptest   xmm0,   xmm0
jz   second_cacheline_all_zero

不，这并不比

; First 32B of the cache-line arrives in L1D on cycle n (IvB has a 32B data path from L2->L1)
vmovaps  xmm0,   [rdi+64]              ; result ready on cycle n
vmovaps  xmm1,   [rdi+64 + 16]         ; result ready on cycle n  (data should be forwarded to outstanding load buffers, I think?)
vpor     xmm0,   xmm0, [rdi+64 + 32]   ; ready on cycle n+1
vpor     xmm1,   xmm1, [rdi+64 + 48]   ; ready on cycle n+1, assuming the load uops get their data the cycle after the first pair.
vpor     xmm0,   xmm1                  ; ready on cycle n+2
vptest   xmm0,   xmm0
jz   second_cacheline_all_zero

使用 AVX2，256b 操作将是有意义的，包括 VPTEST ymm,ymm。

于 2017-04-30T21:50:23.097 回答