I don't really blog anymore. Click here to go to my main website.

muhuk's blog

Nature, to Be Commanded, Must Be Obeyed

April 19, 2019

Cost of Laziness in Clojure

This is a technical post and laziness in this context means deferring execution of code. When the machine first meets the code, it may be executed there and then or it may be stored and executed later. Which of those happens depends on the instructions in the code, the computer just executes them without judgement.

Not all types of deferral is laziness. For example making something happen when a button is clicked is (probably) just event driven programming. Similarly asynchronous programming is not necessarily same as lazy evaluation. If we want to find lazy code we need not look further than basic definitions:

;; foo is 7 as soon as code is read:
(def foo (+ 3 4))

;; The expression (+ 3 4) is calculated only when bar is called:
(defn bar [] (+ 3 4))

A few things are worth noting here:

  • We can precisely control when the function body is executed.
  • Since the function body is not required to be executed when the code is read, we can add unknowns (arguments) that can be supplied later. This is one of the reasons why functions are a powerful means of abstraction.
  • Ability to separate definition of functions and calculation of results of invocation enables passing them as arguments to other functions which may or may not call them.

If all this looks like indeterminism that takes the control away from the programmer, you should read on. Laziness is actually a very strong feature. If anything it enables programmers, gives more control.

Haskell is a lazy language[1]. By default, Haskell expressions are evaluated when their values (results) are needed. Clojure, on the other hand, is not a lazy language[2]. However Clojure provides primitives to achieve and control lazy evaluation. I guess we can say Clojure has opt-in laziness. But it would not be entirely correct, because lazy sequences are used throughout the standard library.. Even if you have never created a lazy sequence in your code intentionally, if you have used one of take, drop, filter, map, concat, … list goes on and on, you have worked with lazy sequences.

Infinite Sequences Using Lazy Sequences

You can create infinite sequences using lazy evaluation. Only as much of the sequence as needed gets realized:

(def all-numbers (range))

(->> all-numbers
     (drop 1e5)
     (take 10))
;; => (100000 100001 100002 100003 100004 100005 100006 100007 100008 100009)

Example above is not idiomatic Clojure and neither is it efficient[3]. But it should illustrate the point of the separation between the definition of the whole sequence and the operations defined on it. We did not have to know, initially, how many numbers are supposed to be in all-numbers. All numbers are in it. This expressive power came at a cost of course, the first 10k elements in the lazy sequence had to be realized (CPU & memory cost) before we can access the first result (which is 10000).

Here is a more practical and more idiomatic example using infinite sequences:

;; infinite sequence that goes on like (:odd :even :odd ...)
(def odd-even (cycle [:odd :even]))

;; finite sequence of numbers from 1 to 10
(def numbers (range 1 11))

(mapv vector numbers odd-even)
;; => [[1 :odd] [2 :even] [3 :odd] [4 :even] [5 :odd]
;;     [6 :even] [7 :odd] [8 :even] [9 :odd] [10 :even]]

We could have written the same code in a few other different ways. In my this is the easiest to reason about if one is familiar with functional concepts.

Selective Realization Sequences

Sometimes we may not be dealing with infinite sequences but just large sequences that we may or may not want to realize (compute). Let us look at this example:

