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)))))