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"

score 4 · Answer 1 · edited May 23 '17 at 11:51

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:

Error java.lang.OutOfMemoryError: GC overhead limit exceeded

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

score 2 · Answer 2 · answered Oct 18 '10 at 05:07

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.

score 2 · Accepted Answer · answered Oct 18 '10 at 06:07

Hmm... This works for me. Tested with Clojure 1.2 on Windows XP.

user=> (defn avg
         [xs & {:keys [n] :or {n 2}}]
         (/ (reduce + xs) n))
#'user/avg
user=> (defn Gregory-Leibniz-n
         [n]
         (/ (Math/pow -1 n) (inc (+ n n))))
#'user/Gregory-Leibniz-n
user=> (->> (range)
         (map #(* 4 (Gregory-Leibniz-n %)))
         (reductions +)
         (partition 20)
         (map #(avg % :n 20))
         first
         println)
3.1689144018345354

Is that the right answer? I don't know this Gregory-Leibniz recursion, so I'm not sure whether this is correct.

One point I noted: You are trying to be too clever. Namely your avg-damp-n stacks lazy seq on lazy seq. Since you can plugin arbitrary values of n, you will sooner or later also experience stack overflows for large n in such a scenario. If there is a straight-forward solution you should prefer it. I'm not sure that this is your actual problem, though. (As I said: rather unhelpfully it works for me.)

Considering this is supposed to resolve to Pi, I don't think that's the right answer. ;) — Alex Taggart, Oct 18 '10 at 17:26
@ataggert You have point there. ;) (Small edit: But it may still be the number the OP expects...) (And of course with the `(partition 2 1 ...)` change the above is doesn't work anymore.) — kotarak, Oct 19 '10 at 05:22

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

3 Answers3