Intent

To use mutable data structures in small, performance-sensitive parts of a program hidden inside of a function while still using immutable data throughout the majority

Overview

Programming with performant, immutable data on machines that are built out of fundamentally mutable components, like main memory and disk, is almost magical. A whole host of technology has contributed to making it possible, especially on the JVM. Growing processor power and memory sizes make it increasingly unnecessary to squeeze every last drop of performance out of a machine.

Small, transient objects are cheap to create and to destroy, thanks to the JVM’s excellent generational garbage collector. Both Scala and Clojure use extremely clever data structures that allow immutable collections to share state. This obviates the need to copy the entire collection when one piece of it is changed, which means collections have a reasonable memory footprint and can be modified fairly quickly.

Still, using immutable data has some performance costs. Even the clever data structures Clojure and Scala use may take up more memory than their mutable counterparts, and they perform somewhat worse. The benefits of immutable data, which greatly ease not only concurrent programming but also ease programming large systems in general, often outweigh the costs. However, sometimes you really do need that extra performance, usually in a tight loop in a part of the program that is frequently called.

Focused Mutability shows how to use mutable data in these situations by creating functions that take in some immutable data structures, operate on mutable data inside of the function, and then return another immutable data structure. This lets us get more performance without letting mutability muck up our programs, since we’re confining it inside a function, where nothing else can see it.

One consideration we need to make when using Focused Mutability is what the cost of translating a mutable data structure into an immutable one is. Clojure provides first-class support here with a feature called transients. Transients let us take an immutable data structure, convert it into a mutable one in constant time, and then convert it back into an immutable one when we’re done with it, also in constant time.

In Scala, it’s a bit trickier, since there’s no first-class support for something like Clojure’s transients. We have to use the mutable versions of Scala’s data structures and then convert them into immutable ones using conversion methods on the collections library. Thankfully, Scala can do this conversion quite efficiently.

Code Sample: Adding to Indexed Sequence

Let’s start off with a look at a very simple sample, adding a range of numbers to an indexed sequence. This isn’t a particularly useful thing to do in practice, but it’s a very simple example, which makes it easy to do some basic performance analysis.

For this example, we’ll compare the time it takes to add a million elements to a mutable indexed sequence and then translate it into an immutable one with the amount of time it takes to build up the immutable sequence directly. This involves some microbenchmarking, so we’ll do several trial runs of each test to try to spot outliers caused by garbage collection, caching issues, and so on.

This certainly isn’t a perfect way to perform a microbenchmark, but it’s good enough so that we can get a feel for which solutions are faster and by how much.

In Scala

In Scala, we’ll compare the results of adding elements to an immutable Vector directly to the results of adding them to a mutable ArrayBuffer and then converting it into an immutable Vector. In addition to our test functions, which add elements to a Vector and an ArrayBuffer, we’ll need a bit of infrastructure code to help out with timing and test runs.

Let’s take a look at the immutable piece first. The following code defines a function, testImmutable, which appends count elements to an immutable Vector and updates a reference to point at the new vector each time a new element is appended:

Now let’s take a look at testMutable, which is similar except that it appends elements to a mutable ArrayBuffer, which is a bit like a Java ArrayList. The code is here:

Now we just need a way of getting timing information from runs of our test functions. We’ll time runs by recording system time before the test run and after. Instead of embedding this in the test functions themselves, we’ll create a higher-order function that can do the timing, time, and another one, timeRuns, that will run multiple tests at a time. Here is the code for both:

With the pieces in place, we can run some tests. Let’s try five test runs with a count of one million against our immutable version:

As we can see, the times range from around 123 milliseconds to about 142 milliseconds. Now let’s give it a shot with our mutable version, which only converts to an immutable data structure when modifications are done:

Here, the times range from around 54 milliseconds to around 105 milliseconds. Comparing the shortest run from our immutable version, 123 milliseconds, with the shortest run from our mutable version, 54 milliseconds, yields about a 128 percent improvement. Comparing the longest runs, 142 milliseconds with 105 milliseconds, yields an improvement of about 35 percent.

While your mileage may vary somewhat depending on your machine, on your JVM version, on your garbage collection tuning, and so forth, this basic microbenchmark suggests that the mutable version is generally faster than the immutable one, as we’d expect.

In Clojure

Clojure has built-in support for Focused Mutability through a feature named transients. Transients allow us to magically transform an immutable data structure into a mutable one. To use it, the immutable data structure is passed into the transient! form. For example, this would get us a transient, mutable vector, (def t (transient [])).

As the name suggests, transients are supposed to be, well, transient, but in a very different way than the transient keyword in Java means. Transients in Clojure are transient in the sense that you use them briefly inside a function and then transform them back into an immutable data structure before passing them around.

Transients can be appended to with a special version of conj called conj!. Using an exclamation point for operations on mutable data is an old Lisp convention meant to convey that you’re about to do something exciting and dangerous!

Let’s take a look at our basic Focused Mutability example, which has been rewritten to use Clojure’s transients. First off, we need our mutable function. In Clojure, we’ll build up our sequence of numbers with a recursive function that passes a vector through the call chain and conjes a single number to the vector in each call. The code is here:

Our mutable version looks almost identical; the only difference is that we create a transient vector using transient to be modified internal to the function. Then we convert it back to an immutable data structure with persistent! when done, as the code shows:

