nth yields "java.lang.OutOfMemoryError: Java heap space"

Showing 1-5 of 5 messages
nth yields "java.lang.OutOfMemoryError: Java heap space" arasoft 7/4/09 5:04 AM
Using a fairly recent 1.1 snapshot, I get an OutOfMemoryError for
this:

(defn fib-seq []
    ((fn more [a b]
        (lazy-seq (cons a (more b (+ a b)))))
     0 1)
)

(nth (fib-seq) 200000)

However, this works fine:

(defn xth [coll i]
  (if (zero? i) (first coll) (recur (rest coll) (dec i))))

(xth (fib-seq) 200000)

Am I doing anything wrong, or is this a bug?
Re: nth yields "java.lang.OutOfMemoryError: Java heap space" Daniel Lyons 7/4/09 7:37 AM


You aren't doing anything wrong, it's just that recur is a local jump  
which creates no stack and calling a function recursively is not. In  
other words Clojure doesn't have built-in tail call elimination, but  
recur creates the same effect. (I actually prefer this behavior  
because it's easy to see where you're paying the penalty for recursion  
and where you aren't, unlike in OCaml, Scheme and Haskell, where it  
can be easy to get confused about which form is the final position.)


Daniel Lyons

Re: nth yields "java.lang.OutOfMemoryError: Java heap space" Lennart Staflin 7/4/09 8:11 AM
I don't think this explains it. It is a OutOfMemoryError not a stack
overflow. It is not a recursion problem. I think it is that nth hangs
on to the head of the lazy fib sequence, and therefor all the elements
including the big integers can not be garbage collected.

The xth function does not hang on to the head, and all the
intermediate elements can be garbage collected.

//Lennart Staflin
Re: nth yields "java.lang.OutOfMemoryError: Java heap space" Meikel Brandmeyer 7/4/09 9:43 AM
Hi,

Am 04.07.2009 um 17:11 schrieb Lennart Staflin:

> I don't think this explains it. It is a OutOfMemoryError not a stack
> overflow. It is not a recursion problem. I think it is that nth hangs
> on to the head of the lazy fib sequence, and therefor all the elements
> including the big integers can not be garbage collected.
>
> The xth function does not hang on to the head, and all the
> intermediate elements can be garbage collected.

This was my first thought, too. But this is not
the case. If the collection "is" Sequential, the
seq is obtained from it via seq() and then the
original pointer is nulled. Maybe this gets
optimised away by the JVM?

Sincerely
Meikel

Re: nth yields "java.lang.OutOfMemoryError: Java heap space" Rich Hickey 7/4/09 9:49 AM
A recent optimization attempt introduced a head-retaining hop in
RT.nth, now removed. Thanks for the report!

http://github.com/richhickey/clojure/commits/master

Rich