Persistence and Transience

02 Jan 2014

In an earlier post I explored the reasons for having immutable data structures, now I want to dive into useful implementations of immutable structures as I see them.

The major advantage that immutable data gives you is the ability to reason about public APIs. When you know that because your data is immutable, you'll never have to worry about it changing in some unauthorized way, it is much easier to track the flow of programs locally.

The drawback that comes with immutability is the problem of performance. Using only immutable data can use many times more resources in certain cases. Many will argue that the thread-safe nature of immutable data will make up for this deficit, but the fact remains that the data will often be much slower to work with.

One way that we can help solve the performance problem is to limit immutability in some way. One way this can be done is using a logging system that will allow anyone to 'roll back' an object to a previous state, but it often has such bad performance when this is done that it's virtually unusable. Rather than take that approach, I believe that we can do better by allowing unrestricted mutation to an object up until it is frozen for use in an API that requires immutability. Below I've created a sample binary tree (without any balancing) that uses this strategy.

public final class BinaryTree<T extends Comparable<T>> {
    private boolean       mutable = true;
    private int           size    = -1;
    private T             val;
    private BinaryTree<T> left;
    private BinaryTree<T> right;

    private BinaryTree(
            T val,
            BinaryTree<T> left,
            BinaryTree<T> right) {
        if (val == null && (left != null || right != null))
            throw new AssertionError("Empty node should not have children");

        this.val   = val;
        this.left  = left;
        this.right = right;
    }

    public BinaryTree() {
        this(null, null, null);
    }

    public BinaryTree(T val) {
        this(val, null, null);
    }

    /**
     * Computes the current size of the tree with an optimization if the tree
     * is frozen, the size is cached for all future calls.
     */
    public int size() {
        if (!mutable && size >= 0)
            return size;

        int size = (left  == null ? 0 : left.size())
                 + (right == null ? 0 : right.size())
                 + (val   == null ? 0 : 1);

        if (!mutable)
            this.size = size;

        return size;
    }

    /**
     * Freezes this object. All future mutating calls will result in a new
     * object being created.
     */
    public BinaryTree<T> freeze() {
        mutable = false;

        if (left != null && left.mutable)
            left.freeze();

        if (right != null && right.mutable)
            right.freeze();

        return this;
    }

    /**
     * Creates a new mutable clone of the tree.
     */
    public BinaryTree<T> thaw() {
        return new BinaryTree<T>(val, left, right);
    }

    /**
     * Inserts the given value into the tree. If the tree is mutable, all
     * possible changes are done in-place, otherwise a new tree is constructed.
     *
     * @throws IllegalArgumentException if val is null
     */
    public BinaryTree<T> insert(T val) {
        if (val == null)
            throw new IllegalArgumentException("val cannot be null");

        if (this.val == null) {
            if (mutable) {
                this.val = val;
            } else {
                return new BinaryTree<T>(val);
            }
        } else {
            int cmp             = val.compareTo(this.val);
            BinaryTree<T> left  = this.left;
            BinaryTree<T> right = this.right;

            if (cmp < 0) {
                if (left == null)
                    left = new BinaryTree<T>(val);
                else
                    left = left.insert(val);
            } else {
                if (right == null)
                    right = new BinaryTree<T>(val);
                else
                    right = right.insert(val);
            }

            if (!mutable) {
                return new BinaryTree<T>(val, left, right);
            }

            this.left = left;
            this.right = right;
        }

        return this;
    }
}

The immediate reaction I expect is something along the lines of "Ugh, that's horrible". That's to be expected, I'm hoping on coming up with a language where we can avoid so much typing to achieve what I believe is a good thing.