Second attempt to shoot myself in the foot; Scala

In this blogpost I will use Scala to solve the exact same problem I described in my previous blogpost:
write a program that given G produces sequences of numbers x, x+1, x+2..., x+n such that G = sum(x, x+1...x+n).

Scala currently is at the center of attention and rightly so. Scala allows for massively parallel and fault-tolerant computing. It supports both object-orientation and functional programming and produces code for Java's Virtual Machine, a highly optimized and robust runtime. No surprise more and more companies adopt Scala.

Looking at Scala one thing becomes obvious. Martin Odersky and his team are clearly heading in the right direction. Previous attempts at tools for massively parallel computing —Occam and Erlang among others— never became generally adopted. Chances are that Scala will become a mainstream language, as it is already adopted for production by companies like Twitter, LinkedIn, UBS, CSC and others.

So here's my attempt using Scala:


import scala.annotation.tailrec
object FindRangeWithSum { 
  def find(goal:Int):List[(Int,Int)] = { 

    @tailrec    def scan(tail:Int, head:Int, sum:Int, goal:Int, 
             accu: List[(Int, Int)]):List[(Int, Int)] = { 
      if (tail + head > goal) 
        accu 
      else if (sum < goal) 
        scan(tail, head+1, sum+head+1, goal, accu) 
      else if (sum > goal) 
        scan(tail+1, head, sum-tail, goal, accu) 
      else /*(sum == goal)*/ 
        scan(tail+1, head, sum-tail, goal, (tail, head):: accu) 
    } 
    scan(1, 2, 3, goal, List()) 
  } 
}

import Profiling._
object RangeFinder extends App { 
  val data = timed(printTime("Execution took: ")) {
    val list = FindRangeWithSum.find(10000)
    println(list)
  }

}

scala.annotation.tailrec provides an annotation that checks wether a method allows for tailrec elimination. A method annotated with @tailrec is checked to be tail recursive. If not, the compiler issues a warning. Compared to Erlang that's a better. While this problem is simple there are a lot of situations where tail-recursion is a lot less obvious.

By the way, if you're interested in experimenting with this code you need to pickup the profiling code written by Matthias Mann.

Now to the performance of this code. This will run within the JVM which uses JIT (Just In Time compilation). JIT is known to have a startup delay. I've been tinkering around firing the code with different values for goal. For most values for goal the Erlang example outperformed the Scala implementation by a wide margin where the Scala code never came in the range of micro seconds. Only for goal = 1.000.000.000 the Scala code outperformed the Erlang implementation.

To do justice to the JVM and the effort a lot of bright minds put into JIT, I modified the code:

object RangeFinder extends App {
  for (runs <- 0 to 1) {
    for (x <- 1 to 9) {
      val data = timed(printTime(" Execution took: ")) {
        val list = FindRangeWithSum.find(math.pow(10, x).toInt)
        print("10^" + x)
      }
    }
  }
}

This lead to remarkable results that definitely confirm the startup delay of JIT.  When warming up JIT by repeating the code, Scala outperforms Erlang for almost every value for goal.

10^1 Execution took: 12ms 858us 0ns
10^2 Execution took: 33us 0ns
10^3 Execution took: 59us 0ns
10^4 Execution took: 356us 0ns
10^5 Execution took: 4ms 261us 0ns
10^6 Execution took: 3ms 79us 0ns
10^7 Execution took: 32ms 903us 0ns
10^8 Execution took: 307ms 669us 0ns
10^9 Execution took: 2s 969ms 420us 0ns
10^1 Execution took: 35us 0ns
10^2 Execution took: 21us 0ns
10^3 Execution took: 23us 0ns
10^4 Execution took: 49us 0ns
10^5 Execution took: 316us 0ns
10^6 Execution took: 2ms 977us 0ns
10^7 Execution took: 29ms 556us 0ns
10^8 Execution took: 298ms 727us 0ns
10^9 Execution took: 2s 977ms 928us 0ns

This shows Scala clearly outperforms the Erlang implementation. And by a wide margin. Note the 3 seconds for goal = 1,000,000,000. It took the Erlang version 2 minutes to complete.

Let me try to put these results into perspective. With 'one-shot' execution, Erlang outperforms Scala by a wide margin. But when code executes repeatedly, Scala really shines and Erlang is -let's be fair- no match. Now try to imagine what will happen in a situation where an application is comprised of hundreds or possibly thousands of SCP's (Sequential Communicating Processes). Each of these processes complete a distinct and hopefully well defined and simple task.

The larger the load on such a system, the more Scala and JIT will shine and the more it will outperform an equivalent implementation in Erlang. Until now Erlang used to be in a class of it's own when it came to applications under heavy load. In a shoot out between Apache and YAWS (a web server implemented in Erlang), YAWS was still functioning at over 80,000 parallel connections. Apache died when subject to a load of 4,000 parallel connections. Check the Apache vs Yaws report for further details.

In a similar setup for Erlang vs. Scala my money definitely would be on Scala. I didn't dive into Akka yet, but the information I've seen until now gives me confidence that Scala, accompanied by frameworks like Akka and Play will be a winning combination for those who have the guts to dare. Especially Play is worth noting since it combines the strengths of Node.js (asynchronous I/O) with those of Erlang (massively parallel processing).