A Java long read : Is functional programming worth it?
This blog post is extracted from a talk I gave at St. Petersburg’s excellent Joker Conf in 2018.
The goal of this post is to examine whether the cost-benefit trade-off stacks up for functional programming in Java across 3 dimensions
Correctness
Performance
& Complexity
Correctness
An informal definition of correctness is :
an algorithm is correct if it is error free.
In Java we could define hierarchy of errors as something like
Compile time errors : errors the Java compiler catches and alerts us about.
Runtime errors : Runtime exceptions and errors the Java runtime (hopefully) alerts us about.
Logic errors : potentially more insidious errors that provide no explicit feedback that something has gone wrong.
As we move through this hierarchy of errors, the maximum potential cost of an error explodes upwards at each stage. If I introduce a compile time error, I really should only inconvenience myself. With proper processes in place, I will find and fix the problem on my development branch before it is committed to master.
If I cause a Runtime error to appear on our codebase, if we have good unit tests, I may be lucky enough to be alerted to the problem before it gets merged into master. If we are not so well prepared (and lucky!) we may instead get a call late at night when the effected code path is triggered and our monitoring and alerting systems kick in and do their jobs.
With logic errors the situation is worse again, the compiler won’t alert us if we have misunderstood a requirement and no exceptions may be thrown at runtime. Our software could run, incorrectly, for years, giving or storing incorrect data costing our employers or their customers money.
Functional programming (in Java)
As we shall see functional programming imposes a cost (often at the nexus of a performance / complexity trade off), and the main benefit of FP in Java is the ability to improve application correctness by pushing most (if not all) errors that may occur in the Runtime Error Tier down a level to the Compile time Error tier where they are easy to spot and cheap to fix.
Let’s examine functional and imperative Collections
And discover what the trade offs are between application correctness, performance and complexity.
Traditional mutable Collections
The JDK Collections are standard imperative collections that are (or can be) mutated in place. It’s generally easier to implement Mutable Collections (e.g. see the stub for a mutable ArrayList with set method below.
In addition to being straightforward to implement, they also set the gold standard for performance. While it’s possible for functional data structures to approach the performance of imperative ones, this often comes at a cost of increased complexity of implementation.
If we were to summarize the characteristics of mutable Collections in terms of performance and complexity it would look something like this :-
So far — so good! But… You can probably guess that they are going to fall down in terms of application correctness (or otherwise there wouldn’t be much point in this blog post!). Let’s take a look at how these are often used in practice..
This type of method signature is very common in Java applications. It consists of
void return type
mutable input parameters
The void return type indicates that this method is performing a side-effect, hopefully this is limited to some I/O operation, but as we are also providing mutable input parameters we can’t be sure that the scope of this method is limited to I/O. (If we allow the mutation of global state held in static variables we can be even less confident about the nature of this method).
In terms of our List of user ids, because it is mutable we can never really be sure it is unchanged after passing it as a method parameter. In Java it is not uncommon (unfortunately) for methods with signatures like the one above to mutate it’s input parameter 🤮.
With the implementation above we see an I/O operation and a call to a method that in all likelihood has a similar method signature. If we want to be sure that our input parameter hasn’t changed, we’d need to check that method too. It really is mutable turtles all the way down🐢!
We could take a risk and write a method that makes use of our List without making a costly defensive copy first. In the listAndPersistUsers method below we extract the active user ids from the current context and persist them before returning them to the caller for further processing.
But, can we rely on this?
Callers of listAndPersistUsers have to assume that none of the child calls recieving the mutable list of active users change it in any way.
Can we rely on this now and in the future?
At some point in the future we may decide to always persist a Special Admin user, by adding it to our mutable list we also return it to clients of listAndPersistUsers. If this causes problems for them, there is nothing the type system and the compiler can do to help us here.
If we have introduced a bug we are relying on having good unit tests to catch it (in a piece of code that is also performing I/O, so expect the unit tests to be gnarly knot of mocking infrastructure and occasional asserts).
With some additional insight, we can revisit our classification of mutable datastructures. While they are often the easiest to implement, they push uncertainty and complexity down into our application code! Perhaps we should split our complexity classification in two?
complexity of implementation — which remains simple
complexity of client code— which as we have seen can start to become difficult to reason about.
Are JDK Unmodifiable datastructures any better?
These are collections that expose an unmodifiable view into a mutable collection, and if anything, they are worse! Let’s start by looking at the characteristics they share with mutable collections :
We’ve already broken out the performance classification into two aspects (only one of which will be good like mutable collections)
read (or access) performance : remains identical (almost) to mutable collections
write (append / update) performance : well, let’s see
It’s pretty easy to create an unmodifiable collection, and we can modify our current code to pass one in to saveAndLogActiveUsers
But this has no compile time impact on what code is permissable in saveAndLogActiveUsers (but it does have a runtime one).
We can still add our Special Admin, to a supposedly immutable collection and our application will still compile! When we run this code however..
We get an UnsupportedOperationException, and we’ve swapped an insidious logic error for a slightly less insidious runtime one. Perhaps, we should be thankful for small mercies?, But if enough of these sneak into application the probability of us being rudely awakened out-of-hours by our boss with a production issue rapidly approaches 1!
Not only does this introduce the possibility of a new set of exceptions being thrown, the fact that these immutable views also masquerade as mutable ones (and are accepted as input into methods that take mutable collections) makes our code even harder to reason about than it was before.
In order to ensure the correct behaviour of our application once we have introduce unmodidfiable views, we should make a defensive copy of our collection before making changes to it.
Time complexity
But what will this do to performance?
Because, in order to change an unmodifiable view we need to perform a copy-on-write operation performance really suffers as Collection sizes increase. What this means is — to make any change we must make a defensive copy of the existing view into a new mutable collection, make the change and create a new replacement unmodiable view. The performance of modification operations scale linearly with the size of the collection! By contrast changing a single entry in an ArrayList takes the same amount of time regardless of its size!
That leaves us with a set of characteristics that looks like this -
But there is more — and it gets worse! Unmodifiable Views are just wrappers over independently modifiable mutable datastructures. As the underlying datasstructure can still change we can’t rely on Unmodifiable Views to keep our data (and it’s meaning) in tact! Let’s take a look at an example :
We could modify listAndPersistUsers to make the call to saveAndLogActiveUsers on a different thread.
Although we are passing in an Unmodifiable View of the currently active users into saveAndLogActiveUsers, this is not actually immutable.
The mutable list of currently active users still exists, and in the code above, we retain and return a reference to it
If some client code were to change the returned list this would result in a race condition — saveAndLogActiveUsers expects the full list of active users to be past to it, and despite the fact that we pass a List to it we may feel is immutable — it is still possible to change it. Above we remove the first active user from the List and as the Unmodifiable View is a proxy into the List it is gone from there too!
Unmodifiable Collections in the JDK really are a very poor way to implement immutability in your applications introducing needless additional complexity and performance cost. There must be better alternatives..
Immutable Collections (copy-on-write a la Guava)
We could define immutable collections as simply collections that can’t be changed. This would include two distinct types of immutability
- Datastructures with copy-on-write semantics — that copy the entire datastructure when making a change
- So-called persistent data structures that utilize shared portions of memory to make updates more efficient.
#1 above is by far the most common type of immutable collection in Java, largely thanks to the immense popularity of Google’s Guava library.
The chief benefit of Immutable copy-on-write collections that continue to implement the mutable JDK collection interfaces over the awful Unmodifiable Views is that they remove the loose reference to the underlying mutable collection. This leaves their core characteristics as looking something like this :
And we can see this in action if we plug Guava into our listAndPersistUsers method :
Because ImmutableList implements List, this is all we need do. Of course if saveAndLogActiveUsers still adds the Special Admin directly to the input parameter we will be in trouble. Because Guava’s ImmutableList implements List we can still attempt to add elements to an immutable Collection and the compiler will not stop us.
Running this code will still result in a nasty Exception.
It would be nice if the compiler could help us out here, and unlike with Unmodifiable Collections Guava does provide us with a specific type ImmutableList.
When we replace the input parameter to saveAndLogActiveUsers the buggy code that attempts to add a new element to that code still compiles! (Albeit with a warning that add has been deprecated on ImmutableList — again we should probably be thankful for small mercies). Running this code will result in the same Exception as before.
We can fix this error (when we are lucky enough to spot it) via a defensive copy-on-write operation. Guava provides us with a nice fluent interface to do this, but the performance impact is the same :
The cost of this operation is going to scale linearly with the size of the collection.
Immutable and Unmodifiable : the risks
We could summarize the downsides of JDK Unmodifiable Views and Guava style Immutable Collections as follows
Reduced compile time safety due to
- Increased complexity due to the availability of illegal operations on the API
- Increased complexity due to the ability to masquerade as a completely different and incompatible type (mutable v immutable)
Significantly Reduced runtime performance due to
- Poor scaling characteristics of modification operations (add, delete, set)
To chart away out of this morass, to unlock the chief benefits of typed functional programming in terms of enhanced compile time safety and roughly comparable performance to imperative & mutable alternatives we need to turn to Chris Okasaki and his seminal paper on Purely Functional Data Structures.
Persistent Collections
Persistent collections are immutable collections that leveraged shared memory a la Chris Okasaki to enable more efficient modification operations ideally approaching the scaling characteristics of their imperative analogues.
Bitmapped Vector Trie an efficient Persistent ArrayList
For persistent ArrayList type structures the Bitmapped Vector Trie, pioneered by Rich Hickey in Clojure offers reasonably close performance to it’s imperative cousin.
At it’s core the Bitmapped Vector Trie is an array of arrays, indexed by groups of bits in a single bitmap index.
Daniel Spiewak walks through one implementation approach in his rather excellent talk “Extreme Cleverness: Functional Data Structures in Scala”, and this was the approach we took when implementing a functional ArrayList (or Vector) in the functional library for Java — Cyclops.
There are some interesting features of this particular approach which I will attempt to cover here. First the Array of Arrays used is sized to the size of the Vector. If the Vector has a less than 32 elements then a 1D “Array-of-arrays” is used, I’ve put Array-of-arrays in quotes as a 1D Array-of-arrays is best implemented as a single Array. A small persistent Vector implemented in this way will have identical look up charcteristics as a standard mutable array (the implementations being virtually identical). The larger the array becomes (as per Guava style copy-on-write collections and JDK Unmodifiable views) the slower modification operations become. But we cap the max array size at 32 elements. This means our most expensive individual copy operation copies 32 entries. Once our 1D array exceeds 32 elements we switch to a 2D array structure. And we’ll need to figure out way to locate each element within that structure.
Indexing a Bitmapped Vector Trie
For a single Array of 32 elements we can use an int to capture the index, and in practice only the first 5 bits are needed.
The index for a 1D Bitmapped Vector Trie looks just like it would for a stanadard Java Array or ArrayList.
But once we move on to a 2D array, we need an index into the root level (or parent array), to extract the active node (or child array) that contains the data we need.
Let’s visualize a numeric sequence from 0 stored in a 2D Array of Arrays sized at 32 elements.
In the truncated diagram above the top level Array contains other Arrays, the child Arrays contain Integers. At position A in the root we have a child array containing 0–31, at position 2 we have a child array containing 32–63 (and so on).
To access any element we need two numbers — the index in the root array, and the index in the child array. As each array as a max size of 32 elements we can store each index in 5 bits, or both together in 10 bits of a single integer. To extract each index we first shift by 5 (if needed) and then mask by anding with 31 (if needed). As our list get bigger we will scale from 2D to 3D, from 3D to 4D and so on.
Performance
Because we have to walk the multi-dimensional array structure retrieval and modification times scale logarthimically with the size of the collection. For small collections, stored in a standard array read performance should even be as fast as for JDK mutable collections! For larger collections modifications should perform orders of magnitude better than for JDK Unmodifiable Views and Guava Immutable collections!
If we run a benchmark for get operations on small (typical most of the time) lists we can see performance is pretty much identical across all 3 types.
In fact we won’t see differences until the sizes are a lot larger. By the time we are accessing Strings from a List with 10k elements the overhead of the indexing and nested array lookup becomes apparent (note these times are in micro-seconds)
But as expected the overhead of mutating large copy-on-write Immutable Collections is extortionate : (note these times are in milli-seconds!!)
Appending to Persistent Vector performs better on average then even a mutable ArrayList because the occasional overhead of having to copy a full (and large) array into an even larger one is avoided entirely.
To put things in perspective the access operation on a very large Persistent Vector is much faster than the relatively performant append operation on a similarly large Vector.
Unlike copy-on-write Immutable datastructures, Persistent shared-memory datastructures in the purely functional style have great all round performance characteristics.
Correctness
Now that we have found away to build immutable datastructures with sound performance, it would be good to ensure that we also cleanly and completely solve the real challenges with imperative mutable datastructures. We should aim to make our code easier to reason about. The core design principal to follow here is to make illegal states unrepresentable in our code.
If we bought a toy for a child that broke when we pulled it’s levers or pressed it’s buttons, we’d consider it exceptionally bad design. We would probably think twice about purchasing from the company again. But, we make heavy use development kits and libraries that will blow up our apps when we call public methods on their APIs. We make heavy use of these libraries in the code that powers our financial markets, our civil infrastructure, our enterprise software, our consumer gadgets, our self-driving cars and our healthcare projects. But it really shouldn’t be this way.
The APIs of our libraries should guide is as developers along the right path and not into states from which the only way out is to throw an Exception. For Immutable Collections this means they can’t implement or extend java.util.Collection. Why not?
If our Persistent Vector implements List we would be forced to implement methods such as add. Look at the method signature — the return type is a boolean, this forces us to make no change or mutate in place. We can either fail silently, and implement an alternative method to add that returns a new Vector — or follow the direction of the spec and throw that nasty UnsupportedOperationException : a Hobson’s choice. Better to start from scratch and create a new API which prevents developers from ever getting the Vector into an exceptional state!
Instead in Cyclops we created a ‘plus’ method instead, this returns a new Vector with the new element efficiently added.
There is no legacy add method. It is just not possible to write code that will cause it to throw an Exception at runtime.
And — we can always rely on listAndPersistUsers returning only (and all of) the currently active users no matter how deep we pass our Vector to other methods before returning it. Our code becomes much easier to reason about.
Not just Collections
If we make all our datastructures efficiently immutable with safe, with helpful and guiding APIs our application code will become much more easy to reason about and much less likely to fall prey to runtime Exceptions.
Within something as simple as a List (or Vector) there are many places where we would traditionally default to throwing Exceptions — when attempting to retrieve an element at an out-of-bounds index for example.
Running this traditional imperative Java code results in another nasty runtime Exception
A better an alternative to throwing an IndexOutOfBoundsException, as shown in the example below is to return an Optional or Option type.
But why not Optional?
Although it is inspired by functional ideas, the JDK’s Optional type does not adhere to the pinciple of making illegal states unrepresentable :-
Running this code also results in a nasty runtime error
So for Cyclops we had to define our own more principled implementation
The key goal is to switch our application call-stack from a messy hierarchy of mutable turtles all the way down, to a safe principled stack of immutable datastructures — simplifying our code.
Because life is complicated enough
Performant, safe immutable datastructures often don’t come for free. The nested multi-dimensional arrays of a Persistent Vector certainly gave a more complex view in the debugger than traditional simple mutable ArrayLists.
The overall characteristics for Persistent Collections looks like this :- shared memory implementation leading to decent performance, and principled implementations will simplify client and help drive application correctness.
Is functional programming in Java worth it?
By adopting functional techniques and principles you introduce a learning curve for your team (e.g. See the standardized ladder of Functional Programming - http://lambdaconf.us/downloads/documents/lambdaconf_slfp.pdf). Although you don’t have to climb high to reap significant benefits in terms of improvements in application correctness and the ability to simplify your code. Immutable datastructures and pure functions are enough to get you started. Just be sure to choose wisely and select those that will help ensure your application is performant and correct!
