Performance of Arrays vs. Lists

Question

Say you need to have a list/array of integers which you need iterate frequently, and I mean extremely often. The reasons may vary, but say it's in the heart of the inner most loop of a high volume processing.

In general, one would opt for using Lists (List) due to their flexibility in size. On top of that, msdn documentation claims Lists use an array internally and should perform just as fast (a quick look with Reflector confirms this). Neverless, there is some overhead involved.

Did anyone actually measure this? would iterating 6M times through a list take the same time as an array would?

Answer 1

Short answer:

More detailed answer you will find by the following link: https://stackoverflow.com/a/29263914/4423545

Answer 2

I think the performance will be quite similar. The overhead that is involved when using a List vs an Array is, IMHO when you add items to the list, and when the list has to increase the size of the array that it's using internally, when the capacity of the array is reached.

Suppose you have a List with a Capacity of 10, then the List will increase it's capacity once you want to add the 11th element. You can decrease the performance impact by initializing the Capacity of the list to the number of items it will hold.

But, in order to figure out if iterating over a List is as fast as iterating over an array, why don't you benchmark it ?

int numberOfElements = 6000000;

List<int> theList = new List<int> (numberOfElements);
int[] theArray = new int[numberOfElements];

for( int i = 0; i < numberOfElements; i++ )
{
    theList.Add (i);
    theArray[i] = i;
}

Stopwatch chrono = new Stopwatch ();

chrono.Start ();

int j;

 for( int i = 0; i < numberOfElements; i++ )
 {
     j = theList[i];
 }

 chrono.Stop ();
 Console.WriteLine (String.Format("iterating the List took {0} msec", chrono.ElapsedMilliseconds));

 chrono.Reset();

 chrono.Start();

 for( int i = 0; i < numberOfElements; i++ )
 {
     j = theArray[i];
 }

 chrono.Stop ();
 Console.WriteLine (String.Format("iterating the array took {0} msec", chrono.ElapsedMilliseconds));

 Console.ReadLine();

On my system; iterating over the array took 33msec; iterating over the list took 66msec.

To be honest, I didn't expect that the variation would be that much. So, I've put my iteration in a loop: now, I execute both iteration 1000 times. The results are:

iterating the List took 67146 msec iterating the array took 40821 msec

Now, the variation is not that large anymore, but still ...

Therefore, I've started up .NET Reflector, and the getter of the indexer of the List class, looks like this:

