Stream#filter Runs out of Memory for 1,000,000 items
out-of-memory, scala
Solution
Overhead of `List` - single object (instance of `::`) with 2 fields (2 pointers) per element.
Overhead of `Stream` - instance of `Cons` (with 3 pointers) plus an instance of `Function` (`tl: => Stream[A]`) for lazy evaluation of `Stream#tail` per element.
So you'll spend ~2 times more memory on `Stream`.
You have defined your `Stream` as `val`. Alternatively you could define `million` as `def` - in this case after `filter` GC will delete all created elements and you'll get your memory back.
Note that only `tail` in `Stream` is lazy, `head` is strict, so `filter` evaluates strictly until it gets first element that satisfies a given predicate, and since there is no such elements in your `Stream` `filter` iterates over all your `million` stream and puts all elements in memory.
Problem
Let's say I have a `Stream` of length `1,000,000` with all 1's. ``` scala> val million = Stream.fill(100000000)(1) million: scala.collection.immutable.Stream[Int] = Stream(1, ?) scala> million filter (x => x % 2 == 0) Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded ``` I get an `Out of Memory` exception. Then, I tried the same `filter` call with `List`. ``` scala> val y = List.fill(1000000)(1) y: List[Int] = List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ... scala> y.filter(x => x % 2 == 0) res2: List[Int] = List() ``` Yet it succeeds. Why does the `Stream#filter` run out of memory here, but the `List#filter` completes just fine? Lastly, with a large stream, will `filter` result in the non-lazy evaluation of the entire stream?