Preview of Immutable Collections Released on NuGet

Preview of Immutable Collections Released on NuGet

Rate This
  • Comments 57




Background and reasons for immutable collections

The .NET Framework already includes many highly-tuned generic collections. And in several cases read-only interfaces or wrapper classes exist as well. So how are immutable collections different and why do we need them? In short, because read-only collection types are merely facades over collections that can change.


In contrast, if someone provides you with data via an immutable type, the guarantee is that the data will never change. You can hold a reference to it as long as you want, enumerate it, search it, etc., from any thread at any time, and be completely confident that you’ll get the expected behavior.

There are several kinds or levels of immutability, in fact. These immutable collections never allow mutation, yet offer mutating methods that return new collections, while sharing data across versions very efficiently. You can read up more on various types of immutability from Eric Lippert blog post Immutability in C# Part One: Kinds of Immutability.

Why should I use immutability?


  4. Functional programming friendly.

Introducing the immutable collections

The NuGet package preview includes these types:

  • ImmutableStack<T>
  • ImmutableQueue<T>
  • ImmutableList<T>
  • ImmutableHashSet<T>
  • ImmutableSortedSet<T>
  • ImmutableDictionary<K, V>
  • ImmutableSortedDictionary<K, V>


I’ll look at how you might use ImmutableList<T>. First, I’ll start by acquiring an empty immutable list of fruit:

        var emptyFruitBasket = ImmutableList<string>.Empty;

Notice that rather than a public constructor we provide a  static Empty property. Using a static Empty property is a departure from a well-entrenched pattern, and there is a reason for it. A constructor must allocate an object, yet given the immutability of these collections, a new object could only ever represent an empty list. Since mutating the collection creates a new collection, using a constructor would cause the creation of multiple objects to represent an empty list, which would be wasteful. A static property allows us to return an empty list singleton which all code in your app can share.

An empty list isn’t that interesting. Next I will add some elements to it. As just stated, this is an immutable list, so when I request a change, a new list is allocated and the results are assigned to some variable:

        var fruitBasketWithApple = emptyFruitBasket.Add("Apple");

The Add method returned a new list with one element, and I assigned this list to a new variable. The original emptyFruitBasket list is still empty. This is similar to System.String, which has an Empty static property, and mutating methods that always return new strings that include the requested change.

You may not want to come up with unique names for new local variables on each assignment, so you can simply reassign to the same local variable:

       var fruitBasket = ImmutableList<string>.Empty;
       fruitBasket = fruitBasket.Add("Apple");
       fruitBasket = fruitBasket.Add(“Banana”);
       fruitBasket = fruitBasket.Add(“Celery”);  

Just as before, the original empty list was not modified. But I’ve replaced the reference to the empty list with a reference to the new populated list.

Watch out for this common pitfall though: it’s easy to forget to reassign the result of a mutation to a local variable:

       var list = ImmutableList<int>.Empty;
       list.Add(3); // forgot to reassign result to a local variable
       // contents of the “list” local variable is still empty!    

To avoid creating so many intermediate list objects, you can add several elements at once:

        fruitBasket = fruitBasket.AddRange(new [] { “Kiwi”, “Lemons”, “Grapes” });    

Since every mutating operation returns a new object that you can then mutate, you can also use a fluent-like syntax:

        var fruitBasket = ImmutableList<string>.Empty
            .AddRange(new [] { “Kiwi”, “Lemons”, “Grapes” });

We do not simply copy the contents of the immutable collections with each change. This would result in poor performance with collections of any interesting size, occupy too much memory and stress the GC. Instead, we built these immutable collections to share as much memory between instances as possible. Following is a contrived extreme case of a list with 10,000 elements:

        var hugeList = ImmutableList<int>.Empty.AddRange(Enumerable.Range(1, 10000));  

Now I’ll add one more item to the list:

        var hugeListPlus1 = hugeList.Add(10001);    

