math.combinatorics

OutOfMemory Error with combinatorics/subsets

Details

  • Type: Defect Defect
  • Status: Resolved Resolved
  • Priority: Minor Minor
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Environment:

Description

Hello guys,

I have an issue with an OutOfMemory error with bigger sets and the subsets command.

I have bigger sets of 1000+ elements and want to lazily create all possible subsets of this set in order to filter out some that are interesting to me.

I was very happy to run into your library as it handles the heavy lifting for me and I only have to do the filtering. Nice!

But if I run this sample code

lein repl
=> (last (clojure.math.combinatorics/subsets (range 1000)))
OutOfMemoryError Java heap space  clojure.core/map (core.clj:2469)

it returns with an OutOfMemory Error to me.
I thought the memory usage of subsets would be constant as the function should return a lazy list.

It would be really nice if this library could calculate subsets of bigger lists without running into memory problems.

I posted this question on StackOverflow with more information:
http://stackoverflow.com/questions/16194841/clojure-lazy-sequences-in-math-combinatorics-results-in-outofmemory-oom-error

And people replied that they don't have this issue. Is this an issue with my platform or is this an issue with the memory usage of subsets?
It would be great if you could show me a way to get around this issue.

If I can be of any help, just let me know.

Cheers, Mark

Activity

Hide
Stefan du Fresne added a comment -

I get this as well, 2009 MBP, with any (range x) higher than 18.

Show
Stefan du Fresne added a comment - I get this as well, 2009 MBP, with any (range x) higher than 18.
Hide
Mark Engel added a comment - - edited

Great to have the problem reproduced at another computer.

I just found an article describing an OutOfMemory Error with mapcat, which is used in the subsets function
http://clojurian.blogspot.de/2012/11/beware-of-mapcat.html.

Show
Mark Engel added a comment - - edited Great to have the problem reproduced at another computer. I just found an article describing an OutOfMemory Error with mapcat, which is used in the subsets function http://clojurian.blogspot.de/2012/11/beware-of-mapcat.html.
Hide
Andy Fingerhut added a comment -

Patch mcomb-2-allow-subsets-to-use-less-memory-v1.txt dated May 2 2013 seems to fix this problem.

range returns a chunked sequence, and when map processes a chunked sequence it preserves the chunks. Chunks are little Java arrays of Object references, pointing at the results, and none of them will be GCed until the entire chunk is finished being processed.

It might be that a few other calls to unchunk wrapped around range calls might be useful in the math.combinatorics library, but certainly not all of them.

Show
Andy Fingerhut added a comment - Patch mcomb-2-allow-subsets-to-use-less-memory-v1.txt dated May 2 2013 seems to fix this problem. range returns a chunked sequence, and when map processes a chunked sequence it preserves the chunks. Chunks are little Java arrays of Object references, pointing at the results, and none of them will be GCed until the entire chunk is finished being processed. It might be that a few other calls to unchunk wrapped around range calls might be useful in the math.combinatorics library, but certainly not all of them.
Hide
David James added a comment -

Thanks Andy, that worked for me!

Andy's patch, applied to my fork:
https://github.com/xpe/math.combinatorics/commit/5adb2fdfd6e1661eb4056cbf06e8d4a633dd0088

Show
David James added a comment - Thanks Andy, that worked for me! Andy's patch, applied to my fork: https://github.com/xpe/math.combinatorics/commit/5adb2fdfd6e1661eb4056cbf06e8d4a633dd0088
Hide
Andy Fingerhut added a comment -

Mark, any thoughts on this patch? The reason for the memory exhaustion without the patch is a bit subtle, and I can try explaining it differently if you are interested.

Show
Andy Fingerhut added a comment - Mark, any thoughts on this patch? The reason for the memory exhaustion without the patch is a bit subtle, and I can try explaining it differently if you are interested.
Hide
Andy Fingerhut added a comment -

Mark Engelberg committed this fix: https://github.com/clojure/math.combinatorics/commit/4b5312218344264c3227f7f814db6c688d0ab2fc

I will close this ticket.

Show
Andy Fingerhut added a comment - Mark Engelberg committed this fix: https://github.com/clojure/math.combinatorics/commit/4b5312218344264c3227f7f814db6c688d0ab2fc I will close this ticket.

People

Vote (1)
Watch (2)

Dates

  • Created:
    Updated:
    Resolved: