[SOLVED] Heap Space with mutable.HashMap

Heap Space with mutable.HashMap

I'm generating a HashMap where I can estimate the requiered size, for factorials:

  import scala.collection.mutable.HashMap

  val mm = new HashMap [Int, BigInt] 
  mm.put (0, 1)
  def fak (i: Int) : BigInt = mm.getOrElseUpdate (i, i * fak (i-1))

I frequently request the factorial (fak) of primes in ascending order, and like to reach pretty high values (> 10 Mio factorials).

Calling it with about 70000 results in an OutOfMemory-Error: Java Heap Space. I started the program with

scala -J-Xmx4G TestFak 70000

With 60000 as parameter it works. I guess, it builds 70000 MutableMaps which get frequently thrown away and garbage collected. Since I know the requiered size in advance, is it possible to generate a mutableMap of the right size from start?

The error is thrown in the mm.getOrElseUpdate - Line.

Version: Scala version 2.11.6 (OpenJDK 64-Bit Server VM, Java 1.8.0_66-internal)

Solution

The factorial of 70000 is huge! The BigInt required to store that is going to be fairly large in and of itself! Just to give you an idea, the BigInt is probably backed by an Array[Int] in Java. That means the total size required to store 1!, 2!, ..., 70000! is going to be sum_(1 to n) of 4 * log_(2^32) n! for n = 70000, which is on the order of four gigabytes.