logo标签列表

为什么本地数组读写比静态数组快？

c#arraysperformance
14

我正在编写一些基准测试，以弄清为什么相似的纯算法（没有C++库/.net内置类）在C++中运行速度比在C#中快得多，即使考虑到预期的特性差异。在这样做的过程中，我遇到了这两个让我困惑的测试，有人知道为什么其中一个明显比另一个慢吗？第二个测试（在我的机器上需要51ms，而不是88ms）唯一的区别是两个数组在方法中被声明为局部变量，而不是在外面声明。在两种情况下，数组在我们开始计时之前就已经创建好。

    const int Runs = 100;
    const int Width = 5000;
    const int Height = 5000;
    const int Size = Width * Height;


    static int[] Input = Enumerable.Range(0, Size).ToArray();
    static int[] Output = new int[Size * 2];

    static int SimpleTest()
    {
        // Removing those 2 lines and using the static arrays instead give substantially slower performance, nearly half the speed!
        int[] Input = Enumerable.Range(0, Size).ToArray();
        int[] Output = new int[Size * 2];

        Stopwatch sw = new Stopwatch();
        sw.Start();

        for (int run = 0; run < Runs; run++)
        {
            int InputIndex = 0;
            for (int x = 0; x < Width; x++)
            {
                for (int y = 0; y < Height; y++)
                {
                    int pixel = Input[InputIndex];
                    var OutputIndex = InputIndex * 2;
                    Output[OutputIndex] = pixel;
                    Output[OutputIndex + 1] = pixel;
                    InputIndex++;
                }
            }
        }
        sw.Stop();
        return (int)(sw.ElapsedMilliseconds / Runs);
    }
1
有趣的发现...我相信一定有一个合理的解释。我认为这与您访问这些变量的方式有关。当在方法内部时，它们被视为该方法的本地变量，因此我认为访问速度比访问全局变量要快得多。像@JonSkeet这样熟悉内部情况的人可能会有一个解释。 - B.K.
这可能是因为本地和全局作用域的问题吗？我的意思是，当代码存储在内存中时，函数的全局变量与本地变量放置在不同位置。 - Abhishek
@Abhishek 可能是... 我相信静态变量存储在堆上，但那些在静态方法内的变量...它们存储在栈上还是堆上？ - B.K.
据我所知，@B.K. 是关于堆栈的。 - Abhishek
这是一个有 250 万元素的数组，我很确定它没有被存储在堆栈中。 - Ronan Thibaudau
@RonanThibaudau 我并不是说值会被存储在堆栈中，我是说变量的引用 :) - Abhishek
3个回答
15
当变量为局部变量时，编译器知道 Input 和 Output 永远不会改变，这就打开了许多优化。
  • 可以将 Input 和 Output 变量的值保存在寄存器中。
  • Input.Length 和 Output.Length 可以计算一次并缓存。
  • 编译器可以证明 Input[InputIndex] 和 Output[OutputIndex] 永远不会导致数组索引越界，因此边界检查可以被优化掉。
  • 编译器可以观察到 Input 和 Output 的结果从未被使用过，所以可以将循环优化为空！

如果使用静态版本，则编译器无法执行这些优化。编译器必须在每个访问时重新加载 Input 和 Output，并且必须对每个数组索引操作执行边界检查，以防其他线程修改了 Input 或 Output。

例如，如果另一个线程执行 Input = new int [Size]，那么所有未来的计算都必须使用此备用的 Input。如果另一个线程执行 Output = new int[1]，则代码必须引发 IndexOutOfRangeException。

1
输入和输出都是相当大的数组，因此它们仍然必须存储在内存中。那里并没有使用输入或输出的长度。边界检查不能被排除，因为据我所知C#编译器只会在您明确使用.Length时进行检查（我这里没有使用）。它可以优化循环，但显然没有这样做（否则我们应该有0毫秒，而不是50而不是80）。 - Ronan Thibaudau
2
我在r12寄存器中看到了64位JIT缓存的Input，而在rsi寄存器中则是Output。它还硬编码了Input.Length和Output.Length的值（例如 cmp rax, 2faf080h），以优化边界检查。 - Raymond Chen
3
我的原始回答描述了编译器可用的优化。它实际使用了哪些优化是一个试验的问题。在实践中，优化可能会因为编译器选项或使用的编译器版本而有所不同。请注意，当您附加调试器时，编译器会禁用某些优化。 - Raymond Chen
我的回答（在本页面的其他地方发布）中为什么结果相反，静态更快？ - Nic Foster
2
@NicFoster 你使用了Mono进行测试，而我则使用了微软的编译器。顺便说一下，这里有一篇关于数组边界检查优化的博客文章（http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds-check-elimination-in-the-clr.aspx）。其中“全局位置中的数组”部分似乎与此相关。 - Raymond Chen
显示剩余3条评论
5

