清单()列表使Add()更快？

Question

我编写了一个小项目来测试类和结构的初始化之间的时间差,并将它们添加到列表中.
它只在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 ms(类)
300 ms(结构)
900 ms(类)
100 ms(结构)

在第一个循环之后,将类添加到它的列表中的速度并不快,但结构的添加要快得多.为什么？？

我使用Visual Studio 2012 附带的调试器在Release版本中运行此测试.

Answer 1

在第一个循环之后,将类添加到它的列表中的速度并不快,但结构的添加要快得多.

错误.包含类的版本的列表插入时间已经缩短,但您无法分辨,因为它被实例创建的成本所淹没,这并不快.尝试在循环外创建一个实例,并多次添加它.

然后你会看到两者List<SomeClass>并List<SomeStruct>从预分配中受益.

Answer 2

添加到预先分配的列表(这是Clear给你的东西)比添加项目时增加列表要快得多.有关演示此内容的代码,请参阅下面的第二个示例

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

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时间的原因,第一次迭代是一种异常现象.进行第三次迭代,这是非常有代表性的.类需要1,251毫秒,其中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毫秒.