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

Question

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

问题：memchr如何在底层工作以达到如此快的速度？在Win32上，我使用简单的循环所能创建的任何东西都至少比显然的优化技术（例如禁用边界检查、循环展开等）慢两倍。对于如此简单的找到字符串中的字符这样的事情，有哪些非明显的技巧可用？

- dsimcha

Answer 1

我建议查看GNU libc的源代码。对于大多数函数，它将包含一个通用的优化C版本的函数，以及针对尽可能多的支持架构进行优化的汇编语言版本，利用机器特定的技巧。 x86-64 SSE2版本将整个缓存行数据（四个16B向量）上的pcmpeqb结果组合在一起，以摊销提前退出pmovmskb/test/jcc的开销。

gcc和clang目前无法自动向量化带有if() break提前退出条件的循环，因此它们从明显的C实现中制作幼稚的逐字节asm。

- Chris Young

---

谢谢，不过这是LGPL代码，而且D的标准库应该是许可证宽松的。我不想让这成为问题。 - dsimcha

我建议你看一下它，以获取技术灵感，而不是复制源代码。 - Chris Young

大约有150行代码，其中一半或更多是注释，因此它详细解释了优化的内容。 - Chris Young

我是这个问题的原始提问者。http://stackoverflow.com/questions/405208/gpl-code-what-counts-as-a-derivative-work - dsimcha

我之前读过这个问题，这是一个好问题。答案是你不能版权技术，只能版权代码本身。此外，自由软件基金会强烈反对软件专利或算法和思想可以被有效版权保护并限制使用的想法。 - Chris Young

Answer 2

这里有一个新libc的memchr实现，是优化过的memchr的一个例子：（链接）它每次读取和测试4个字节（除了memchr之外，newlib库中的其他函数在这里）。顺便说一下，大多数MSVC运行时库的源代码都可以作为MSVC安装的可选部分获得（因此，您可以查看该源代码）。

- ChrisW

---

我本来想用newlib的memchr代码来回答，直到我点击了你的链接并发现它也与newlib有关 :) - Johannes Schaub - litb

如果您喜欢，可以将它们链接到此处：http://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/?cvsroot=src，其中包含newlib的所有快速字符串函数，包括memchr.c。 - Johannes Schaub - litb

URL已更改为：https://sourceware.org/viewvc/src/newlib/libc/string/memchr.c?revision=1.4&view=markup - bluss

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);
}

- cpeterso

---

是的，我也发现了这个问题。不过，没有什么特别的东西可以解释这种荒谬的速度差异。 - dsimcha

Answer 4

memchr、memset 和 memcpy 通常可以转化为相当少量的机器代码。除非 内联类似的汇编代码，否则您不太可能能够复制那种速度。在实现中需要考虑的一个主要问题是 数据对齐。

您可能能够使用的通用技术之一是在被搜索的字符串末尾插入一个哨兵，以确保您能找到它。这样可以将字符串结束的测试从循环内部移到循环后面。

- EvilTeach

Answer 5

GNU libc 绝对使用 memchr() 的 汇编 版本（在任何常见的 Linux 发行版上）。这就是为什么它如此不可思议地快速。

例如，如果我们计算一个 11Gb 文件中的行数（就像 "wc -l" 命令一样），使用 GNU libc 中的 汇编 版本的 memchr() 大约需要 2.5 秒。但是，如果我们将 memchr() 汇编调用替换为来自 FreeBSD 的 memchr() C 实现，速度将降至大约 30 秒。

这相当于将 memchr() 替换为只比较一个字符的 while 循环。

- pulse