Why is ImmutableList<T>'s enumerator so much slower compared to List<T>

Question

I have a piece of code that iterates over a small list frequently. Given that the list never changes during runtime, I replaced the implementation with ImmutableList<T>. Looking at a performance trace by dotTrace, this performs much worse than a normal List<T>:

(List<T> on left, ImmutableList<T> on right)

Why is this occurring and is there a workaround?

Answer 1

Unlike List<T> which wraps around an array that is resized as needed, ImmutableList<T> internally uses an immutable AVL tree (see Channel9 video discussing this).

So how can I still achieve this using Immutable Collections?

Use ImmutableArray<T>.

Quoting from a .NET Framework blog post about Immutable Collections

Reasons to use immutable array:

• Updating the data is rare or the number of elements is quite small (<16)
• you need to be able to iterate over the data in performance critical sections
• you have many instances of immutable collections and you can’t afford keeping the data in trees

Reasons to stick with immutable list:

• Updating the data is common or the number of elements isn’t expected to be small
• Updating the collection is more performance critical than iterating the contents