查找缓冲区中第一次出现字节的最快方法

Question

放弃

• 我读过什么是最快的子串搜索算法？,对于单个字符的情况可能不是最理想的.
• strchr 需要一个以NUL结尾的字符串

---

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

这让人联想到在字符串中第一次出现字符,除了:

• 字节缓冲区不是NUL终止的,而是我有一个显式长度(可能是嵌入的NUL字符)
• 字节缓冲区没有在一个string或中分配vector,我只传下一个切片(又名,指针和长度)

基本解决方案是:

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，我还没有检查过），如果你寻找一个 byte ，无论如何都会std::find使用，所以我会检查是否真的让程序运行得更快。memchrmemchr