Download source - 22.59 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 usefull when thread safety is a concern and/or when an instance of an object must be acccessed outside of our code in a readonly mode. This is why the designer of .NET and Java frameworks decided both 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, tought 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 be of course of the type byte, but also an int, a char, etc.
The objects of the immutable array must be immutable themself: so I put o constraint on the generic type specifing that it must be a value type (struct).

In short

Advantages:

• Thread safety
• 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

At the beginning of our code we declare these type alias, 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, in this way:

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;

The array3 is a concatenation of the other two instances of the immutable array. That instance is NOT consuming 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()) is not consuming memory:

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

The 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 the ImmutableArray<T> overrides and implements the Equals() 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 advantes 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 the future (see next chapter) to reduce memory usage.
The ImmutableArray<T> is implemented as an array (List) of InternalImmutableArray<T>s. This is really comfortable because in 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 each other 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 the performance due of the increased CPU work that needs to be done during array allocation/construction. Of course this depends on how 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 complete new article :-)

Faster item access

Accessing items requires to cicle 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 the implementation in order to speed up the 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;
}
</this.arrayscollection.count;>