Scala unexpected stack overflow

Question

I've written this basic program in Scala :

import scala.collection.mutable.HashMap

object HelloWorld {

  val treasureMap = new HashMap[BigInt, BigInt]

  def main(args: Array[String]) {
    println(fibCache(10))
  }

  def fibCache(n: BigInt): BigInt = {
    if (n == 0 || n == 1) {
      return n
    }
    return treasureMap.getOrElseUpdate(n, fibCache(n - 1) + fibCache(n - 2))
  }
}

and I would expect that with really large values, I'd have an OutOfMemoryError or something, but instead I see this:

Exception in thread "main" java.lang.StackOverflowError
    at java.math.BigInteger.compareMagnitude(Unknown Source)
    at java.math.BigInteger.compareTo(Unknown Source)
    at scala.math.BigInt.compare(BigInt.scala:141)
    at scala.math.BigInt.$less$eq(BigInt.scala:145)
    at scala.math.BigInt.fitsInLong(BigInt.scala:130)
    at scala.math.BigInt.hashCode(BigInt.scala:120)
    at scala.runtime.BoxesRunTime.hashFromNumber(Unknown Source)
    at scala.collection.mutable.HashTable$HashUtils$class.elemHashCode(HashTable.scala:366)
    at scala.collection.mutable.HashMap.elemHashCode(HashMap.scala:43)
    at scala.collection.mutable.HashTable$class.findEntry(HashTable.scala:108)
    at scala.collection.mutable.HashMap.findEntry(HashMap.scala:43)
    at scala.collection.mutable.HashMap.get(HashMap.scala:63)
    at scala.collection.mutable.MapLike$class.getOrElseUpdate(MapLike.scala:186)
    at scala.collection.mutable.HashMap.getOrElseUpdate(HashMap.scala:43)

Can someone help explain why? Also, is there a runtime setting I can use to alleviate this? Will -Xss help?

Just ran it on my machine (3GB Macbook) with the latest version of scala and it ran as expected. — Brian Gianforcaro
– Brian Gianforcaro, Commented May 15, 2011 at 16:39
32/64 bit, available physical memory, and the -Xss parameter will all affect the exact point at which which the problem occurs, so don't fret about the actual numbers chosen. It's enough to know there will be some point at which this blows up, depending on your configuration. — Kevin Wright
– Kevin Wright, Commented May 15, 2011 at 16:58

Kevin Wright · Accepted Answer · 2011-08-29 15:25:42Z

7

A StackOverflowError is a variation on the theme of running out of memory, it's just being precise about exactly which memory area has run out.

So yes, -Xss will help, but there's a better way....

This page has several alternative implementations that you can try: http://en.literateprograms.org/Fibonacci_numbers_(Scala)

You'll want to use the tail-recursive or stream-based variant to keep the stack size down.

edited Aug 29, 2011 at 15:25

answered May 15, 2011 at 16:42

Kevin Wright

49.7k9 gold badges107 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Amir Afghani Over a year ago

I'm familiar with what a StackOverflow is. When I write this equivalent in Java, it doesn't SO. It runs out of memory before blowing the stack.

Kevin Wright Over a year ago

@Amir the code emitted by Scala tends to lean on the stack a bit more heavily than Java code. Especially if you're writing in a more functional style or adding a couple of levels to the stack by using Scala methods that wrap methods from the Java standard lib. I wouldn't let it worry you.

Babu Srinivasan Over a year ago

How does a tail-recursive implementation keep the stack size down? jvm based languages such as scala, clojure do not do tail call optimization as the jvm doesn't support it.

Daniel C. Sobral Over a year ago

@Babu JVM doesn't do tail call optimization. Scala does.

Kevin Wright Over a year ago

@Babu, @Daniel - To expand on that a bit more... The Scala compiler will recognise the tail-call and emit bytecode that performs a jump to the start of the method, feel free to verify this with a Java decompiler of your choosing. No JVM involvement is required.

|

Collectives™ on Stack Overflow

Scala unexpected stack overflow

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related