SafeList, SafeDictionary–fast immutable structures

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.