Immutable Collections Performance, Take II

Why is the performance of an immutable list over 16 times slower than a standard list? I took a peek at what it was actually doing, and it made a lot of sense. In order to maintain efficient indexing access, the actual storage of the data in the immutable list is a binary tree. With the key being used as the indexer.

This result is a much higher cost for pretty much everything. Let us look at the following:

 var listsp = Stopwatch.StartNew();
 var list = new List<int>(Enumerable.Range(0, 10*1000*1000));
  
 for (int i = 0; i < list.Count; i++)
 {
     var _ = list[i];
 }
  
 Console.WriteLine(listsp.Elapsed);
  
 var ilist = ImmutableList<int>.Empty.AddRange(list);
 listsp.Restart();
  
 for (int i = 0; i < ilist.Count; i++)
 {
     var _ = ilist[i];
 }
 Console.WriteLine(listsp.Elapsed);

This List<T> is 0.23 seconds, ImmutableList<T> takes 1.28 seconds. When I use foreach, instead, we get 0.22 seconds vs. 2.29 seconds.

As you can see from the blog post describing them, because immutable collections are mostly implemented as binary trees, I don’t really think that there is a good way to approach this as is. The problem is that the immutable collections actually need to do a lot more than what I need them to do.

Now, it might have been more acceptable to use them if the perf was limited to just writing to them, it might have been acceptable. But as you can see, we have the same problem when we are reading, and that is quite unacceptable.