Andrew Arnott

Immutable Object Graph updates

Andrew L Arnott — Tue, 07 May 2013 15:31:16 GMT

In my last post, I introduced a T4 template that constructs efficient and quite capable immutable objects based on the simplest mutable type definition. I also mentioned that the published sample is (necessarily, ala T4 style) open source and hosted online. Two outsiders have already submitted pull requests that have been accepted. Some thoughtful feedback came in the form of comments to my last blog post as well. Thank you for your participation!

The latest incarnation of the T4 template is substantially improved over what my last post described. Here are a few of them:

The immutable types now look and feel more like the immutable collections, having static factory Create() methods instead of a static Default property.
The With(…) multiple parameter method is easier to use.
Partial methods give you the opportunity to set defaults for any property on your type.
Certain fields can be marked as required, so that they are not optional parameters in the Create() method.
Better support for immutable collections as members of the immutable types.
The T4 template is broken up into several files, modeled as extensions, making it easier for you to add additional functionality to the template without having to fork the code in your own codebase, making future updates from the official project easier.
Better support for a network of immutable objects referencing each other (the graph part of the name).

#7 is where I expect to spend much of the future work on this effort.

If this topic interests you, please take a fresh look at the latest version, and keep the feedback coming.

Simple immutable objects

Andrew L Arnott — Tue, 08 Jan 2013 20:19:00 GMT

We’re all familiar with immutable collections now. But immutability is only as immutable as it is deep. And an immutable collection of mutable objects may not provide the depth you’re looking for. So how can one create an immutable object?

Suppose you would define the mutable version like this:

public class Fruit { 
    public string Color { get; set; }
}

An immutable version might be defined like this:

public class ImmutableFruit {
	private readonly string color;
	
	public ImmutableFruit(string color) {
		this.color = color;
	}
	
	public string Color {
		get { return this.color; }
	}
}

Now that’s fine for very simple objects. But once objects have several fields on them, the code you have to write to create a new object with just one or two fields changed gets tedious to write and maintain. So we can add a helper method for each property, that returns a new object with just that property changed. The method name convention is WithPropertyName.

We can make a couple more enhancements though. For classes with many properties, if you need to change several properties at once, allocating a new object with each property change as an intermediate step is wasteful and can contribute to GC pressure. So we also add a With method that takes optional parameters for every property found on the class, allowing bulk property changes. Finally, for scenarios where you have several changes to make to the object but wish to do so in a multistep fashion (or just prefer property setters to With- method calls), we can construct a Builder class that allows mutation, and then can return the immutable copy when you’re done. This pattern is very similar to String and StringBuilder in the .NET Framework, and also like the recent immutable collections mentioned earlier.

Another enhancement we can make is to make all constructors private. Why? Because a public constructor will end up allowing callers to allocate many copies of the default instance. Since these are immutable, this is just wasted memory and GC pressure. Alternatively, a static Default property that returns what a public default constructor would have but sharing the instance with all other callers, alleviates the pressure while also putting the caller in the “mood” for functional programming.

What does the resulting immutable object look like? Considering it’s just a simple immutable object with one property, it’s rather large.

public partial class Fruit {
	[DebuggerBrowsable(DebuggerBrowsableState.Never)]
	private static readonly Fruit DefaultInstance = new Fruit();
	
	[DebuggerBrowsable(DebuggerBrowsableState.Never)]
	private readonly System.String color;
	
	/// <summary>Initializes a new instance of the Fruit class.</summary>
	private Fruit()
	{
	}
	
	/// <summary>Initializes a new instance of the Fruit class.</summary>
	private Fruit(System.String color)
	{
		this.color = color;
		this.Validate();
	}
	
	public static Fruit Default {
		get { return DefaultInstance; }
	}
	
	public System.String Color {
		get { return this.color; }
	}
	
	public Fruit WithColor(System.String value) {
		if (value == this.Color) {
			return this;
		}
	
		return new Fruit(value);
	}
	
	/// <summary>Returns a new instance of this object with any number of properties changed.</summary>
	public Fruit With(
		System.String color = default(System.String),
		bool defaultColor = false) {
		return new Fruit(
				defaultColor ? default(System.String) : (color != default(System.String) ? color : this.Color));
	}
	
	public Builder ToBuilder() {
		return new Builder(this);
	}
	
	/// <summary>Normalizes and/or validates all properties on this object.</summary>
	/// <exception type="ArgumentException">Thrown if any properties have disallowed values.</exception>
	partial void Validate();
	
	public partial class Builder {
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		private Fruit immutable;
	
		[DebuggerBrowsable(DebuggerBrowsableState.Never)]
		private System.String color;
	
