c++ - 为什么 std::count 和 std::find 没有优化为使用 memchr？

Question

我正在阅读 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？

Answer 1

只有在匹配之间的平均距离不小的情况下，使用对 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 存储时。