JacksonDunstan.com

Last week’s article compared the performance of arrays with List<T> and found List lacking. This week we’ll optimize both List and array to maximize performance regardless of which you choose to use.

As we found last week, part of the reason it’s slow to set to an index on a List is due to the unoptimized setter:

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

Since this class is built into the .NET libraries via mscorlib.dll, we can’t directly modify it. Instead, we can decompile the class and make our own QuickList with optimizations.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
 
[Serializable]
public class QuickList<T>
    : IEnumerable, ICollection, IList, ICollection<T>, IEnumerable<T>, IList<T>
{
	private const int DefaultCapacity = 4;
	private T[] _items;
	private int _size;
	private int _version;
	private static readonly T[] EmptyArray;
 
	bool ICollection<T>.IsReadOnly
	{
		get
		{
			return false;
		}
	}
 
	bool ICollection.IsSynchronized
	{
		get
		{
			return false;
		}
	}
 
	object ICollection.SyncRoot
	{
		get
		{
			return (object) this;
		}
	}
 
	bool IList.IsFixedSize
	{
		get
		{
			return false;
		}
	}
 
	bool IList.IsReadOnly
	{
		get
		{
			return false;
		}
	}
 
	object IList.this[int index]
	{
		get
		{
			return (object) this[index];
		}
		set
		{
			try
			{
				this[index] = (T) value;
				return;
			}
			catch (NullReferenceException)
			{
			}
			catch (InvalidCastException)
			{
			}
			throw new ArgumentException("value");
		}
	}
 
	public int Capacity
	{
		get
		{
			return _items.Length;
		}
		set
		{
			if ((uint) value < (uint) _size)
				throw new ArgumentOutOfRangeException();
			Array.Resize<T>(ref _items, value);
		}
	}
 
	public int Count
	{
		get
		{
			return _size;
		}
	}
 
	public T this[int index]
	{
		get
		{
			if ((uint) index >= (uint) _size)
				throw new ArgumentOutOfRangeException("index");
			return _items[index];
		}
		set
		{
			if (index < 0 || (uint) index >= (uint) _size)
				throw new ArgumentOutOfRangeException("index");
			_items[index] = value;
		}
	}
 
    public T[] BackingArray
    {
        get
        {
            return _items;
        }
    }
 
    static QuickList()
	{
		EmptyArray = new T[0];
	}
 
    public QuickList()
	{
		_items = EmptyArray;
	}
 
    public QuickList(IEnumerable<T> collection)
	{
		CheckCollection(collection);
		ICollection<T> collection1 = collection as ICollection<T>;
		if (collection1 == null)
		{
			_items = EmptyArray;
			AddEnumerable(collection);
		}
		else
		{
			_items = new T[collection1.Count];
			AddCollection(collection1);
		}
	}
 
    public QuickList(int capacity)
	{
		if (capacity < 0)
			throw new ArgumentOutOfRangeException("capacity");
		_items = new T[capacity];
	}
 
    internal QuickList(T[] data, int size)
	{
		_items = data;
		_size = size;
	}
 
	IEnumerator<T> IEnumerable<T>.GetEnumerator()
	{
		return (IEnumerator<T>) GetEnumerator();
	}
 
	void ICollection.CopyTo(Array array, int arrayIndex)
	{
		Array.Copy((Array) _items, 0, array, arrayIndex, _size);
	}
 
	IEnumerator IEnumerable.GetEnumerator()
	{
		return (IEnumerator) GetEnumerator();
	}
 
	int IList.Add(object item)
	{
		try
		{
			Add((T) item);
			return _size - 1;
		}
		catch (NullReferenceException)
		{
		}
		catch (InvalidCastException)
		{
		}
		throw new ArgumentException("item");
	}
 
	bool IList.Contains(object item)
	{
		try
		{
			return Contains((T) item);
		}
		catch (NullReferenceException)
		{
		}
		catch (InvalidCastException)
		{
		}
		return false;
	}
 
	int IList.IndexOf(object item)
	{
		try
		{
			return IndexOf((T) item);
		}
		catch (NullReferenceException)
		{
		}
		catch (InvalidCastException)
		{
		}
		return -1;
	}
 
	void IList.Insert(int index, object item)
	{
		CheckIndex(index);
		try
		{
			Insert(index, (T) item);
			return;
		}
		catch (NullReferenceException)
		{
		}
		catch (InvalidCastException)
		{
		}
		throw new ArgumentException("item");
	}
 
	void IList.Remove(object item)
	{
		try
		{
			Remove((T) item);
		}
		catch (NullReferenceException)
		{
		}
		catch (InvalidCastException)
		{
		}
	}
 
	public void Add(T item)
	{
		if (_size == _items.Length)
			GrowIfNeeded(1);
		_items[_size++] = item;
		++_version;
	}
 
	private void GrowIfNeeded(int newCount)
	{
		int val2 = _size + newCount;
		if (val2 <= _items.Length)
			return;
		Capacity = Math.Max(Math.Max(Capacity * 2, 4), val2);
	}
 
	private void CheckRange(int idx, int count)
	{
		if (idx < 0)
			throw new ArgumentOutOfRangeException("index");
		if (count < 0)
			throw new ArgumentOutOfRangeException("count");
		if ((uint) (idx + count) > (uint) _size)
			throw new ArgumentException("index and count exceed length of list");
	}
 
	private void AddCollection(ICollection<T> collection)
	{
		int count = collection.Count;
		if (count == 0)
			return;
		GrowIfNeeded(count);
		collection.CopyTo(_items, _size);
		_size += count;
	}
 
	private void AddEnumerable(IEnumerable<T> enumerable)
	{
		foreach (T obj in enumerable)
			Add(obj);
	}
 
	public void AddRange(IEnumerable<T> collection)
	{
		CheckCollection(collection);
		ICollection<T> collection1 = collection as ICollection<T>;
		if (collection1 != null)
			AddCollection(collection1);
		else
			AddEnumerable(collection);
		++_version;
	}
 
	public ReadOnlyCollection<T> AsReadOnly()
	{
		return new ReadOnlyCollection<T>((IList<T>) this);
	}
 
	public int BinarySearch(T item)
	{
		return Array.BinarySearch<T>(_items, 0, _size, item);
	}
 
	public int BinarySearch(T item, IComparer<T> comparer)
	{
		return Array.BinarySearch<T>(_items, 0, _size, item, comparer);
	}
 
	public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
	{
		CheckRange(index, count);
		return Array.BinarySearch<T>(_items, index, count, item, comparer);
	}
 
	public void Clear()
	{
		Array.Clear((Array) _items, 0, _items.Length);
		_size = 0;
		++_version;
	}
 
	public bool Contains(T item)
	{
		return Array.IndexOf<T>(_items, item, 0, _size) != -1;
	}
 
	public QuickList<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
	{
		if (converter == null)
			throw new ArgumentNullException("converter");
		QuickList<TOutput> list = new QuickList<TOutput>(_size);
		for (int index = 0; index < _size; ++index)
			list._items[index] = converter(_items[index]);
		list._size = _size;
		return list;
	}
 
	public void CopyTo(T[] array)
	{
		Array.Copy((Array) _items, 0, (Array) array, 0, _size);
	}
 
	public void CopyTo(T[] array, int arrayIndex)
	{
		Array.Copy((Array) _items, 0, (Array) array, arrayIndex, _size);
	}
 
	public void CopyTo(int index, T[] array, int arrayIndex, int count)
	{
		CheckRange(index, count);
		Array.Copy((Array) _items, index, (Array) array, arrayIndex, count);
	}
 
	public bool Exists(Predicate<T> match)
	{
		CheckMatch(match);
		return GetIndex(0, _size, match) != -1;
	}
 
	public T Find(Predicate<T> match)
	{
		CheckMatch(match);
		int index = GetIndex(0, _size, match);
		if (index != -1)
			return _items[index];
		return default (T);
	}
 
	private static void CheckMatch(Predicate<T> match)
	{
		if (match == null)
			throw new ArgumentNullException("match");
	}
 
	public QuickList<T> FindAll(Predicate<T> match)
	{
		CheckMatch(match);
		if (_size <= 65536)
			return FindAllStackBits(match);
		return FindAllList(match);
	}
 
	private unsafe QuickList<T> FindAllStackBits(Predicate<T> match)
	{
		uint* numPtr1 = stackalloc uint[(int) checked (unchecked ((uint) (_size / 32 + 1)) * 4U)];
		uint* numPtr2 = numPtr1;
		int size = 0;
        uint num1 = unchecked((uint) int.MinValue);
		for (int index = 0; index < _size; ++index)
		{
			if (match(_items[index]))
			{
				*numPtr2 = *numPtr2 | num1;
				++size;
			}
			num1 >>= 1;
			if ((int) num1 == 0)
			{
				++numPtr2;
                num1 = unchecked((uint) int.MinValue);
			}
		}
		T[] data = new T[size];
        uint num2 = unchecked((uint) int.MinValue);
		uint* numPtr3 = numPtr1;
		int num3 = 0;
		for (int index = 0; index < _size && num3 < size; ++index)
		{
			if (((int) *numPtr3 & (int) num2) == (int) num2)
				data[num3++] = _items[index];
			num2 >>= 1;
			if ((int) num2 == 0)
			{
				++numPtr3;
                num2 = unchecked((uint) int.MinValue);
			}
		}
		return new QuickList<T>(data, size);
	}
 
	private QuickList<T> FindAllList(Predicate<T> match)
	{
		QuickList<T> list = new QuickList<T>();
		for (int index = 0; index < _size; ++index)
		{
			if (match(_items[index]))
				list.Add(_items[index]);
		}
		return list;
	}
 
	public int FindIndex(Predicate<T> match)
	{
		CheckMatch(match);
		return GetIndex(0, _size, match);
	}
 
	public int FindIndex(int startIndex, Predicate<T> match)
	{
		CheckMatch(match);
		CheckIndex(startIndex);
		return GetIndex(startIndex, _size - startIndex, match);
	}
 
	public int FindIndex(int startIndex, int count, Predicate<T> match)
	{
		CheckMatch(match);
		CheckRange(startIndex, count);
		return GetIndex(startIndex, count, match);
	}
 
	private int GetIndex(int startIndex, int count, Predicate<T> match)
	{
		int num = startIndex + count;
		for (int index = startIndex; index < num; ++index)
		{
			if (match(_items[index]))
				return index;
		}
		return -1;
	}
 
	public T FindLast(Predicate<T> match)
	{
		CheckMatch(match);
		int lastIndex = GetLastIndex(0, _size, match);
		if (lastIndex == -1)
			return default (T);
		return this[lastIndex];
	}
 
	public int FindLastIndex(Predicate<T> match)
	{
		CheckMatch(match);
		return GetLastIndex(0, _size, match);
	}
 
	public int FindLastIndex(int startIndex, Predicate<T> match)
	{
		CheckMatch(match);
		CheckIndex(startIndex);
		return GetLastIndex(0, startIndex + 1, match);
	}
 
	public int FindLastIndex(int startIndex, int count, Predicate<T> match)
	{
		CheckMatch(match);
		int num = startIndex - count + 1;
		CheckRange(num, count);
		return GetLastIndex(num, count, match);
	}
 
	private int GetLastIndex(int startIndex, int count, Predicate<T> match)
	{
		int num = startIndex + count;
		while (num != startIndex)
		{
			if (match(_items[--num]))
				return num;
		}
		return -1;
	}
 
	public void ForEach(Action<T> action)
	{
		if (action == null)
			throw new ArgumentNullException("action");
		for (int index = 0; index < _size; ++index)
			action(_items[index]);
	}
 
	public Enumerator GetEnumerator()
	{
		return new Enumerator(this);
	}
 
	public QuickList<T> GetRange(int index, int count)
	{
		CheckRange(index, count);
		T[] data = new T[count];
		Array.Copy((Array) _items, index, (Array) data, 0, count);
		return new QuickList<T>(data, count);
	}
 
	public int IndexOf(T item)
	{
		return Array.IndexOf<T>(_items, item, 0, _size);
	}
 
	public int IndexOf(T item, int index)
	{
		CheckIndex(index);
		return Array.IndexOf<T>(_items, item, index, _size - index);
	}
 
	public int IndexOf(T item, int index, int count)
	{
		if (index < 0)
			throw new ArgumentOutOfRangeException("index");
		if (count < 0)
			throw new ArgumentOutOfRangeException("count");
		if ((uint) (index + count) > (uint) _size)
			throw new ArgumentOutOfRangeException("index and count exceed length of list");
		return Array.IndexOf<T>(_items, item, index, count);
	}
 
	private void Shift(int start, int delta)
	{
		if (delta < 0)
			start -= delta;
		if (start < _size)
			Array.Copy((Array) _items, start, (Array) _items, start + delta, _size - start);
		_size += delta;
		if (delta >= 0)
			return;
		Array.Clear((Array) _items, _size, -delta);
	}
 
	private void CheckIndex(int index)
	{
		if (index < 0 || (uint) index > (uint) _size)
			throw new ArgumentOutOfRangeException("index");
	}
 
	public void Insert(int index, T item)
	{
		CheckIndex(index);
		if (_size == _items.Length)
			GrowIfNeeded(1);
		Shift(index, 1);
		_items[index] = item;
		++_version;
	}
 
	private void CheckCollection(IEnumerable<T> collection)
	{
		if (collection == null)
			throw new ArgumentNullException("collection");
	}
 
	public void InsertRange(int index, IEnumerable<T> collection)
	{
		CheckCollection(collection);
		CheckIndex(index);
		if (collection == this)
		{
			T[] array = new T[_size];
			CopyTo(array, 0);
			GrowIfNeeded(_size);
			Shift(index, array.Length);
			Array.Copy((Array) array, 0, (Array) _items, index, array.Length);
		}
		else
		{
			ICollection<T> collection1 = collection as ICollection<T>;
			if (collection1 != null)
				InsertCollection(index, collection1);
			else
				InsertEnumeration(index, collection);
		}
		++_version;
	}
 
	private void InsertCollection(int index, ICollection<T> collection)
	{
		int count = collection.Count;
		GrowIfNeeded(count);
		Shift(index, count);
		collection.CopyTo(_items, index);
	}
 
	private void InsertEnumeration(int index, IEnumerable<T> enumerable)
	{
		foreach (T obj in enumerable)
			Insert(index++, obj);
	}
 
	public int LastIndexOf(T item)
	{
		return Array.LastIndexOf<T>(_items, item, _size - 1, _size);
	}
 
	public int LastIndexOf(T item, int index)
	{
		CheckIndex(index);
		return Array.LastIndexOf<T>(_items, item, index, index + 1);
	}
 
	public int LastIndexOf(T item, int index, int count)
	{
		if (index < 0)
			throw new ArgumentOutOfRangeException("index", (object) index, "index is negative");
		if (count < 0)
			throw new ArgumentOutOfRangeException("count", (object) count, "count is negative");
		if (index - count + 1 < 0)
			throw new ArgumentOutOfRangeException("cound", (object) count, "count is too large");
		return Array.LastIndexOf<T>(_items, item, index, count);
	}
 
	public bool Remove(T item)
	{
		int index = IndexOf(item);
		if (index != -1)
			RemoveAt(index);
		return index != -1;
	}
 
	public int RemoveAll(Predicate<T> match)
	{
		CheckMatch(match);
		int index1 = 0;
		while (index1 < _size && !match(_items[index1]))
			++index1;
		if (index1 == _size)
			return 0;
		++_version;
		int index2;
		for (index2 = index1 + 1; index2 < _size; ++index2)
		{
			if (!match(_items[index2]))
				_items[index1++] = _items[index2];
		}
		if (index2 - index1 > 0)
			Array.Clear((Array) _items, index1, index2 - index1);
		_size = index1;
		return index2 - index1;
	}
 
	public void RemoveAt(int index)
	{
		if (index < 0 || (uint) index >= (uint) _size)
			throw new ArgumentOutOfRangeException("index");
		Shift(index, -1);
		Array.Clear((Array) _items, _size, 1);
		++_version;
	}
 
	public void RemoveRange(int index, int count)
	{
		CheckRange(index, count);
		if (count <= 0)
			return;
		Shift(index, -count);
		Array.Clear((Array) _items, _size, count);
		++_version;
	}
 
	public void Reverse()
	{
		Array.Reverse((Array) _items, 0, _size);
		++_version;
	}
 
	public void Reverse(int index, int count)
	{
		CheckRange(index, count);
		Array.Reverse((Array) _items, index, count);
		++_version;
	}
 
	public void ArraySort()
	{
		Array.Sort<T>(_items, 0, _size, (IComparer<T>) Comparer<T>.Default);
		++_version;
	}
 
	public void ArraySort(IComparer<T> comparer)
	{
		Array.Sort<T>(_items, 0, _size, comparer);
		++_version;
	}
 
	public void ArraySort(Comparison<T> comparison)
	{
		ArraySort(_items, _size, comparison);
		++_version;
	}
 
	public void ArraySort(int index, int count, IComparer<T> comparer)
	{
		CheckRange(index, count);
		Array.Sort<T>(_items, index, count, comparer);
		++_version;
	}
 
	public T[] ToArray()
	{
		T[] objArray = new T[_size];
		Array.Copy((Array) _items, (Array) objArray, _size);
		return objArray;
	}
 
	public void TrimExcess()
	{
		Capacity = _size;
	}
 
	public bool TrueForAll(Predicate<T> match)
	{
		CheckMatch(match);
		for (int index = 0; index < _size; ++index)
		{
			if (!match(_items[index]))
				return false;
		}
		return true;
	}
 
    private static void ArraySort(T[] array, int length, Comparison<T> comparison)
    {
        if (comparison == null)
            throw new ArgumentNullException("comparison");
        if (length <= 1)
            return;
        if (array.Length <= 1)
            return;
        try
        {
            int low0 = 0;
            int high0 = length - 1;
            ArrayQsort(array, low0, high0, comparison);
        }
        catch (Exception ex)
        {
            throw new InvalidOperationException("Comparison threw an exception.", ex);
        }
    }
 
    private static void ArrayQsort(T[] array, int low0, int high0, Comparison<T> comparison)
    {
        if (low0 >= high0)
            return;
        int index1 = low0;
        int index2 = high0;
        int index3 = index1 + (index2 - index1) / 2;
        T obj = array[index3];
        while (true)
        {
            while (index1 >= high0 || comparison(array[index1], obj) >= 0)
            {
                while (index2 > low0 && comparison(obj, array[index2]) < 0)
                    --index2;
                if (index1 <= index2)
                {
                    ArraySwap(array, index1, index2);
                    ++index1;
                    --index2;
                }
                else
                {
                    if (low0 < index2)
                        ArrayQsort(array, low0, index2, comparison);
                    if (index1 >= high0)
                        return;
                    ArrayQsort(array, index1, high0, comparison);
                    return;
                }
            }
            ++index1;
        }
    }
 
    private static void ArraySwap(T[] array, int i, int j)
    {
        T obj = array[i];
        array[i] = array[j];
        array[j] = obj;
    }
 
	[Serializable]
	public struct Enumerator : IEnumerator, IDisposable, IEnumerator<T>
	{
		private QuickList<T> l;
		private int next;
		private int ver;
		private T current;
 
		object IEnumerator.Current
		{
			get
			{
				VerifyState();
				if (next <= 0)
					throw new InvalidOperationException();
				return (object) current;
			}
		}
 
		public T Current
		{
			get
			{
				return current;
			}
		}
 
		internal Enumerator(QuickList<T> l)
		{
			this.l = l;
            next = 0;
			ver = l._version;
            current = l._items[0];
		}
 
		void IEnumerator.Reset()
		{
			VerifyState();
			next = 0;
		}
 
		public void Dispose()
		{
			l = (QuickList<T>) null;
		}
 
		private void VerifyState()
		{
			if (l == null)
				throw new ObjectDisposedException(GetType().FullName);
			if (ver != l._version)
				throw new InvalidOperationException("Collection was modified; enumeration operation may not execute.");
		}
 
		public bool MoveNext()
		{
			VerifyState();
			if (next < 0)
				return false;
			if (next < l._size)
			{
				current = l._items[next++];
				return true;
			}
			next = -1;
			return false;
		}
	}
}

