Random access on .NET lists is slow, but what if I always reference the first element?

Question

I know that in general, .NET Lists are not good for random access. I've always been told that an array would be best for that. I have a program that needs to continually (like more than a billion times) access the first element of a .NET list, and I am wondering if this will slow anything down, or it won't matter because it's the first element in the list. I'm also doing a lot of other things like adding and removing items from the list as I go along, but the List is never empty.

I'm using F#, but I think this applies to any .NET language (I am using .NET Lists, not F# Lists). My list is about 100 elements long.

Answer 1

There is not much difference between the performance of random access for an array and a list. Here's a test on my machine.

var list = Enumerable.Range(1, 100).ToList();
var array = Enumerable.Range(1, 100).ToArray();

int total = 0;

var sw = Stopwatch.StartNew();
for (int i = 0; i < 1000000000; i++) {
    total ^= list[0];
}
Console.WriteLine("Time for list: {0}", sw.Elapsed);

sw.Restart();
for (int i = 0; i < 1000000000; i++) {
    total ^= array[0];
}
Console.WriteLine("Time for list: {0}", sw.Elapsed);

This produces this output:

 Time for list: 00:00:05.2002620 
 Time for array: 00:00:03.0159816

If you know you have a fixed size list, it makes sense to use an array, otherwise, there's not much cost to the list. (see update)

Update!

I found some pretty significant new information. After executing the script in release mode, the story changes quite a bit.

Time for list: 00:00:02.3048339
Time for array: 00:00:00.0805705

In this case, the performance of the array totally dominates the list. I'm pretty surprised, but the numbers don't lie.

Go with the array.