michau michau - 2 months ago 6
Scala Question

OutOfMemoryError in a Fibonacci stream in Scala

When I define

fib
like this (1):

def fib(n: Int) = {
lazy val fibs: Stream[BigInt] = 0 #:: 1 #:: fibs.zip(fibs.tail).map{n => n._1 + n._2}
fibs.drop(n).head
}


I get an error:

scala> fib(1000000)
java.lang.OutOfMemoryError: Java heap space


On the other hand, this works fine (2):

def fib = {
lazy val fibs: Stream[BigInt] = 0 #:: 1 #:: fibs.zip(fibs.tail).map{n => n._1 + n._2}
fibs
}

scala> fib.drop(1000000).head
res17: BigInt = 195328212...


Moreover, if I change the stream definition in the following way, I can call
drop(n).head
within the function and don't get any error either (3):

def fib(n: Int) = {
lazy val fibs: (BigInt, BigInt) => Stream[BigInt] = (a, b) => a #:: fibs(b, a+b)
fibs(0, 1).drop(n).head
}

scala> fib(1000000)
res18: BigInt = 195328212...


Can you explain relevant differences between (1), (2) and (3)? Why does (2) work, while (1) does not? And why don't we need to move
drop(n).head
out of the function in (3)?

Answer

In the first case reference to the beginning of fibs stream exists while element number n is calculated - thus all values from 0 to 1000000 have to be kept in memory. This is the source of OutOfMemoryError.

In the second case reference to beginning of stream is not preserved anywhere, so items can be garbage collected (only one item at a time have to be kept in memory).

In the third case reference to beginning of stream does not exists anywhere explicitly (it can be garbage collected while next values are dropped). However if we change it into:

def fib(n: Int) = {
  lazy val fibs: (BigInt, BigInt) => Stream[BigInt] = (a, b) => a #:: fibs(b, a+b)
  val beg = fibs(0, 1)
  beg.drop(n).head
}

Then OutOfMemoryError will occur again.