public T get_Item(int index)
{
    if (index >= this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    return this._items[index];
}

As you can see, when you use the indexer of the List, the List performs a check whether you're not going out of the bounds of the internal array. This additional check comes with a cost.

Answer 3

Since I had a similar question this got me a fast start.

My question is a bit more specific, 'what is the fastest method for a reflexive array implementation'

The testing done by Marc Gravell shows a lot, but not exactly access timing. His timing include the looping over the array's and lists as well. Since I also came up with a third method that I wanted to test, a 'Dictionary', just to compare, I extended hist test code.

Firts, I do a test using a constant, which gives me a certain timing including the loop. This is a 'bare' timing, excluding the actual access. Then I do a test with accessing the subject structure, this gives me and 'overhead included' timing, looping and actual access.

The difference between 'bare' timing and 'overhead indluded' timing gives me an indication of the 'structure access' timing.

But how accurate is this timing? During the test windows will do some time slicing for shure. I have no information about the time slicing but I asume it is evenly distributed during the test and in the order of tens of msec which means that the accuracy for the timing should be in the order of +/- 100 msec or so. A bit rough estimate? Anyway a source of a systematic mearure error.

Also, the tests were done in 'Debug' mode with no optimalisation. Otherwise the compiler might change the actual test code.

So, I get two results, one for a constant, marked '(c)', and one for access marked '(n)' and the difference 'dt' tells me how much time the actual access takes.

And this are the results:

          Dictionary(c)/for: 1205ms (600000000)
          Dictionary(n)/for: 8046ms (589725196)
 dt = 6841

                List(c)/for: 1186ms (1189725196)
                List(n)/for: 2475ms (1779450392)
 dt = 1289

               Array(c)/for: 1019ms (600000000)
               Array(n)/for: 1266ms (589725196)
 dt = 247

 Dictionary[key](c)/foreach: 2738ms (600000000)
 Dictionary[key](n)/foreach: 10017ms (589725196)
 dt = 7279

            List(c)/foreach: 2480ms (600000000)
            List(n)/foreach: 2658ms (589725196)
 dt = 178

           Array(c)/foreach: 1300ms (600000000)
           Array(n)/foreach: 1592ms (589725196)
 dt = 292


 dt +/-.1 sec   for    foreach
 Dictionary     6.8       7.3
 List           1.3       0.2
 Array          0.2       0.3

 Same test, different system:
 dt +/- .1 sec  for    foreach
 Dictionary     14.4   12.0
       List      1.7    0.1
      Array      0.5    0.7

With better estimates on the timing errors (how to remove the systematic measurement error due to time slicing?) more could be said about the results.

It looks like List/foreach has the fastest access but the overhead is killing it.

The difference between List/for and List/foreach is stange. Maybe some cashing is involved?

Further, for access to an array it does not matter if you use a for loop or a foreach loop. The timing results and its accuracity makes the results 'comparible'.

Using a dictionary is by far the slowest, I only considered it because on the left side (the indexer) I have a sparse list of integers and not a range as is used in this tests.

Here is the modified test code.

Dictionary<int, int> dict = new Dictionary<int, int>(6000000);
List<int> list = new List<int>(6000000);
Random rand = new Random(12345);
for (int i = 0; i < 6000000; i++)
{
    int n = rand.Next(5000);
    dict.Add(i, n);
    list.Add(n);
}
int[] arr = list.ToArray();

int chk = 0;
Stopwatch watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    int len = dict.Count;
    for (int i = 0; i < len; i++)
    {
        chk += 1; // dict[i];
    }
}
watch.Stop();
long c_dt = watch.ElapsedMilliseconds;
Console.WriteLine("         Dictionary(c)/for: {0}ms ({1})", c_dt, chk);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    int len = dict.Count;
    for (int i = 0; i < len; i++)
    {
        chk += dict[i];
    }
}
watch.Stop();
long n_dt = watch.ElapsedMilliseconds;
Console.WriteLine("         Dictionary(n)/for: {0}ms ({1})", n_dt, chk);
Console.WriteLine("dt = {0}", n_dt - c_dt);

watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    int len = list.Count;
    for (int i = 0; i < len; i++)
    {
        chk += 1; // list[i];
    }
}
watch.Stop();
c_dt = watch.ElapsedMilliseconds;
Console.WriteLine("               List(c)/for: {0}ms ({1})", c_dt, chk);

watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    int len = list.Count;
    for (int i = 0; i < len; i++)
    {
        chk += list[i];
    }
}
watch.Stop();
n_dt = watch.ElapsedMilliseconds;
Console.WriteLine("               List(n)/for: {0}ms ({1})", n_dt, chk);
Console.WriteLine("dt = {0}", n_dt - c_dt);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    for (int i = 0; i < arr.Length; i++)
    {
        chk += 1; // arr[i];
    }
}
watch.Stop();
c_dt = watch.ElapsedMilliseconds;
Console.WriteLine("              Array(c)/for: {0}ms ({1})", c_dt, chk);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    for (int i = 0; i < arr.Length; i++)
    {
        chk += arr[i];
    }
}
watch.Stop();
n_dt = watch.ElapsedMilliseconds;
Console.WriteLine("Array(n)/for: {0}ms ({1})", n_dt, chk);
Console.WriteLine("dt = {0}", n_dt - c_dt);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    foreach (int i in dict.Keys)
    {
        chk += 1; // dict[i]; ;
    }
}
watch.Stop();
c_dt = watch.ElapsedMilliseconds;
Console.WriteLine("Dictionary[key](c)/foreach: {0}ms ({1})", c_dt, chk);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    foreach (int i in dict.Keys)
    {
        chk += dict[i]; ;
    }
}
watch.Stop();
n_dt = watch.ElapsedMilliseconds;
Console.WriteLine("Dictionary[key](n)/foreach: {0}ms ({1})", n_dt, chk);
Console.WriteLine("dt = {0}", n_dt - c_dt);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    foreach (int i in list)
    {
        chk += 1; // i;
    }
}
watch.Stop();
c_dt = watch.ElapsedMilliseconds;
Console.WriteLine("           List(c)/foreach: {0}ms ({1})", c_dt, chk);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    foreach (int i in list)
    {
        chk += i;
    }
}
watch.Stop();
n_dt = watch.ElapsedMilliseconds;
Console.WriteLine("           List(n)/foreach: {0}ms ({1})", n_dt, chk);
Console.WriteLine("dt = {0}", n_dt - c_dt);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    foreach (int i in arr)
    {
        chk += 1; // i;
    }
}
watch.Stop();
c_dt = watch.ElapsedMilliseconds;
Console.WriteLine("          Array(c)/foreach: {0}ms ({1})", c_dt, chk);

