c++ - 在缓冲区中找到第一次出现的字节的最快方法

Question

免责声明

• 我已阅读 What is the fastest substring search algorithm? ，这对于单个字符的情况可能不是最优的。
• strchr 需要一个以 NUL 结尾的字符串

---

我正在寻找最快的方法来识别给定字节在字节缓冲区中的第一次出现。

这让人想起查找字符串中字符的第一次出现，除了:

• 字节缓冲区不是以 NUL 结尾的，而是我有一个明确的长度(并且可能嵌入 NUL 字符)
• 字节缓冲区未分配到string 或vector 中，我只传递了一个slice(也称为指针和长度)

基本的解决方案是:

size_t search(char const* buffer, size_t length, char c) {
    return std::find(buffer, buffer + length, c) - buffer;
}

但是，与 Godbolt 编译器 (-O2 -msse2 -mavx) 的快速往返没有显示任何向量化指令的提示，只有一些展开，所以我想知道这是否是最优的。

有没有更快的方法来查找缓冲区中给定字节的第一次出现？

注意:只有第一次出现才重要。

注意:我只关心 Linux 上的现代 x86_64 CPU，尽管我鼓励答案尽可能通用并清楚地提及假设。

Answer 1

您可以使用 memchr ，它通常作为内部函数实现，通常(根据我的经验)比任何手动循环都快得多。

http://en.cppreference.com/w/c/string/byte/memchr

编辑:至少在 VC++ 上(我也打赌 GCC，我还没有检查过)，std::find 无论如何都会使用 memchr 如果你看的话对于一个字节，所以我会检查 memchr 是否真的让程序运行得更快。