3

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.

  • 3
    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. – Ordous May 11 '15 at 12:01
  • 4
    Also the post is from 2009, wouldnt be surprised if optimizations had been added since – Ewan May 11 '15 at 12:06
  • 1
    @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. – Doc Brown May 11 '15 at 14:28
  • 1
    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. – Jon Raynor May 11 '15 at 14:29
  • 1
    Found the source code here: referencesource.microsoft.com/#mscorlib/system/collections/…. – Doc Brown May 11 '15 at 19:32
5

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.

  • 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. – JPtheK9 May 11 '15 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.