使用32位JIT编译器时，我认为罪魁祸首就是Raymond Chen提到的问题，即当输入和输出是本地变量时，它们可以保存在寄存器中，但如果它们不是本地变量，则需要每次重新加载。生成的汇编代码如下：

对于本地变量：

007426F0  mov         eax,dword ptr [ebp-18h]  
007426F3  mov         edi,dword ptr [eax+4]  
                        int pixel = Input[InputIndex];
007426F6  mov         eax,dword ptr [ebp-18h]  
007426F9  cmp         edx,edi  
007426FB  jae         0074276E  
007426FD  mov         ecx,dword ptr [eax+edx*4+8]

对于静态内容：

011C2718  mov         dword ptr [ebp-18h],edx  
011C271B  mov         esi,dword ptr ds:[3BB7E90h]  
011C2721  mov         eax,dword ptr [esi+4]  
011C2724  mov         dword ptr [ebp-1Ch],eax  
                        int pixel = Input[InputIndex];
011C2727  mov         eax,dword ptr [ebp-1Ch]  
011C272A  cmp         ecx,eax  
011C272C  jae         011C27A2  
011C272E  mov         edi,dword ptr [esi+ecx*4+8]

正如您所看到的，mov esi,dword ptr ds:[3BB7E90h] 访问数据段。 正如您还可以看到的那样，在两种情况下都进行了边界检查（cmp-jae），因此这是无关紧要的，并且循环实际上并没有被优化为什么都不做。
64位JIT是如何避免这个问题的我不知道。
以下是两种情况的完整反汇编：
快速版本：
               for (int x = 0; x < Width; x++) {
007426EB  mov         dword ptr [ebp-14h],edx  
                    for (int y = 0; y < Height; y++) {
007426EE  xor         ebx,ebx  
007426F0  mov         eax,dword ptr [ebp-18h]  
007426F3  mov         edi,dword ptr [eax+4]  
                        int pixel = Input[InputIndex];
007426F6  mov         eax,dword ptr [ebp-18h]  
007426F9  cmp         edx,edi  
007426FB  jae         0074276E  
007426FD  mov         ecx,dword ptr [eax+edx*4+8]  
                        var OutputIndex = InputIndex * 2;
00742701  mov         esi,edx  
00742703  add         esi,esi  
                        Output[OutputIndex] = pixel;
00742705  mov         eax,dword ptr [ebp-1Ch]  
00742708  cmp         esi,dword ptr [eax+4]  
0074270B  jae         0074276E  
0074270D  mov         dword ptr [eax+esi*4+8],ecx  
                        Output[OutputIndex + 1] = pixel;
00742711  inc         esi  
00742712  mov         eax,dword ptr [ebp-1Ch]  
00742715  cmp         esi,dword ptr [eax+4]  
00742718  jae         0074276E  
0074271A  mov         dword ptr [eax+esi*4+8],ecx  
                        InputIndex++;
0074271E  inc         edx  
                    for (int y = 0; y < Height; y++) {
0074271F  inc         ebx  
                    for (int y = 0; y < Height; y++) {
00742720  cmp         ebx,1388h  
00742726  jl          007426F6  
                for (int x = 0; x < Width; x++) {
00742728  inc         dword ptr [ebp-14h]  
0074272B  cmp         dword ptr [ebp-14h],1388h  
00742732  jl          007426EE

缓慢版本：

                for (int x = 0; x < Width; x++) {
011C2713  mov         dword ptr [ebp-14h],ecx  
                    for (int y = 0; y < Height; y++) {
011C2716  xor         edx,edx  
011C2718  mov         dword ptr [ebp-18h],edx  
011C271B  mov         esi,dword ptr ds:[3BB7E90h]  
011C2721  mov         eax,dword ptr [esi+4]  
011C2724  mov         dword ptr [ebp-1Ch],eax  
                        int pixel = Input[InputIndex];
011C2727  mov         eax,dword ptr [ebp-1Ch]  
011C272A  cmp         ecx,eax  
011C272C  jae         011C27A2  
011C272E  mov         edi,dword ptr [esi+ecx*4+8]  
                        var OutputIndex = InputIndex * 2;
011C2732  mov         ebx,ecx  
011C2734  add         ebx,ebx  
                        Output[OutputIndex] = pixel;
011C2736  mov         edx,dword ptr ds:[3BB7E94h]  
011C273C  cmp         ebx,dword ptr [edx+4]  
011C273F  jae         011C27A2  
011C2741  mov         dword ptr [edx+ebx*4+8],edi  
                        Output[OutputIndex + 1] = pixel;
011C2745  inc         ebx  
011C2746  cmp         ebx,dword ptr [edx+4]  
011C2749  jae         011C27A2  
011C274B  mov         dword ptr [edx+ebx*4+8],edi  
                        InputIndex++;
011C274F  inc         ecx  
                    for (int y = 0; y < Height; y++) {
011C2750  inc         dword ptr [ebp-18h]  
011C2753  cmp         dword ptr [ebp-18h],1388h  
011C275A  jl          011C2727  
                for (int x = 0; x < Width; x++) {
011C275C  inc         dword ptr [ebp-14h]  
011C275F  cmp         dword ptr [ebp-14h],1388h  
011C2766  jl          011C2716
1
有没有两个不同的答案的原因？ - B.K.
我已经删除了第一个并将反汇编添加到此答案中。 - Asik
2
我想知道这是否类似于静态函数和成员函数之间的性能差异？静态方法调用不进行空值检查，而实例函数调用则进行空值检查。
此外，我的结果与您看到的不同。在我的机器上，静态数组的运行时间较短。每次运行大约为64.x毫秒，而不是75.x毫秒。
以下是我使用的完整程序。在OSX上运行Mono C#。
using System;
using System.Diagnostics;
using System.Linq;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Time per run was: " + SimpleTest());
        }

        const int Runs = 10;
        const int Width = 5000;
        const int Height = 5000;
        const int Size = Width * Height;


        static int[] Input = Enumerable.Range(0, Size).ToArray();
        static int[] Output = new int[Size * 2];

        static float SimpleTest()
        {
            // Removing those 2 lines and using the static arrays instead give substantially slower performance, nearly half the speed!
            //int[] Input = Enumerable.Range(0, Size).ToArray();
            //int[] Output = new int[Size * 2];

            Stopwatch sw = new Stopwatch();
            sw.Start();

            for (int run = 0; run < Runs; run++)
            {
                int InputIndex = 0;
                for (int x = 0; x < Width; x++)
                {
                    for (int y = 0; y < Height; y++)
                    {
                        int pixel = Input[InputIndex];
                        var OutputIndex = InputIndex * 2;
                        Output[OutputIndex] = pixel;
                        Output[OutputIndex + 1] = pixel;
                        InputIndex++;
                    }
                }
            }
            sw.Stop();
            return (sw.ElapsedMilliseconds / (float)Runs);
        }
    }
}
我对于为什么在我的情况下是这样的非常感兴趣，即使Mono实现相反。 - Ronan Thibaudau
您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Nic Foster
我真的怀疑这可能是硬件相关的，但不足为奇的是两种不同的实现（.NET与Mono）会表现出不同的行为。我对为什么.NET上会有速度差异非常感兴趣，因为在Mono上几乎没有速度差异，我认为这在那里不是个问题。 - Ronan Thibaudau
各种CPU的缓存大小怎么样？静态数组分配的内存是否可能与本地创建的数组不同？在使用静态数组的情况下，更多被修改的数据是在函数外部分配的，并且位于类中。而对于局部数组，数组本身在内存的一个段中，并且在调用函数时进行分配，但Runs、Width和Height位于函数外部。 - Nic Foster
我刚试着将所有变量移到函数范围内，但没有性能差异，静态版本对我仍然快大约15%。 - Nic Foster
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接