System.Collections.List<T> is used everywhere in C# code. Except for very special cases, it’s the replacement for arrays, linked lists, queues, and most other one-dimensional data structures. This is because it has all kinds of extra functionality, including the ability to grow in size on-demand. Today’s article wonders about how much performance is lost to gain this convenience and tests the List<T> class against the lowly C# array: T[]. How much performance are you giving up with List and why is that happening? Read on to find out!

Today’s test is actually very simple. We’re just going to test reading from and writing to an array and a List. Operator overloading makes them even look the same:

// Read
val = array[i];
val = list[i];
 
// Write
array[i] = val;
list[i] = val;

Here’s the test script:

using System.Collections.Generic;
 
using UnityEngine;
 
public class TestScript : MonoBehaviour
{
	private const int NumIterations = 10000;
	private const int Length = 10000;
 
	private string report;
 
	void Start()
	{
		var stopwatch = new System.Diagnostics.Stopwatch();
		int sum;
		var array = new int[Length];
		var list = new List<int>(Length);
		for (var i = 0; i < Length; ++i)
		{
			array[i] = i;
			list.Add(i);
		}
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			sum = 0;
			for (var i = 0; i < Length; ++i)
			{
				sum += array[i];
			}
		}
		var arrayReadTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			for (var i = 0; i < Length; ++i)
			{
				array[i] = i;
			}
		}
		var arrayWriteTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			sum = 0;
			for (var i = 0; i < Length; ++i)
			{
				sum += list[i];
			}
		}
		var listReadTime = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			for (var i = 0; i < Length; ++i)
			{
				list[i] = i;
			}
		}
		var listWriteTime = stopwatch.ElapsedMilliseconds;
 
		report =
			"Test,Array Time,List Time\n"
			+ "Read," + arrayReadTime + "," + listReadTime + "\n"
			+ "Write," + arrayWriteTime + "," + listWriteTime;
	}
 
	void OnGUI()
	{
		GUI.TextArea(new Rect(0, 0, Screen.width, Screen.height), report);
	}
}

If you want to try out the test yourself, simply paste the above code into a TestScript.cs file in your Unity project’s Assets directory and attach it to the main camera game object in a new, empty project. Then build in non-development mode for 64-bit processors and run it windowed at 640×480 with fastest graphics. I ran it that way on this machine:

  • 2.3 Ghz Intel Core i7-3615QM
  • Mac OS X 10.10.3
  • Unity 5.0.2f1, Mac OS X Standalone, x86_64, non-development
  • 640×480, Fastest, Windowed

And got these results:

Test Array Time List Time
Read 230 340
Write 65 452

Array vs. List Performance Graph

Reading from a List takes 47% longer than reading from an array. That’s a really big gap, but not as big as writing where List takes a whopping 695% longer!

Each of the above tests involved 100 million reads or writes, so the individual cost is extremely low. A few reads and writes won’t matter at all. In fact, the test computer would need to make 258,000 writes in order for switching from List to array to save one millisecond. A slower machine or one trying to achieve a very high framerate (e.g. for VR) might hit the limit in the tens of thousands of writes rather than the hundreds of thousands. The decision to switch should depend highly on what work your app is doing.

So why is List so much slower? To find out, let’s decompile the mscorlib.dll that comes with Unity to look at its implementation:

public T this[int index]
{
	get
	{
		if ((uint) index >= (uint) this._size)
			throw new ArgumentOutOfRangeException("index");
		return this._items[index];
	}
	set
	{
		this.CheckIndex(index);
		if (index == this._size)
			throw new ArgumentOutOfRangeException("index");
		this._items[index] = value;
	}
}
 
private void CheckIndex(int index)
{
	if (index < 0 || (uint) index > (uint) this._size)
		throw new ArgumentOutOfRangeException("index");
}

First, List implements the IList interface’s slow virtual function. Second, all index values passed to either read or write are checked to make sure they’re within the bounds of the array with an exception possible in case they’re not. For reading this is just a simple if, but that branching shows up as quite costly in the test. For writing, there is both an if and a non-virtual function call to CheckIndex which has another if with two comparisons in it and yet-another possible exception.

With this in mind we can make a more informed decision when deciding between List and arrays. In general, List is fine to use and certainly much more convenient. However, if you find yourself using them thousands of times per frame you should probably consider switching to an array to skip the function calls and if statements.

Have you run into trouble with List or any of the other .NET classes in System.Collections? How’d you work around it? Let me know in the comments!