Performance of List<struct> vs List<class>

Question

Out of curiosity, I was trying to test the performance of List<T> using both value and reference types.

The results were not as I expected, leading me to believe my understanding of how these objects are laid out in memory might not be correct.

This was my experiment:

• Create a basic class containing just two members, an int and a bool

• Create 2 List<T> objects to hold my test classes (List1 and List2)

• Randomly generate test objects and add them to List1 and List2 alternately

• Time how long it takes to iterate through List1 (doing some arbitrary work such as incrementing a counter and then accessing the element)

I then repeated with a struct in place of a class

My assumptions were that when using a class, the references held in the List<T> would be contiguous, but because of how I created them (switching between adding to List1 and List2), the objects they point to probably wouldn't be.

I thought that when using a struct, because it is a value type, the objects themselves would be held contiguously in memory (since the List<T> holds the actual items rather than a collection of references).

Because of this, I expected struct to perform better (due to prefetchers etc..)

In actual fact, both were very similar.

What's going on here?

Edit - Added code to actually access the element in the iterator, code sample included

Test class (or struct)

public class/struct TestClass
{
    public int TestInt;
    public bool TestBool;
}

Creating random Lists:

var list1 = new List<TestClass>();
var list2 = new List<TestClass>();

var toggle = false;
for (var i=0; i < 4000000; i++)
{
    // Random object generation removed for simplicity

    if (toggle)
        list1.Add(randomObject);
    else
        list2.Add(randomObject);

    toggle = !toggle;    
}

Testing:

var stopWatch = new Stopwatch();
var counter = 0;
var testBool = false;

stopwatch.Start();

foreach(var item in list1)
{
    // Access the element
    testBool = item.TestBool;
    counter++;
}

stopwatch.Stop();

Repeat with TestObject as both a class and a struct.

I realise there isn't much difference, but I expected struct to perform significantly better than class

Answer 1

// Access the element
testBool = item.TestBool;

That has no effect, the optimizer will remove the statement since it has no useful side-effects. You are not actually measuring the difference between a struct and a class since you never actually access the element.

counter++;

Same story, pretty likely to be optimized away. Unless you actually use the counter value, after the loop completes. Having the optimizer remove too much code and make the test meaningless is a common micro-benchmark hazard. A workaround would be:

foreach(var item in list1)
{
    // Access the element
    counter += item.TestInt;
}
Console.WriteLine(counter);

Benchmark guidelines are:

• Only profile code produced by the Release configuration. The Debug build produces too much extra code and suppresses optimization
• Tools + Options, Debugging, General, untick the "Suppress JIT optimization on module load". This ensures that you get optimized code even if you run with the debugger
• Debug + Windows + Disassembly is a very important debugger window to show you what code really runs. Having some understanding of machine code is required to interpret that window correctly
• Very important to put an outer loop around the test code to ensure that you run the test at least 10 times. This removes cold start effects, like the processor having to fill the L1 instruction cache and the jitter having to load the IL from the assembly and compile it the first time it executes. And removes random outliers you'll get from having to compete with other processes that run on the machine and also compete for the processor.
• Differences of 15% are not statistically significant.

Answer 2

If you aren't actually accessing members of the class objects stored in your list, then the following two types should provide equivalent performance for iteration.

1. List<IntPtr>
2. List<object>

Even though the reference type instances aren't filling a contiguous section of memory, the references themselves are.

The exception to the above case would be if the CLR compresses pointers when executing 64-bit applications with less than 32GiB of memory. This strategy is documented as Compressed OOPS in the JVM. However, the x86-64 instruction set includes instructions that allow this compression/decompression to be performed extremely efficiently, so even in this case you should see performance similar to List<int>.

Things get interesting when your value types exceed the size of a pointer (IntPtr.Size). After that point, the performance of a List<T> containing references should quickly surpass the performance of a List<T> of value types. This is due to the fact that regardless of how big your reference type instance is, the reference to that instance is at most IntPtr.Size.