Immutable Collections Performance

 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 .