How much memory have we used between both hugeList and hugeListPlus1? Only slightly more than for hugeList alone. We did this by storing the immutable collections in immutable binary tree structures instead of flat arrays. When we create a list based on an existing list, we start with the existing binary tree and change just a few nodes in it, allocating new objects for each changed node, and return a list that points to the new root node of the binary tree. So hugeList and hugeListPlus1 actually share almost all their memory. If the app releases its reference to either list, the data unique to that particular list is immediately a candidate for garbage collection, so we don’t create memory leaks.

Introducing the Builders

Sometimes you need to “mutate” an immutable collection many times as you’re initializing it. Each top-level mutation call into an immutable collection results in allocating a few new nodes in that binary tree. All those extra allocations can add up in terms of GC pressure and performance. The same problem exists when you mutate strings repeatedly, which you can avoid by using the StringBuilder in those cases. Immutable collections use the same approach as strings. All the immutable collections that create GC pressure from many mutations provide ToBuilder() methods. The builder classes implement the same mutable interfaces that you’re used to, allowing you to pass these builders around as needed to initialize or update your collections. Then you can restore immutability by calling ToImmutable(). Here’s an example:

        /// <summary>Maintains the set of customers.</summary>
        private ImmutableHashSet<Customer> customers;

        public ImmutableHashSet<Customer> GetCustomersInDebt()
            // Since most of our customers are debtors, start with
            // the customers collection itself.
    var debtorsBuilder = this.customers.ToBuilder();
    // Now remove those customers that actually have positive balances.
    foreach (var customer in this.customers)     {         if (customer.Balance >= 0.0)         {             // We don’t have to reassign the result because             // the Builder modifies the collection in-place.             debtorsBuilder.Remove(customer);         }     }       return debtorsBuilder.ToImmutable(); }

These builders are mutable collections that use exactly the same data structure as the immutable collections, but without the immutability requirement, allowing them to be very efficient about their memory use as you add or remove elements. In the above sample, the ToBuilder() did not copy the customers collection, but rather keeps using the existing immutable collection you already had. When the builder collection is modified, it allocates a new reference to the collection that points to a slightly modified collection, which preserves the original this.customers collection unmodified. Finally, when ToImmutable() is called, the builder “freezes” its modified internal structure and returns the new reference to the immutable collection. Important note: No immutable collections are modified in the execution of the above example, nor was the entire collection copied at any time.

You don’t always need to use builders though. If you can mutate your collections with just one method call then a builder isn’t necessary. For example, the above sample could be rewritten without builders using a lambda:

       private ImmutableHashSet<Customer> customers;

       public ImmutableHashSet<Customer> GetCustomersInDebt()
           return this.customers.Except(c => c.Balance >= 0.0);

The above example is just as efficient as the Builder approach. However, not all bulk modifications to immutable collections are expressible as a single method call with a lambda, and you can use the Builders in those cases.

Performance characteristics


When they are typically faster

Immutable collections’ performance shines best when your application already requires snapshot semantics, whether for thread-safety or just for the simplicity it offers your codebase. For example, you might have code like this in your application, in order to provide some “snapshot” semantics or provide thread-safety:

     private List<T> collection;
     public IReadOnlyList<int> SomeProperty
             lock (this)
                 return this.collection.ToList();

Every time this property is queried, it makes an entire copy of your internal collection. Replacing this mutable collection with an immutable collection can dramatically improve this scenario because returning a reference of the current immutable collection implicitly retains the snapshot semantic and no copying (or locking) is required. It becomes:

    private ImmutableList<T> collection;
public IReadOnlyList<int> SomeProperty { get { return this.collection; } }

Switching to immutable collections in some components of Visual Studio has helped us dramatically improve the performance of some features.

When they might be slower

There are some noteworthy differences in algorithmic complexity between mutable and immutable collection types:


Mutable (amortized)

Mutable (worst case)













O(log n)




O(log n)


O(log n)


O(log n)




O(log n)


O(log n)

O(n log n)

O(log n)

Why are the immutable types more prone to O(log n) time where mutable types are O(1)? It’s a consequence of the internal data structures that allow sharing across instances of the collections. For instance a mutable HashSet<T> allocates a single array, and stores elements in that array at the index determined by their hash code. This providers O(1) lookup and storage times. If an ImmutableHashSet<T> used this same kind of data storage, then every mutation would require reallocating and copying the entire array just to change one entry, which would quickly tank performance and GC pressure as the collections grew large. Instead, these immutable collections use immutable balanced binary trees to store their data, allowing very efficient data sharing across mutated instances of the collections. As a result however, every lookup or change requires a tree traversal that has (at worst) an algorithmic complexity of O(log n).

Another point to consider when considering algorithm complexity however is worst case. Mutable collections can outgrow their initially allocated capacity and have to reallocate and copy their contents into a larger array. These immutable collections grow organically so they don’t experience the O(n) worst case on growth that mutable collections do. The hash-based immutable collections can still degrade to O(n) time on hash collisions just like mutable collections however.

Memory characteristics

The immutable collections spend a bit more memory per element for storage than their mutable counterparts, but without the slack space that mutable collections tend to have in their arrays. This means you win some, but you lose some too. Given a single instance of a collection, your actual mileage may vary as far as how its memory consumption compares between the two types.

When removing elements from your collection, the mutable collections generally don’t shrink their arrays so you don’t reclaim that memory. Immutable collections immediately shrink their binary trees for each removed element so the memory is a candidate for garbage collection.

How can I get started?


Call for feedback


Frequently asked questions

Q: Can I only store immutable data in these immutable collections?
A: You can store all types of data in these collections. The only immutable aspect is the collections themselves, not the items they contain.

Q: Do Builders let you modify an immutable collection?
A: No. Immutable collections can never be modified. Builders give you the ability to start and finish a series of mutations with immutable instances, but in between use mutability for greater efficiency. Both the collections you start and finish with are in fact immutable.

Q: Is it safe to use immutable collections in a multi-threaded environment?
A: Yes. All truly immutable object graphs in .NET are safe in a multi-threaded environment.

Q: Mutable collections are fine for me, aren’t they? I’m not into F# or a math buff. How can immutable collections help me?
A: Immutable collections don’t entirely supersede the mutable collections found in the .NET Framework. You can and often should continue to use them as you have before. To learn more about immutability and what its benefits are, you may be interested in reading Read only, frozen, and immutable collections.

Q: I’ve heard that immutable collections are slow. Are these any different? Can I use them when performance or memory is important?
A: These immutable collections have been highly tuned to have competitive performance characteristics to the mutable collections while balancing memory sharing. In some cases they are very nearly as fast as the mutable collections both algorithmically and in actual time, sometimes even faster, while in other cases they are algorithmically more complex. In many cases however the difference will be negligible. Generally you should use the simplest code to get the job done and then tune for performance as necessary. The immutable collections help you write simple code, especially when thread-safety has to be considered.

Q: I want to try these immutable collections out but I need a convenient escape hatch in case their performance doesn’t meet my requirements. What can I do?
A: Use the new .NET 4.5 readonly interfaces on all your public APIs, such as IReadOnlyCollection<T> and IReadOnlyList<T>. In your implementation you may use immutable collections, which implement these interfaces. If in the end you need to switch to mutable collections, you’ll be able to do so without any breaking changes.

Q: I’m totally jazzed about these immutable collections. Where can I find out more?
A: There are lots of fun details about optimizations these collections have, best practices and anti-practices, etc. that don’t fit in this post. But these details may appear in future posts if you follow the immutability tag on my blog here on MSDN.

  • I'm just starting to play! Looks like an answer to a bunch of difficulties I was having with a design...

    - When I try to add this as a dependency to a portable library I'm creating I get a fail due to the Validation library... perhaps Validation doesn't have a portable library version?

    - When I build a simple windows store test I get an warning that "NeutralResourcesLanguageAttribute" is missing on Sytem.Collections.Immutable in the lib\win8 subdir. I've not tried building a real Windows store app with this, just exploring via tests now, so this may disappear.

  • Gordan: the Validation failure you're seeing is probably because you're using an old version of NuGet. Try upgrading it using Tools -> Extensions and Updated. Thanks for the tip about the missing attribute. We should be able to get that sorted out.

  • @Fduch:

    >>@Ark-kun, what are you looking for in an immutable bag collection that the ImmutableList type can't provide?

    >I want the modification speed of a Dictionary/HashSet without the uniqueness requirement.  But if all immutable collections are equally slow, then ImmutableList is same as ImmutableBag.

    What you're describing actually sounds like a MultiDictionary. Which isn't included in this library but we may in the future, so thanks for the feedback.

  • Thanks for your answers!

    I'm using v 2.2.31210.9045 of nuget. According to the webpage in the visual studio extensions web page, that is the most recent version.

    Maybe I should try installing validation first to get around this error. I'll do this at some point and get back to you if it works.

  • @Gordon: What is you portable class library targeting? The current drop only supports .NET 4.5 and Windows Store. We are working on enabling phone support (mostly likely Phone 8).

  • It was windows store. I'll try to do some more careful cross checks this evening.

  • @Gordon: Strange. Are you sure your portable class library isn't targeting anything except .NET 4.5 and Windows Store? If that's the case please contact me via mail (immol at microsoft dot com). Thanks!

  • Weird. The last comment with details got eaten. Ok, so the portable library sounds like it might have been targeting others. I didn't realize the multi-platform targeting of the portable library needed that much fine grained control. I'll report back as soon as I try it out.

  • Thanks for the great work! Immutable collections  are indeed a necessity in multithreaded scenarios.

    Is there any chance that we'll see an article on the internal workings of these collections? It would be extremely interesting to dig in the algorithms for reconstructing the binary trees for reuse.

  • Thanks for this package - I'm already finding it indispensable. Just a few comments:

    1. It's great to see ImmutableDictionary<K,V>.GetValueOrDefault - it's my most-used extension method on Dictionaries. However, it does not seem to be implemented on the ImmutableDictionary<K,V>.Builder type.

    2. Can I suggest an enhancement to GetValueOrDefault? It would be good to have an extra optional parameter allowing the user to specify their own default. So the method would be, roughly:

           public static TValue GetValueOrDefault<TKey, TValue>(this ImmutableDictionary<TKey, TValue> dictionary, TKey key, TValue @default = default(TValue))


               TValue res;

               return dictionary.TryGetValue(key, out res) ? res : @default;


    This is compatible with existing use, but gives a bit more flexibility.

    3. There's something slightly odd with the ImmutableDictionary<K,V>.Builder type. When using it with ReSharper 7.1 installed I get warnings using the TryGetValue and ContainsKey methods, saying "Cannot implicitly convert type 'bool [mscorlib, Version=, ...]' to 'bool [mscorlib, Version=, ...]'". Also, when indexing into an element of this type, I get a warning "Cannot apply indexing to an expression of type 'System.Collections.ImmutableDictionary<Foo,Bar>.Builder'". In both cases the program compiles and runs, but the warnings suggest something is not quite right (though it might be a ReSharper problem, of course).

  • @Oleh Zheleznyak: Thanks! Regarding the inner workings -- stay tuned.

    @Nick N: Good suggestions. I've added (1) and (2) to our backlog. Regarding (3): looks to me like are using portable class library. What platforms do you target?

  • @Immo Landwerth - thanks for your reply. I haven't done anything in particular about the portable class library: I don't have the Portable Library Tools installed, and the solution is just targetting AnyCPU. The project reference is to the DLL in lib\net45 if that's useful to know.

Page 4 of 4 (57 items) 1234