14

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

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

4

5 回答 5

13

我建议看一下GNU libc的源代码。对于大多数函数，它将包含该函数的通用优化 C 版本，以及为尽可能多的受支持架构优化的汇编语言版本，利用机器特定的技巧。

x86-64 SSE2 版本一次组合pcmpeqb了整个缓存行数据的结果（四个 16B 向量），以分摊提前退出//pmovmskb的开销test。jcc

gcc 和 clang 目前无法对具有if() break提前退出条件的循环进行自动矢量化，因此它们从明显的 C 实现中生成了简单的 byte-at-a-time asm。

于 2009-02-08T03:56:04.857 回答
7

这个来自 newlib 的 memchr 实现是某人优化 memchr 的一个例子：它一次读取和测试 4 个字节（除了 memchr，newlib 库中的其他函数都在这里）。

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

于 2009-02-08T03:59:58.717 回答
6

这是来自memchr.c的 FreeBSD（BSD 许可）memchr() 。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);
}
于 2009-02-08T04:09:04.767 回答
2

像 memset 和 memcpy 这样的 memchr 通常会减少到相当少量的机器代码。如果不内联类似的汇编代码，您不太可能重现这种速度。在实现中要考虑的一个主要问题是数据对齐。

您可以使用的一种通用技术是在要搜索的字符串的末尾插入一个标记，以保证您会找到它。它允许您将字符串结尾的测试从循环内部移动到循环之后。

于 2009-02-08T05:15:06.600 回答
0

GNU libc 肯定使用 memchr() 的汇编版本（在任何常见的 linux 发行版上）。这就是为什么它如此之快令人难以置信。

例如，如果我们计算 11Gb 文件中的行数（如“ wc -l ”所做的），使用来自 GNU libc 的 memchr() 的汇编版本大约需要2.5秒。但是如果我们用 FreeBSD 的 memchr() C 实现替换 memchr() 程序集调用- 速度将降低到30秒左右。这相当于用一个 while 循环替换 memchr() ，该循环一个接一个地比较一个字符。

于 2018-11-24T23:10:19.137 回答