optimization - Why does a small change to this Scala code make such a huge difference to performance?

Question

I'm running on a 32-bit Debian 6.0 (Squeeze) system (a 2.5 GHz Core 2 CPU), sun-java6 6.24-1 but with the Scala 2.8.1 packages from Wheezy.

This code, compiled with scalac -optimise, takes over 30 seconds to run:

object Performance {

  import scala.annotation.tailrec

  @tailrec def gcd(x:Int,y:Int):Int = {
    if (x == 0)
      y 
    else 
      gcd(y%x,x)
  }

  val p = 1009
  val q = 3643
  val t = (p-1)*(q-1)

  val es = (2 until t).filter(gcd(_,t) == 1)
  def main(args:Array[String]) {
    println(es.length)
  }
}

But if I make the trivial change of moving the val es= one line down and inside the scope of main, then it runs in just 1 second, which is much more like I was expecting to see and comparable with the performance of equivalent C++. Interestingly, leaving the val es= where it is but qualifying it with lazy also has the same accelerating effect.

What's going on here? Why is performing the calculation outside function scope so much slower?

Answer 1

The JVM doesn't optimize static initializers (which is what this is) to the same level that it optimizes method calls. Unfortunately, when you do a lot of work there, that hurts performance--this is a perfect example of that. This is also one reason why the old Application trait was considered problematic, and why there is in Scala 2.9 a DelayedInit trait that gets a bit of compiler help to move stuff from the initializer into a method that's called later on.

---

(Edit: fixed "constructor" to "initializer". Rather lengthy typo!)