Immutable collections ready for prime time

Immutable collections ready for prime time

Rate This
  • Comments 34

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 Order
{
    public Order()
    {
        Lines = new List<OrderLine>();
    }

    public List<OrderLine> Lines { get; private set; }
}

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);
        }
    }
}

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; private set; }

    public decimal UnitPrice { get; private set; }

    public float Discount { get; private set; }

    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; private set; }

    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:

  1. apple.WithDiscount() will return the existing instance of apple because the new discount is identical to the current value of the Discount property.
  2. 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!

Summary

We’ve just shipped a stable release of Microsoft.Bcl.Immutable. The license now allows usage in production, so they are ready for prime time.

Please have a look at the new documentation on MSDN and let us know what you think!

Leave a Comment
  • Please add 3 and 3 and type the answer here:
  • Post
  • What's the deal with the Windows-only distribution restriction in the license? That's super lame. Can we at least have an explanation, if not the removal of that clause from the license?

  • Everybody should avoid this package from Microsoft and work on creating an actual portable project with github.com/.../ImmutableCollections.

    I'm sure you guys put a lot of effort into this project. It's really sad it's been ruined with license you chose for it.

  • Great to see, though frustrating that we will have to wait a few years to use it as we are still on XP :(

    Presumably this bit about getting the package via nuget in MSDN is no longer true:

    'In the drop-down list box in the middle pane, choose Include Prerelease instead of Stable Only. '

    msdn.microsoft.com/.../dn385366.aspx

  • Great news!

    I think this is going to be a real help at my day job. We've got a lot of code dedicated to locking of collections whilst reading/writing them, and it's fairly frequent that we end up having to fix a deadlock after someone got the locking a bit wrong. If we can get rid of some of the locks by using immutable collections it'll be a great help.

    I'm really looking forward to the return of ImmutableArray<T>, as well. There are places where we need to provide performant read-only access to large chucks of data and this could really help us out.

    That said, it is a shame if the library has ended up with what seems to be the default "Windows only" license restriction. It makes it essentially impossible to justify taking a dependency on Immutable Collections in open source libraries, even if I personally just want to use those libraries on Windows.

    Obviously you are aware of the issue, as Immo replied to Phil Haack's comment about it on an earlier post. If you could give us an indication of whether you are trying to get the restriction removed, or if you've had a firm "No" from Legal it would be helpful.

    Thanks, and keep up all the good work.

  • Thank you!

    Please someone answer:

    - Can we consume immutable collections in Windows Phone 8?

    - Can we consume immutable collections in Windows 8.1 apps?

    - Can we consume immutable collections in building Portable Class Library - PCL?

  • MSDN documentation includes a thread safety warning for all collection types:

    "Any public static (Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe."

    Is this a documentation error?

  • Wow! Jim Caviezel works for Microsoft. I didn't knew that.. :-D

  • @Xero, I created a project from apps.windowsstore.com/default.htm, downloaded the source and installed the immutable collection nuget package and its installed without error. I haven't consumed it in any scenario. But I think it will work with Windows Phone and Windows Store. Not sure about PCL though.

  • I know the C# team has been thinking about how to make immutable types easier to create- I hope they're successful, because it really requires a huge amount of code to do this pattern yourself.

  • @AdamMarkson: Yes, you no longer need to select "Include Prerelease". By the time we published this article the new version of the docs were staged but not yet live. Stay tuned.

    @James Chaldecott, Bart, fm: We are very much aware that this license restriction is an issue for the community. At this point the best explanation I can offer is that we neither made a decisions to remove it, nor to keep it. Until now, this is the standard EULA Microsoft teams have been using for years, so it's not like we specifically added this clause.

    @Xero: Immutable Collections is supported on .NET 4.5, .NET for Windows Store and Windows Phone 8, as well as portable class libraries targeting those platforms.

    @Eren: Excellent catch. I'll forward this to the documentation team. That's most likely part of the standard documentation that got incorrectly applied.

    @Tim: ahem, so does George Clooney ;-)

    @MgSm88: Indeed. The good news is that the C# team itself is now implementing the compilers and IDE services in C# using an immutable design. They are very much aware of the number of keystrokes involved :-)

  • For a high-volume HTTP server (foundation is OWIN/Katana), does it make sense to store cross-application state/configuration in an ImmutableDictionary, or ConcurrentDictionary or MemoryCache, when the instances will feature thousands of reads per second but infrequent writes/updates per hour?

    Also, when I first heard about this announcement, I went to Bing and searched for "msdn immutable collections 2013/09/25" and got no hits. Then I went to Google and searched for "msdn immutable collections 2013/09/25" and got this page as a top hit. So I submitted "blogs.msdn.com" to Bing as a "new site" in the hopes that they will try harder over there....

  • @Finder: The canonical answer is: it depends. It sounds to me like this scenario could benefit from using immutable collections but it always depends on how you need to handle updates. In general, you can use Interlocked.CompareExachange to update the reference to an immutable collection in an atomic fashion. You can use these to build somewhat higher-level operations like atomic updates (like the one we include in msdn.microsoft.com/.../system.collections.immutable.immutableinterlocked.aspx), at which it becomes very similar to concurrent collections.

  • The license is so complicated you have to ask a lawyer if you can even use this library. I was really looking forward to this, but I'll be avoiding this for reasons I've put in a blog post earlz.net/.../why-i-wont-be-using-microsoftbclimmutable-package-despite

  • @Immo, this is awesome. I just finished the Ch9 videos also. Great stuff!

    To add more detail to what I am exploring, with 20 collections (lower case "c" in "collections"), each with 3000+ key/value pairs, all collections will simultaneously serve a value based on the key lookup (no iteration). Read-only stuff, but the lookup and subsequent value serving would occur thousands of times per second. Every n minutes, the collections would be completely destroyed and a new one would replace it. The collections themselves are in a List<>.

    From my currently thin understanding, the new ImmutableDictionary<TKey, TValue> seems like a better move than ConcurrentDictionary<TKey, TValue>. I am trying to get some more "compare and contrast" ideas however before I begin blindly writing code and potentially taking my tests in the wrong direction.

    Thanks.

  • To anyone else who wants to see the platform limitations removed, please vote up at visualstudio.uservoice.com/.../4494577-remove-the-platform-restriction-on-microsoft-nuget

    @Immo, I can't stress enough how important it is to review the platform restrictions. I'm currently building an app for multiple platforms (who isn't) and I'd like to be able to reuse my code. If I could use this library in mono on android and iOS, then I would use it (along with Xamarin and Visual Studio). Otherwise my options are to build in javascript or build a native version in each platform, which largely cuts visual studio out of the picture.

Page 1 of 3 (34 items) 123