Now that we’ve spent a book’s worth of material learning the why and how of Clojure, it’s high time we turned our attention to the subject of performance. There’s a meme in programming that can be summarized as follows: make it work first, then make it fast. Throughout this book, we’ve taught you the ways that Clojure allows you to “make it work,” and now we’re going to tell how to make it fast.
In many cases, Clojure’s compiler will be able to highly optimize idiomatic Clojure source code. But there are times when the form of your functions, especially in interoperability scenarios, will prove to be ambiguous or even outright counter to compiler optimizations. Therefore, we’ll lead you through optimization techniques such as type hints, transients, chunked sequences, memoization, and coercion. Using some combination of these techniques will help you approach, and sometimes exceed, the performance of Java itself.
The most obvious place to start, and the one you’re most likely encounter, is type hinting—so this is where we’ll begin.
The path of least resistance in Clojure often produces the fastest and most efficient compiled code, but not always. The beauty of Clojure is that this path of least resistance allows simple techniques for gaining speed via type hints. The first thing to know about type hints is that they’re used to indicate that an object is an instance of some class—never a primitive.
Write your code so that it’s first and foremost correct; then add type-hint adornment to gain speed. Don’t trade the efficiency of the program for the efficiency of the programmer.
There are epic debates about the virtues of static versus dynamic type systems; we won’t engage in those arguments here. But there are a few advantages to a dynamic type system like Clojure’s that also allows type hinting to occur after the bulk of development. One such advantage is that in a static type system, the cost of changing argument lists is extended to all of the callers, whereas in Clojure the cost is deferred until adornment time or even outright avoided.[1] This scenario isn’t limited to the case of function arguments in Clojure nor to statically typed languages, but instead to any typed element. This dynamic type system provides an agile experience in general to Clojure, which can later be optimized when there’s a need.
1 Aside from the case where type hints don’t require client changes, the use of keyword arguments as seen in section 7.1 can help to localize additional function requirements to only the callers needing them.
If you recall from section 10.3, we created a function asum-sq that took an array of floats and performed a sum of squares on its contents. Unfortunately, asum-sq wasn’t as fast as it could’ve been. We can illuminate the cause of its inefficiency using a REPL flag named *warn-on-reflection*, which by default is set to false:
(set! *warn-on-reflection* true) ;=> true
What this seemingly innocuous statement does is to signal to the REPL to report when the compiler encounters a condition where it can’t infer the type of an object and must use reflection to garner it at runtime. You’ll see a reflection warning by entering asum-sq into the REPL:
(defn asum-sq [xs]
(let [dbl (amap xs i ret
(* (aget xs i)
(aget xs i)))]
(areduce dbl i ret 0
(+ ret (aget dbl i)))))
; Reflection warning - call to aclone can't be resolved.
; ...
Though not terribly informative in and of itself, the fact that a reflection warning occurs is portentous. Running the call to asum-sq in a tight loop verifies that something is amiss:
(time (dotimes [_ 10000] (asum-sq (float-array [1 2 3 4 5])))) ; "Elapsed time: 410.539 msecs" ;=> nil
Though the reflection warning didn’t point to the precise inefficiency, you can infer where it could be given that Clojure deals with the java.lang.Object class across function boundaries. Therefore, you can assume that the problem lies in the argument xs coming into the function as something unexpected. Adding two type hints to xs and dbl (because it’s built from xs) might do the trick:
(defn asum-sq [ ^floats xs] (let [^floats dbl (amap xs i ret ...
Rerunning the tight loop verifies that the assumption was correct:
(time (dotimes [_ 10000] (asum-sq (float-array [1 2 3 4 5])))) ; "Elapsed time: 17.087 msecs" ;=> nil
This is a dramatic increase in speed using a simple type hint that casts the incoming array xs to one containing primitive floats. The whole range of array type hints is shown next:
The problems might still not be solved, especially if you want to do something with the return value of asum-sq, as shown:
(.intValue (asum-sq (float-array [1 2 3 4 5]))) ; Reflection warning, reference to field intValue can't be resolved. ;=> 55
This is because the compiler can’t garner the type of the return value and must therefore use reflection to do so. By hinting the return type of asum-sq, the problem goes away:
(defn ^Float asum-sq [ ^floats xs] ... (.intValue (asum-sq (float-array [1 2 3 4 5]))) ;=> 55
With minor decoration on the asum-sq function, we’ve managed to increase its speed as well as potentially increasing the speed of expressions downstream.
In addition to allowing for the hinting of function arguments and return values, you can also hint arbitrary objects. If you didn’t have control over the source to asum-sq, then these reflection problem would be insurmountable when executing (.intValue (asum-sq (float-array [1 2 3 4 5]))). But you can instead hint at the point of usage and gain the same advantage as if asum-sq had been hinted all along:
(.intValue ^Float (asum-sq (float-array [1 2 3 4 5]))) ;=> 55
All isn’t lost when you don’t own a piece of code causing performance problems, because Clojure is flexible in the placement of type hints.
We’ve harped on you for this entire book about the virtues of persistent data structures and how wonderful they are. In this section, we’ll present an optimization technique provided by Clojure called transients, which offer a mutable view of a collection. It seems like blasphemy, but we assure you there’s a good reason for their existence, which we’ll discuss currently.
The design of Clojure is such that it presumes that the JVM is extremely efficient at garbage collection of ephemeral (or short-lived) objects, and in fact it is. But as you can imagine based on what you’ve learned so far, Clojure does create a lot of young objects that are never again accessed, shown (in spirit) here:
(reduce merge [{1 3} {1 2} {3 4} {3 5}])
;=> {1 2, 3 5}
A naive implementation[2] of reduce would build intermediate maps corresponding to the different phases of accumulation. The accumulation of these short-lived instances can in some circumstances cause inefficiencies, which transients are meant to address.
2 The actual implementation of reduce follows a reduce protocol that delegates to a smart “internal reduce” mechanism that’s meant for data structures that know the most efficient way to reduce themselves.
Write your code so that it’s first and foremost correct using the immutable collections and operations; then, make changes to use transients for gaining speed. But you might be better served by writing idiomatic and correct code and letting the natural progression of speed enhancements introduced in new versions of Clojure take over. Spot optimizations often quickly become counter-optimizations by preventing the language/libraries from doing something better.
We’ll explore how you can use transients in the next section.
Mutable objects generally don’t make new allocations during intermediate phases of an operation on a single collection type, and comparing persistent data structures against that measure assumes a lesser memory efficiency. But you can use transients to provide not only efficiency of allocation, but often of execution as well. Take a function zencat, intended to work similarly to Clojure’s concat, but with vectors exclusively:
(defn zencat1 [x y]
(loop [src y, ret x]
(if (seq src)
(recur (next src) (conj ret (first src)))
ret)))
(zencat1 [1 2 3] [4 5 6])
;=> [1 2 3 4 5 6]
(time (dotimes [_ 1000000] (zencat1 [1 2 3] [4 5 6])))
; "Elapsed time: 486.408 msecs"
;=> nil
The implementation is simple enough, but it’s not all that it could be. The effects of using transients is shown next.
Wait, what? It seems that by using transients, we’ve actually made things worse—but have we? The answer lies in the question, “what am I actually measuring?” The timing code is executing zencat2 in a tight loop. This type of timing isn’t likely representative of actual use, and instead highlights an important consideration: the use of persistent! and transient, though constant time, aren’t free. By measuring the use of transients in a tight loop, we’ve introduced a confounding measure, with the disparate cost of using transients compared to the cost of concatenating two small vectors. A better benchmark would instead be to measure the concatenation of larger vectors, therefore minimizing the size-relative cost of transients:
(def bv (vec (range 1e6))) (first (time (zencat1 bv bv))) ; "Elapsed time: 181.988 msecs" ;=> 0 (first (time (zencat2 bv bv))) ; "Elapsed time: 39.353 msecs" ;=> 0
In the case of concatenating large vectors, the use of transients is ~4.5 times faster than the purely functional approach. Be careful how you use transients in your own applications, because as you saw, they’re an incredible boon in some cases, and quite the opposite in others. Likewise, be careful designing performance measurements, because they might not always measure what you think.
Because transients are a mutable view of a collection, you should take care when exposing outside of localized contexts. Fortunately, Clojure doesn’t allow a transient to be modified across threads and will throw an exception if attempted. But it’s easy enough to forget that you’re dealing with a transient and return it from a function. That’s not to say that you couldn’t return a transient from a function—it can be useful to build a pipeline of functions that work in concert against a transient structure. Instead, we ask that you remain mindful when doing so.
The use of transients can help to gain speed in many circumstances. But be mindful of the trade-offs when using them, because they’re not cost-free operations.
With the release of Clojure 1.1, the granularity of Clojure’s laziness was changed from a one-at-a-time model to a chunk-at-a-time model. Instead of walking through a sequence one node at a time, chunked sequences provide a windowed view (Boncz 2005) on sequences some number of elements wide, as illustrated here:
(def gimme #(do (print \.) %)) (take 1 (map gimme (range 32)))
You might expect that this snippet would print (.0) because we’re only grabbing the first element, and if you’re running Clojure 1.0, that’s exactly what you’d see. But in later versions, the picture is different:
;=> (................................0)
If you count the dots, you’ll see exactly 32, which is what you’d expect given the statement from the first paragraph. Expanding a bit further, if you increase the argument to range to be 33 instead, you’ll see the following:
(take 1 (map gimme (range 33))) ;=> (................................0)
Again you can count 32 dots. Moving the chunky window to the right is as simple as obtaining the 33rd element:
(take 1 (drop 32 (map gimme (range 64)))) ;=> (................................................................32)
As we showed in chapter 5, Clojure’s sequences are implemented as trees fanning out at increments of 32 elements per node. Therefore, chunks of size 32 are a natural fit, allowing for the garbage collection of larger chunks of memory as seen in figure 12.1.
You might be worried that chunked sequences have squashed the entire point of lazy sequences, and for small sequences this would be correct. But the benefits of lazy sequences are striking when dealing with cyclopean magnitudes or sequences larger than memory. Chunked sequences in the extreme cases are an incredible boon because not only do they make sequence functions more efficient overall, they still fulfill the promise of lazy sequences: avoiding full realization of interim results.
There are legitimate concerns about this chunked model, and one such concern is the desire for a one-at-a-time model to avoid exploding computations. Assuming that you have such a requirement, one counterpoint against chunked sequences is that of building an infinite sequence of Mersenne primes.[3] Implicit realization of the first 32 Mersenne primes through chunked sequences will finish long after the Sun has died.
But you can use lazy-seq to create a function seq1 that can be used to restrict (or dechunkify, if you will) a lazy sequence and enforce the one-at-a-time model, as in the following listing.
(defn seq1 [s]
(lazy-seq
(when-let [[x] (seq s)]
(cons x (seq1 (rest s))))))
(take 1 (map gimme (seq1 (range 32))))
;=> (.0)
(take 1 (drop 32 (map gimme (seq1 (range 64)))))
;=> (.................................32)
You can again safely generate your lazy, infinite sequence of Mersenne primes. The world rejoices. But seq1 eliminates the garbage-collection efficiencies of the chunked model and again regressed back to that shown in figure 12.2.
Clojure may one day provide an official API for one-at-a-time lazy sequence granularity, but for now seq1 will suffice. We advise that you instead stick to the chunked model, because you’ll probably never notice its effects during normal usage.
As we mentioned briefly in section 11.4, memoization (Michie 1968) refers to storing a cache of values local to a function so that its arguments can be retrieved rather than calculated on every call. The cache is a simple mapping of a given set of arguments to a previously calculated result. In order for this to work, the memoized function must be referentially transparent, which we discussed in section 7.1. Clojure comes with a memoize function that can be used to build a memoized version of any referentially transparent function, as shown:
(def gcd (memoize
(fn [x y]
(cond
(> x y) (recur (- x y) y)
(< x y) (recur x (- y x))
:else x))))
(gcd 1000645475 56130776629010010)
;=> 215
Defining a “greatest common denominator” function using memoize helps to speed subsequent calculations using the arguments 1000645475 and 56130776629010010. The function memoize wraps another function[4] in a cache lookup pass-through function and returns it. This allows you to use memoize on literally any referentially transparent function. The operation of the memoize is analogous to, but not exactly the operation of Clojure’s lazy sequences that cache the results of their realized portions. This general technique can be useful, but the indiscriminate storage provided by memoize might not always be appropriate. Therefore, we’ll take a step back and devise a way to generalize the operation of memoization into useful abstractions and build a framework for employing caching strategies more appropriate to the domain at hand.
4 You might’ve noticed that we explicitly bound the Var gcd to the memoization of an anonymous function but then used recur for implementing the function body. This approach suffers from the inability to cache the intermediate results (Norvig 1991) of gcd. We leave the solution to this short-coming as an exercise for the reader.
Similar to Haskell’s typeclasses, Clojure’s protocols define a set of signatures providing a framework of adherence to a given set of features. This section serves a threefold goal:
As mentioned in section 11.4, memoization is a personal affair, requiring a certain domain knowledge to perform efficiently and correctly. That’s not to say that the core memoize function is useless, only that the base case doesn’t cover all cases. In this section, we’ll define a memoization protocol in terms of the primitive operations: lookup, has?, hit, and miss. Instead of providing a memoization facility that allows the removal of individual cache items, it’s a better idea to provide one that allows for dynamic cache-handling strategies.[5]
5 This section is motivated by the fantastic work of the brilliant Clojurians Meikel Brandmeyer, Christophe Grand, and Eugen Dück summarized at http://kotka.de/blog/2010/03/memoize_done_right.html.
The protocol for a general-purpose cache feature is provided in the following listing.
(defprotocol CacheProtocol (lookup [cache e]) (has? [cache e] ) (hit [cache e]) (miss [cache e ret]))
The function lookup retrieves the item in the cache if it exists. The function has? will check for a cached value. The function hit is called when an item is found in the cache, and miss is called when it’s not. If you’re familiar with creating Java interfaces, the process of creating a protocol should be familiar. Moving on, we next implement the core memoize functionality.
(deftype BasicCache [cache]
CacheProtocol
(lookup [_ item]
(get cache item))
(has? [_ item]
(contains? cache item))
(hit [this item] this)
(miss [_ item result]
(BasicCache. (assoc cache item result))))
The BasicCache takes a cache on construction used for its internal operations. Testing the basic caching protocol in isolation shows:
(def cache (BasicCache. {}))
(lookup (miss cache '(servo) :robot) '(servo))
;=> :robot
In the case of a miss, the item to be cached is added and a new instance of BasicCache (with the cached entry added) is returned for retrieval using lookup. This is a simple model for a basic caching protocol, but not terribly useful in isolation. We can go further by creating an auxiliary function through, meaning in effect, “pass an element through the cache and return its value”:
(defn through [cache f item]
(if (has? cache item)
(hit cache item)
(miss cache item (delay (apply f item)))))
With through, the value corresponding to a cache item (function arguments in this case) would either be retrieved from the cache via the hit function, or calculated and stored via miss. You’ll notice that the calculation (apply f item) is wrapped in a delay call instead of performed outright or lazily through an ad hoc initialization mechanism. The use of an explicit delay in this way helps to ensure that the value is calculated only on first retrieval. With these pieces in place, we can then create a PluggableMemoization type, as shown next.
(deftype PluggableMemoization [f cache]
CacheProtocol
(has? [_ item] (has? cache item))
(hit [this item] this)
(miss [_ item result]
(PluggableMemoization. f (miss cache item result)))
(lookup [_ item]
(lookup cache item)))
The purpose of the PluggableMemoization type is to act as a delegate to an underlying implementation of a CacheProtocol occurring in the implementations for hit, miss, and lookup. Likewise, the PluggableMemoization delegation is interposed at the protocol points to ensure that when utilizing the CacheProtocol, the Pluggable-Memoization type is used and not the BasicCache. We’ve made a clear distinction between a caching protocol fulfilled by BasicCache and a concretized memoization fulfilled by PluggableMemoization and through. With the creation of separate abstractions, you can use the appropriate concrete realization in its proper context. Clojure programs will be composed of various abstractions. In fact, the term abstraction-oriented programming is used to describe Clojure’s specific philosophy of design.
The original manipulable-memoize function from section 11.4 is modified in the following listing to conform to our memoization cache realization.
(defn memoization-impl [cache-impl]
(let [cache (atom cache-impl)]
(with-meta
(fn [& args]
(let [cs (swap! cache through (.f cache-impl) args)]
@(lookup cs args)))
{:cache cache})))
If you’ll recall from the implementation of the through function, we stored delay objects in the cache requiring they be deferenced when looked up. Returning to our old friend the slowly function, we can exercise the new memoization technique as shown:
(def slowly (fn [x] (Thread/sleep 3000) x))
(def sometimes-slowly (memoization-impl
(PluggableMemoization.
slowly
(BasicCache. {}))))
(time [(sometimes-slowly 108) (sometimes-slowly 108)])
; "Elapsed time: 3001.611 msecs"
;=> [108 108]
(time [(sometimes-slowly 108) (sometimes-slowly 108)])
; "Elapsed time: 0.049 msecs"
;=> [108 108]
You can now fulfill your personalized memoization needs by implementing pointed realizations of CacheProtocol, plugging them into instances of PluggableMemoization, and applying them as needed via function redefinition, higher-order functions, or dynamic binding. Countless caching strategies can be used to better support your needs, each displaying different characteristics, or if needed your problem may call for something wholly new.
We’ve only scratched the surface of memoization in this section in favor of providing a more generic substrate on which to build your own memoization strategies. Using Clojure’s abstraction-oriented programming techniques, your own programs will likewise be more generic and be built largely from reusable parts.
Although Clojure is a dynamically typed language, it does provide mechanisms for specifying value types. The first of these mechanisms, type hints, was covered in section 12.1. The second, coercion, is the subject of this section. Although the nature of type hints and coercion are similar, their intended purposes are quite different. In the case of coercion, its purpose is to get at the primitive data type for a value, which we’ll show next.
Clojure’s compiler is sophisticated enough that in many ways it’ll be unnecessary to coerce values into primitives. It’s often better to start with a function or code block devoid of coercions. Unless your specific application requires the utmost speed in execution, it’s better to stick with the version that favors simplicity over the alternative. But should you decide that coercion might be the choice for you, then this section will provide guidance.
If you’ve determined that coercion can help, then it’s worth stressing that you have to be careful when going down that road. In many cases with coercion, the act of adding it can actually slow your functions. The reason lies in the nature of Clojure. Functional composition leads to passing arguments back and forth between pieces, and in the circumstance of coercion you’re just boxing and unboxing[6] from one call to the next. This particular circumstance is especially devious within the body of a loop, and follows the same performance degradations observed with Java. Clojure’s unboxing is an explicit[7] operation performed using the coercion functions, so there’s a speck of light there. Unfortunately, autoboxing is still a danger and should be avoided if speed is a concern, as we’ll explore now:
6 Autoboxing is the automatic conversion the Java compiler makes between the primitive types and their corresponding object wrapper classes.
7 Except when directly or indirectly (via inlining or a macro body) calling a method.
(defn occur-count [words]
(let [res (atom {})]
(doseq [w words] (swap! res assoc w (+ 1 (@res w 0))))
@res))
(defn roll [n d]
(reduce + (take n (repeatedly #(inc (rand-int d))))))
(time (dorun (occur-count (take 1000000 (repeatedly #(roll 3 6))))))
; "Elapsed time: 4055.505 msecs"
The function occur-count will return a map of the occurrence counts[8] found in a given sequence. This fairly straightforward implementation uses the function roll to populate a sequence with a million simulated rolls of three six-sided dice. But four seconds seems like a long time to wait, so perhaps we can speed things up by using coercions. An initial attempt to gain speed may be to pull out the stored count from the table and coerce it into an int:
8 Clojure has a function frequencies that does this, so we provide occur-count for illustrative purposes only.
(defn occur-count [words]
(let [res (atom {})]
(doseq [w words]
(let [v (int (@res w 0))]
(swap! res assoc w (+ 1 v))))
@res))
(time (dorun (occur-count (take 1000000 (repeatedly #(roll 3 6))))))
; "Elapsed time: 4385.8 msecs"
Well, that didn’t work. The reason for a decrease in speed is that although we’re specifying the type at the outer loop, we haven’t reduced the need to box and unbox that value further downstream in the roll function. We might then be led to try and optimize the roll function too:
(defn roll [n d]
(let [p (int d)]
(reduce + (take n (repeatedly #(inc (rand-int p)))))))
(time (dorun (occur-count (take 1000000 (repeatedly #(roll 3 6))))))
; "Elapsed time: 4456.393 msecs"
;=> nil
Again we’ve made matters worse and have spread the problems over the surface of the entire code. Being adventurous, we grasp for straws and attempt to force integer arithmetic with roll by using the unchecked-inc function:
(defn roll [n d]
(let [p (int d)]
(reduce + (take n (repeatedly #(unchecked-inc (rand-int p)))))))
(time (dorun (occur-count (take 1000000 (repeatedly #(roll 3 6))))))
Go ahead and run that in the REPL, then go get some coffee and a bagel. Toast the bagel. Eat the bagel. Drink the coffee. By that time, you might’ve received a result.
So what happened? In an attempt to be clever, we’ve confused the Clojure compiler into near unconsciousness. Instead of making direct calls to Clojure’s math functions, we’re now making calls indirectly via Java reflection! You can observe this by setting *warn-on-reflection* to true and reentering roll.
How can we speed things up? The problem isn’t with coercion itself, but instead with the implementations of roll and occur-count. You can observe significant speed-ups by rethinking your original implementations first and then resorting to coercion second. The use of coercion should always be preceded by a reevaluation of your implementation, because often by doing so you can eliminate the need for coercion altogether, as shown next.
By refactoring the original functions, we’ve gained a five-fold increase in speed and yet used only a single coercion. Additionally, we’ve managed to make the new implementation faster while also maintaining clarity. This should be a general goal when writing your Clojure code, and when forced to make a trade between the two, it might be a good idea to favor clarity.
In the previous example, there’s too much noise in collection and sequence operations for primitive coercion to help much. This goes to show that it’s important to remember that the Clojure compiler will often do a better job at optimization than you.
When coercing a local to a primitive type, it’s tempting to do so at the point of use, but this practice should be avoided. A good rule of thumb for coercion is to coerce only within a local context via let, binding, or loop. This provides a stable value point for the primitive, allowing you to reuse that same local elsewhere in the same function without having to again coerce at different points of use. This can be illustrated by the following:
(defn mean
"Takes a sequence of integers and returns their mean value"
[sq]
(let [length (int (count sq))]
(if (zero? length)
0
(/ (int (reduce + sq)) length))))
The length value has been bound in the let, allowing it to be reused twice within the body of the function. This allows for a cleaner implementation than the alternative, which coerces the results of (count sq) in multiple places. Using this advice and the fact that Clojure provides lexical scope by default, you can also avoid the need to define a name-mangled local by instead using let to rebind original argument names to coerced values (defn [x] (let [x (int x)] ...)).
Primitive type coercions in Clojure act the same as type truncation in Java. If a given value is coerced into a type that can’t hold a value of its magnitude, then data loss will occur, and in the case of integer overflow, exceptions will be thrown.
By default, Clojure doesn’t limit the accuracy of mathematical operations, but this can occur when using coercion. There will be many instances in your own projects when speed is more important than accuracy in mathematical operations. Likewise, there will also be times when truncation is necessary, especially when dealing with Java library methods that take primitive types:
(Math/round 1.23897398798929929872987890030893796768727987138M) ; java.lang.IllegalArgumentException: ; No matching method found: round
When a method or function isn’t overloaded, the Clojure compiler can determine whether an argument can be coerced to a primitive type and will do so if able. The preceding issue exception arises from the fact that Math/round is overloaded, taking either a float or double typed argument. Therefore, you have to explicitly use coercion to truncate the argument:
(Math/round (float 1.23897398798929929872987890030893796768727987138M)) ;=> 1
Our goal in using the truncating operation float was to get a result that we knew wouldn’t be affected by truncation. But many instances will arise when truncation will affect your results and will often do so to your detriment. Therefore, it’s best to be wary when using coercion, because it propagates inaccuracies. It’s best to limit its usage when truncation is desired and document vigorously when it’s absolutely needed for speed.
Coercion can be an effective tool in your Clojure applications, but take care to be sure you understand the caveats. If you take away one lesson from this section, let it be this: do not rush to coercion.
Clojure provides numerous ways to gain speed in your applications. Using some combination of type hints, transients, chunked sequences, memoization, and coercion, you should be able to achieve noticeable performance gains. Like any powerful tool, these performance techniques should be used cautiously and thoughtfully. But once you’ve determined that performance can be gained, their use is minimally intrusive and often natural to the unadorned implementation.
In the final chapter, we’ll cover a number of ways that the Clojure way of thinking might be different from what you’re accustomed to. The discussion therein, when explored with an open mind, will change the way that you write software.