问题：

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

左丘昊天

2023-03-14

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

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

我使用的是一台配备英特尔Ivy Bridge Core i7 3770处理器、32 GB内存和免费版微软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

我能够通过Intel instrinsic改进这一点：

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语言的内部函数外，针对这个问题的原始英特尔汇编语言解决方案也很受欢迎。

共有3个答案

东方森

2023-03-14

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

咸正平

2023-03-14

不好意思回答帖子，我没有足够的口碑来评论。< br >如果使用以下内容作为测试，会发生什么情况？

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代码的具体操作，但在我看来，二进制或比单个==比较更快。我也不知道什么是英特尔内部函数，但可能以与您已经做过的类似的方式优化上述代码
我希望我的回答有帮助
马斯

郑波

2023-03-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未命中。这些成本很高，尤其是在 64 位系统中。与其使用 4KB 页面，不如考虑使用 2MB 的大页面。有关以下各项的 Windows 支持，请参阅此链接：大页面支持（Windows）

如果您必须以某种随机方式访问4GB数据，但您提前知道m7值的序列（您的索引），那么您可以在使用之前显式地管道获取内存（它需要比您使用它的时间提前100个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#

类似资料：

检查字节数组是否全为零的最快方法

问题内容：我有一个，并且想知道最快的方法是检查所有值是否均为零？有没有比做更快的方法：问题答案：我先将所有字节加总后就重写了这个答案，但是这是不正确的，因为Java已经对字节进行了签名，因此我需要or。另外，我已将JVM预热更改为正确。最好的选择实际上是简单地遍历所有值。我想您有三种主要选择：或所有元素并检查总和。进行无分支比较。与分支进行比较。我不知道使用Java添加字节的
测试XMM/YMM寄存器是否为零的更快方法？

因此，每个测试都有3+1=4个周期的延迟。其中一些可以通过在、等之间交替并行运行。但它仍然相当慢。有没有更快的方法来实现这一点？我需要在一行中测试8个XMM/YMM寄存器。一字节位图中每个寄存器1位。
方法查看string是否包含所有数字

但应返回false 还有：我的代码高效吗？我觉得这是一个更容易的方法。如有任何帮助，不胜感激
确定字符串是否包含Swift中的字符集的最佳方法是什么

问题内容：我需要确定一个字符串是否包含我定义的自定义集中的任何字符。您可以使用rangeOfString确定一个字符串是否包含另一个字符串。如果您一次测试一个字符，那么这当然也适用于字符。我想知道什么是最好的方法。问题答案：您可以创建一个包含自定义字符集的，然后针对此字符集测试成员资格：斯威夫特3：对于不区分大小写的比较，请使用（假设字符集仅包含小写字母）。斯威夫特2：斯威夫特
检查列表是否最快的方法包含唯一的字符串

问题内容：基本上，我大约有1,000,000个字符串，对于每个请求，我都必须检查一个String是否属于列表。我担心性能，最好的方法是什么？？哈希？问题答案：最好的选择是使用并通过方法检查集合中是否存在字符串。建立HashSet可以通过使用Object方法和进行快速访问。状态的Javadoc ：此类为基本操作（添加，删除，包含和调整大小）提供了恒定的时间性能， HashSet 将对象存储
交换内存中未对齐的64位值字节的最快方法是什么？

我在内存中有大量64位值。不幸的是，它们可能无法与64位地址对齐。我的目标是更改所有这些值的endianess，即交换/反转它们的字节。我知道bswap指令交换32位或64位寄存器的字节。但由于它需要一个register参数，我无法将内存地址传递给它。当然，我可以先将内存加载到寄存器中，然后交换，然后再写回：但考虑到地址可能未对齐，这是否正确？另一种可能性是手动进行交换：这显然是更多的指示
是否有一种方法来测试响应是否包含在架构中？

在空手道中，我希望有一个模式变量，它是响应数据的超集，这样我就可以用相同的模式测试多个请求。这对于GraphQL应该特别有用，因为请求本身定义了返回的字段。预期模式：回答数据：在本例中，响应返回的所有键。数据应该在架构中，但架构中的任何键都不在响应中。数据应该被忽略。在空手道中有没有办法做到这一点，或者有没有计划在将来增加这一功能？编辑：更新了示例，因为唯一遗漏的属性是一个可为空的属性
使用标准C++/C++11/C检查文件是否存在的最快方法？

我想找到一种最快的方法来检查一个文件是否存在于标准C++11、C++或C中。我有数千个文件，在对它们进行操作之前，我需要检查它们是否全部存在。在下面的函数中，我可以写什么来代替？

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

共有3个答案

相关问答

相关文章

相关阅读

相关工具

相关文档