Why are arrays in .NET so much faster than lists?

user2033412 picture user2033412 · Jan 9, 2017 · Viewed 9.6k times · Source

Consider the following code:

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ListAllocationPerformance
{
    class Program
    {
        const int count = 100000000;

        public static object Memory { get; private set; }

        static void Main(string[] args)
        {
            Console.WriteLine(string.Format("count: {0}", count));
            MeasureFunction(FillListWithoutAllocation, "without allocation");
            MeasureFunction(FillListWithAllocation, "with allocation");
            MeasureFunction(FillArray, "array");
            MeasureFunction(FillUnmanagedArray, "unsafe array");
            string input = Console.ReadLine();
        }

        static void MeasureFunction(Action function, string name)
        {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            function();
            stopwatch.Stop();
            Console.WriteLine(string.Format("Function {0} finished after \t {1}ms", name, stopwatch.ElapsedMilliseconds, count));
        }

        static void FillListWithoutAllocation()
        {
            List<int> list = new List<int>();
            for (int i = 0; i < count; i++) list.Add(i);
        }

        static void FillListWithAllocation()
        {
            List<int> list = new List<int>(count);
            for (int i = 0; i < count; i++) list.Add(i);
        }

        static void FillArray()
        {
            int[] array = new int[count];
            for (int i = 0; i < count; i++) array[i] = i;
        }

        static void FillUnmanagedArray()
        {
            unsafe
            {
                int[] array = new int[count];
                fixed(int* ptr = array)

                for (int i = 0; i < count; i++) *ptr = i;
            }
        }
    }
}

The result of the release-built is stunning:

count: 100000000
Function without allocation finished after       871ms
Function with allocation finished after          684ms
Function array finished after                    168ms
Function unsafe array finished after              91ms

The array outperforms even the pre-allocated list by far! I thought that the list was basically an array under the hood -- but how come that the results differ so much?

Answer