		internal Builder(Fruit immutable) {
			this.immutable = immutable;
	
			this.color = immutable.Color;
		}
	
		public System.String Color {
			get {
				return this.color;
			}
	
			set {
				if (this.color != value) {
					this.color = value;
					this.immutable = null;
				}
			}
		}
	
		public Fruit ToImmutable() {
			if (this.immutable == null) {
				this.immutable = Fruit.Default.With(
					this.color);
			}
	
			return this.immutable;
		}
	}
}

Of course adding more properties will be common, and the code will increase a bit more with each one. Since each added property means two new fields (one for the immutable type and one for the Builder), two new properties, and one new method and several other methods to update, this gets quite tedious to write and maintain.

So what can we do to simplify immutable programming? After all, immutable programming is supposed to be easy, right? Why can’t authoring immutable types in C# be as easy as mutable types (or immutable types in F#)? There is a better way, using Visual Studio T4 templates.

Consider this simple definition of a mutable type:

class Fruit {
    string color;
}

We can leverage code generation to produce an immutable version of this class that fulfills all the patterns described above. And due to the built-in support for T4 in Visual Studio, the experience can be just as easy as maintaining the above simple mutable type. Adding a property to the Fruit class is as simple as adding one line for the field in the above mutable type. Saving the updated file will immediately update the code generated immutable Fruit class, allowing you to get Intellisense and compile against the immutable version. T4 is built into Visual Studio, so it will already work for you today. Because code generation happens at design-time, you don’t need any additional support for it in any customized build system you may have.

I’ve published the code generation tool in source form as a sample. You can see a live example of the before and after code generation. The README in that project describes more and provides instructions for incorporating this tool into your source projects.

I’d like to add features as we go so your feedback is welcome.

Immutable collection algorithmic complexity

Andrew L Arnott — Mon, 07 Jan 2013 14:19:22 GMT

I received some feedback from my recent BCL blog post on the prerelease of the immutable collections that my algorithm complexity table left a few important entries out. Here is the table again, with more data filled in (particularly around list indexer lookup and enumeration):

	Mutable (amortized)	Mutable (worst case)	Immutable
Stack.Push	O(1)	O(n)	O(1)
Queue.Enqueue	O(1)	O(n)	O(1)
List.Add	O(1)	O(n)	O(log n)
List lookup by index	O(1)	O(1)	O(log n)
List enumeration	O(n)	O(n)	O(n)
HashSet.Add, lookup	O(1)	O(n)	O(log n)
SortedSet.Add	O(log n)	O(n)	O(log n)
Dictionary.Add	O(1)	O(n)	O(log n)
Dictionary lookup	O(1)	O(1) – or strictly O(n)	O(log n)
SortedDictionary.Add	O(log n)	O(n log n)	O(log n)

A noteworthy trait to call out here is that where a List<T> can be efficiently enumerated using either a for loop or a foreach loop, ImmutableList<T> does a poor job inside a for loop, due to its O(log n) time for its indexer. It does fine when using foreach however. This is because ImmutableList<T> uses a binary tree to store its data instead of a simple array like List<T> uses. An array can be very quickly indexed into, whereas a binary tree must be walked down until the node with the desired index is found.

Another point to call out from the above table is that SortedSet<T> has the same complexity as ImmutableSortedSet<T>, and in fact in perf tests they show up as pretty close. That’s because they both use binary trees. The significant difference of course is that ImmutableSortedSet<T> uses an immutable one. Since ImmutableSortedSet<T> also offers a Builder class that allows mutation, you can have your immutability and performance too. Woot.

The cost of context switches

Andrew L Arnott — Fri, 28 Dec 2012 17:56:08 GMT

Context switches are not free. But how expensive are they? I wrote a small program to find out, and I’m sharing the program and its results here.

I focused on purely context switches (no work is actually performed between context switches). So it’s not a real-world scenario, but it really brings out the hidden costs. Below are the results 500,000 context switches performing no work between each one.

Executing 500000 work cycles of 0 iterations each, in different ways...
Scenario            Total time (ms)     Time per unit (µs)
No-switch           0                   0.0002
Async w/o yield     67                  0.0353
Async w/ yield      664                 0.349
Thread switches     5215                2.7412

Notice how with each kind, the order of magnitude of the overhead increases. The code below will help you understand what each each scenario name actually means. Then we add a bit of work (counting to 500) per context switch, which is closer to a possible real-world work load (although relatively lightweight) that might occur for a given context:

Executing 500000 work cycles of 500 iterations each, in different ways...
Scenario            Total time (ms)     Time per unit (µs)
No-switch           380                 0.1998
Async w/o yield     368                 0.1935
Async w/ yield      832                 0.4374
Thread switches     5185                2.7257

