查找缓冲区中第一次出现字节的最快方法(Fastest way to find first occurrence of byte in buffer)

 放弃 
 
 
 
 我读过什么是最快的子串搜索算法？ ，对于单个字符的情况可能不是最理想的。 
 
 
 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，但我鼓励尽可能通用的答案并清楚地提及假设。 

Disclaimer
 
 
 
I have read What is the fastest substring search algorithm?, which may be suboptimal for the single character case.
 
 
strchr requires a NUL-terminated string
 
 
 
I am looking for the fastest way to identify the first occurrence of a given byte in a byte buffer.
 
This is reminiscent of looking for the first occurrence of a character in a string except that:
 
 
 
the byte buffer is not NUL-terminated, instead I have an explicit length (and possibly embedded NUL characters)
 
 
the byte buffer is not allocated in a string or vector, I am only handed down a slice (aka, pointer & length)
 
 
The basic solution is:
 
size_t search(char const* buffer, size_t length, char c) {
    return std::find(buffer, buffer + length, c) - buffer;
}
 
However, a quick round-trip with the Godbolt compiler (-O2 -msse2 -mavx) does not show any hint of a vectorized instruction, only some unrolling, so I am wondering whether this is the optimal.
 
Is there a faster way to find the first occurrence of a given byte in a buffer?
 
Note: only the first occurrence matters.
 
Note: I am exclusively concerned with modern x86_64 CPUs on Linux, though I encourage answers to be as generic as possible and mention assumptions clearly.

原文：https://stackoverflow.com/questions/40633025