Re: Memory issues processing large lazy sequences

[Jorge Barrios]

The first version completes without problems.
Make sure your JVM has plenty of memory available to garbage collect.
Look at the -Xmx setting (for instance with leiningen :jvm-opts ["-
Xmx2g" "-server"])

REPL started; server listening on localhost port 18885
user=> (def atoms '(a b c))
#'user/atoms
user=>
user=> (defn get-ch [n] (map #(str n %) atoms))
#'user/get-ch
user=> (defn add-ch
([] (apply concat (iterate add-ch atoms)))
([n] (mapcat get-ch n)))
#'user/add-ch
user=> (time (dorun (take 20000000 (add-ch))))
"Elapsed time: 89922.105 msecs"
nil
user=>

On Jun 7, 10:53 am, Tom Hume <twh...@gmail.com> wrote:
> Hi
>
> I'm trying to generate a sequence which corresponds to a breadth-first
> search of a very wide, deep tree... and I'm hitting memory problems when I
> go too far along the sequence. Having asked around on the IRC channel and
> looked here, the number 1 cause of such problems is inadvertently holding
> onto the head; but I can't see where I'm doing this.
>
> The code is quite simple; here's a version which displays the problem:
>
> (def atoms '(a b c))
>
> (defn get-ch [n] (map #(str n %) atoms))
>
> (defn add-ch
>   ([] (apply concat (iterate add-ch atoms)))
>   ([n] (mapcat get-ch n)))
>
> (dorun (take 20000000 (add-ch)))
> And here's another version (which is the one I started out with before
> getting help from #clojure), which displays the same issue:
>
> (def atoms '(a b c))
>
> (defn get-children [n] (map #(str n %) atoms))
>
> (defn add-layer
>   ([] (add-layer atoms))
>   ([n] (let [child-nodes (mapcat get-children n) ]
>       (lazy-seq (concat n (add-layer child-nodes))))))
>
> (dorun (take 20000000 (add-layer)))
> Both give me an "OutOfMemoryError Java heap space". I'm running them from
> the REPL in Eclipse/CounterClockwise, on a Macbook Air.
>
> I'm pretty new to Clojure, so after beating my head against this for a day
> I'm hoping that this is something trivial I'm overlooking. I realise I
> could up my heap-size to make the issue less likely to occur, but the
> sequences I ultimately want to process are so vast I don't think this is
> going to help me...
>
> Any suggestions warmly welcomed.
>
> Thanks
> Tom

[Chris Perkins]

On Thursday, June 7, 2012 1:53:30 PM UTC-4, Tom Hume wrote:

Hi

I'm trying to generate a sequence which corresponds to a breadth-first search of a very wide, deep tree... and I'm hitting memory problems when I go too far along the sequence. Having asked around on the IRC channel and looked here, the number 1 cause of such problems is inadvertently holding onto the head; but I can't see where I'm doing this.

(dorun (take 20000000 (add-layer)))

take holds on to the head, because that is what it returns. Try changing take to drop.

- Chris
 

[David Powell]

(dorun (take 20000000 (add-layer)))

take holds on to the head, because that is what it returns. Try changing take to drop.

Take is lazy though, and dorun should drop the head, so that shouldn't be a problem.

The problem here is not an holding onto the head issue.  Lots of memory is being used, because the algorithm requires lots of memory.

A breadth first search takes each level in the tree and makes a new level by adding 3 nodes for each existing node.  So the original level has to exist in memory at some point in order to do that.

When you get to the 2millionth element (not even the 20millionth element), the strings are already 13 characters long.  To add an extra character to each of those, then it will use 3^13 strings * 13 characters * (2 bytes per character + some overhead) - this is at least 41mb.

By the 14th character, you are going to need at least 133mb.

By the 15th character, you are going to need at least 430mb.

This is just the cost of using a breadth-first search.

Either use a different type of search; get more memory and up the heap size; or make a compact numeric of the strings, and map them back to readable string form as a post-processing step.

-- 

Dave

[Tom Hume]

Thanks David. Could you recommend any other types of search, or a different algorithm entirely, which might give me the same output in a sequence?

[Tom Hume]

Nope, that doesn't make any difference; if something's keeping hold of the head, it isn't the take:

=> (first (drop 19999999 (add-ch)))

OutOfMemoryError Java heap space  clojure.lang.RT.cons (RT.java:552)

=> (first (drop 19999999 (add-layer)))

OutOfMemoryError Java heap space  java.lang.AbstractStringBuilder.<init> (AbstractStringBuilder.java:45)

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en