Suddenly no context switch and async methods all share an order of magnitude, while thread switches still takes significantly longer. In fact closely comparing shows that Async w/o yield is faster than no switch at all. This of course is ludicrous and can be written off as noise. But several runs produced the same result, so we can glean from this that when doing even a small amount of work per context switch, that the no-yield async method adds insignificant overhead.

Following is the application that produced the above results.

using System;
using System.Diagnostics;
using System.Threading;
using System.Threading.Tasks;

class Program {
	const int unitSize = 500;
	const int workSize = 500000;
	const string spacing = "{0,-20}{1,-20}{2,-20}";

	private static void Main(string[] args) {
		Console.WriteLine("Executing {0} work cycles of {1} iterations each, in different ways...", workSize, unitSize);

		Console.WriteLine(spacing, "Scenario", "Total time (ms)", "Time per unit (μs)");
		Scenario("No-switch", DoSync);
		Scenario("Async w/o yield", DoAsyncNoYield);
		Scenario("Async w/ yield", DoAsyncWithYield);
		Scenario("Thread switches", ThreadSwitch);
	}

	static void Scenario(string name, Action operation) {
		GC.Collect();
		operation(); // warm it up
		var timer = Stopwatch.StartNew();
		operation();
		timer.Stop();
		Console.WriteLine(spacing, name, timer.ElapsedMilliseconds, MicroSecondsPerItem(timer));
	}

	static void ThreadSwitch() {
		int workRemaining = workSize;
		var evt = new AutoResetEvent(true);
		ThreadStart worker = () => {
			while (workRemaining > 0) {
				evt.WaitOne();
				workRemaining--;
				WorkUnit();
				evt.Set();
			}
		};

		var threads = new Thread[Environment.ProcessorCount];
		for (int i = 0; i < threads.Length; i++) {
			threads[i] = new Thread(worker);
			threads[i].Start();
		}

		for (int i = 0; i < threads.Length; i++) {
			threads[i].Join();
		}
	}

	static void DoAsyncNoYield() {
		var tcs = new TaskCompletionSource<object>();
		tcs.SetResult(null);
		var task = tcs.Task;
		Task.Run(
			async delegate {
				int workRemaining = workSize;
				while (--workRemaining >= 0) {
					await NoYieldHelper(task);
				}
			}).Wait();
	}

	static async Task NoYieldHelper(Task task) {
		WorkUnit();
		await task;
	}

	static void DoAsyncWithYield() {
		Task.Run(
			async delegate {
				int workRemaining = workSize;
				while (--workRemaining >= 0) {
					WorkUnit();
					await Task.Yield();
				}
			}).Wait();
	}

	static void DoSync() {
		int workRemaining = workSize;
		while (--workRemaining >= 0) {
			WorkUnit();
		}
	}

	private static double MicroSecondsPerItem(Stopwatch timer) {
		var ticksPerItem = (double)timer.ElapsedTicks / workSize;
		var microSecondsPerItem = TimeSpan.FromTicks((long)(ticksPerItem * 1000)).TotalMilliseconds;
		return microSecondsPerItem;
	}

	static void WorkUnit() {
		for (int i = 0; i < unitSize; i++) {
		}
	}
}

Immutable collections now available

Andrew L Arnott — Thu, 20 Dec 2012 03:28:18 GMT

In previous posts, I discussed immutable collections. I’m pleased to say they are now available. Read my announcement on the BCL blog.

Update to Visual C++ 2012 Debugger launch extension template

Andrew L Arnott — Fri, 08 Jun 2012 18:11:07 GMT

A few days ago I posted about an updated Visual C++ 2012 debugger extensibility project template. Since then, I realized it had a couple of issues that prevented it from working out of the box. With those fixed, I also added a demonstration of how to read project properties that aren’t specifically dedicated to debugger support. For example, if you want to determine the target framework of the project, or read the TargetPath property, that requires that you read properties that aren’t in your own debugger property page. The project template on the Visual Studio Gallery is already updated with these new capabilities.

Unfortunately there’s a slight new problem with the initial project expansion (when you use New Project to create a project based on the template), but the opening web page that explains next steps tells you the workaround.

Enable C++ and Javascript project system tracing

Andrew L Arnott — Thu, 07 Jun 2012 21:10:00 GMT

I’ve previously posted on how to enable logging in the C++ project system in Visual Studio 2010. In Visual Studio 2012 we’ve changed the way the Common Project System (aka “CPS”) emits trace messages so below I introduce an updated xml snippet that works in Visual Studio 2012. Since CPS is now the project system driving JavaScript as well, the below xml snippet impacts that as well.

