memchr()如何在引擎盖下工作？

Question

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

问题: memchr如何在引擎盖下工作以尽可能快地执行？在Win32上,我使用简单循环在纯D中创建的任何东西,即使有明显的优化技术,例如禁用边界检查,循环展开等,也至少要慢2倍.有哪些非显而易见的技巧可用于像在字符串中查找字符一样简单？

Answer 1

我建议看看GNU libc的来源.对于大多数函数,它将包含函数的通用优化C版本,以及尽可能多的支持体系结构的优化汇编语言版本,利用机器特定的技巧.

所述X86-64 SSE2版本从结合的结果pcmpeqb上的数据的同时(4个16B载体)整体高速缓存行,分期偿还早期出口的开销pmovmskb/ test/ jcc.

gcc和clang目前无法在if() break早期退出条件下自动向量化循环,因此它们从明显的C实现中一次性地进行字节化.

Answer 2

这个来自newlib的memchr实现是某人优化memchr的一个例子:它一次读取和测试4个字节(除了memchr,newlib库中的其他函数都在这里).

顺便提一下,MSVC运行时库的大多数源代码都是可用的,作为MSVC安装的可选部分(因此,您可以查看它).

Answer 3

这是来自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);
}