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

Immutable Collections Performance

DZone's Guide to

Immutable Collections Performance

· Performance Zone
Free Resource

Download our Introduction to API Performance Testing and learn why testing your API is just as important as testing your website, and how to start today.

After finding out that a lot of our costs in Voron is actually related to immutable collections, I decided to run some isolated perf tests.

 private static void Dictionary()
 {
     var dic = new Dictionary<object, object>();
     var sp = Stopwatch.StartNew();
  
     for (int i = 0; i < 10*1000*1000; i++)
     {
         var obj = new object();
         dic[obj] = obj;
     }
  
     Console.WriteLine(sp.Elapsed);
 }                                                          

3.639 seconds

 private static void ImmutableDictionary()
 {
     var dic = ImmutableDictionary<object,object>.Empty;
     var sp = Stopwatch.StartNew();
  
     for (int i = 0; i < 10 * 1000 * 1000; i++)
     {
         var obj = new object();
         dic = dic.SetItem(obj, obj);
     }
  
     Console.WriteLine(sp.Elapsed);
 }

1 minute and 58 seconds

Yes, that is correct, the immutable version is over thirty times slower. And given that we are only using 10 million items, that is a ridiculous high rate.

I decided to do some tests to see if it is just the number of calls that we are making here:

 private static void ImmutableDictionary()
 {
     var dic = ImmutableDictionary<object,object>.Empty;
     var sp = Stopwatch.StartNew();
  
     dic = dic.SetItems(Enumerable.Range(0, 10*1000*1000).Select(i =>
     {
         var obj = new object();
         return new KeyValuePair<object, object>(obj, obj);
     }));
     
     Console.WriteLine(sp.Elapsed);
 }

1 minute

So that it appears that it isn’t the number of calls, but something intrinsic to the way it works. And how about lists?

 private static void List()
 {
     var list = new List<object>();
     var sp = Stopwatch.StartNew();
  
     for (int i = 0; i < 10 * 1000 * 1000; i++)
     {
         var obj = new object();
         list.Add(obj);
     }
  
     Console.WriteLine(sp.Elapsed);
 }                                                           

0.9 seconds

 private static void ImmutableList()
 {
     var list = ImmutableList<object>.Empty;
     var sp = Stopwatch.StartNew();
 
     for (int i = 0; i < 10 * 1000 * 1000; i++)
     {
         var obj = new object();
         list = list.Add(obj);
     }
  
     
     Console.WriteLine(sp.Elapsed);
 }

16 seconds

Ouch.

I think we are going to need to do something about this, even though I love the idea of immutable collections, 16 – 32 times slower is just going to be utterly unacceptable.

But this is for writes, how about reads?

I had written the following for both of them:

 var sp = Stopwatch.StartNew();
 for (int i = 0; i < 10*1000*1000; i++)
 {
     object value;
     dic1.TryGetValue(i, out value);
 }
  
 Console.WriteLine(sp.Elapsed);

0.45 seconds

 var sp1 = Stopwatch.StartNew();
  
 for (int i = 0; i < 10 * 1000 * 1000; i++)
 {
     object value;
     dic2.TryGetValue(i, out value);
 }
 Console.WriteLine(sp1.Elapsed);

3.11 seconds


So the summary is, the performance for our workloads is probably going to be simply unacceptable. We’ll have to find another way to handle this. The way to handle this nicely is to basically copy the values. So I wanted to know how long it would take to fully clone a 10-million items dictionary. The answer: 0.6 seconds. Doing the same with immutable dictionary? 16 seconds.

So we are going to need to do something else Sad smile.














 

Find scaling and performance issues before your customers do with our Introduction to High-Capacity Load Testing guide.

Topics:

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

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

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

{{ parent.tldr }}

{{ parent.urlSource.name }}