Why does reducing this lazy sequence slow down this Clojure program 20x?

Question

I have a Clojure program that returns the sum of a lazy sequence of even Fibonacci numbers below n:

(defn sum-of-even-fibonaccis-below-1 [n]
  (defn fib [a b] (lazy-seq (cons a (fib b (+ b a)))))
  (reduce + (take-while (partial >= n) (take-nth 3 (fib 0 1)))))

(time (dotimes [n 1000] (sum-of-even-fibonaccis-below-1 4000000))) ;; => "Elapsed time: 98.764msecs"

It's not very efficient. But if I don't reduce the sequence and simply return a list of the values (0 2 8 34 144...) it can do its job 20x faster:

(defn sum-of-even-fibonaccis-below-2 [n]
  (defn fib [a b] (lazy-seq (cons a (fib b (+ b a)))))
  (take-while (partial >= n) (take-nth 3 (fib 0 1))))


(time (dotimes [n 1000] (sum-of-even-fibonaccis-below-2 4000000))) ;; => "Elapsed time: 5.145msecs"

Why is reduce so costly to this lazy Fibonacci sequence, and how can I speed it up without abandoning idiomatic Clojure?

Piotrek Bzdyl Piotrek Bzdyl · Accepted Answer · 2016-04-06T07:11:19

The difference in the execution time is a result of lazyness. In sum-of-even-fibonaccis-below-2 you only produce a lazy seq of Fibonacci numbers which is not realised (dotimes only calls sum-of-even-fibonaccis-below-2 to create a lazy sequence, but does not evaluate all of its contents). So in fact your second time expression doesn't return a list of values but a lazy seq that will produce its elements only when you ask for them.

To force realisation of the lazy sequence you can use dorun if you don't need to preserve it as a value or doall if you want to get the realised seq (be careful with inifinite seqs).

If you measure the second case with sum-of-even-fibonaccis-below-2 wrapped in dorun you will get time comparable to sum-of-even-fibonaccis-below-1.

Results from my machine:

(time (dotimes [n 1000] (sum-of-even-fibonaccis-below-1 4000000))) ;; => "Elapsed time: 8.544193 msecs"

(time (dotimes [n 1000] (dorun (sum-of-even-fibonaccis-below-2 4000000)))) ;; => "Elapsed time: 8.012638 msecs"

I also noticed that you defined your fib function with defn inside another defn. You shouldn't do that as defn will always define function at the top level in your namespace. So your code should look like:

(defn fib [a b] (lazy-seq (cons a (fib b (+ b a)))))

(defn sum-of-even-fibonaccis-below-1 [n]
  (reduce + (take-while (partial >= n) (take-nth 3 (fib 0 1)))))

(defn sum-of-even-fibonaccis-below-2 [n]
  (take-while (partial >= n) (take-nth 3 (fib 0 1))))

If you do want to define a locally scoped function you can take a look at letfn.

Why does reducing this lazy sequence slow down this Clojure program 20x?

2 Answers