Finally, we need a way to time our examples. Clojure has a built-in time function that’s much like the one we wrote for Scala, but we still need a way of running multiple trials in one shot. The somewhat cryptic-looking macro here fits the bill. If Lisp macros aren’t in in your bag of tricks yet, we discuss them in Pattern 21, ​Domain-Specific Language​.

Now we can put our Clojure solution through its paces. First, here’s the immutable version:

Next, the mutable one:

These times are fairly similar to the Scala times, which isn’t surprising since Scala’s immutable data structures and Clojure’s immutable data structures are based on the same set of techniques. Comparing the shortest and longest runs of both versions gives us a speedup of about 50 percent for the mutable version, which isn’t too shabby.

One other interesting thing to note about this example is that the two outliers, 300.29 ms for the immutable run and 196.601 ms for the mutable one, are both twice as slow as the fastest run for their respective solutions.

A bit of digging into these examples with a profiling tool reveals that the culprit here is indeed a major garbage collection that ran during those samples and not the others. The effects of garbage collection on this example might be reduced with tuning, but that, alas, would be a book in itself!

Code Sample: Event Stream Manipulation

Let’s take a look at an example with a bit more weight. Here, we’ll process a stream of events that represent purchases. Each event contains a store number, a customer number, and an item number. Our processing will be straightforward; we’ll organize the stream of events into a map keyed off of the store number so that we can sort purchases by store.

In addition to the processing code itself, we’ll need a simple way of generating test data. For that, we’ll use Pattern 18, ​Lazy Sequence​, to generate an infinitely long sequence of test purchases, from which we’ll take as many as we need. Let’s take a look!

In Scala

Our Scala solution starts with a Purchase case class to hold on to our purchases. We’ll also need a sequence of test purchases, as well as the immutable and mutable versions of our test functions. In both cases, we’ll go through our test purchases in a for comprehension, pull out the store number from the purchase, and add it to a list of other purchases from that store, which we’ll then put into a map keyed off of by store number.

For timing, we’ll reuse the same code from the above example. Let’s start with the Purchase class, a straightforward case class:

Generating our test data can be done with an infinitely long lazy sequence, from which we’ll take as many samples as we need. It’s okay if you don’t understand the details here; they can be found in Pattern 18, ​Lazy Sequence​. The upshot for our current example is that we can easily generate test data with infiniteTestPurchases, from which we can use take. Here’s the code:

If we wanted to take, say, five items from our infinite sequence, we do so with take, like this:

Now that we’ve got a way of generating test data, let’s put it to good use in our immutable solution, immutableSequenceEventProcessing. This function takes the number of test purchases, obtains the test purchases from our infinite sequence of test data, and adds them to a map indexed by store, as described earlier.

To add a new purchase to the map, we pull the store number out of the purchase and attempt to get any existing purchases for that store from the map. If they exist, we add the new purchase to the existing list and create a new map with the updated key. The code to do so is here:

Our mutable version is quite similar to the immutable version, except that we modify a mutable map and then turn it into an immutable one when done, as this code shows:

So how do these two solutions perform? Let’s take a look by running it over 500,000 samples, starting with the immutable version first:

And now here’s the mutable one:

As we can see, the mutable version is only a tiny bit faster. A bit of profiling reveals that this is largely because much of the time in the example was spent generating test data, and not manipulating the map.

If we were reading the events off the filesystem or over the network, this overhead would be even greater, and the difference between the two solutions even smaller! On the other hand, even a tiny amount of time shaved off of each event processing may end up mattering if the data set is big enough.

In Clojure

Our Clojure solution is fairly similar to the Scala one. Just as in Scala, we’ll use Pattern 18, ​Lazy Sequence​, to generate an infinite sequence of test purchases from which we’ll take a finite number. We’ll examine two implementations of our test functions. The first uses a normal, immutable map, and the second a mutable, transient one.

Let’s get started with a look at the code that lets us generate test data. We can use a function named repeatedly, which, as the name suggests, calls the function multiple times and uses the results to create a lazy sequence. Outside of that, we just need a function to create the test purchases themselves. Here’s the code for both:

Now we need our test functions. We’ll use reduce to turn a sequence of purchases into a map indexed by store number. Just as in the Scala example, we’ll use take to take a finite number of test purchases from our infinite sequence of them. Then we’ll reduce over that sequence, building up our map of purchases indexed by store number.

As before, we need to handle the case when we first see the store number, which we can do by passing in a default empty list to get. The code is here:

Since Clojure has handy-dandy transients, the mutable solution looks very similar, save that we need to transform our map to and from a transient and that we need to use assoc! to add to it, as the code shows:

Now let’s give it a whirl, starting with the mutable version:

Now on to the immutable one:

As we can see, the differences are fairly minimal, but the mutable version is a bit faster.

Discussion

Focused Mutability is an optimization pattern. It’s the sort of thing that the old advice to avoid premature optimization is all about. As we’ve seen from this chapter, Scala and Clojure’s immutable data structures perform very well—not much worse than their mutable counterparts! If you’re modifying several immutable data structures in one go and if you’re doing it for large amounts of data, you’re likely to see a significant improvement. However, immutable data structures should be the default—they’re usually plenty fast.

Before using Focused Mutability or any small-scale performance optimization, it’s a good idea to profile your application and make sure you’re optimizing in the right place; otherwise, you might find that you’re spending time optimizing a section of code that is rarely called, which will have little effect on the overall performance of the program.