Read only, frozen, and immutable collections

[Update: a more recent post with new data on attainable performance of immutable collections]

The topics of immutability and functional programming has fascinated me lately.  Mostly because of my work on the Visual Studio Common Project System (CPS) which is a large, highly multi-threaded code base that only remains sane because of its reliance on immutable types in many areas.

In my research and conversations on this topic, I’ve learned to appreciate the differences between several adjectives often used interchangeably among programmers that I’d like to share with you, detailing the differences including some pros and cons of each.  At the bottom of the post I include a summary table and my own personal verdict for what kinds of collections (mutable and immutable) I prefer.

Although the principles here apply to any type in any language and platform, I’ll be using for some references and examples the collection types in the .NET base class library.

First a little terminology as I will use it in this post:

1. Mutable (a.k.a read/write): a collection or type that allows for in-place updates that anyone with a reference to that object may observe.
2. Immutable: a collection or type that cannot be changed at all, but can be efficiently mutated by allocating a new collection that shares much of the same memory with the original, but has new memory describing the change.
3. Freezable: a collection or type that is mutable until some point in time when it is frozen, after which it cannot be changed.
4. Read only: a reference whose type does not permit mutation of the underlying data, which is usually mutable by another reference.

The de facto read only standards in .NET

There are not yet any freezable or immutable collections included in the  .NET base class library.  But we have a couple of read-only views of data, as outlined below. 

De facto standard #1: IEnumerable<T>

Often considered a convenient way to express data in a read-only way, IEnumerable<T> actually provides very few, if any, guarantees and almost no protections.

• NO thread-safety to issuer or receiver. If the underlying collection changes while being enumerated from another thread, data corruption may result or exceptions may be thrown.
• NO immutability guarantee to the receiver. The underlying collection may be changed.
• NO immutability guarantee to the issuer. The receiver may cast the enumerable to ICollection or some other read/write type and may mutate the data through that interface if the underlying object allows it.
• NO performance guarantee to the receiver. The enumerable may represent a deferred execution query (LINQ for example) that may incur significant cost including network overhead with each enumeration.

Avoiding these shortcomings usually requires enumerating exactly once into a cloned collection, which comes with a perf and memory hit, and doesn’t entirely protect you from thread-safety issues that may occur during that one enumeration.

De facto standard #2: ReadOnlyCollection<T>

Somewhat misleadingly named, this collection is neither immutable nor a general collection. It is merely a wrapper around a mutable list.  Perhaps a more accurate name would be ReadOnlyListFacade<T>. 

This collection type is better than IEnumerable<T> in several ways, but still deficient in others:

• YES, immutable guarantee to the issuer.  The collection owner never releases a reference to the mutable collection, as the ReadOnlyCollection<T> is a genuine wrapper around the mutable data, making it impossible for a receiver of the collection to mutate the data.
• YES, thread safety to the issuer, since the receiver cannot mutate the data, the underlying collection may be mutated without fear that the issuer with throw an exception or corrupt its own data.
• YES, reasonable performance guarantee to the receiver.  The IList<T> that the ReadOnlyCollection<T> wraps is virtually never populated via deferred execution.  Therefore enumerating the ReadOnlyCollection<T> repeatedly can generally be done with high performance and without side effects.
• NO thread-safety to the receiver.  If the receiver is reading the ReadOnlyCollection<T> while the issuer is mutating the underlying collection, the client may get an exception or perhaps even incorrectly perceive the contents of the collection.
• NO immutability guarantee to the receiver. The underlying collection may be changed.

Considerations among collections

Thread-safety

Collections that are not thread-safe cannot be made thread-safe in a shareable way.  For example, although you can put lock { } statements around all uses of a collection to make it thread-safe, you cannot share references to your collection or any part of it outside your class because outside holders of that reference will not synchronize access to it with the same lock object you do (and ICollection.SyncRoot seems increasingly unpopular if it were ever known at all).  This suggests the importance of thread-safety built into collection classes.

Freezable collections

There are no freezable collection types in .NET (yet anyway).  So a discussion on them is somewhat speculative.  If the traditional List<T> class were to pick up a “Freeze()” method and an “IsFrozen” property, there would still be missing a type-safe way of communicating that a method expects or returns a frozen collection. You would have to perform a runtime check to see what is allowed or provided. Collection types that guarantee immutability are preferable for this purpose. If a method accepts an immutable collection parameter or returns an immutable collection, you have 100% confidence that that collection cannot ever change, period. If a List<T>.Freeze() method returned a FrozenList<T> object, and both the original List<T> and the FrozenList<T> pointed to the same data structure that could no longer be changed, that would provide a type-safe way of requiring or guaranteeing immutable data, however.

