Immutable collections ready for prime time

Today I’m very happy to announce that we released the stable version of the Microsoft.Bcl.Immutable NuGet package. We also published the MSDN documentation on immutable collections.

Thank you!

Nine months ago, we shipped the first preview of immutable collections. This was one of the first BCL features that we decided to ship early and often by releasing out of band (that is, outside the core .NET Framework releases). This allowed us to have a public design discussion, which, in turn, gave us the ability to address your feedback in a faster and more direct way than ever before.

Many of you participated and commented on our blog posts. Immutable collections wouldn’t be what it is now in this stable release if it weren’t for the great feedback and discussion we had with you. Thanks to everybody who participated!

What are immutable collections?

Over time, the .NET Framework has added many features that made concurrent programming a lot easier. This started with the introduction of the thread pool, got a lot more powerful with the task-based model and the Task Parallel Library (TPL), and was improved even more by the addition of the async and await language keywords.

While creating and running concurrently is easier than ever, one of the fundamental problems still exists: mutable shared state. Reading from multiple threads is typically very easy, but once the state needs to be updated, it gets a lot harder, especially in designs that require locking.

An alternative to locking is making use of immutable state. Immutable data structures are guaranteed to never change and can thus be passed freely between different threads without worrying about stepping on somebody else’s toes.

This design creates a new problem though: How do you manage changes in state without copying the entire state each time? This is especially tricky when collections are involved.

This is where immutable collections come in. We created the following immutable collections to make it a lot easier to create immutable data structures:

Let’s look at an example. You have built a billing system and you see that an immutable design will enable you to pass orders around without having to worry about data corruption when multiple threads are involved. For example, you could implement printing selected orders from a worker thread by passing a snapshot of them to the thread. This way you avoid blocking the UI, and allow the user to edit orders without affecting the snapshot passed to the worker thread.

Your mutable design might look like this:

class OrderLine
{
    public int Quantity { get; set; }
    public decimal UnitPrice { get; set; }
    public float Discount { get; set; }

    public decimal Total
    {
        get
        {
            return Quantity * UnitPrice * (decimal) (1.0f - Discount);
        }
    }
}

class Order 
{     
    public Order()
    {
         Lines = new List<OrderLine>();
    } 

    public List<OrderLine> Lines { get; } 
}

Now let’s see how you would convert this to an immutable design.

Let’s start with OrderLine. A first step would be to make the properties read-only and initialize them from the constructor:

class OrderLine
{
    public OrderLine(int quantity, decimal unitPrice, float discount)
    {
        Quantity = quantity;
        UnitPrice = unitPrice;
        Discount = discount;
    }

    public int Quantity { get; }

    public decimal UnitPrice { get; }

    public float Discount { get; }

    public decimal Total
    {
        get
        {
            return Quantity * UnitPrice * (decimal) (1.0f - Discount);
        }
    }
}

This new design requires that you create a new instance of an OrderLine whenever any of the values changes. You can make the design a bit more convenient by adding WithXxx methods that let you update individual properties without having to explicitly call the constructor yourself:

class OrderLine
{
    // ...

    public OrderLine WithQuantity(int value)
    {
        return value == Quantity
                ? this
                : new OrderLine(value, UnitPrice, Discount);
    }

    public OrderLine WithUnitPrice(decimal value)
    {
        return value == UnitPrice
                ? this
                : new OrderLine(Quantity, value, Discount);
    }

    public OrderLine WithDiscount(float value)
    {
        return value == Discount
                ? this
                : new OrderLine(Quantity, UnitPrice, value);
    }
}

This makes the immutable type very easy to use:

OrderLine apple = new OrderLine(quantity: 1, unitPrice: 2.5m, discount: 0.0f);
OrderLine discountedAppled = apple.WithDiscount(.3f);

Two things are noteworthy:

The WithXxx methods try to avoid creating new instances if the new value is identical to the current value.
Fruits, especially apples, seem to be expensive.

(By the way, if you dislike the amount of typing involved in creating an immutable type, you aren’t alone. Andrew Arnott has created a T4 template that helps you with that.)

Now let’s see how we would implement Order in an immutable fashion. The Lines property is already read-only, but it refers to an object that is mutable. Since it’s a collection, it’s easy to convert by simply replacing it with ImmutableList<T>:

class Order
{
    public Order(IEnumerable<OrderLine> lines)
    {
        Lines = lines.ToImmutableList();
    }

    public ImmutableList<OrderLine> Lines { get; }

    public Order WithLines(IEnumerable<OrderLine> value)
    {
        return Object.ReferenceEquals(Lines, value)
            ? this
            : new Order(value);
    }
}

This design has some interesting properties:

The constructor accepts IEnumerable<T>, which allows passing in any collection.
We use the ToImmutableList() extension method, which will convert the enumerable to an ImmutableList<OrderLine>. If the instance is already an immutable list, it will simply cast instead of creating a new collection.
The WithLines() method follows the convention from our OrderLine, which avoids creating a new instance if the new list is identical to the current list of lines.

We could also add some convenience methods to make it easier to update the order lines:

class Order
{
    //...

    public Order AddLine(OrderLine value)
    {
        return WithLines(Lines.Add(value));
    }

    public Order RemoveLine(OrderLine value)
    {
        return WithLines(Lines.Remove(value));
    }

    public Order ReplaceLine(OrderLine oldValue, OrderLine newValue)
    {
        return oldValue == newValue
                ? this
                : WithLines(Lines.Replace(oldValue, newValue));
    }
}

These additions allow creating orders like this:

OrderLine apple = new OrderLine(quantity: 1, unitPrice: 2.5m, discount: 0.0f);
Order order = new Order(ImmutableList.Create(apple));

OrderLine discountedApple = apple.WithDiscount(discount);
Order discountedOrder = order.ReplaceLine(apple, discountedApple);

The nice thing about this design is that it avoids unnecessary object creation whenever possible. For example, when the value of discount is equal to 0.0f, i.e., when there is no discount, discountedApple and discountedOrder refer to the existing instances of apple and order.

Here is why:

apple.WithDiscount() will return the existing instance of apple because the new discount is identical to the current value of the Discount property.
order.ReplaceLine() will return the existing instance if both arguments are the same.

Other operations of our immutable collections follow this spirit of maximizing reuse. For example, adding an order line to an order with 1,000 order lines will not create an entire new list with 1,001 elements. Instead, it will reuse a large chunk of the existing list. This is possible because the list is internally represented as a tree which allows sharing nodes between different instances.

That sounds great – I’d like to learn more

The one-stop shop for all API questions is MSDN. So your first visit should be the MSDN documentation on immutable collections.

Our very first blog post on immutable collections is also a great in-depth introduction. It covers algorithmic complexities as well as the builder pattern, which allows for more efficient bulk updates.

If your question is more along the lines of “why did Microsoft do it this way,” take a look at the entire blog post series on the .NET Blog as well as the now retired BCL Blog. Many of you asked challenging questions and even proposed design improvements which we discussed in following posts.

If you are like me, you probably prefer videos and face-to-face conversations over reading text. If so, you may want to watch the two videos we put together for Channel 9. They allow you to meet the team and gain more insight into the design and inner workings of immutable collections.

Immutable Collections in .NET

Inner workings of immutable collections

Are immutable collections now done?

No. We still plan on bringing back ImmutableArray<T>, which we decided to remove for now, due to some design issues.

Also, our documentation team is publishing updates to MSDN every three weeks. Since the documentation on immutable collections is all new, we’re very interested to get your feedback so we can make the docs even better!