我正在阅读 sehe's answer至 this question并且惊讶地看到 sehe 发现使用 std::memchr
的手写循环比使用 std::count
快 3 倍以上 (看评论)。使用 std::count
的代码可以在编辑 2 中看到,但它基本上可以归结为:
const auto num_lines = std::count(f, l, '\n');
对比
uintmax_t num_lines = 0;
while (f && f != l)
if ((f = static_cast<const char*>(memchr(f, '\n', l - f))))
num_lines++, f++;
我本来希望 std::count
版本至少和 std::memchr
版本一样快——原因与 using std::copy
should be at least as fast as std::memcpy
的原因类似。 .
我检查了我的标准库 (libc++) 的 std::count
实现,没有尝试优化 char
输入类型(同上 std::查找
).
这是为什么?如果提供了 char*
迭代器和 char
值,实现是否可以不分派(dispatch)给 std::memchr
?
最佳答案
只有在匹配之间的平均距离不小的情况下,使用对 memchr
的实际函数调用才是胜利。
特别是对于 count
,调用 memchr
可能会慢很多,如果你正在计算 t
个字符,当它们平均每 2 或每 4 个。(例如,使用 ACGT 字母表的 DNA 碱基对)。
我对使用 memchr
循环作为 std::count
在 char
数组上的默认实现持怀疑态度。更有可能有其他方法来调整源代码,使其编译成更好的 asm。
对于 find
它会更有意义,即使它确实可能会显着增加开销,如果在前几个字节中有命中,则与简单的一次字节循环相比。
您也可以将其视为编译器优化失误。如果编译器为 std::count
和 std::find
中的循环编写更好的代码,调用手写 asm 库函数的 yield 就会减少。
如果在进入循环之前不知道行程计数,gcc 和 clang 从不自动向量化循环。 (即他们不进行搜索循环,这是对小至字节的元素大小的主要错过优化)。 ICC 没有这个限制,并且可以向量化搜索循环。不过,我还没有研究它如何处理 libc++ 的 std::count 或 find。
std::count
必须检查每个元素,因此它应该自动矢量化。但是,如果 gcc 或 clang 甚至不使用 -O3
,那就太不幸了。它应该在 x86 上使用 pcmpeqb
(打包的比较字节)很好地矢量化,然后是 paddb
0/-1 比较结果。 (至少每 255 次迭代,psadbw
对零水平求和字节元素)。
库函数调用开销至少是从内存中使用函数指针的间接调用(可以缓存未命中)。在具有动态链接的 Linux 上,通常还有一个额外的 jmp
通过 PLT(除非您使用 -fno-plt
进行编译)。 memchr
比 strchr
更容易优化且启动开销较低,因为您可以快速检查 16B vector 加载是否可以结束(相对于对齐 的指针>strchr
或 strlen
以避免跨越页面或缓存行边界)
如果调用 memchr
是在 asm 中实现某些东西的最佳方式,那么理论上这就是编译器应该发出的。 gcc/clang 已经根据目标选项 (-march=
) 优化了调用 libc memcpy
的大型复制循环。例如当拷贝大到 libc 版本可能决定在 x86 上使用 NT 存储时。
关于c++ - 为什么 std::count 和 std::find 没有优化为使用 memchr?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43483378/