On a Lesson Learned from Immutability and Cloning

I was introduced to the concepts behind immutability when I was building with Redux in 2016, back when my understanding of immutability was simply “unchangeable.” But unchangeable, how? And for what significance?

I understood then that an immutable store, for example, would minimize any unintended consequences from state-sharing. And it’s true. Immutability could help in that regard.

Let’s say that there is some data that is shared by two different areas of a system. Both areas read from this state and do what they need to do with it. But what if one area accidentally splices an array within this shared state instead of slicing it before the other area gets to read from it. Shit. The shared state has just been mutated. Now that other area is going to be reading inaccurate data. Now whatever actions and operations it was going to perform are also going to be inaccurate. These are the unintended consequences that can happen in a system that mutates state.

That was largely my understanding of the benefits of immutability. I figured: Okay, state needs to be immutable so that when this button is clicked, the text in this div isn’t unintendedly altered or the items rendered from this array aren’t erroneously changed.

But, oh, I’d come to find that there is an additional benefit of immutability that I totally was unaware of at that time, a benefit that helped deepen my understanding of the concept.

This benefit of immutability was discovered while working on a distributed system written in C#. The discovery arose from a problem that confounded us: why in the **** are these slowdowns happening in one of the nodes of the system and what’s causing them?

A particular node in the system would run smoothly when we started it up, but then it would slow down. And slow down even more. And even more the longer it ran. This would absolutely cripple this node. And we couldn’t have that. With a figurative magnifying glass in hand, we went out sleuthing to find what in the **** was causing this hindrance.

We searched and tested and continually narrowed it down. We placed stopwatches here and there, and crossed out all the areas that were performing optimally. Guided by the .NET Stopwatch class, we followed the slowdown. Until we found it. In a clone method.

This system was an event-sourced system, so state was built from a sequence of processed events. To get the state of an event-sourced system at any point in time, just play – or replay – events until the desired point, and you’ll get the exact state of the system at that moment. Think of Time Travel Debugging in Redux as an example.

Anyway, this node in the system would process events. Hundreds of thousands, sometimes up to a few million, of events at times. With each event, the system would first load the state from memory, or re-create it from scratch, depending on the scenario. Then, the state would be cloned and the cloned state would have the event that is currently being processed applied to it. Business would then be done on both the original and cloned state and so on with each subsequent event.

So, what was the issue? What during the cloning was causing the slowdown?

Well, the state that was being cloned wasn’t tiny or uncomplicated at all. The state was a mean, meaty complicated nest of data. There were layers. And more layers. So, cloning the entire state would mean cloning each and every layer all the way down.

And this was where the slowdown stemmed from because we treated the entire state object as a mutable object, and cloning it would literally involve making new copies of every property.

Yeah, cloning the entire state would cause a cascade of new objects to be created. And all the dictionaries, lists, hash sets, arrays and other data structures, too. Many, many layers deep.

So, that was it! All the mutable objects and data structures that we were recreating while cloning. That was causing the ever-increasing slowdown as all the events were being processed.

So what was our solution?

Immutability.

Remember that first benefit of immutability I briefly touched on earlier? That an immutable store in Redux minimizes any unintended consequences that could arise from mutation because, well, the state can’t be mutated. Let’s dissect that.

The Redux reducers are pure functions. And one of the traits of a pure function is that it doesn’t mutate its input. So, the state that would be passed to the reducer would be cloned using the Object.assign method, if the input is an object. The cloned state would then be mutated with whatever updates, and this cloned state would be passed to the store, replacing the existing state, all the while the original state is left untouched, unmutated at its memory address somewhere.

Note something here: it isn’t so much that the Redux store is immutable, that it is incapable of being changed. The Redux store, at least from when I was using it, is a regular Javascript object, which can be mutated. The immutability of the store stems from how the store is interacted with: the previous state is cloned, the cloned copy is mutated, and the store is replaced with the cloned, updated state. Mutation is still going on, but not to the original state.

This is key and what drives the benefit of immutability that I bring up: that there are two objects at play here: an unmutated object and its cloned mutation. They are two totally distinct entities. They can have the same values, yes, right after the original is cloned, but they are not the same object; they are just two objects with the same values.

So why is this important? How did immutability improve cloning in our system?

In short, the behemoth of a state object didn’t need to be cloned – at least, not in its entirety, if it was fully immutable.

Rather, when cloning the state, the clone could be built by swiftly pointing to the existing properties of the original instead of recreating exact copies of the properties. This would result in two different state objects with the same values because the properties on both objects would be pointing to the same objects in memory.

If the cloned state object needed to be mutated? Well, only the relevant property or properties would be cloned, and the cloned properties would be mutated. This preserves the original state object, as all their properties are still pointing to the same, untouched objects. And the mutated state object now has properties that are pointing to different objects.

So, cloning sped up significantly. Which gained an extra boost in speed from reference comparisons.

The final task within the clone method was to validate the values of the clone. Previously, we had to be certain that each of the values were the exact same as the original and that there was no accidental tampering in the cloning process because, you know, everything was mutable. This would involve a ton of value comparisons. And if one value was off, an exception would be thrown; the cloning would have failed.

But with immutability, the task of validating a clone involved just making reference comparisons of the objects and data structures. Why? Because if they’re the same object, they have the same values. And I’ve they’re fully immutable, the values won’t – or, at least, shouldn’t – change because new objects are created for mutations. No more having to make tons of value comparisons; parity between the original state object and its clone could be verified by checking if all the properties point to the same objects.

