列表的Clear()使Add()更快

本文关键字：Add 更快 列表 Clear | 更新日期: 2023-09-27 18:29:02

我写了一个小项目，通过将类和结构添加到列表来测试初始化之间的时间差
它只需在foreach循环中创建10000000个类，将它们添加到列表中，并将所需的时间写入控制台。结构也是如此。这是在while(true)循环中。每个循环的开始都以两个列表的.Clear()开始。

我的班级

internal static void Main(string[] args)
    {
        var classes = new List<CoordClass>();
        var structs = new List<CoordStruct>();
        var sw = new Stopwatch();
        while (true)
        {
            classes.Clear();
            structs.Clear();
            sw.Reset();
            sw.Start();
            for (var i = 0; i < 10000000; i++)
            {
                classes.Add(new CoordClass(23, 24));
            }
            sw.Stop();
            Console.WriteLine("Classes: {0} ms ({1})", sw.ElapsedMilliseconds, classes.Count);
            sw.Reset();
            sw.Start();
            for (var i = 0; i < 10000000; i++)
            {
                structs.Add(new CoordStruct(23, 24));
            }
            sw.Stop();
            Console.WriteLine("Structs: {0} ms ({1})", sw.ElapsedMilliseconds, structs.Count);
            Console.WriteLine("===================");
        }

结构/等级

 public struct CoordStruct
 {
    public int x, y;
    public CoordStruct(int p1, int p2)
    {
        x = p1;
        y = p2;
    }
 }
public class CoordClass
{
    public int x, y;
    public CoordClass(int p1, int p2)
    {
        x = p1;
        y = p2;
    }
}

我的输出如下：

900毫秒（类）
300毫秒（结构）
900毫秒（类）
100毫秒（结构）

在第一个循环之后，将类的添加到它的列表中并没有更快，但添加结构要快得多。为什么？

我在Release版本中运行此测试，该版本带有Visual Studio 2012中的附加调试器。

列表的Clear()使Add()更快

在第一个循环之后，向其列表中添加类的速度不会更快，但添加结构的速度要快得多。

错了。带有类的版本的列表插入时间减少了，但您无法判断，因为它被实例创建的成本淹没了，而实例创建的速度并不快。尝试在循环之外创建一个实例，并多次添加它。

然后您将看到List<SomeClass>和List<SomeStruct>都从预分配中受益。

添加到预先分配的列表（这就是Clear给您的）比随着项目的添加而增加列表要快得多。请参阅下面的第二个示例，以获取演示这一点的代码。

我不知道你的Coord类和结构是什么样子的，所以我拼凑了一些。我还修改了你的程序，将创建结构/类所花费的时间与将其添加到列表中所花费的费用分开。这是输出。第一个数字是运行测试所花费的总时间。第二个数字是创建类和结构所花费的时间（不包括将它们添加到列表中所花费的花费）：

Classes: 1404 ms (922.253)
Structs: 803 ms (215.9278)
===================
Classes: 1231 ms (895.7751)
Structs: 520 ms (215.7464)
===================
Classes: 1251 ms (911.6303)
Structs: 523 ms (220.119)
===================
Classes: 1337 ms (990.2042)
Structs: 519 ms (215.3085)
===================
Classes: 1251 ms (909.4082)
Structs: 521 ms (215.2579)
===================
Classes: 1237 ms (894.4974)
Structs: 522 ms (216.5798)
===================
Classes: 1289 ms (947.2457)
Structs: 525 ms (217.9129)
===================
Classes: 1226 ms (887.7574)
Structs: 520 ms (214.7768)
===================

此测试在.NET 4.5 64位发布模式下运行，调试器已分离。

当然，由于JIT时间的原因，第一次迭代是异常的。以第三次迭代为例，它非常具有代表性。上课时间为1251毫秒，其中911毫秒为创建时间。这就留下了340毫秒的加法和开销。

结构耗时523毫秒，其中215毫秒为创建时间。这就留下了308毫秒的加法和开销。称之为清洗。

您看到的是创建一个类和在堆栈上创建一个结构并将这个非常小的结构复制到列表的内部数组之间的区别，前者必须在堆上分配，并将对它的引用复制到列表中。

我的测试没有说明第一次和第二次迭代之间的差异有多少是JIT时间，有多少是列表重新分配。你必须对添加进行计时（就像我对创建所做的那样），才能看到差异。

不过，要明白，我们谈论的是1000万次迭代中700毫秒的差异。你必须创建大量这样的东西，才能在任何非平凡程序的运行时产生真正的差异。

代码如下。

    private struct CoordStruct
    {
        public readonly int X;
        public readonly int Y;
        public CoordStruct(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
    private class CoordClass
    {
        public readonly int X;
        public readonly int Y;
        public CoordClass(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
    private void DoStuff()
    {
        const int Iterations = 10000000;
        var classes = new List<CoordClass>();
        var structs = new List<CoordStruct>();
        var sw = new Stopwatch();
        while (true)
        {
            TimeSpan createTimeStruct = TimeSpan.Zero;
            TimeSpan createTimeClass = TimeSpan.Zero;
            classes.Clear();
            structs.Clear();
            // force garbage collection so that it doesn't happen
            // in the middle of things.
            GC.Collect();
            GC.WaitForPendingFinalizers();
            sw.Reset();
            sw.Start();
            for (var i = 0; i < Iterations; i++)
            {
                var start = sw.Elapsed;
                var c = new CoordClass(23, 24);
                var stop = sw.Elapsed;
                createTimeClass += (stop - start);
                classes.Add(c);
            }
            sw.Stop();
            Console.WriteLine("Classes: {0} ms ({1})", sw.ElapsedMilliseconds, createTimeClass.TotalMilliseconds);
            sw.Reset();
            sw.Start();
            for (var i = 0; i < Iterations; i++)
            {
                var start = sw.Elapsed;
                var c = new CoordStruct(23, 24);
                var stop = sw.Elapsed;
                createTimeStruct += (stop - start);
                structs.Add(c);
            }
            sw.Stop();
            Console.WriteLine("Structs: {0} ms ({1})", sw.ElapsedMilliseconds, createTimeStruct.TotalMilliseconds);
            Console.WriteLine("===================");
        }
    }

现在，如果您想了解添加到空列表和添加到预分配列表之间的区别，请运行以下代码：

    private void DoStuff()
    {
        const int Iterations = 10000000;
        while (true)
        {
            GC.Collect();
            GC.WaitForPendingFinalizers();
            var sw = Stopwatch.StartNew();
            var structs = new List<CoordStruct>();
            AddItems(structs, Iterations);
            sw.Stop();
            Console.WriteLine("Empty list: {0:N0} ms", sw.ElapsedMilliseconds);
            sw.Restart();
            structs = new List<CoordStruct>(Iterations);
            AddItems(structs, Iterations);
            sw.Stop();
            Console.WriteLine("Pre-allocated list: {0:N0} ms", sw.ElapsedMilliseconds);
            Console.WriteLine("===================");
        }
    }
    private void AddItems(List<CoordStruct> list, int nItems)
    {
        for (var i = 0; i < nItems; ++i)
        {
            list.Add(new CoordStruct(23, 24));
        }
    }

在我的机器上，空列表大约需要140毫秒，预分配的列表大约需要100毫秒。

Lists没有Reset方法，但我认为您指的是Clear方法。List<T>通过一个数组在内部管理项目，随着新项目添加到列表中，数组会逐渐扩展。只有在内部数组已满时才会发生这种情况，此时List将分配一个新数组，并将上一个数组中的每个项复制到新数组中—这是一个耗时的过程。内部数组的大小可以通过Capacity属性进行检查。Clear方法将"擦除"对添加到数组中的对象的任何内部引用，并将Count设置为0，但它使内部数组保持相同大小。这可以用这个简单的脚本来验证：

var list = new List<int>();
for(int i = 0; i < 10000; i++)
{
    list.Add(i);
}
Console.WriteLine(list.Capacity); // 16384
list.Clear();
Console.WriteLine(list.Capacity); // 16384

因此，第二次通过循环时，速度明显更快，因为它可以避免调整内部数组的大小。这种影响在大型结构列表中要显著得多，因为它们比引用类占据了更大的内存部分。

为了解决为什么只在结构上观察到这种情况的问题，这似乎是因为你没有进行适当的"热身"。当我按原样运行您的代码时，我的结果是：

Classes: 1787 ms (10000000)
Structs: 554 ms (10000000)
===================
Classes: 1618 ms (10000000)
Structs: 229 ms (10000000)
===================

在第一次和第二次迭代之间，性能只提高了9%。但是，如果我在while循环之前添加一小段代码：

classes.Add(new CoordClass(23, 24));
structs.Add(new CoordStruct(23, 24));

我的结果是：

Classes: 1786 ms (10000000)
Structs: 548 ms (10000000)
===================
Classes: 1527 ms (10000000)
Structs: 216 ms (10000000)
===================

这是14%的性能改进。它仍然没有在structs上观察到的那么重要，但我认为这有助于解释你所看到的。

List<T>根本不是一个列表（在计算机科学/数据结构的意义上）：它是一个长度可调的数组，使用固定长度的数组作为其后备存储。

您对List<T>的声明没有指定初始大小，我相信初始大小是16个元素（尽管我在Reflector中查找已经有一段时间了）。

当您向列表中添加元素时，每次超过后备存储阵列的大小时，都会分配一个新阵列，并将下一个大小增量和现有阵列复制到其中。第一次迭代的成本很高，因为List<T>必须随着列表的增长重复重新分配和复制集合。后续的执行速度要快得多，因为它们不必做额外的工作。

FWIW，扩展List<T>后备存储的增量是非线性的（我认为大小翻倍，但我不确定。）

相关文章：