Clojure: gc overhead limit exceeded, lazy evaluation, pi sequence

Question

For the next code:

(ns clojure101.series)

(defn avg [[x y]] (/ (+ x y) 2))

(defn avg-damp
  [seq]
  (map avg (partition 2 seq)))

(defn avg-damp-n
  [n]
  (apply comp (repeat n avg-damp)))

(defn sums
  [seq]
  (reductions + seq))

(defn Gregory-Leibniz-n
  [n]
  (/ (Math/pow -1 n) (inc (* 2 n))))

(def Gregory-Leibniz-pi
     (map #(* 4 (Gregory-Leibniz-n %)) (iterate inc 0)))

(println (first ((avg-damp-n 10) (sums Gregory-Leibniz-pi))))

I get "gc overhead limit exceeded" error for n=20. How can I fix this?

UPDATE: I changed avg-damp-n function

(defn avg-damp-n
  [n seq]
  (if (= n 0) seq
      (recur (dec n) (avg-damp seq))))

now I can get number for n=20

(time
 (let [n 20]
   (println n (first (avg-damp-n n (sums Gregory-Leibniz-pi))))))

20 3.141593197943081
"Elapsed time: 3705.821263 msecs"

UPDATE 2 I fixed some error and now it works just fine:

(ns clojure101.series)

(defn avg [[x y]] (/ (+ x y) 2))

(defn avg-damp
  [seq]
  (map avg (partition 2 1 seq)))

(defn avg-damp-n
  [n]
  (apply comp (repeat n avg-damp)))

(defn sums
  [seq]
  (reductions + seq))

(defn Gregory-Leibniz-n
  [n]
  (/ (int (Math/pow -1 n)) (inc (* 2 n))))

(def Gregory-Leibniz-pi
     (map #(* 4 (Gregory-Leibniz-n %)) (range)))

; π = 3.14159265358979323846264338327950288419716939937510...

(time
 (let [n 100]
   (println n (double (first ((avg-damp-n n) (sums Gregory-Leibniz-pi)))))))

OUTPUT:

100 3.141592653589793
"Elapsed time: 239.253227 msecs"

Answer 1

First of all, try the stupid solution that works: increase your java heap space.

;in your clojure launch script
java -Xmx2G ...other options...

There is one part of the program which is not lazy in partition, but changing it so that it is lazy (by getting rid of a call to count) still gives me an OutOfMemoryError for the default heap size. Replacing the cleverness of avg-damp-n with a reduce-calculated average on

(take (integer-exponent 2 20) seq)

still causes an OutOfMemoryError. Looking at the source of everything else I don't see any other things that look like they should be consuming heap.

Answer 2

As kotarak stated, the stacking of lazy seq's on lazy seq's seems quite inefficient with regard to GC. I could reproduce this issue on a slow atom system. See also:

http://stackoverflow.com/questions/1393486/what-means-the-error-message-java-lang-outofmemoryerror-gc-overhead-limit-excee

For me Gregory-Leibniz PI caclulation directly transforms into this Clojure Code which uses only one lazy sequence:

(defn Gregory-Leibniz-pi [n]
  (->> (range n)
       (map (fn [n] (/ (Math/pow -1 n) (inc (* 2 n)))))
       (apply +)
       (* 4)))