Here’s how my optimized index operator looks:

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

This version should be faster because it skips the CheckIndex function call and the redundant index < 0 check. It also combines the index > _size check with the index == _size check into a single index >= _size check.

Another optimization is to allow users of QuickList to directly access the array the QuickList abstracts. This gives advanced users access to the same performance that arrays have for situations where performance is critical. The tradeoff is that reads and writes to this array skip the above range checks, which may let errors go undetected. Here's the BackingArray getter:

public T[] BackingArray
{
    get
    {
        return _items;
    }
}

The last optimization was suggested in the comments section of last week's article by Benjamin Guihaire. He reminded me that unsafe code could be used to gain even lower level access than simply indexing into the array. Here's a comparison of the two techniques for iterating over an array:

// Normal array iteration
for (var i = 0; i < Length; ++i)
{
	val = array[i]; // read
	array[i] = val; // write
}
 
// Unsafe array iteration
unsafe
{
	// Get a pointer to the first element in the array
	fixed (int* p = &array[0])
	{
		// Start a pointer out at the first element in the array
		// Advance it to the next element with each loop
		// Stop before getting to a pointer right after the last element
		for (int* pCur = p, pEnd = p+Length; pCur < pEnd; ++pCur)
		{
			val = *pCur; // read
			*pCur = val; // write
		}
	}
}

