Why is iterating through List<T> more expensive than iterating through Array in .NET?

Question

According to the answers in this post, List<T> is backed by an Array. According to this article, list iteration is considerably slower than array iteration.

If Lists are arrays 'under the hood', why do they take longer to iterate over, especially with foreach?

Note: This is assuming Lists are implemented with Arrays. I might have just interpreted the information wrong.

• Ordous: Because there's a hood to go under. When doing something as simple as integer or double addition, that extra method access and object creation takes its toll.
• Ewan: Also the post is from 2009, wouldnt be surprised if optimizations had been added since
• Doc Brown: @Ewan: surprise - I did some benchmarks 10 minutes ago using .NET framework 4.5.1, VS 2013, Release build), and I can confirm reading arrays with a classic for loop is still faster than reading lists (~4 to 5 times on my machine for an int array). However, in most real world situations, the difference is irrelevant.
• Jon Raynor: Most likely because an array uses the length of the array and an index to loop through the elements and a list uses an Enumerator which has to maintain state and check whether it can move to the next element.
• Doc Brown: Found the source code here: referencesource.microsoft.com/#mscorlib/system/collections/….

Answer 1

Iterating through a List is (slightly) slower than a plain array due to a few factors:

1. Bounds checks: This is likely to be the biggest factor; every single indexer access to the List is going to do a bounds check. Bounds checking on a raw array can often be trivially optimized out of a loop by the JIT.

2. Method call costs: The indexer on a List is a method call. This might get inlined, but it also might not.

3. An extra indirection: In order to get to the array inside the List, you need to dereference the List reference. With an array, you have a reference directly to the necessary data.

4. Potentially an extra copy of the element: When you use the List indexer, you get a copy of the element back. With an array, you can access the element directly in memory. Depending on what the rest of your code looks like, you can avoid making a copy of that data.

5. When using the Enumerator to iterate, your costs are mostly dominated by the aforementioned bounds check as well as the "version" check to make sure you haven't modified the list while iterating over it.

• JPtheK9: Thanks for the thorough answer. I guess the articles I read are a bit outdated but it's interesting that just going through the 'hood' requires this much to be done and creates that much overhead.