{"id":703,"date":"2013-09-12T14:31:00","date_gmt":"2013-09-12T14:31:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/dotnet\/2013\/09\/12\/immutable-collections-are-now-rc\/"},"modified":"2021-09-30T17:23:29","modified_gmt":"2021-10-01T00:23:29","slug":"immutable-collections-are-now-rc","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/immutable-collections-are-now-rc\/","title":{"rendered":"Immutable collections are now RC"},"content":{"rendered":"<p>Over the past several months, we&rsquo;ve been working on a new set of collection types that offer an immutable design. Today we are happy to announce that we are one step closer to a stable version of this work: we&rsquo;ve just shipped the release candidate (1.0.23 RC) of the <a href=\"http:\/\/www.nuget.org\/packages\/Microsoft.Bcl.Immutable\/\">Microsoft.Bcl.Immutable NuGet package<\/a>.<\/p>\n<p style=\"text-align: center\"><a href=\"https:\/\/devblogs.microsoft.com\/dotnet\/wp-content\/uploads\/sites\/10\/2013\/09\/7331.Graph_.png\"><img decoding=\"async\" src=\"https:\/\/devblogs.microsoft.com\/dotnet\/wp-content\/uploads\/sites\/10\/2013\/09\/7331.Graph_.png\" alt=\"\" border=\"0\" \/><\/a><\/p>\n<p style=\"text-align: center\"><strong>Because we could: an immutable representation of our release timeline<\/strong><\/p>\n<h2>What has changed in RC?<\/h2>\n<p>The changes in this update can be summarized into the following areas:<\/p>\n<ul>\n<li><strong>Removal of <code>ImmutableArray&lt;T&gt;<\/code><\/strong>. With a heavy heart we&rsquo;ve decided to remove <code>ImmutableArray&lt;T&gt;<\/code> for now because we aren&rsquo;t happy with the current design.<\/li>\n<li><strong>Comparers<\/strong>. We&rsquo;ve simplified the exposed concepts by not exposing the comparers through the interfaces.<\/li>\n<li><strong>Consistent construction<\/strong>. In the last update, we split the factory methods into methods that deal with scalars and ones that deal with other collections. We&rsquo;ve improved this by renaming some APIs in order to&nbsp;apply the split consistently.<\/li>\n<li><strong>Consistency with <code>ToString<\/code><\/strong>. Previously, we didn&rsquo;t override <code>ToString<\/code> consistently. We&rsquo;ve fixed this by not overriding <code>ToString<\/code> at all.<\/li>\n<li><strong>Minor improvements<\/strong>. We&rsquo;ve added a few convenience APIs.<\/li>\n<\/ul>\n<p>I&rsquo;ll discuss these areas in more detail.<\/p>\n<h2><code>ImmutableArray&lt;T&gt;<\/code> removed for now<\/h2>\n<p>After careful consideration we decided to remove <code>ImmutableArray&lt;T&gt;<\/code> from our 1.0 release plans. We aren&rsquo;t happy with the design as it is today. This doesn&rsquo;t mean we have given up on having an <code>ImmutableArray&lt;T&gt;<\/code> &ndash; it just means we need more time to do it properly, and we don&rsquo;t want to block releasing a stable version of immutable collections because we aren&rsquo;t happy with a single type. After we ship the stable 1.0, we&rsquo;ll ship a 1.1 beta that will include <code>ImmutableArray&lt;T&gt;<\/code>.<\/p>\n<p>Here&rsquo;s why we weren&rsquo;t happy with <code>ImmutableArray&lt;T&gt;<\/code>:<\/p>\n<p>The primary goal for <code>ImmutableArray&lt;T&gt;<\/code> is to be a zero-overhead wrapper around an ordinary array. The current implementation, although it had little overhead, didn&rsquo;t satisfy the performance needs of one of our most important partners, <a href=\"http:\/\/msdn.microsoft.com\/en-us\/vstudio\/hh500769.aspx\">Project Roslyn<\/a>, which served as an excellent benchmark for building a large-scale immutable system.<\/p>\n<p>Because of performance requirements, <code>ImmutableArray&lt;T&gt;<\/code> needs to be a value type, i.e., a struct. In the CLR, all value types have an implied default state. This state is defined as having an underlying memory of all zeros. For <code>ImmutableArray&lt;T&gt;<\/code> that means that the underlying array it wraps is null. In order to provide meaningful semantics, we believe it&rsquo;s best for an immutable array in its default state to behave exactly like an empty array. That&rsquo;s consistent with the way the .NET Framework <a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/ms229031.aspx\">deals with value types in general<\/a>.<\/p>\n<p>Unfortunately, we discovered that this design causes a general performance issue. The JIT compiler is normally able to <a href=\"http:\/\/blogs.msdn.com\/b\/clrcodegeneration\/archive\/2009\/08\/13\/array-bounds-check-elimination-in-the-clr.aspx\">eliminate the bounds checks for standard <code>for<\/code> loops<\/a>. For <code>ImmutableArray&lt;T&gt;<\/code>, the indexer and <code>Length<\/code> property are inlined so one would think the bounds check would be eliminated as well. Unfortunately, that&rsquo;s not the case, because these properties don&rsquo;t just forward to the underlying array but also contain an additional null check to provide the behavior I explained. This causes the JIT to no longer be able to eliminate the bounds checks. Our partner Roslyn uses <code>ImmutableArray&lt;T&gt;<\/code> throughout its system, so this caused an unacceptable performance loss.<\/p>\n<p>Today, the only way to get the performance we need is to remove the additional null checks from the indexer and <code>Length<\/code> property. However, we believe this has significant usability issues.<\/p>\n<p>For example, consider the following code:<\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">int[] ints = new int[] { 1, 2, 3 };<\/span><\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">ImmutableArray&lt;int&gt; empty = new ImmutableArray&lt;int&gt;();<\/span><br \/><span style=\"font-family: courier new,courier\">ImmutableArray&lt;int&gt; immutableInts = empty.AddRange(ints);<\/span><\/p>\n<p>Since all value types have an automatic default constructor that initializes the value type to its default state, empty will be an <code>ImmutableArray&lt;T&gt;<\/code> whose underlying array is null. Thus, the implementation of <code>AddRange<\/code> will crash with a <code>NullReferenceException<\/code>.<\/p>\n<p>There are other places where this problem manifests itself. Since <code>ImmutableArray&lt;T&gt;<\/code> implements certain collection interfaces (such as <code>IEnumerable<\/code> and <code>IReadOnlyList<\/code>), you can pass it to methods that work against the interface. Since the interface reference will be non-null, consumers won&rsquo;t expect any methods or property invocations to cause a <code>NullReferenceException<\/code>.<\/p>\n<p>Not exactly a happy place. However, we do have some ideas on how to address this issue and decided to give it more baking time by removing <code>ImmutableArray&lt;T&gt;<\/code> for now.<\/p>\n<h2>Reduced complexity around comparers<\/h2>\n<p>After reviewing some of your feedback, we decided that certain APIs that exposed comparers were overkill within the current design. Thus, we removed <code>IHashKeyCollection&lt;TKey&gt;<\/code> and <code>ISortKeyCollection&lt;TKey&gt;<\/code> as well as the <code>ValueComparer<\/code> property from <code>IImmutableDictionary&lt;TKey,TValue&gt;<\/code>.<\/p>\n<h2>Consistent construction<\/h2>\n<p>When we <a href=\"http:\/\/blogs.msdn.com\/b\/bclteam\/archive\/2013\/03\/06\/update-to-immutable-collections.aspx\">introduced factory methods<\/a> for constructing immutable collections, we also removed all <code>Empty<\/code> properties. So instead of:<\/p>\n<p style=\"padding-left: 30px\"><code>return ImmutableList&lt;int&gt;.Empty;<\/code><\/p>\n<p>you have to write:<\/p>\n<p style=\"padding-left: 30px\"><code>return ImmutableList.Create&lt;int&gt;();<\/code><\/p>\n<p>We received feedback that this looks quite bad in code reviews, because most reviewers assume that <code>Create<\/code> would return a new instance. For added expressiveness, we decided to bring back the <code>Empty<\/code> properties, so now you have both options.<\/p>\n<p>In the past update, we introduced the <code>From<\/code> factory method so you could differentiate between factory methods that work on scalars (<code>Create<\/code>) and and factory methods that operate on collections (<code>From<\/code>). We realized that the name <code>From<\/code> is an unfortunate choice because it doesn&rsquo;t show up together in IntelliSense with <code>Create<\/code>. In the RC update, we renamed <code>From<\/code> to <code>CreateRange<\/code>.<\/p>\n<p>Also, our naming wasn&rsquo;t fully consistent. There are some <code>Create<\/code> overloads on <code>ImmutableDictionary<\/code> that accepted an <code>IEnumerable<\/code>. We renamed those to <code>CreateRange<\/code> as well.<\/p>\n<h2>Consistency with ToString<\/h2>\n<p><code>ImmutableDictionary&lt;TKey, TValue&gt;<\/code> now no longer overrides <code>ToString<\/code> (it was the only collection that did that anyway). This means that calling <code>ToString<\/code> on any immutable collection will now return the fully qualified type (which is the behavior of <code>Object.ToString<\/code>).<\/p>\n<p>For debugging purposes, all collections already make use of <a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/system.diagnostics.debuggerdisplayattribute.aspx\">DebuggerDisplayAttribute<\/a> and <a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/system.diagnostics.debuggertypeproxyattribute.aspx\">DebuggerTypeProxyAttribute<\/a>.<\/p>\n<h2>Minor improvements<\/h2>\n<p>The current signature of the <code>ToImmutableDictionary<\/code> method requires two selectors: one that determines the key and one that determines the value. This is inconsistent with <a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/system.linq.enumerable.todictionary.aspx\">Enumerable.ToDictionary<\/a>, which provides an overload that allows you to specify only the key. The RC update includes the equivalent overload for <code>ToImmutableDictionary<\/code>. Thus, code like this will now compile:<\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">ImmutableList&lt;Customer&gt; customers = GetCustomers();<\/span><br \/><span style=\"font-family: courier new,courier\">ImmtuableDictionary&lt;int, Customer&gt; customerById = customers.ToImmutableDictionary(c =&gt; c.Id);<\/span><\/p>\n<p>Performing a binary search is a fairly common operation for collections. Since <code>ImmutableList&lt;T&gt;<\/code> is using a tree behind the scenes, indexing is O(log n). Thus, providing a <code>BinarySearch<\/code> method on <code>ImmutableList&lt;T&gt;<\/code> can do a better job because it can traverse the internal tree and avoid having to repeatedly re-locate the node in the loop. For symmetry, we also added the <code>BinarySearch<\/code> method to the <code>ImmutableList&lt;T&gt;.Builder<\/code>.<\/p>\n<h2>What has not changed?<\/h2>\n<p>We&rsquo;ve received a lot of feedback on immutable collections. There were two major design points many of you commented on: the lack of constructors and the implementation of mutable interfaces. I&rsquo;d like to explain these design decisions.<\/p>\n<h2>The lack of constructors<\/h2>\n<p>Some of you asked us to bring back the constructors. The concern was that this code:<\/p>\n<p style=\"padding-left: 30px\"><code>ImmutableList&lt;int&gt; list = new ImmutableList&lt;int&gt;(new int[] { 1, 2, 3});<\/code><\/p>\n<p>is, by far, more intuitive than this code:<\/p>\n<p style=\"padding-left: 30px\"><code>ImmutableList&lt;int&gt; list = ImmutableList.Create&lt;int&gt;(new[] { 1, 2, 3}); <\/code><\/p>\n<p>That&rsquo;s absolutely true. When designing APIs, we generally avoid factory methods because they are often an indication of overengineering and generally hurt usability. For example, most developers would agree that <code>XDocument<\/code> is easier to use than <code>XmlDocument<\/code>. The fact that <code>XDocument<\/code> avoids factories is one of the reasons why it&rsquo;s more usable.<\/p>\n<p>The challenge in designing immutable APIs is that it&rsquo;s very important to avoid unnecessary allocations. For example, most immutable collections start off with an empty instance. Offering a constructor will inevitably cause significant GC pressure due to the fact that this is the most intuitive way to construct them.<\/p>\n<p>Using factory methods also provide other interesting opportunities for optimization. For example, consider this code:<\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">class NumberProcessor<\/span><br \/><span style=\"font-family: courier new,courier\">{<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp; private readonly ImmutableList&lt;int&gt; _numbers;<\/span><\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp; NumberProcessor(IEnumerable&lt;int&gt; numbers)<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp; {<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; _numbers = ImmutableList.CreateRange&lt;int&gt;(numbers);<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp; }<\/span><\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp; \/\/ other methods elided for brevity<\/span><br \/><span style=\"font-family: courier new,courier\">}<\/span><\/p>\n<p>The goal of this code is to keep the numbers around. Since the input is typed as <code>IEnumerable&lt;T&gt;<\/code>, you can pass virtually any collection, including collections that are already immutable. In case <code>numbers<\/code> is already an instance of <code>ImmutableList&lt;int&gt;<\/code>, the <code>CreateRange<\/code> factory method can simply cast it and thus avoid the construction of a new object. A constructor would have forced us to create a brand new immutable list.<\/p>\n<p>There is also the problem of collection initializers. Suppose we provide a default constructor for <code>ImmutableList&lt;int&gt;<\/code>. In that case, the following code would compile just fine:<\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">ImmutableList&lt;int&gt; items = new ImmutableList&lt;int&gt; {1, 2, 3};<\/span><br \/><span style=\"font-family: courier new,courier\">Console.WriteLine(items.Count);<\/span><\/p>\n<p>You would probably expect the output to be <code>3<\/code> but in fact it&rsquo;s <code>0<\/code>. The reason is that <a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/vstudio\/bb384062.aspx\">collection initializers<\/a> follow a pattern. As long as the type has a constructor, implements <code>IEnumerable<\/code>, and provides a public <code>Add<\/code> method, the compiler lets you use the syntax above. The code that the compiler generates looks like this:<\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">ImmutableList&lt;int&gt; items = new ImmutableList&lt;int&gt;();<\/span><br \/><span style=\"font-family: courier new,courier\">items.Add(1);<\/span><br \/><span style=\"font-family: courier new,courier\">items.Add(2);<\/span><br \/><span style=\"font-family: courier new,courier\">items.Add(3);<\/span><br \/><span style=\"font-family: courier new,courier\">Console.WriteLine(items.Count);<\/span><\/p>\n<p>Now it&rsquo;s clear why the output is <code>0<\/code>: It&rsquo;s because collection initializers don&rsquo;t expect the <code>Add<\/code> method to return a new instance and instead rely on side effects to mutate the existing instance. Since the result is never used, the items variable still refers to the original, empty collection.<\/p>\n<p>Thus, we decided to exclusively offer factory methods to ensure that you get the best behavior and cannot accidentally do the wrong thing.<\/p>\n<h2>Implementing the mutable interfaces<\/h2>\n<p>Several people raised the issue that our immutable collection types implement the mutable interfaces. For example, this is what the declaration of <code>ImmutableList&lt;T&gt;<\/code> looks like:<\/p>\n<p style=\"padding-left: 30px\"><span style=\"font-family: courier new,courier\">public sealed class ImmutableList&lt;T&gt; :<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IImmutableList&lt;T&gt;,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IEnumerable,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IEnumerable&lt;T&gt;,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IReadOnlyCollection&lt;T&gt;,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IReadOnlyList&lt;T&gt;,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ICollection,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ICollection&lt;T&gt;,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IList,<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; IList&lt;T&gt;<\/span><br \/><span style=\"font-family: courier new,courier\">{<\/span><br \/><span style=\"font-family: courier new,courier\">&nbsp;&nbsp; &#8230;<\/span><br \/><span style=\"font-family: courier new,courier\">}<\/span><\/p>\n<p>It&rsquo;s worth pointing out that this declaration does not have a correctness issue &ndash; you cannot mutate an instance of <code>ImmutableList&lt;T&gt;<\/code> by casting it to a mutable interface. For example, calling <code>IList&lt;T&gt;.Add<\/code> would throw <code>NotSupportedException<\/code>.<\/p>\n<p>The mutable interfaces always supported a read-only mode, which means that consumers can&rsquo;t change the contents. This mode is exposed via <a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/0cfatk9t.aspx\">ICollection.IsReadOnly<\/a>, which all mutable interfaces inherit from. Thus, the concrete immutable collection types all implement the existing, mutable interfaces in a read-only fashion, which means that <code>IsReadOnly<\/code> returns true and all methods that would mutate the collection throw <code>NotSupportedException<\/code>.<\/p>\n<p>That&rsquo;s not fundamentally incompatible with immutable collections; for all intents and purposes, immutable collections provide an even stronger guarantee that nobody, not just the consumer, can change their contents. Some of you suggested that we shouldn&rsquo;t implement the mutable interfaces at all, so you shouldn&rsquo;t be able to accidentally pass an immutable collection to a method that takes an <code>IList&lt;T&gt;<\/code>. This would compile just fine, but might cause a <code>NotSupportedException<\/code> at runtime if the method in question tries to modify the collection through the mutable interface.<\/p>\n<p>Based on the data we have, we found that in many cases where methods take a mutable interface (such as <code>IList&lt;T&gt;<\/code>), the consumer only needs to read the contents. We believe that enabling interoperability with mutable collections is very important, because otherwise it would be difficult to adopt immutable collections into existing code.<\/p>\n<p>Also, this interoperability is consistent with how the rest of the .NET Framework is designed. For example, Streams can support reading, writing, and seeking. Instead of providing separate types, we&rsquo;ve decided to expose the capabilities via the <a href=\"http:\/\/blogs.msdn.com\/b\/kcwalina\/archive\/2004\/06\/17\/158326.aspx\">optional features pattern<\/a> because it is typically much simpler and doesn&rsquo;t result in an explosion of combinatorial types. The <code>IsReadOnly<\/code> property on <code>ICollection&lt;T&gt;<\/code> is another instance of this pattern.<\/p>\n<p>Thus, we decided that it&rsquo;s best to implement the mutable interfaces on the concrete types.<\/p>\n<h2>Summary<\/h2>\n<p>Today we shipped the release candidate of our <a href=\"http:\/\/www.nuget.org\/packages\/Microsoft.Bcl.Immutable\/\">Microsoft.Bcl.Immutable NuGet package<\/a>. We plan to release a stable 1.0 package by the end of September. We&rsquo;ve removed <code>ImmutableArray&lt;T&gt;<\/code> from 1.0 because we weren&rsquo;t happy with its design. It will re-appear in 1.1, which will be available as a beta release shortly after we ship a stable 1.0 package.<\/p>\n<p>Please play around with the RC and let us know what you think!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Over the past several months, we&rsquo;ve been working on a new set of collection types that offer an immutable design. Today we are happy to announce that we are one step closer to a stable version of this work: we&rsquo;ve just shipped the release candidate (1.0.23 RC) of the Microsoft.Bcl.Immutable NuGet package. Because we could: [&hellip;]<\/p>\n","protected":false},"author":335,"featured_media":58792,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[685],"tags":[30,43,84,104,110],"class_list":["post-703","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-dotnet","tag-announcement","tag-bcl","tag-immutable","tag-nuget","tag-portable-class-libraries"],"acf":[],"blog_post_summary":"<p>Over the past several months, we&rsquo;ve been working on a new set of collection types that offer an immutable design. Today we are happy to announce that we are one step closer to a stable version of this work: we&rsquo;ve just shipped the release candidate (1.0.23 RC) of the Microsoft.Bcl.Immutable NuGet package. Because we could: [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/703","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/users\/335"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/comments?post=703"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/posts\/703\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media\/58792"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/media?parent=703"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/categories?post=703"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/dotnet\/wp-json\/wp\/v2\/tags?post=703"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}