为什么将List <T>转换为IList <T>导致性能降低？

Question

我正在做一些性能指标,我遇到了一些对我来说很奇怪的事情.我计时以下两个功能:

  private static void DoOne()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
          int s=0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < A.Count; c++) s += A[c];
         }

      }

   private static void DoTwo()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
         IList<int> L = A;
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < L.Count; c++) s += L[c];
         }

      }

即使在发布模式下进行编译,时序结果仍然表明DoTwo比DoOne长约100倍:

 DoOne took 0.06171706 seconds.
 DoTwo took 8.841709 seconds.

鉴于List直接实现了IList,我对结果感到非常惊讶.任何人都可以澄清这种行为吗？

血淋淋的细节

回答问题,这里是完整的代码和项目构建首选项的图像:

死图像链接

using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.Collections;

namespace TimingTests
{
   class Program
   {
      static void Main(string[] args)
      {
         Stopwatch SW = new Stopwatch();
         SW.Start();
         DoOne();
         SW.Stop();

         Console.WriteLine(" DoOne took {0} seconds.", ((float)SW.ElapsedTicks) / Stopwatch.Frequency);
         SW.Reset();
         SW.Start();
         DoTwo();
         SW.Stop();

         Console.WriteLine(" DoTwo took {0} seconds.", ((float)SW.ElapsedTicks) / Stopwatch.Frequency);

      }

      private static void DoOne()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
         int s=0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < A.Count; c++) s += A[c];
         }

      }
      private static void DoTwo()
      {
         List<int> A = new List<int>();
         for (int i = 0; i < 200; i++) A.Add(i);
         IList<int> L = A;
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < L.Count; c++) s += L[c];
         }

      }
   }
}

感谢所有的好答案(特别是@kentaromiura).虽然我觉得我们仍然错过了这个难题的一个重要部分,但我会关闭这个问题.为什么通过它实现的接口访问类会慢得多？我能看到的唯一区别是通过接口访问函数意味着使用虚拟表,而通常可以直接调用函数.为了查看是否是这种情况,我对上面的代码进行了一些更改.首先,我介绍了两个几乎相同的类:

  public class VC
  {
     virtual public int f() { return 2; }
     virtual public int Count { get { return 200; } }

  }

  public class C
  {
      public int f() { return 2; }
      public int Count { get { return 200; } }

  }

正如您所看到的,VC正在使用虚拟功能而C则没有.现在到DoOne和DoTwo:

    private static void DoOne()
      {  C a = new C();
         int s=0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < a.Count; c++) s += a.f();
         }

      }
      private static void DoTwo()
      {
           VC a = new VC();
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int c = 0; c < a.Count; c++) s +=  a.f();
         }

      }

事实上:

DoOne took 0.01287789 seconds.
DoTwo took 8.982396 seconds.

这更可怕 - 虚函数调用速度慢800倍？所以社区有几个问题:

1. 你可以重现吗？(鉴于之前所有人的表现都比较差,但并不像我的那么糟糕)
2. 你可以解释吗？
3. (这可能是最重要的) - 你能想到一种避免的方法吗？

波阿斯

Answer 1

给那些试图对这样的东西进行基准测试的所有人的注释.

不要忘记,代码在第一次运行之前不会被jitted.这意味着第一次运行方法时,运行该方法的成本可能由加载IL所花费的时间,分析IL以及将其嵌入到机器代码中所占用的时间来控制,特别是如果它是一个简单的方法.

如果您要做的是比较两种方法的"边际"运行时成本,最好同时运行它们两次并仅考虑第二次运行以进行比较.

Answer 2

一对一分析:

使用Snippet编译器进行测试.

使用您的代码结果:

0.043s vs 0.116s

消除临时L

0.043s vs 0.116s - inInfluent

通过在两个方法的cmax中缓存A.count

0.041s vs 0.076s

     IList<int> A = new List<int>();
     for (int i = 0; i < 200; i++) A.Add(i);

     int s = 0;
     for (int j = 0; j < 100000; j++)
     {
        for (int c = 0,cmax=A.Count;c< cmax;  c++) s += A[c];
     }

现在我将尝试减慢DoOne,首先尝试,在添加之前转换为IList:

for (int i = 0; i < 200; i++) ((IList<int>)A).Add(i);

0,041s 0,076s - 所以add是不流利的

所以它仍然只是减速可能发生的地方:s += A[c]; 所以我试试这个:

s += ((IList<int>)A)[c];

0.075s 0.075s - TADaaan!

所以看起来在接口版本上访问Count或索引元素的速度较慢:

编辑:只是为了好玩,看看这个:

 for (int c = 0,cmax=A.Count;c< cmax;  c++) s += ((List<int>)A)[c];

0.041s 0.050s

所以不是演员问题,而是反思一个!

Answer 3

首先,我要感谢所有人的回答.在确定我们正在发生的事情的路径中,这是非常重要的.特别感谢@kentaromiura,它找到了解决问题所需的关键.

通过IList <T>接口减慢使用List <T>的原因是缺少JIT编译器内联Item属性get函数的能力.通过IList接口访问列表导致的虚拟表的使用可防止发生这种情况.

作为证明,我写了以下代码:

      public class VC
      {
         virtual public int f() { return 2; }
         virtual public int Count { get { return 200; } }

      }

      public class C
      {
         //[MethodImpl( MethodImplOptions.NoInlining)]
          public int f() { return 2; }
          public int Count 
          {
            // [MethodImpl(MethodImplOptions.NoInlining)] 
            get { return 200; } 
          }

      }

并将DoOne和DoTwo类修改为以下内容:

      private static void DoOne()
      {
         C c = new C();
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int i = 0; i < c.Count; i++) s += c.f();
         }

      }
      private static void DoTwo()
      {
         VC c = new VC();
         int s = 0;
         for (int j = 0; j < 100000; j++)
         {
            for (int i = 0; i < c.Count; i++) s += c.f();
         }

      }

现在功能时间与以前非常相似:

 DoOne took 0.01273598 seconds.
 DoTwo took 8.524558 seconds.

现在,如果删除C类中MethodImpl之前的注释(强制JIT不要内联) - 时间变为:

DoOne took 8.734635 seconds.
DoTwo took 8.887354 seconds.

瞧 - 这些方法几乎同时进行.您可以看到DoOne仍然稍微快一点,这与虚拟函数的额外开销是一致的.

Answer 4

我认为问题在于你的时间指标,你用什么来衡量经过的时间？

仅供记录,以下是我的结果:

DoOne() -> 295 ms
DoTwo() -> 291 ms

和代码:

        Stopwatch sw = new Stopwatch();

        sw.Start();
        {
            DoOne();
        }
        sw.Stop();

        Console.WriteLine("DoOne() -> {0} ms", sw.ElapsedMilliseconds);

        sw.Reset();

        sw.Start();
        {
            DoTwo();
        }
        sw.Stop();

        Console.WriteLine("DoTwo() -> {0} ms", sw.ElapsedMilliseconds);