To enable tracing, add the following xml block to devenv.exe.config file directly under the <configuration> root node, after the </configSections> end tag. Make sure to make a backup first so that you can revert back in case something goes wrong. You may need to change "Warning" below with "Verbose" if you want verbose logging.

<system.diagnostics>
    <sources>
        <source name="CPS" switchName="CPS" switchType="System.Diagnostics.SourceSwitch">
            <listeners>
                <add name="cpsFileLogger"/>
            </listeners>
        </source>
    </sources>
    <switches>
        <add name="CPS" value="Warning"/>
    </switches>
    <sharedListeners>
        <add name="cpsFileLogger" type="System.Diagnostics.TextWriterTraceListener" initializeData="c:\temp\devenv-cps.log">
            <filter type="System.Diagnostics.EventTypeFilter" initializeData="Warning"/>
        </add>
    </sharedListeners>
    <trace autoflush="true" indentsize="4" />
</system.diagnostics>

Visual C++ 2012 Debugger Extensibility

Andrew L Arnott — Tue, 05 Jun 2012 17:56:24 GMT

Back in Visual C++ 2010 we introduced debugger extensibility so that third party vendors can either add new debugger engines or new ways of launching existing debugger engines for C++ projects.

In Visual C++ 2012 this debugger extensibility has been updated. Any previous extensions that were compiled against Visual C++ 2010 will have to be recompiled after updating your source code to implement the new interface. Visual Studio doesn’t usually break backward compatibility, particularly for extension points, and we realize this can cause some additional work for our partners. This interface in both its 2010 and 2012 versions isn’t considered “final”, so while we knew our partners need this extensibility point in these intermediate forms, we appreciate your patience and understanding as we evolve what we hope will become a common extensible platform for project systems.

With that out of the way, please check out the new Visual C++ 2012 Debugger Launch Extension project template on the Visual Studio Gallery to get started.

Immutable collections with mutable performance

Andrew L Arnott — Tue, 30 Aug 2011 03:33:29 GMT

In my last post, I detailed the differences among read/write, read only, frozen and immutable collection types. I described how immutable collections come with a hit to the garbage collector due to the garbage they generate during mutations. I have a very positive update on that topic.

My previous implementation for the immutable collections used a truly immutable binary tree as its backing data structure. As a result, every individual mutation required a spine rewrite where (log n) nodes were recreated. For a batch of m changes, this meant m log n objects were created and immediately discarded. That’s a lot of garbage. And all those memory allocations (and GC interruptions) hurt performance to the tune of about being twice as slow as mutable collections.

By changing the collections to use a freezable binary tree data structure, spine rewrites retain new nodes that are mutable until the (bulk) operation has completed. As a result, only log n nodes are created instead of m log n. And those new nodes aren’t garbage: they’re the important “new” part of the updated collection. By eliminating all garbage from intermediate steps of mutations, I’ve measured a 91% drop in overall memory allocation (the remaining 9% is not garbage) and a 50% improvement in performance. This brings performance and memory load of immutable collections on par with the mutable collections, while retaining all their immutable properties that make them so attractive.

Is there anything worse about the immutable collections then? Yes, if you have rapid changes to the collections that you make individually (you don’t batch them with AddRange or some similar method) then you still may produce a lot of garbage assuming you release each version as you update it, whereas a mutable collection may have vacant memory slots it can fill when you add elements, immutable collections do not, and thus allocate memory for every element addition. But as discussed in my previous post, this “slack space” is also a point against mutable collections as it wastes memory that isn’t reclaimable until to release the entire collection.

We expect (not promise) to ship these highly tuned immutable collections as a public CTP release soon. I’m stoked.

Read only, frozen, and immutable collections

Andrew L Arnott — Sun, 21 Aug 2011 23:21:00 GMT

[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:

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.
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.
Freezable: a collection or type that is mutable until some point in time when it is frozen, after which it cannot be changed.
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 immutable 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 most 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

	Read only	Frozen	Immutable
Capabilities
Thread-safe	No	Yes	Yes
Type-safe declaration	Yes	TBD	Yes
Immutable guarantee	No	Yes	Yes
Allows mutation	Yes, shared	No	Yes, isolated
CPU
Isolated mutations performance	Poor	Poor	Great
Shared mutation performance	Great, except when underlying data structure is outgrown and must be cloned.	N/A. No mutations allowed.	N/A. All mutations are isolated.
Memory
Storage data structure	Array	Array	Binary tree
Memory across isolated versions	Full duplication	Full duplication	Efficient sharing
Garbage generation	Low	Low	Potentially high [update]

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.