Performance Zone is brought to you in partnership with:

Ayende Rahien is working for Hibernating Rhinos LTD, a Israeli based company producing developer productivity tools for OLTP applications such as NHibernate Profiler (nhprof.com), Linq to SQL Profiler(l2sprof.com), Entity Framework Profiler (efprof.com) and more. Ayende is a DZone MVB and is not an employee of DZone and has posted 435 posts at DZone. You can read more from them at their website. View Full User Profile

SafeList, SafeDictionary–fast immutable structures

12.13.2013
| 3973 views |
  • submit to reddit

After the issues we run into with immutable structures, I decided that I still wanted to maintain the same guarantees that immutable data structures gave us, but that still maintain the speed of mutable structures.

I managed to do that by making different design choices when building my implementation. While the BCL immutable collections are based on binary trees, and attempt to spare GC pressure in favor of CPU cycles, I find that for a lot of the things that we do, we can spare the memory in favor of actually being faster overall. In particular, this is true since the immutable collections are order of magnitude slower for reads than their mutable counterparts. I could have dealt with the slow writes, somehow. But we do a lot of reads, and that is utterly unacceptable.

Here is how I implemented SafeList:

   1: public class SafeList<T> : IEnumerable<T>
   2: {
   3:     List<T> _inner = new List<T>();
   4:  
   5:     public static readonly SafeList<T> Empty = new SafeList<T>();
   6:  
   7:     private SafeList()
   8:     {
   9:  
  10:     }
  11:  
  12:     public SafeList<T> AddRange(IEnumerable<T> items)
  13:     {
  14:         var inner = new List<T>(_inner);
  15:         inner.AddRange(items);
  16:         return new SafeList<T>
  17:         {
  18:             _inner = inner
  19:         };
  20:     }
  21:  
  22:     public SafeList<T> Add(T item)
  23:     {
  24:         return new SafeList<T>
  25:         {
  26:             _inner = new List<T>(_inner) {item}
  27:         };
  28:     }
  29:  
  30:     public int Count
  31:     {
  32:         get { return _inner.Count; }
  33:     }
  34:  
  35:     public T this[int i]
  36:     {
  37:         get { return _inner[i]; }
  38:     }
  39:  
  40:  
  41:     public SafeList<T> RemoveAll(Func<T, bool> filter)
  42:     {
  43:         return new SafeList<T>
  44:         {
  45:             _inner = new List<T>(_inner.Where(x => filter(x) == false))
  46:         };
  47:     }
  48:  
  49:     public T Find(Predicate<T> predicate)
  50:     {
  51:         return _inner.Find(predicate);
  52:     }
  53:  
  54:     public SafeList<T> RemoveAllAndGetDiscards(Predicate<T> filter, out List<T> discards)
  55:     {
  56:         var list = new List<T>();
  57:  
  58:         discards = list;
  59:  
  60:         return new SafeList<T>
  61:         {
  62:             _inner = new List<T>(_inner.Where(x =>
  63:             {
  64:                 if (filter(x) == false)
  65:                 {
  66:                     list.Add(x);
  67:                     return false;
  68:                 }
  69:                 return true;
  70:             }))
  71:         };
  72:  
  73:     }
  74: }

The implementation for SafeDictionary is pretty similar as well. Note that I have dedicated & optimized methods for the type of things that I need in my code.

But the key part here is that I gain the safety by always creating another copy of the underlying implementation. We are never actually mutating anything.

Sure, this results in us having to deal with a lot more allocations, but we get the same speed for reads as you do for the standard mutable collections. And more importantly, we are still faster for writes.

Published at DZone with permission of Ayende Rahien, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)