为什么我的string.indexof(char)更快？

Question

不要问我是怎么到达那里的,但是我正在玩一些屏蔽,循环展开等.无论如何,出于兴趣,我正在考虑如何实现indexof方法,长话短说,所有掩盖等除此之外,这个天真的实现:

public static unsafe int IndexOf16(string s, int startIndex, char c) {
            if (startIndex < 0 || startIndex >= s.Length) throw new ArgumentOutOfRangeException("startIndex");
            fixed (char* cs = s) {
                for (int i = startIndex; i < s.Length; i++) {
                    if ((cs[i]) == c) return i;
                }
                return -1;
            }
        }

比string.IndexOf(char)快.我写了一些简单的测试,它似乎完全匹配输出.我的机器的一些样品输出数字(当然会有所不同,但趋势很明显):

short haystack 500k runs
1741 ms for IndexOf16
2737 ms for IndexOf32
2963 ms for IndexOf64
2337 ms for string.IndexOf <-- buildin

longer haystack:
2888 ms for IndexOf16
3028 ms for IndexOf32
2816 ms for IndexOf64
3353 ms for string.IndexOf <-- buildin

IndexOfChar标记为extern,因此您无法反射它.但是我认为这应该是(本机)实现:http: //www.koders.com/cpp/fidAB4768BA4DF45482A7A2AA6F39DE9C272B25B8FE.aspx?s=IndexOfChar#L1000

他们似乎使用相同的天真实现.

我想到了一些问题:

1)我在实现中遗漏了哪些东西,这解释了为什么它更快？我只能想到扩展字符支持,但是它们的实现表明它们也没有做任何特殊的事情.

2)我假设很多低级方法最终将在手动汇编程序中实现,但事实并非如此.如果是这样,为什么要在本地实现它,而不仅仅是像我的示例实现一样在C#中？

(在这里完成测试(我认为它太长了,无法粘贴):http://paste2.org/p/1606018)

(不,这不是过早的优化,它不是我只是搞乱的项目):-)

更新:Thnx向Oliver提供有关nullcheck和Count参数的提示.我已将这些添加到我的IndexOf16Implementation中,如下所示:

public static unsafe int IndexOf16(string s, int startIndex, char c, int count = -1) {
    if (s == null) throw new ArgumentNullException("s");
    if (startIndex < 0 || startIndex >= s.Length) throw new ArgumentOutOfRangeException("startIndex");
    if (count == -1) count = s.Length - startIndex;
    if (count < 0 || count > s.Length - startIndex) throw new ArgumentOutOfRangeException("count");

    int endIndex = startIndex + count;
    fixed (char* cs = s) {
        for (int i = startIndex; i < endIndex; i++) {
            if ((cs[i]) == c) return i;
        }
        return -1;
    }
}

数字略有变化,但仍然明显更快(省略了32/64结果):

short haystack 500k runs
1908 ms for IndexOf16
2361 ms for string.IndexOf
longer haystack:
3061 ms for IndexOf16
3391 ms for string.IndexOf

Update2:这个版本更快(特别是对于长干草堆的情况):

public static unsafe int IndexOf16(string s, int startIndex, char c, int count = -1) {
            if (s == null) throw new ArgumentNullException("s");
            if (startIndex < 0 || startIndex >= s.Length) throw new ArgumentOutOfRangeException("startIndex");
            if (count == -1) count = s.Length - startIndex;
            if (count < 0 || count > s.Length - startIndex) throw new ArgumentOutOfRangeException("count");

            int endIndex = startIndex + count;
            fixed (char* cs = s) {
                char* cp = cs + startIndex;
                for (int i = startIndex; i <= endIndex; i++, cp++) {
                    if (*cp == c) return i;
                }
                return -1;
            }
        }

更新4: 根据与LastCoder的讨论,我相信这是建筑依赖.我的Xeon W3550似乎更喜欢这个版本,而他的i7似乎喜欢buildin版本.我的家用机器(Athlon II)似乎介于两者之间.我对这个巨大的差异感到惊讶.

Answer 1

可能性 1) 这在 C# 中可能不成立（确实如此），但是当我对 x86-64 汇编器进行优化工作时，我很快发现在基准测试中从 DLL（标记为外部）调用代码比在我的系统中实现相同的函数要慢可执行的。最明显的原因是分页和内存，DLL（外部）方法加载到内存中，远离正在运行的代码的其余部分，如果之前没有访问过它，则需要对其进行分页。您的基准测试代码应该这样做您正在基准测试的函数的一些预热循环，以确保它们在计时之前首先被分页到内存中。

可能性 2) Microsoft 倾向于不充分优化字符串函数，因此优化本机字符串长度、子字符串、indexof 等并不是真正闻所未闻的。轶事; 在 x86-64 汇编器中，我能够创建 WinXP64 的 RtlInitUnicodeString 函数的一个版本，该函数在几乎所有实际用例中运行速度都快 2 倍。

可能性 3) 您的基准测试代码显示您正在使用 IndexOf 的 2 参数重载，此函数可能调用 3 参数重载 IndexOf(Char, Int32, Int32)，这会为每次迭代增加额外的开销。

这可能会更快，因为您删除了每次迭代的 i 变量增量。

            char* cp = cs + startIndex;
            char* cpEnd = cp + endIndex;
            while (cp <= cpEnd) {
                if (*cp == c) return cp - cs;
                cp++;
            }

出于您的好奇心，编辑回复关于（2）的内容，编码早在2005年，用于修补我的WinXP64机器的ntdll.dll。http://board.flatassembler.net/topic.php?t=4467

RtlInitUnicodeString_Opt: ;;rcx=buff rdx=ucharstr 77bytes
             xor    r9d,r9d
             test   rdx,rdx
             mov    dword[rcx],r9d
             mov    [rcx+8],rdx
             jz     .end
             mov    r8,rdx
   .scan:
             mov    eax,dword[rdx]

             test   ax,ax
             jz     .one
             add    rdx,4
             shr    eax,16
             test   ax,ax
             jz     .two
             jmp    .scan
   .two:
             add    rdx,2
   .one:
             mov    eax,0fffch
             sub    rdx,r8
             cmp    rdx,0fffeh
             cmovnb rdx,rax
             mov    [ecx],dx
             add    dx,2
             mov    [ecx+2],dx
             ret
   .end:
             retn  

编辑 2运行示例代码（用最快的版本更新），string.IndexOf 在我的 Intel i7、4GB RAM、Win7 64 位上运行得更快。

short haystack 500k runs
2590 ms for IndexOf16
2287 ms for string.IndexOf
longer haystack:
3549 ms for IndexOf16
2757 ms for string.IndexOf

优化有时非常依赖于架构。