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

Question

免责声明

• 我已阅读什么是最快的子串搜索算法？，但对单个字符情况可能不够优化。
• strchr要求以空字符结尾的字符串

---

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

这种情况类似于在字符串中查找字符的第一次出现，不同之处在于：

• 字节缓冲区没有以空字符结尾，而是有一个明确的长度（可能包含嵌入的空字符）
• 字节缓冲区没有分配在 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，但我鼓励答案尽可能通用并清楚地提到假设。

- Matthieu M.

---

也许可以尝试使用memchr - 它类似于strchr，但不需要以NUL结尾的字符串。 - Paul R

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

@KonradRudolph：我也很惊讶，特别是根据David Haim的说法，优化是在VC++上完成的。也许是关于内联的问题？（例如，纯C++实现可以在编译时进行评估，而汇编实现则不能） - Matthieu M.

@MatthieuM。至少在VC++上，如果数据在编译时已知，则所有的strXXX和memXXX函数都将在编译时进行编译时评估。我认为这不是一个技术问题，阻止GCC使用它。 - David Haim

@DavidHaim：可能是因为解析为内置函数，编译器知道它们的功能。 - Matthieu M.

Answer 1

您可以使用通常作为内置函数实现的memchr，它通常比任何手写循环更快（根据我的经验）。 http://en.cppreference.com/w/c/string/byte/memchr 编辑：至少在VC++上（我敢打赌在GCC上也是这样，我没有检查），std::find将使用memchr来查找字节，因此我会检查memchr是否确实可以使程序运行更快。

- David Haim

---

memchr 的实现解释可以在这里找到。来自BurntSushi的Rust memchr crate的注释暗示libc的memchr在Windows上速度较慢。 - Matthieu M.

从Godbolt来看，不，gcc（6.2）上的char上的std::find并没有被简化为memchr。 - Matthieu M.

@MatthieuM. 所以这里有一个可以尝试的东西 :) - David Haim

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Matthieu M.