Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Immutable Collections Performance, Take II

DZone's Guide to

Immutable Collections Performance, Take II

· Performance Zone
Free Resource

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.

Topics:

Published at DZone with permission of Oren Eini, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}