memchr() 底层是如何工作的？

Question

背景： 我正在尝试创建一个纯 D 语言实现的功能，大致相当于 C 的内存 但使用数组和索引而不是指针。原因是 std.string 将与编译时函数求值一起使用。对于那些不熟悉 D 的人来说，如果满足某些限制，则可以在编译时评估函数。一项限制是它们不能使用指针。另一个是它们不能调用 C 函数或使用内联汇编语言。让字符串库在编译时工作对于某些编译时代码生成黑客很有用。

问题： memchr 是如何在幕后工作以实现如此快的性能的？在 Win32 上，即使使用明显的优化技术（例如禁用边界检查、循环展开等），我能够使用简单循环在纯 D 中创建的任何内容都至少慢 2 倍。对于像在字符串中查找字符这样简单的事情，有哪些不明显的技巧可用？

Answer 1

我建议考虑看看 GNU库的源。对于大多数功能，它将包含功能的两者的通用优化的C版本，和优化的汇编语言版本为尽可能多的支持的体系结构尽可能，服用的特定于机器的技巧优势。

在 X86-64 SSE2版本联合收割机从 pcmpeqb 上的数据的同时整个高速缓存行的结果（4个16B载体），分期偿还早期出口pmovmskb / test / jcc的开销。

gcc和铛目前不能自动向量化与if() break早期退出条件循环，因此它们使从显而易见C实现幼稚字节在-A-时间ASM。

Answer 2

newlib 中 memchr 的实现 这是某人优化 memchr 的一个例子：它一次读取和测试 4 个字节（除了 memchr 之外，newlib 库中的其他函数是 这里).

顺便说一句，MSVC 运行时库的大部分源代码都是可用的，作为 MSVC 安装的可选部分（因此，您可以查看它）。

Answer 3

这是 FreeBSD 的（BSD 许可的） memchr() 来自 memchr.c. 。FreeBSD 的在线源代码浏览器是经过时间考验的 BSD 许可代码示例的良好参考。

void *
memchr(s, c, n)
    const void *s;
    unsigned char c;
    size_t n;
{
    if (n != 0) {
        const unsigned char *p = s;

        do {
            if (*p++ == c)
                return ((void *)(p - 1));
        } while (--n != 0);
    }
    return (NULL);
}

Answer 4

memchr 与 memset 和 memcpy 一样，通常会减少到相当少量的机器代码。如果没有的话，你不可能重现那种速度 内联类似的汇编代码. 。实施中需要考虑的一个主要问题是 数据对齐.

一 您可能可以使用的通用技术 是插入一个 哨兵 位于正在搜索的字符串的末尾，这保证您能找到它。它允许您将字符串结尾的测试从循环内部移至循环之后。

Answer 5

GNU libc肯定使用 大会 版本的memchr()(在任何共同的linux发行版).这就是为什么它是如此的令人难以置信的速度快。

例如，如果我们最线11Gb文件(就像"wc-l"不会)它需要周围 2.5 秒 大会 版本的memchr()从GNU libc.但是，如果我们换memchr()大会呼吁与例如memchr() C执行情况 从FreeBSD-的速度将减少到喜欢的 30 几秒钟内。

这等于替换memchr()只有一段时间的循环，其比较的一个焦炭。