The advantage of the unsafe approach is that the built-in range checks that are done by the array index operator in C# are not being done when we use pointers in unsafe code. There are some disadvantages though. First, this is "unsafe" code because we could accidentally write bad code that writes outside of just the array's memory and causes all kinds of trouble. Second, there's a lot more code to write and it's a lot less clear than the normal version. Third, unsafe code isn't usable in some environments such as the Unity web player plugin. Lastly, you need to explicitly enable unsafe code in your Unity project. You can do that by adding a text file with -unsafe in it and putting it into your project's Assets directory with smcs.rsp as the file name.

Now let's do a performance test on the above optimizations to see if they were worth it. 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 System.Diagnostics.Stopwatch stopwatch;
	private int testIndex;
 
	private long arrayRead;
	private long arrayWrite;
	private long arrayUnsafeRead;
	private long arrayUnsafeWrite;
	private long listRead;
	private long listWrite;
	private long quickListRead;
	private long quickListWrite;
	private string report = string.Empty;
 
	void Start()
	{
		stopwatch = new System.Diagnostics.Stopwatch();
		var array = new int[Length];
		var list = new List<int>(Length);
		var quickList = new QuickList<int>(Length);
		for (var i = 0; i < Length; ++i)
		{
			array[i] = i;
			list.Add(i);
			quickList.Add(i);
		}
	}
 
	void Update()
	{
		switch (testIndex++)
		{
			case 0: TestArray(); break;
			case 1: TestArrayUnsafe(); break;
			case 2: TestList(); break;
			case 3: TestQuickList(); break;
			default: return;
		}
		BuildReport();
	}
 
	private void TestArray()
	{
		var array = new int[Length];
		for (var i = 0; i < Length; ++i)
		{
			array[i] = i;
		}
 
		int sum;
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			sum = 0;
			for (var i = 0; i < Length; ++i)
			{
				sum += array[i];
			}
		}
		arrayRead = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			for (var i = 0; i < Length; ++i)
			{
				array[i] = i;
			}
		}
		arrayWrite = stopwatch.ElapsedMilliseconds;
	}
 
	private void TestArrayUnsafe()
	{
		var array = new int[Length];
		for (var i = 0; i < Length; ++i)
		{
			array[i] = i;
		}
 
		int sum;
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			sum = 0;
			unsafe
			{
				fixed (int* p = &array[0])
				{
					for (int* pCur = p, pEnd = p+Length; pCur < pEnd; ++pCur)
					{
						sum += *pCur;
					}
				}
			}
		}
		arrayUnsafeRead = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			unsafe
			{
				fixed (int* p = &array[0])
				{
					int* pCur = p;
					for (var i = 0; i < Length; ++i)
					{
						*pCur = i;
						pCur++;
					}
				}
			}
		}
		arrayUnsafeWrite = stopwatch.ElapsedMilliseconds;
	}
 
	private void TestList()
	{
		var list = new List<int>(Length);
		for (var i = 0; i < Length; ++i)
		{
			list.Add(i);
		}
 
		int sum;
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			sum = 0;
			for (var i = 0; i < Length; ++i)
			{
				sum += list[i];
			}
		}
		listRead = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			for (var i = 0; i < Length; ++i)
			{
				list[i] = i;
			}
		}
		listWrite = stopwatch.ElapsedMilliseconds;
	}
 
	private void TestQuickList()
	{
		var quickList = new QuickList<int>(Length);
		for (var i = 0; i < Length; ++i)
		{
			quickList.Add(i);
		}
 
		int sum;
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			sum = 0;
			for (var i = 0; i < Length; ++i)
			{
				sum += quickList[i];
			}
		}
		quickListRead = stopwatch.ElapsedMilliseconds;
 
		stopwatch.Reset();
		stopwatch.Start();
		for (var it = 0; it < NumIterations; ++it)
		{
			for (var i = 0; i < Length; ++i)
			{
				quickList[i] = i;
			}
		}
		quickListWrite = stopwatch.ElapsedMilliseconds;
	}
 
	private void BuildReport()
	{
		report = string.Format(
			"Test,Array Time,Array Unsafe Time,List Time,QuickList Time\n"
			+ "Read,{0},{1},{2},{3}\n"
			+ "Write,{4},{5},{6},{7}",
			arrayRead, arrayUnsafeRead, listRead, quickListRead,
			arrayWrite, arrayUnsafeWrite, listWrite, quickListWrite
		);
	}
 
	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 640x480 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