While one might consider that guarantee more theoretically aesthetic than practically useful, I can speak from some experience now that I avoid a lot of collection cloning code (and the perf problems that showed up as a result) because I know that a collection I just received cannot possibly be changed. It’s gotten to the point that when I see a method accepting an IList<T> I ask myself “Why? Is that method expecting the caller to further mutate that list during or after its invocation and that the method will need to see that mutation?” Call me a functional programming geek, but if a method does not expect the caller the tamper with a collection that it passes to the method, I now greatly prefer to see IImmutableList<T> as the method parameter.

Before freezing, freezable collections offer the high construction performance and compact memory utilization of traditional mutable collections.  After freezing, any further mutation requires shallow cloning of the entire collection, with the perf and memory hit that comes with it. 

One possible danger of using a collection that is freezable (but unfrozen) is that someone you share a reference to the collection with might want an immutable copy of the collection and may freeze the collection behind your back, not realizing that your class still “owns” the collection and thus expects it to not be frozen.

Performance

The performance of mutable collections, particularly when they are initially sized adequate for their contents, can’t be beat by immutable collections.  However the performance of immutable collections can be remarkably good.  Much better than one might expect, and certainly good enough for due consideration in your design.

Immutable collections primary shortcoming is that raw add performance tends to be 2-3X slower than the amortized cost of its mutable collection counterparts.  This is chiefly due to the mandatory “spine rewrite” of the binary tree and the memory allocations that go along with it.  I just compared against amortized cost of mutable collections because mutable collections have the shortcoming of occasionally breaking the bounds of their pre-allocated memory, which usually means allocating twice as much and then copying all the data from the old location to the new location.

Before you write off mutable collections due to their perf impact on initialization, keep in mind that this may rarely be where the performance problems in apps come from.  In my experience the perf problems never come from creating a new collection, but rather from cloning a collection within a lock to provide immutability and thread-safety guarantees, which completely vanish when you switch to genuinely immutable collections.  Also, the spine rewrite that leads to the slower fill performance can be avoided by using an immutable collection that optimizes around that scenario, as described in the below discussion on garbage collection.

Memory efficiency

When dealing with collections, there’s no tighter data structure than an array, which is the underlying data structure of choice for must flat collections.  It has almost no overhead beyond the data stored, and that’s hard to beat.  On the other hand, since arrays have fixed size, it usually means there is memory wasted in the slack between the last element in the collection and the last slot in the preallocated array.  And when you have more elements than you have slots in the array, the array growth algorithm tends to be to allocate a new array of double the length and move all the data over, which means even more slack space wasting your memory.

Immutable collections can’t afford (in memory or performance) to use arrays because changing the collection would require cloning the array every time.  Instead, performant immutable collections can use binary trees that allow for incremental, non-mutating updates to the collection.  Without going deep into the theory of it, it allows (for example) an immutable collection of 500 elements to be mutated into a new collection with one element added or removed while sharing almost all the memory between the two collections.  But because binary tree data structures require a heap-allocated “node” to represent each element in the array, with references to two other nodes in the tree, there is an overhead of at least 12 bytes per element in immutable collections.

Garbage generation and collection

Garbage generation is also an important concern when considering the memory impact of immutable collections.  Every mutation of an immutable collection necessarily allocates more memory.  And while most memory is shared across the different versions of the collection, when a particular version of a collection is no longer referenced, it automatically gets garbage collected.  This is a convenient feature of immutable collections in that they optimally share and automatically free memory.  However, since each mutation of the collection makes the last version of the collection uninteresting and thus available for garbage collection, it generally means that more garbage is produced than for the mutable counterpart. 

What’s the problem with allocating objects if they are freed as soon as they are not used any more?  The problem comes at garbage collection time. The more memory you allocate and release, the more frequently the garbage collector has to run, which usually suspends all other threads in your .NET application, potentially causing perf problems during or sometime after all that memory had been allocated and freed. 

This garbage collection pain is usually most poignantly felt when initializing very large immutable collections.  Without appropriate optimizations for this scenario, a large immutable collection will produce many times as much garbage during construction as its own final size in memory at completion.  So if you built a collection that requires 1MB of RAM just for the collection itself, you might have just blown through 4MB of RAM during its construction (freeing 3MB immediately after).  A well-written immutable collection class could optimize for this initialization case by allowing itself to reuse (i.e. mutate) tree nodes during initialization only, when such reuse could never be detectable outside as a “mutation”, which would solve the garbage generation problem for immutable collections, unless your collections tend to mutate very rapidly even after initial construction.

Summary

If you enjoyed this post, you may enjoy Eric Lippert’s blog posts tagged Immutability.  Eric Lippert wrote a good post on different kinds of immutability back in 2007.

And please let me know if you found this post useful or interesting.