Immutable Array for .NET

• Download source - 17.9 KB

Introduction

Wikipedia defines an immutable object as "an object whose state cannot be modified after it is created". The most wildly used immutable object is certainly the String object: I think it's also the most wildly used object in general. Immutable objects are useful when thread safety is a concern and/or when an instance of an object must be accessed outside of our code in a readonly mode. This is why the designers of both the .NET and Java frameworks decided to write the String object as an immutable one.

The lack of on immutable byte array in the .NET Framework (and of course the fact that really few, if none, thought to write it and Open Source it) pushed me to write it. In the beginning, I just needed/wanted to write an immutable byte array. Then I found that the same code could work also for other types, so I converted it into an immutable array of <T>, where <T> can, of course, be of type byte, but also an int, a char, etc. The objects of the immutable array must be immutable themselves: so I put a constraint on the generic type specifying that it must be a value type (struct).

In short

Advantages:

• Thread safety
• It is secure to pass a reference of an immutable object outside of a class without the risk that the data could be changed

Disadvantages:

• Memory usage

Using the code

In the beginning of our code, we declare these type aliases, for more code readability. Of course this is not mandatory:

using ImmutableByteArray = System.ImmutableArray<byte>;
using ImmutableCharArray = System.ImmutableArray<char>;

The immutable array can be created from a mutable array, like this:

ImmutableByteArray array1 = new ImmutableByteArray(new byte[] { 0, 1, 2, 3 });
ImmutableCharArray string1 = new ImmutableCharArray("test".ToCharArray());

In these cases, a copy of the mutable array is created so we are consuming memory. Instead, if we create the immutable array from another immutable array:

ImmutableByteArray array2 = new ImmutableByteArray(new byte[] { 0, 1, 2, 3 });
ImmutableByteArray array3 = array1 + array2;

array3 is a concatenation of the other two instances of the immutable array. That instance does not consume further memory. This is due to the implementation of the immutable array. We will talk about this in the next chapter. Also, the Subarray() operation (that is similar to a String.Substring()) does not consume memory:

ImmutableByteArray array4 = array1.Subarray(0,2);

ImmutableArray<T> supports enumeration:

foreach (byte b in array1)
    Console.Write(b + " ");

And implements the ICloneable interface:

array5 = array1.Clone();

As long as this is an immutable object, the Clone() method simply returns the reference of the object itself. Finally, ImmutableArray<T> overrides and implements the Equals() and '==' and '!=' operators, so we can do:

Console.WriteLine("array1 == array2: {0}", (array1 == array2); //same as Equals()
Console.WriteLine("array1 equals array2: {0}", (array1.Equals(array2));
Console.WriteLine("array1 != array2: {0}", (array1 != array2); //same as ! Equals()

Implementation

The implementation takes all the advantages of the fact that we are working with immutable arrays. At first, I created an InternalImmutableArray<T> class that simply wraps a mutable array of T. This is the only place where memory is allocated, and is open to further improvements in future (see next chapter) to reduce memory usage. ImmutableArray<T> is implemented as an array (List) of InternalImmutableArray<T>s. This is really comfortable because this way, concatenation and subarray operations are simple operations on the list items, and do not consume further memory. In fact, they reference the same InternalImmutableArray<T> objects, but with different offsets. They can safely share and reference these objects because they are immutable, so anyone can alter the stored data.

Improvements

Memory usage optimization

The first improvement is the memory allocation strategy. When we create a new ImmutableArray<T> from a mutable array, new memory is allocated. In a scenario where we have a lot of ImmutableArray<T>s allocated, it should be fair to think that most of them will partially or totally share the same data. As an example, look at this scenario:

ImmutableByteArray array1 = new ImmutableByteArray(new byte[] { 0, 1, 2, 3 });
ImmutableByteArray array2 = new ImmutableByteArray(new byte[] { 0, 1, 2, 3, 4, 5 });

The second array has in common the first 4 elements with the first array. In the current implementation, the total allocation of memory would be 4 + 6 bytes, for a total of 10 bytes.

{ 0, 1, 2, 3 } = 4 bytes
{ 0, 1, 2, 3, 4, 5 } = 6 bytes

If the memory allocation could be more "smart", the memory allocation would be 4 + 2, for a total of 6 bytes, because the second array would be a concatenation of the first array plus the last two elements of the second one.

{ 0, 1, 2, 3 } = 4 bytes
{ 0, 1, 2, 3 } (shared) + { 5, 6} = 2 bytes

Anyway, an implementation of this kind could result in a decrease of performance due of increased CPU work that needs to be done during array allocation/construction. Of course, this depends on how much the "look for a partial/total equal array" algorithm will need in terms of CPU cycles. I think that the discussion about a topic like this will require a completely new article :-)

Faster item access

Accessing items requires to cycle over all the internal list items of the immutable array. This can become expensive in terms of CPU cycles if the items of the list are a lot. Some optimizations can/should be done in this area of implementation in order to speed up access to the i^th item of the array.

private int GetArrayIndexAt(ref int index)
{
    if ((index < 0) || (index >= this.Count))
        throw new IndexOutOfRangeException(String.Format(
            "Index {0} out of array bounds", index));

    for(int i=0; i<this.arrayscollection.count;>< this.ArraysCollection[i].Length)
            return i;

        index -= this.ArraysCollection[i].Length;
    }

    return -1;
}