chk = 0;
watch = Stopwatch.StartNew();
for (int rpt = 0; rpt < 100; rpt++)
{
    foreach (int i in arr)
    {
        chk += i;
    }
}
watch.Stop();
n_dt = watch.ElapsedMilliseconds;
Console.WriteLine("Array(n)/foreach: {0}ms ({1})", n_dt, chk);
Console.WriteLine("dt = {0}", n_dt - c_dt);

Answer 4

Since List<> uses arrays internally, the basic performance should be the same. Two reasons, why the List might be slightly slower:

• To look up a element in the list, a method of List is called, which does the look up in the underlying array. So you need an additional method call there. On the other hand the compiler might recognize this and optimize the "unnecessary" call away.
• The compiler might do some special optimizations if it knows the size of the array, that it can't do for a list of unknown length. This might bring some performance improvement if you only have a few elements in your list.

To check if it makes any difference for you, it's probably best adjust the posted timing functions to a list of the size you're planning to use and see how the results for your special case are.

Answer 5

Here's one that uses Dictionaries, IEnumerable:

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

static class Program
{
    static void Main()
    {
        List<int> list = new List<int>(6000000);

        for (int i = 0; i < 6000000; i++)
        {
                list.Add(i);
        }
        Console.WriteLine("Count: {0}", list.Count);

        int[] arr = list.ToArray();
        IEnumerable<int> Ienumerable = list.ToArray();
        Dictionary<int, bool> dict = list.ToDictionary(x => x, y => true);

        int chk = 0;
        Stopwatch watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = list.Count;
            for (int i = 0; i < len; i++)
            {
                chk += list[i];
            }
        }
        watch.Stop();
        Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                chk += arr[i];
            }
        }
        watch.Stop();
        Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in Ienumerable)
            {
                chk += i;
            }
        }

        Console.WriteLine("Ienumerable/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in dict.Keys)
            {
                chk += i;
            }
        }

        Console.WriteLine("Dict/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);


        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in list)
            {
                chk += i;
            }
        }

        watch.Stop();
        Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in arr)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);



        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in Ienumerable)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("Ienumerable/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in dict.Keys)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("Dict/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        Console.ReadLine();
    }
}

Answer 6

[See also this question]

I've modified Marc's answer to use actual random numbers and actually do the same work in all cases.

Results:

         for      foreach
Array : 1575ms     1575ms (+0%)
List  : 1630ms     2627ms (+61%)
         (+3%)     (+67%)

(Checksum: -1000038876)

Compiled as Release under VS 2008 SP1. Running without debugging on a Q6600@2.40GHz, .NET 3.5 SP1.

Code:

class Program
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>(6000000);
        Random rand = new Random(1);
        for (int i = 0; i < 6000000; i++)
        {
            list.Add(rand.Next());
        }
        int[] arr = list.ToArray();

        int chk = 0;
        Stopwatch watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = list.Count;
            for (int i = 0; i < len; i++)
            {
                chk += list[i];
            }
        }
        watch.Stop();
        Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = arr.Length;
            for (int i = 0; i < len; i++)
            {
                chk += arr[i];
            }
        }
        watch.Stop();
        Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in list)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in arr)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);
        Console.WriteLine();

        Console.ReadLine();
    }
}