List<T>与数组的性能对比

Question

我尝试设置一个 List< int > 类型的值。

List< int > a;
//...
a[i] = X;

ilspy显示设置编译为：

callvirt instance void class [mscorlib]System.Collections.Generic.List`1<int32>::set_Item(int32, !0)

但是这段代码

int[] b;
//...
b[i] = Y;

编译成

stelem.i4

我的基准测试结果比之前快了7倍。

据我所知，虚拟调用比stelem更昂贵。是否可以使用具有数组性能的List<T>？

更新

代码：

   static void Main(string[] args)
    {
        int N = int.Parse(args[0]);
        int M = int.Parse(args[1]);

        var sw = new Stopwatch();
        sw.Start();
        int[] a = new int[N];
        for (int k = 0; k < M; ++k)
        {
            for (int i = 0; i < N; ++i)
            {
                a[i] = i * 2;
                a[i] -= i;
                a[i] += 1;
            }
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedMilliseconds + ":" + a[N - 1]);

        var b = new List<int>(N);
        for (int i = 0; i < N; ++i)
        {
            b.Add(0);
        }
        sw.Restart();
        for (int k = 0; k < M; ++k)
        {
            for (int i = 0; i < N; ++i)
            {
                b[i] = i * 2;
                b[i] -= i;
                b[i] += 1;
            }
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedMilliseconds + ":" + b[N - 1]);
    }

运行并输出：

> ./Console.exe 1000000 100

166:1000000
1467:1000000

- user1312837

---

你需要集合的大小是动态的吗？如果是，使用List<T>，否则使用Array。 - Sriram Sakthivel

Answer 1

List<T>是一个数组的包装类，具有一些必要的开销（因为它是一个类）。此外，插入和删除等操作代价高昂，特别是当它导致重新排序所有其他元素时。如果你不想承受List<T>的开销，或者需要像动态大小、插入和删除这样的功能，那么请使用数组。如果你想或需要使用List<T>，那么就接受性能损失吧。在重新调整数组大小和其他可以从直接访问底层内存/操作系统函数中获益的操作方面，你很难编写比.NET BCL团队更有效的代码。

- Patrick Hofman

---

昂贵的插入/删除是可以接受的。但是难道不能优化设置先前存在的元素吗？即在不进行昂贵的虚拟调用的情况下设置列表元素。 - user1312837

这听起来好像列表总是不太高效，但实际上并非如此。如果您需要不断调整大小，则列表的性能要高得多。OP正在进行微观优化。 “如果您不想使用List <T>的开销，请使用数组”——不，当适用时请使用它，因此如果要添加或删除项目，请使用列表，如果要使用固定大小的集合，请使用数组。 - Tim Schmelter

我认为你的测量可能有误（7倍因子对我来说似乎太多了）。使用List<T>，你不可能比.NET团队获得更好的性能。 - Patrick Hofman

@user1312837 我不明白你在写什么样的代码？如果性能如此关键，我认为你根本不应该使用 .Net。 - Sriram Sakthivel

@TimSchmelter：你可能是对的。我已经修改了答案以强调这一点。 - Patrick Hofman

@user1312837：这个很难准确地衡量。如果你使用真正的分析器并进行多次尝试，那么结果会是什么呢？ - Patrick Hofman