640x480, Fastest, Windowed

And got these results:

Test	Array Time	Array Unsafe Time	List Time	QuickList Time
Read	94	67	354	315
Write	77	70	528	347

List and Array Performance Graph

Both optimizations have clearly paid off. List takes 9% longer to read from an index than QuickList and 52% longer to write. The 9% read optimization is probably just measurement variance since the code is exactly the same, but the write 52% write optimization is clearly due to the optimized set block that removes a function call and two comparisons. Even so, the performance is still nowhere near that of plain arrays as it's at least 3x slower.

As for the other optimization, iterating over the array with unsafe code has improved both read and write times. The normal index operator takes 40% longer to read and 10% longer to write. Is that worth the drawbacks? It really depends on your particular project, but at least it's an option if you need to squeeze some more performance out of your arrays when those range checks are dragging out down.

Certainly the bigger optimization is using an array directly rather than a List, even if it's a QuickList. The QuickList, however, allows you direct access via the BackingArray getter, so it's sort of the best of both worlds. If you want to keep using List, Benjamin Guihaire also suggests some code that uses reflection to get access to the private backing array:

// Get the "_items" field. This is an expensive operation, so you should cache the result.
var field = typeof(List<int>).GetField("_items", BindingFlags.NonPublic | BindingFlags.Instance);
 
