最快的方式找到缓冲

我已阅读What is the fastest substring search algorithm?，这可能是次优的单字符大小写字节的第一次出现。
strchr需要一个NULL结尾的字符串

我找识别一个字节的缓冲区指定字节中第一次出现的最快方法。

这使人想起的字符串中寻找一个字符的第一个发生不同之处在于：

字节缓冲器不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，尽管我鼓励尽可能通用的答案，并提出假设。

来源

2016-11-16 Matthieu M.

也许尝试['memchr']（https://linux.die.net/man/3/memchr） - 它就像'strchr'，但它不需要NUL终止的字符串？ –

令人沮丧的是'std :: find'没有被优化以利用GCC上的编译器内在函数。有人应该写一个补丁，这是一个明显的优化。 –

@KonradRudolph：我也很惊讶，尤其是因为根据David Haim的说法，在VC++上进行了优化。也许关于内联的问题？（正如在一个纯粹的C++实现中可以进行编译时评估，而一个程序集则不能） –

你可以使用memchr，它通常作为一个内部函数来实现，并且通常（根据我的经验）比任何手动滚动循环都快得多。

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

编辑：至少在VC++（和我赌GCC为好，我没有检查），std::find将使用memchr无论如何，如果你找一个字节，所以我会检查是否memchr实际使程序运行得更快。

来源

2016-11-16 13:14:06

memchr实现的解释可以在这里找到（http://stackoverflow.com/questions/525123/how-does-memchr-work-under-the-hood）。来自[BurntSushi的Rust memchr crate]（https://github.com/BurntSushi/rust-memchr/blob/master/src/lib.rs）的提示表明，尽管libc的memchr在Windows上速度很慢。 –

从Godbolt，不，''char'上的'std :: find'不会被gcc（6.2）简化为'memchr'。 –

@MatthieuM。所以这是一个尝试:) –

最快的方式找到缓冲

回答

相关问题