(defn send-all-the-files-everywhere!
  [file-seq server-seq]
  (if (network-ready?)
    (for [file file-seq
          server server-seq]
      (send-file! server file)
    (wait-for-a-while #(send-all-the-files-everywhere! file-seq server-seq)))))

Note that the definition of file-seq and server-seq cannot change in this design even if the network does not come back up for weeks. File system can change between the time of definition of file-seq and when the iteration starts (for). But the sequence can be computed lazily and in that case file-seq is pretty much just specifying a recipe of files. In other words when the iterations starts the sequence can produce results correct for that point in time. Similar thing can be said for server-seq. Let us consider a different strategy to follow when the network is down:

(defn send-all-the-files-everywhere!
  [file-seq server-seq admin-seq]
  (if (network-ready?)
    (for [file file-seq
          server server-seq]
      (send-file! server file)
    (notify-admins! admin-seq))))

Now either file-seq & server-seq will be realized or admin-seq. It is an exclusive or.

We can of course achieve the same results with functions. But the only difference between a function and a lazy sequence is not an extra set of parenthesis. In fact implementing lazy sequences via functions would require more than just calling a function. Lazy sequences are sequences, functions are not. With functions any operations defined on sequences cannot be used, what is illustrated below cannot be done:

;; You cannot replace this...
(take n lazy-sequence)

;; ...with this:
(take n (my-fn))

;; Not unless my-fn is returning a sequence.

A simpler mechanism of delayed execution is delay. Any Clojure form can be wrapped with delay to prevent its evaluation. The resulting object can be held onto until it is time to compute the result. Then we can deref it to force evaluation and get the result. Delays are a lot closer to functions than lazy sequences. Dereferencing is analogous to function invocation. Delay offers an all-or-nothing laziness compared to lazy sequences.

Performance Overhead

As the title stipulates we will now look at the performance cost of lazy computation. By definition you are never at a loss for using the right abstraction in the right place. Lazy evaluation has have some performance overhead compared to eager variants. However it does not necessarily mean they are equivalent in terms of expressivenes. There is always the difference between a lazy variant and an eager variant; the latter lacks laziness. Note that all the examples below take an eager computation example and apply laziness to that purely for benchmarking purposes.

Let us start with the simplest, delay:

(bench (+ 3 4))
;; mean: 3.75949677236114e-09
;; variance: 8.226753367116037e-20

(-> (delay (+ 3 4))
    (deref)
    (bench))
;; mean: 4.2919174230351124e-08
;; Variance: 4.299866796080404e-18

Adding delay to a simple calculation made it an order of magnitude slower. But the absolute overhead is not even a millisecond. We should keep that in mind.

What would it cost us to make a sequence lazy which may as well be calculated eagerly:

(letfn [(f [i]
          (if (> i 1)
            (cons i (f (dec i)))
            [1]))]
  (-> (f 100)
      (vec)
      (bench)))
;; mean: 6.889351331527873e-06
;; variance: 2.7162084516916413e-14

(letfn [(f [i]
          (if (> i 1)
            (lazy-seq (cons i (f (dec i))))
            [1]))]
  (-> (f 100)
      (vec)
      (bench)))
;; mean: 1.1262495556481289e-05
;; variance: 7.059663905548016e-13

Lazy sequence is 63.5% slower than the eager variant. But, again, the absolute overhead is less than a millisecond.

Let us look at one last example, map (lazy) vs reduce (eager):

(-> [0 1 2 3 4 5 6 7 8 9]
    (->> (map inc))
    (vec)
    (bench))
;; mean: 9.273368665539242e-07
;; variance: 4.3683408995731724e-16

(-> [0 1 2 3 4 5 6 7 8 9]
    (->> (reduce (fn [acc x] (conj acc (inc x))) []))
    (bench))
;; mean: 5.841981563202665e-07
;; variance: 6.718577305578137e-16

Once again the overhead is insignificant. I have also run some more benchmarks that eager variants were slower. That was because lazy sequences were used in an idiomatic way. I have intentionally picked the benchmarks where laziness is forced on otherwise alright code. And the performance overhead has been negligable in each case.

For your reference, I have used criterium’s quick-benchmark and run all benchmarks via org-babel:

(defmacro bench [expr]
  `(-> (cc/quick-benchmark ~expr nil)
       (select-keys ks)
       (vals)
       (->> (map (fn [v#] (if (coll? v#) (first v#) v#)))
            (vector (map name ks)))))

[1]See Lazy evaluation
[2]See Laziness in Clojure
[3]You should use (range 100000 100010) instead.

If you have any questions, suggestions or corrections feel free to drop me a line.