So, with having to rebuild the entire state object and verifying each value within it was the same when cloning, it’s understandable now, I hope, why the slowdowns were happening in this node of the system. It all came to a slow, crippled crawl because of cloning mutable objects.

Oh, the decisions we make – but oh, the lessons we can learn.

To provide some evidence to these benefits of immutability, following this contains a test that I wrote. The test generates an object and clones its, looping through this procedure up to five million times. This is done with immutable and mutable data structures.

Here is a screenshot of the terminal with the runtimes from a test, which will show that mutable objects take around three times longer to clone than the immutable objects. Now, just imagine all the speed we gained in our system when using this technique on massive state objects.

And here’s the C#:

using System;  
using System.Collections.Generic;  
using System.Collections.Immutable;  
using System.Diagnostics;  
using System.Linq;

namespace ImmutableVersusMutableTest  
{
    public class ImmutableVersusMutable
    {
        static void Main(string[] args)
        {
            string totalResults = "";

            for (var i = 1; i <= 5; i++)
            {
                Stopwatch stopwatchForMutable = new Stopwatch();
                Stopwatch stopwatchForImmutable = new Stopwatch();

                var l = 0;

                stopwatchForMutable.Start();

                for (; l < i * 1000000; l++)
                {
                    var newMutable = new Mutable(123455, 73734, "test string", "test string two", true, false);
                    var clone = newMutable.Clone();
                }

                stopwatchForMutable.Stop();

                //Reset the iterator
                l = 0;

                stopwatchForImmutable.Start();

                for (; l < i * 1000000; l++)
                {
                    var newImmutable = new Immutable(123455, 73734, "test string", "test string two", true, false);
                    var clone = newImmutable.Clone();
                }

                stopwatchForImmutable.Stop();

                TimeSpan timespanForMutable = stopwatchForMutable.Elapsed;
                TimeSpan timespanForImmutable = stopwatchForImmutable.Elapsed;


                var mutableMillionResults = new Result($"RunTime of Mutable with {i} Million: ", ReturnElapsedTime(timespanForMutable));
                var immutableMillionResults = new Result($"RunTime of Immutable with {i} Million: ", ReturnElapsedTime(timespanForImmutable));

                totalResults += mutableMillionResults.ResultString + immutableMillionResults.ResultString;
            }

            Console.WriteLine(totalResults);
        }

        static string ReturnElapsedTime(TimeSpan tp)
        {
            return String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
                tp.Hours, tp.Minutes, tp.Seconds,
                tp.Milliseconds / 10);
        }

    }

    public class Result
    {
        public Result(string description, string elapsedTime)
        {
            this.ResultString = $"\n {description}: {elapsedTime}";
        }

        public string ResultString { get; private set; }
    }

    public class Mutable
    {

        public Mutable(int numberOne, int numberTwo, string nameOne, string nameTwo, bool booleanOne, bool booleanTwo)
        {


            Numbers = new Dictionary<int, int> { { numberOne, numberOne }, { numberTwo, numberTwo } };
            Names = new Dictionary<string, string> { { nameOne, nameOne }, { nameTwo, nameTwo } };
            Booleans = new Dictionary<int, bool> { { 0, booleanOne }, { 1, booleanTwo } };
        }

        private Mutable()
        {

        }

        public Mutable Clone()
        {
            Mutable clone = new Mutable();
            clone.Numbers = this.Numbers.ToDictionary(k => k.Key, v => v.Value);
            clone.Names = this.Names.ToDictionary(k => k.Key, v => v.Value);
            clone.Booleans = this.Booleans.ToDictionary(k => k.Key, v => v.Value);

            if (!this.ValueEquals(clone))
            {
                throw new Exception("Cloning mutable failed");
            }

            return clone;
        }

        public bool ValueEquals(Mutable other)
        {
            return this.Numbers.SequenceEqual(other.Numbers)
                    && this.Names.SequenceEqual(other.Names)
                    && this.Booleans.SequenceEqual(other.Booleans)
                    ;
        }

        public Dictionary<int, int> Numbers { get; private set; }
        public Dictionary<string, string> Names { get; private set; }
        public Dictionary<int, bool> Booleans { get; private set; }
    }

    public class Immutable
    {
        public Immutable(int numberOne, int numberTwo, string nameOne, string nameTwo, bool booleanOne, bool booleanTwo)
        {

            this.Numbers = new Dictionary<int, int> { { numberOne, numberOne }, { numberTwo, numberTwo } }.ToImmutableDictionary();
            this.Names = new Dictionary<string, string> { { nameOne, nameOne }, { nameTwo, nameTwo } }.ToImmutableDictionary();
            this.Booleans = new Dictionary<int, bool> { { 0, booleanOne }, { 1, booleanTwo } }.ToImmutableDictionary();
        }

        private Immutable()
        {

        }

        public Immutable Clone()
        {
            Immutable clone = new Immutable();
            clone.Numbers = this.Numbers;
            clone.Names = this.Names;
            clone.Booleans = this.Booleans;

            if (!this.ValueEquals(clone))
            {
                throw new Exception("Cloning immutable failed");
            }


            return clone;
        }

        public bool ValueEquals(Immutable other)
        {
            return this.Numbers == other.Numbers
                    && this.Names == other.Names
                    && this.Booleans == other.Booleans
                    ;
        }

        public ImmutableDictionary<int, int> Numbers { get; private set; }
        public ImmutableDictionary<string, string> Names { get; private set; }
        public ImmutableDictionary<int, bool> Booleans { get; private set; }
    }
}
comments powered by Disqus