// Get the "_items" array of a List. This is also expensive, so it should be cached too.
var backingArray = field.GetValue(list) as int[];

These are both expensive operations that add overhead compared to using QuickList.BackingArray or just using an array directly. However, you get to use the more standard List class and still have a workaround in case you need the speed of direct array access, optionally with unsafe code. That might make it a good compromise solution, so let's enshrine it into a reusable class:

using System;
using System.Collections.Generic;
using System.Reflection;
 
// Extension class for System.Collections.Generic.List<T> to get
// its backing array field via reflection.
// Author: Jackson Dunstan, http://JacksonDunstan.com/articles/3066
public static class ListBackingArrayGetter
{
	// Name of the backing array field
	private const string FieldName = "_items";
 
	// Flags passed to Type.GetField to get the backing array field
	private const BindingFlags GetFieldFlags = BindingFlags.NonPublic
		| BindingFlags.Instance;
 
	// Cached backing array FieldInfo instances per Type
	private static readonly Dictionary<Type, FieldInfo> itemsFields
		= new Dictionary<Type, FieldInfo>();
 
	// Get a List's backing array
	public static TElement[] GetBackingArray<TElement>(this List<TElement> list)
	{
		// Check if the FieldInfo is already in the cache
		var listType = typeof(List<TElement>);
		FieldInfo fieldInfo;
		if (itemsFields.TryGetValue(listType, out fieldInfo) == false)
		{
			// Generate the FieldInfo and add it to the cache
			fieldInfo = listType.GetField(FieldName, GetFieldFlags);
			itemsFields.Add(listType, fieldInfo);
		}
 
		// Get the backing array of the given List
		var items = (TElement[])fieldInfo.GetValue(list);
		return items;
	}
}

