Clear() of a List makes Add() faster?

Question

I have wrote a small project to test the time difference between the initialization of classes and structs with adding them to lists.
It just creates 10000000 classes in a foreach loop, add them to a list and writes the required time to the console. Then the same for structs. This is in a while(true) loop. The beginning of every loop begins with a .Clear() of both lists.

My Class

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("===================");
        }

Struct / Class

 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;
    }
}

My output is as follows:

900 ms (classes)
300 ms (structs)
900 ms (classes)
100 ms (structs)

After the first loop the adding of classes to it's list isn't be faster but the adding of structs is a lot faster. Why??

I run this test in Release build with attached debugger from Visual Studio 2012.

Answer 1

Adding to a pre-allocated list (which is what Clear gives you) is considerably faster than having the list grow as items are added. See the second example below for code that demonstrates this.

I don't know what your Coord class and struct look like, so I cobbled some together. I also modified your program to separate the time taken for creating the struct/class from the time taken to add it to the list. Here's the output. The first number is the total time it took to run the test. The second number is the time it took to create the classes and structs (exclusive of the time taken to add them to the list):

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)
===================

This test was run in .NET 4.5, 64 bit, release mode with the debugger detached.

The first iteration is an anomoly, of course, due to JIT time. Take the 3rd iteration, which is pretty representative. Classes took 1,251 ms, of that 911 ms was creation time. That leaves 340 ms for adding and overhead.

Structs took 523 ms, of which 215 ms is creation time. That leaves 308 ms for adding and overhead. Call it a wash.

What you're seeing is the difference in creating a class, which must be allocated on the heap and a reference to it copied to the list, and creating a structure on the stack and copying that very small structure to the list's internal array.

My test doesn't say how much of the difference between the first and second iterations is JIT time and how much is list reallocation. You'd have to time the adds (like I did with the creates) in order to see the difference.

Understand, though, that we're talking 700 ms difference over 10 million iterations. You'd have to be creating one heck of a lot of these things for it to make any real kind of difference in the runtime of any non-trivial program.

Code follows.

    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("===================");
        }
    }

Now, if you want to see the difference between adding to an empty list and adding to a pre-allocated list, run this code:

    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));
        }
    }

On my machine the empty list takes about 140 ms and the pre-allocated list takes about 100 ms.

Answer 2

List<T> isn't a list (in the Computer Science/Data Structure sense) at all: it is an adjustable length array that uses a fixed-length array as its backing store.

Your declarations of List<T> don't specify an initial size, and I believe the initial size is 16 elements (though it's been a while since I rummaged around in Refelector).

As you add elements to the list, every time the size of the backing store array is exceeded, a new array is allocated with the next increment of size and the existing array copied into it. Your first iteration is expensive since List<T> must repeatedly reallocate and copy the collection as the list grows. Subsequent executions are much faster since they don't have to do that additional work.

FWIW, the increment by which the List<T> backing store is extended is non-linear (I think the size doubles, but I'm not sure.)

Answer 3

Lists don't have a Reset method, but I presume you're referring to the Clear method. A List<T> manages items internally with an array, which is gradually expanded as new items are added to the list. This will only occur once the internal array is full, at which point the List will allocate a new array and copy each item from the previous array into the new one—a time-consuming process. The size of the internal array can be checked via the Capacity property. The Clear method will 'erase' any internal references to objects which were added to the array and sets the Count to 0, but it leaves the internal array at the same size. This can be verified with this simple script:

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

So the second time through the loop it's significantly faster because it can avoid resizing the internal array. This effect is much more significant on list of large structs as they occupy a larger portion of memory than a reference to a class.

To address the question as to why this was observed on structs only, it appears that this is because you're not performing a proper 'warm-up'. When I run your code as-is, my results are:

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

That's only a 9% performance improvement between the first and second iteration. But if I add a small snippet of code before the while-loop:

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

My results are:

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

That's a 14% performance improvement. It's still not as significant as what is observed on structs, but I think this helps to explain what you're seeing.

Answer 4

After the first loop the adding of classes to it's list isn't be faster but the adding of structs is a lot faster.

Wrong. The list insertion time for the version with classes went down, but you can't tell because it is swamped by the cost of instance creation, which isn't faster. Try creating one instance, outside the loop, and adding it many times.

Then you'll see that both List<SomeClass> and List<SomeStruct> benefit from preallocation.