Immutable Collections

2013/02/17

Immutable Collections

Immutability is a pattern which is suit well parallel programming,
but you have to be aware of a potential memory pressure risk when it’s not implemented right or used wisely.

this post will cover a new BCL library (still in its preview stage) which is targeting immutable collections.

Immutable, Parallel, Task, BCL, collection, Thread-safe

.NET is already having Concurrent implementation for Queue, Stack, Bug and Dictionary, which is thread-safe, but other type of collection like List is missing.
another type of collection are read only collection, but those type of collection are not truly thread-safe because it is just a wrapper upon other collection which can be mutate by it’s owner.
so iterating on a read only collection doesn’t guarantee thread-safety because the collection can be mutate during the iteration by it’s original owner.
currently we do have one option to create an immutable collection by using the ToArray() extension method, but as I mentioned before it can lead to a memory pressure while using a large collection.

the BCL team was targeting this issue and are working on a new kind of collections which are immutable.
those collection is having a cool concept which guarantee that an immutable sequence will not changed, but it can be part of another immutable sequence. this mean that you can take an immutable collection and add an item. this will keep the immutable part as is and you will get a new collection that include your addition and the original collection, but if someone is using the original collection he won’t be affected by your mutation.
as you can see the BCL immutable collection can be mutate but the mutation will return a new collection and leave the original collection untouched.

Start using the immutable collection

you can start using it though NuGet.
on the current preview version it includes:

  • ImmutableStack<T>
  • ImmutableQueue<T>
  • ImmutableList<T>
  • ImmutableHashSet<T>
  • ImmutableSortedSet<T>
  • ImmutableDictionary<K, V>
  • ImmutableSortedDictionary<K, V>
Fluent API

I will speak about 3 APIs:

  • Add
  • AddRange
  • Builder
Add
Code Snippet
  1. [Test]
  2. public void List_AddItem_Test()
  3. {
  4.     var col = ImmutableList<int>.Empty;
  5.     var col1 = col.Add(1);
  6.     var col2 = col1.Add(2);
  7.  
  8.     Assert.AreEqual(0, col.Count);
  9.     Assert.AreEqual(1, col1.Count);
  10.     Assert.AreEqual(2, col2.Count);
  11. }

whenever you want an empty instance of immutable collection you should use the static Empty property (there is no public constructor available).

you should always remember that Adding an item will not affect the original collection therefore you must handle the return value (is is the same concept as string.Replace).

finally you can notice at lines 8-10 that the above code was actually construct 3 different immutable collections.

AddRange

both from performance and usability it is better using the AddRange API when you intend to add multiple items.

Code Snippet
  1. [Test]
  2. public void List_AddRange_Test()
  3. {
  4.     var col = ImmutableList<int>.Empty;
  5.     var col1 = col.AddRange(Enumerable.Range(0, 1000));
  6.  
  7.     Assert.AreEqual(0, col.Count);
  8.     Assert.AreEqual(1000, col1.Count);
  9. }

Builder

if you want to efficiently add multiple items and AddRange doesn’t do the job for you, you can use a Builder (the concept is quit similar to StringBuilder).
you should remember that unlike the immutable collection a builder is not a thread-safe structure, therefore you shouldn’t share its state between threads.
when you complete the mutation, you can extract an immutable collection from the builder.

Code Snippet
  1. [Test]
  2. public void List_Builder_Test()
  3. {
  4.     var col = Enumerable.Range(0, 1000).ToImmutableList();
  5.     var builder = col.ToBuilder();
  6.     for (int i = 0; i < 100; i++)
  7.     {
  8.         builder.Remove(i * 10);
  9.     }
  10.     var col1 = builder.ToImmutable();
  11.     Assert.AreEqual(1000, col.Count);
  12.     Assert.AreEqual(900, col1.Count);
  13. }

line 5: getting a builder from immutable collection.
line 10: getting an immutable back from the builder (after the mutation).

Migration

if you are using a read only collection though the IReadOnlyCollection, IReadOnlyList or IReadOnlyDictionary, migration will be easy because the immutable collections are implementing those interfaces.

Optimization

we already spoke about the memory pressure optimization, but what is the characterize of those collection in compare with the well known BCL mutable collection?
as the BCL team argue that immutable collections have been heavily tuned for maximum performance and minimum GC pressure.

the following table was published by the BCL team.
it compare the performance behavior of the BCL immutable and immutable collection (and remember that this is only a preview version which mean that further optimization can be applied).

Immutable, Parallel, Task, BCL, collection, Thread-safe

you can read more on this at this post.

summary

Immutability is a great pattern for parallelism.
the BCL team are giving us a robust and well design immutable collection.
the potential memory pressure has reduced by the internal data-structure design.
so it is definitely something to wait for its release.

you can read more about it at here.
and if you want more background and comparison to the read only collection, you can check out this post.

Shout it

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>