Using this is pretty simple:

// Get the backing array
var backingArray = list.GetBackingArray();
 
// Loop over it (normal, see above for unsafe version)
// Make sure to use List.Count since the array may be longer than
// just the elements you've put in it.
for (int i = 0, len = list.Count; i < len; ++i)
{
	val = backingArray[i]; // read
	backingArray[i] = val; // write
}

Hopefully you'll find the above techniques useful in optimizing how you use arrays and lists. There are a number of tradeoffs as no solution presented here is the best at everything at once. Which do you prefer? Let me know in the comments!

#1 by Benjamin Guihaire on June 8th, 2015 · Reply

I love the ListBackingArrayGetter class , it makes the reflection “hack” usable, definitely something I will add to my Unity projects !

#2 by Oscar Abraham on December 28th, 2019 · Reply

Hello, dear Jackson Dunstan.

This quick list seems very useful. I noticed that your site has a MIT license logo in the footer. Does that mean that this is under a MIT license? If so, is a “Copyright 2005, Jackson Dunstan” notice correct for a license for this code?

Thank you very much for your time. I hope you have a good day.

#3 by Oscar Abraham on December 28th, 2019 · Reply

PD
Sorry for the double post. I’m realizing now that the fact that the Quick List is based on code from a decompiled mscorelib probably means that it wouldn’t be legal to use it any way, am I right?

Thanks again. Sorry for bothering you.
- #4 by jackson on December 29th, 2019 · Reply
  
  All of the original code on this site (so far) has been licensed under MIT, but you’re right that in cases of code based on other open source it would usually fall under that license. So you’ll need to refer to the licensing of mscorlib rather than MIT for this particular code.

#5 by Tim Smith on March 29th, 2021 · Reply

I reran these tests, it appears QuickList read/write is slower than the native List. Since this article is from 2015, I assume List has received improvements by IL code. Do you have a revisited scenario?

#6 by jackson on April 10th, 2021 · Reply

I don’t, but you’re right that a lot has changed since 2015. We now even have Burst and native collection types that add further high-performance options, not to mention IL2CPP that’s evolved over the years. Old articles like this should be taken with a grain of salt and confirmed, as you did, by re-running the tests on the specific version of Unity the game is using.

Optimizing Arrays and Lists

Comments