使用C / Intel程序集，测试128字节内存块是否包含全零的最快方法是什么？
继续我的第一个问题，我正在尝试优化通过VTune分析64位C程序找到的内存热点。
特别是，我想找到一种最快的方法来测试一个128字节的内存块是否包含全零。 您可以假设内存块有任何所需的内存对齐方式; 我使用64字节对齐。
我使用的是配备Intel Ivy Bridge Core i7 3770处理器和32 GB内存的PC以及免费版的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
通过英特尔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
如您所见，assembly指令较少，此版本在时序测试中进一步certificate更快。
由于我在英特尔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;
它的边界线不可读，并且（不出所料）被certificate比上面给出的两个版本慢。 我确信必须有一种更优雅的方式来使用_mm_cmpeq_epi64（），并欢迎提供有关如何实现这一目标的建议。
除了使用C语言的内在函数之外，还欢迎使用原始的英特尔汇编语言解决方案。
正如其他人所指出的那样，主要的问题是你正在检查的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字节，一旦读取了第一个64字节，CPU就开始为你预取…但你没有做足够的工作，第一个64字节到完全重叠进入内存的延迟。
Ivy Bridge的内存带宽非常高（这取决于你的系统，但我猜测超过10 GB /秒）。 你的内存块是4GB，如果按顺序访问它，你应该能够在不到1秒的时间内通过它进行压缩，并让CPU为您预先提取数据。
我的猜测是你通过以非连续方式访问128字节块来阻止CPU数据预取器。
将您的访问模式更改为顺序，您会惊讶地发现它的运行速度有多快。 然后，您可以担心下一级优化，这将确保分支预测正常运行。
另一件需要考虑的事情是TLB misses 。 这些都很昂贵，特别是在64位系统中。 而不是使用4KB页面考虑使用2MB huge pages 。 有关以下内容的Windows支持，请参阅此链接： 大页面支持（Windows）
如果你必须以一种随机的方式访问4GB数据，但你事先知道m7值的序列（你的索引），那么你可以在使用之前明确地获取内存（它需要提前几个CPU周期）当你将它用于有效时）。 看到
- _mm_prefetch
- “_mm_prefetch（…）”的用法
- MM_PREFETCH
以下是一些可能对内存优化主题有所帮助的链接
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#
对不起，答案的post，我没有足够的评论声誉。
如果您使用以下作为测试会发生什么？
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代码的确切做法，但在我看来，二进制或者比单个更快==比较。 我也不知道英特尔内在函数是什么，但也可能以与您已经完成的方式类似的方式优化上述代码。
我希望我的回答有所帮助。
Mmarss
98％的128字节块全部为零，每平均4K页面平均少于一个非零字节。 对于稀疏的数组，您是否尝试将其存储为稀疏数组？ 您将节省大量内存和随之而来的缓存未命中延迟; 如果一个普通的std :: map变得更快，我不会感到惊讶。
您是否考虑过英特尔字符串扫描指令？ 这些往往具有非常高的数据速率，并且处理器知道数据访问是连续的。
mov rdi, cld xor rax, rax mov rcx, 128/8 repe scasq jne ...
这无助于您的数据不在缓存中的问题。 如果你知道要提前考虑哪个块，你可以通过使用英特尔的预取指令来解决这个问题。 请参阅http://software.intel.com/en-us/articles/use-software-data-prefetch-on-32-bit-intel-architecture
[EDITS编写代码以整合评论中指出的轻微打嗝]
感谢您收到的优秀提示。
我有信心Mmarss“mega or”方法会提高性能，因为它产生的汇编语言指令更少。 然而，当我运行我的基准程序时，我的原始笨重&&解决方案需要163秒而不是150秒，而我原来笨重的英特尔instrinsics解决方案需要145秒（这两个在我的原始post中有描述）。
为了完整性，这里是我用于“mega或”方法的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
然后，我尝试通过以下方式将“超级或”想法转换为英特尔instrinsics：
__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
上面的英特尔instrinsics方法非常粗糙。 欢迎提出改进建议。
这再次表明了衡量的重要性。 几乎每当我猜到哪个会更快我就错了。 也就是说，只要你仔细衡量每一个变化，你就不会变得更糟，只能改善。 虽然我经常倒退（如上所述），但在过去的一周里，我已经能够将小测试程序的运行时间从221秒减少到145.鉴于真正的程序将运行几个月，这将节省几天。
建议：将数组对齐到128B，因此空间预取器总是希望填充正确的高速缓存行以生成128B对高速缓存行。 英特尔优化手册 ，第2-30页（PDF第60页），描述了Sandybridge / Ivybridge：
空间预取程序：此预取程序努力完成获取到L2高速缓存的每个高速缓存行，并使用完成它的对行到128字节对齐的块。
由于您的arrays仅与64B对齐，因此读取128B可触摸两对缓存行，从而导致L2空间预取器为您可能永远不会使用的数据发出更多负载。
你的答案有正确的想法：或者将块与向量一起，然后测试全零。 使用单个分支可能比每8个字节单独分支更好。
但是你测试矢量的策略很糟糕：不要存储它，然后标量加载+ OR两半。 这是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
通常，分支预测良好，生成其标志输入的延迟并不重要。 但在这种情况下，主要的瓶颈是分支错误预测。 因此，花费更多的uops（如果需要）以减少延迟可能是值得的。
我不确定在加载第二个缓存行之前测试第一个缓存行是否更好，以防您发现非零字节而不会遇到第二个缓存未命中。 空间预取器无法立即加载第二个缓存行，因此可能在加载第二个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的工作量是原来的两倍，但只能在port5上运行。 （POR xmm在p015上运行）。 256b负载完成两个128b的一半，但它们仍然只有1个uop。
我没有看到使用单个CMPEQPS检查256b向量的全零的方法。 +0.0比较等于-0.0，因此符号位位置的1位在与零的比较中将不会被检测到。 我认为任何CMPPS谓词都没有帮助，因为它们都没有实现比较+0.0与+0.0不同的比较。 （有关FP等式的更多信息，请参阅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。