{"id":893,"date":"2013-06-24T09:19:00","date_gmt":"2013-06-24T09:19:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/dotnet\/2013\/06\/24\/please-welcome-immutablearrayt\/"},"modified":"2021-10-04T12:28:55","modified_gmt":"2021-10-04T19:28:55","slug":"please-welcome-immutablearrayt","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/dotnet\/please-welcome-immutablearrayt\/","title":{"rendered":"Please welcome ImmutableArray"},"content":{"rendered":"

We’ve just released an update to our immutable collection package<\/a> which adds a new member to the family of immutable collection types: ImmutableArray<T><\/strong>.<\/p>\n

In this post, I’ll talk about why we added another collection and how it relates to the existing types. I’ll also cover some minor updates we did to our package.<\/p>\n

Introduction ImmutableArray<T><\/h2>\n

Sometimes a little bit of code says more than a thousand pictures, so let’s look at the declaration of immutable array:<\/p>\n

        public struct ImmutableArray<T> : IList,\n                                          IList<T>,\n                                          IReadOnlyList<T>,\n                                          IImmutableList<T>,\n                                          IEquatable<ImmutableArray<t>>,\n                                          IStructuralComparable,\n                                          IStructuralEquatable\n        {\n            \/\/ ...\n        }<\/pre>\n
As you can see ImmutableArray<T><\/strong> implements IImmutableList<T><\/strong> which begs the question how it is different from the existing implementation ImmutableList<T><\/strong>.<\/p>\n
The answer: performance.<\/p>\n
Arrays are hard to beat in several ways: they provide an O(1) element access, they are very cache friendly as all data is co-located, and they provide low overhead for small collections (< 16 elements).<\/p>\n
ImmutableArray<T><\/strong> is a very thin wrapper around a regular array and thus shares all the benefits with them. We even made it a value type (struct) as it only has a single field which holds the array it wraps. This makes the size of the value type identical to the reference of the array. In other words: passing around an immutable array is as cheap as passing around the underlying array. Since it’s a value type, there is also no additional object allocation necessary to create the immutable wrapper, which can reduce GC pressure.<\/p>\n
The key operations on ImmutableArray<T><\/strong> just forward to the underlying array, including the indexer. In contrast to List<T><\/strong> or ArraySegment<T><\/strong> the underlying array always has the same length as the outer type, i.e. the immutable array. This means we can avoid having additional bounds checking and just rely on the underlying array. This allows the CLR code generation to inline the indexer access.<\/p>\n
We’ve also implemented custom LINQ operators for ImmutableArray<T><\/strong>. This avoids boxing immutable arrays into an IEnumerable<T><\/strong>.<\/p>\n
Using ImmutableArray<T><\/h2>\n
Creating an immutable array is similar to creating an immutable list, i.e. it follows the factory pattern via static Create<\/strong> methods:<\/p>\n
        ImmutableArray<int> array = ImmutableArray.Create(1, 2, 3);<\/pre>\n
You can also create an immutable array via the ToImmutableArray()<\/strong> extension method:<\/p>\n
        IEnumerable<int> someInts = Enumerable.Range(1, 100);\n        ImmutableArray<int> array = someInts.ToImmutableArray();<\/pre>\n
It also supports the builder pattern which allows constructing immutable arrays via mutation:<\/p>\n
        ImmutableArray<int>.Builder builder = ImmutableArray.CreateBuilder<int>();\n        builder.Add(1);\n        builder.Add(2);\n        builder.Add(3);\n        ImmutableArray<int> oneTwoThree = builder.ToImmutable();<\/pre>\n
You may wonder how using the builder differs from using a List<T><\/strong> with the ToImmutableArray()<\/strong> extension method. Generally, all immutable collection builders are functionally equivalent to their ordinary mutable collection types (List<T><\/strong>, Dictionary<TKey, TValue><\/strong> etc). They are purely there to provide better performance. Using the ImmutableArray<T><\/strong> builder can improve performance as the implementation uses a trick to avoid type checks. Normally the CLR has to perform additional type checks at runtime to ensure that storing an element in an array is type safe, because arrays are covariant which means the correctness can’t be easily checked statically. ImmutableArray<T><\/strong> avoids this by wrapping references in a pointer-sized value type. For more details on this subject I recommend this blog post<\/a> from Eric Lippert.<\/p>\n
Reading data from an ImmutableArray<T><\/strong> is similar to reading regular arrays:<\/p>\n
        ImmutableArray<int> array = \/\/...\n        for (var i = 0; i < array.Length; i++)\n        {\n            Console.WriteLine(array[i]);\n        }<\/pre>\n
We’ve decided to go with having a Length<\/strong> property instead of Count<\/strong> because we see ImmutableArray<T><\/strong> as a replacement for regular arrays. This makes it easier to port existing code. It also makes the design a bit more self-contained.<\/p>\n
Of course we also support enumerating the elements via foreach<\/strong>. ImmutableArray<T><\/strong> follows what other collection types do as well: it implements IEnumerable<T><\/strong> but also provides a custom enumerator which allows the compiler to generate more efficient code which avoids boxing the enumerator.<\/p>\n
Since ImmutableArray<T><\/strong> is a value type, it overloads the equals (==) and not-equals (!=) operators. They are defined as using reference equality on the underlying array.<\/p>\n
The default value of ImmutableArray<T><\/strong> has the underlying array initialized with a null reference. In this case it behaves the same way as an ImmutableArray<T><\/strong> that has been initialized with an empty array, i.e. the Length<\/strong> property returns 0 and iterating over it simply doesn’t yield any values. In most cases this is the behavior you would expect. However, in some cases you may want to know that the underlying array hasn’t been initialized yet. For that reason ImmutableArray<T><\/strong> provides the property IsDefault<\/strong> which returns true if the underlying array is a null reference. For example you can use that information to implement lazy initialization:<\/p>\n
        private ImmutableArray<byte> _rawData;\n        public ImmutableArray<byte> RawData\n        {\n            get\n            {\n                if (_rawData.IsDefault)\n                    _rawData = LoadData();\n                return _rawData;\n            }\n        }<\/pre>\n
ImmutableArray<T> vs. ImmutableList<T><\/h2>\n
In contrast to what I said earlier<\/a>, we decided to make immutable array a persistent data structure. In other words: similar to ImmutableList<T><\/strong> it has methods that allow creating new instances of immutable arrays with different contents. Mind you, the performance characteristic of those operations is fairly different from ImmutableList<T><\/strong>. ImmutabeList<T><\/strong> uses a tree data structure that allows sharing. It also allows for making sure updates can be done in O(log n).<\/p>\n
The following table summarizes the performance characteristics of ImmutableArray<T><\/strong>. You can find a similar table for the existing types here<\/a>.<\/p>\n\n\n\n\n\n\n\n
Operation<\/th>\nImmutableArray<T> Complexity<\/th>\nImmutabeList<T> Complexity<\/th>\nComments<\/th>\n<\/tr>\n<\/thead>\n
Create()<\/th>\nO(n)<\/td>\nO(n)<\/td>\nRequires to copy the input array to ensure the underlying array can’t be modified<\/td>\n<\/tr>\n
this[]<\/th>\nO(1)<\/td>\nO(log n)<\/td>\nDirectly index into the underlying array<\/td>\n<\/tr>\n
Add()<\/th>\nO(n)<\/td>\nO(log n)<\/td>\nRequires creating a new array<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Reasons to use immutable array:<\/p>\n