9

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>:

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

Why is this occurring and is there a workaround?

JohnD
  • 3,884
  • 1
  • 28
  • 40
  • 1
    possible duplicate of [Slow performance from ImmutableList Remove method in Microsoft.Bcl.Immutable](http://stackoverflow.com/questions/24785116/slow-performance-from-immutablelistt-remove-method-in-microsoft-bcl-immutable) – Peter Duniho Feb 20 '15 at 07:53
  • @PeterDuniho no, that's for modifying the list. This is iterating over it. – JohnD Feb 20 '15 at 11:32
  • The _reason_ for the slowness is the same in both cases. So, you are saying that, had you read the answers to the other post before posting your own question, you still would not have been able to figure out for yourself what it was about the `ImmutableList` that made it so much slower than `List`? Interesting. – Peter Duniho Feb 20 '15 at 19:20
  • @PeterDuniho Yes, because those questions were asking about poor modification performance (Which I expected to be bad), I looked past them thinking it was not relevant to my issue. – JohnD Feb 20 '15 at 19:24
  • Sorry, I don't see how the fact that you _didn't read_ the question and its answers is relevant to a determination that the question and its answers do in fact answer your own question, which in turn then is in fact a duplicate of that question and its answers. Being a duplicate or not is a simple factual relationship between the two questions, and is completely unaffected by your own actions (or anyone else's). – Peter Duniho Feb 20 '15 at 19:31
  • 3
    @PeterDuniho I created this question and answered it, because it was a specific problem I encountered (which is not what was asked about in your linked question) and I shared a specific answer. I disagree that because the same conclusions about `ImmutableList` were reached in both questions that this is a duplicate. I do know that there was no question that matched my specific case (iteration perf) so I created and answered this one to fill that gap. – JohnD Feb 20 '15 at 19:38

1 Answers1

19

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
Lukas Kabrt
  • 5,441
  • 4
  • 43
  • 58
JohnD
  • 3,884
  • 1
  • 28
  • 40