On Structural Immutability

Posted: January 21, 2013 in Uncategorized

Recently I’ve being doing quite a bit of coding with vectors, matrices and various higher dimensional mathematical arrays. This is motivated by the fact that I need them for my work at Nuroko, and also because I’m working on a new library for numerical computing in Clojure: core.matrix

There’s lots of interesting stuff to do in this space, but one detail that has recently caught my eye is the concept which, for want of a a better definition, I’m calling “Structural Immutability”.

Definition

Structural Immutability is the property that a compound data structure has when the *structure* of it’s component values is fixed and immutable, but the component values themselves may not be. Examples:

  •  A Clojure persistent data structure is structurally immutable. But that’s because it is completely immutable in the regular sense as well, and structural immutability is necessarily implied by full immutability.
  •  A java.util.ArrayList is not structurally immutable, because you can add and delete elements.
  •  A Java array is structurally immutable. Once it is created, you cannot change the length / layout of the elements it contains. You can, however, mutate the elements themselves freely, so it is not fully immutable.
  •  A Clojure atom is structurally immutable. It always contains exactly one value, but you can mutate it freely.

I’m sure you get the idea.

Why should you care about structural immutability?

Well it turns out that structurally immutable objects have some nice and useful properties.

  •  Performance. Mutability is a necessary evil. As a Clojure developer, I’m happiest when everything is pure and immutable. But for performance reasons, you sometimes need to resort to mutable data structures. Immutability can mean the creation of a *lot* of new objects, which can cause significant performance issues and GC pressure. Structurally immutable objects can generally match the performance of fully mutable data structures for most operations. Indeed, Java arrays (which are structurally immutable) are the usual choice for people wanting to write highly optimised algorithms with mutable data in both Java and Clojure.
  • Structurally immutable objects offer better thread-safety – typically a individual component in a structurally immutable collection can be mutated with a single atomic operation (e.g. updating a value in a Java array). This can be enough to satisfy your thread safety requirements *without locking* – a structurally immutable object can therefore be treated as equivalent to a collection of Clojure atoms. Compare with data structures that allow structural modification (e.g. ArrayList) and you will find that they are fundamentally unsafe under concurrent modification.
  • Structural sharing becomes possible. Normally structural sharing is associated with immutable data structures, but it also works for structurally immutable objects. This isn’t possible with completely mutable data structures, since structural modifications would break the structural sharing.
  • Structurally immutable objects compose – that is, you can glue two structurally immutable objects together and create a new structurally immutable objectThis can exploit structural sharing by just keeping two references to the original object being composed, i.e. the new composed object can be extremely lightweight.
  • Mutable sub-views can be supported, once again via structural sharing. You can create a view into a subset of structurally immutable data structure, where changes to the view also change the underlying data and vice versa.

The last three points about structural sharing and composition are to me the most interesting. Structural sharing is a powerful concept, and is what enables Clojure persistent data structures to achieve O(log n) performance on operations that would otherwise require full O(n) copies of a data structure.  It turns out that you can also achieve effective structural sharing of mutable data structures if they are structurally immutable. Effectively you get opportunity to realise the same O(log n) performance for operations that produce mutable views.

Applications

I’ve found a few good examples where this is all very useful:

  • Taking a row of a matrix and treating it as a vector, while both objects still refer to the same mutable data. You can then run an algorithm on the vector which mutates it, and immediately see the changes reflected in the matrix.
  • Creating compound views of parameter sets. In my machine learning work, I often deal with many models each of which have large parameter vectors. It’s helpful to be able to create a compound object that represents “all the parameters” from multiple models. You can then perform operations on all the parameters at once.
  • Simplifying algorithms: you often see specialised functions designed to work on a subset of a collection, e.g. (foo some-array start-index length). You don’t to do this though if you have a lightweight way of taking a view of a sub-array since you can get the same effect with: (foo (sub-array some-array start-index length)) . If you have a large set of functions this is a big win over giving them all different arity overloads. In a Rich Hickey sense this is more “simple” – you have de-complected the identification of the desired subset from the function / algorithm itself.
  • Performance with large arrays: taking a view with structural sharing is cheap compared to copying the underlying data when you are working with large arrays of numbers. This is very important in numerical applications, where copying and reshaping data to fit different algorithms  can be a significant overhead.

Conclusions and caveats

I’m not saying go and make everything structurally immutable. There are a few downsides to watch up for:

  • It’s still mutable state! – with all the usual caveats that this implies
  • Remembering what is and isn’t a view gets tricky – in particular, you need to be careful if you want to modify a sub-view and expect to see the results reflected in the underlying source data structure. If at any point you made a copy rather than taking a view, then this won’t work.

Nevertheless, I think that on balance structurally immutable objects are much nicer to work with than those that have mutable structure. They have many of the advantages of fully immutable data structures thanks to structural sharing, while avoiding the worst pitfalls around concurrent structural modification.

In particular, I think that aiming for structural immutability should normally be your preferred choice if you decide that you genuinely need mutable data. It’s an effective compromise between the simplicity and elegance of immutability and the underlying performance advantages of mutability.

About these ads
Comments
  1. vemv (@loudlist) says:

    Thanks for the article, great introduction and argumentation of the term.

    On thread safety – while I’m not an expert, it seems to me that S.I. doesn’t entirely free one from synchronization, does it? e.g. given a S.I. array/list/…, consistent/visible updates from different threads would require either locking the cells acted upon, or making them volatile.

    • mikera7 says:

      yeah that’s right if you want precise volatile semantics. OTOH, there are plenty of situations where you don’t need that. caveat emptor, as always with threading-related stuff. :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s