memchr（）如何工作？

背景：我试图创建一个纯粹的D语言实现的功能，大致相当于C's memchr，但使用数组和指标而不是指针。原因是std.string可以在编译时函数评估中使用。对于那些你不熟悉的W/D，如果满足某些限制，可以在编译时评估函数。一个限制是他们不能使用指针。另一个是他们不能调用C函数或使用内联汇编语言。让字符串库在编译时工作对于编译时代码gen hacks很有用。memchr（）如何工作？

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

来源

2009-02-08 dsimcha

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

的x86-64 SSE2 version结合上的数据的同时（4个16B载体）一个整体的高速缓存行从pcmpeqb结果，分期偿还早期出口pmovmskb/test/jcc的开销。

gcc和clang目前无法使用if() break提前退出条件进行自动矢量化循环，因此它们从明显的C实现中获得了天真的byte-at-a-asm。

来源

2009-02-08 03:56:04 Chris

谢谢，除了这是LGPL代码和D的标准库应该是允许许可。我不希望这是一个问题。 – dsimcha 2009-02-08 03:59:50

嗯，我建议你看看它的技术灵感，而不是复制源。 – Chris 2009-02-08 04:03:10

它大约有150行代码，其中大约一半或更多是注释，因此它以相当详细的方式解释了优化。 – Chris 2009-02-08 04:04:15

This implementation of memchr from newlib是某人优化memchr的一个例子：它每次读取和测试4个字节（除memchr之外，newlib库中的其他函数是here）。

顺便提一下，MSVC运行时库的大多数源代码都可用，作为MSVC安装的可选部分（所以，您可以看一下）。

来源

2009-02-08 03:59:58 ChrisW

这是来自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-08 04:09:04

了memchr像memset的和通常的memcpy减少的机器代码相当少量。如果没有inlining similar assembly code，您不可能再现这种速度。在实施中要考虑的一个主要问题是data alignment。

一个generic technique you may be able to use将在搜索字符串的末尾插入一个sentinel，这可以保证您能够找到它。它允许将字符串尾部的测试从循环内移动到循环后面。

来源

2009-02-08 05:15:06 EvilTeach

memchr（）如何工作？

回答

相关问题