CODEWITHSUNDEEP
scalafunctional-programmingstreamfibonacci
kxmh42
kxmh42

Reputation: 3830

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)?

Upvotes: 1

Views: 136

Answers (1)

Marcin Sucharski
Marcin Sucharski

Reputation: 1231

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.

Upvotes: 5

Related Questions