Parallel Computing Made Easy With Scala and Akka

The foreseeable future of micro processors is definitely a multi-cored one. This means that individual CPU cores are not going to get much faster. Instead, chip manufactures are adding more CPU cores to each chipset. For example, the laptop I’m writing this tip on has a 2.3 GHz Intel Core i7. The i7 sports 4 CPU cores with Hyper-Threading, which effectively makes it an 8 core CPU. Servers can have even more CPU cores often spread across multiple processors. What this means for software engineers is that writing code that can run in parallel is not a luxury, but a necessity if you need your application to scale.

Prerequisites

Getting Started with Actor Based Programming Using Scala and Akka

Putting A CPU Core to Work

Lets kick things off by solving a rather basic (but computationally expensive) problem, factorials. Many engineers start solving this problem by thinking sequentially via recursion, so lets make a quick program in Scala and see what we can get out of it.

Add the following to your build.sbt* and then put the specified code into a file called **Factorial.scala. Our program starts off simple, we are just making a list of factorials and iterating through them via for-comprehension. Our factor private method is just using simple recursion and pattern matching. Notice that we are specifying the method to return a BigInt. This is because factorials can be quite large and normal Int values can only hold 32 bits of data. When done, run your program with SBT and look at the output.

build.sbt

name := "factorial"

version := "1.0"

scalaVersion := "2.10.4"

val akkaVersion  = "2.3.1"

libraryDependencies ++= Seq(
  "com.typesafe.akka" %% "akka-actor" % akkaVersion
)

Factorial.scala

object Factorial extends App {
  val factorials = List(20, 18, 32, 28, 22, 42, 55, 48)

  for (num <- factorials) {
    println(s"factorial for $num is ${factor(num)}")
  }

  private def factor(num: Int): BigInt = {
    num match {
      case 0 => 1
      case n => n * factor(n - 1)
    }
  }
}

Console Output

factorial for 20 is 2432902008176640000
factorial for 18 is 6402373705728000
factorial for 32 is 263130836933693530167218012160000000
factorial for 28 is 304888344611713860501504000000
factorial for 22 is 1124000727777607680000
factorial for 42 is 1405006117752879898543142606244511569936384000000000
factorial for 55 is 12696403353658275925965100847566516959580321051449436762275840000000000000
factorial for 48 is 12413915592536072670862289047373375038521486354677760000000000

Good to go, we have just generated some Factorials. However, we can do a lot better.

Introducing Tail Recursion

One thing to always keep in mind when using recursion is that each successive call can add a new frame onto the call stack. This can be rather problematic as very large recursions can produce a stack overflow when stack memory runs dry. The way to solve this is by using Tail Recusion to make each function call finish with all the needed state passed into the next function call. Lets optimize our Factorial.scala file.

First, make a new factorTail method which takes two parameters, a number num and an accumulator acc. Things look most interesting when we use the accumulator to close out all calculations and just pass the result into the next function call. As no calculations are waiting for our factorTail function to return, we do not need to track the frame on the call stack and thus save ourselves some memory. We can also use the optional @tailrec Annotation to have the the Scala compiler ensure that our function is tail recursive.

What are Annotations?

In Java and Scala Annotations are metadata that the compiler and runtime can use to infer how a method or class should behave. In our @tailrec example, the Scala compile will throw an error if our method was programmed to not be tail recursive, and thus make our code safer.

We keep our previous factor method and just have it call our new factorTail method with the required defaults. Let’s run the program and see what we get back.

Factorial.scala

import scala.annotation.tailrec

object Factorial extends App {
  val factorials = List(20, 18, 32, 28, 22, 42, 55, 48)

  for (num <- factorials) {
    println(s"factorial for $num is ${factor(num)}")
  }

  private def factor(num: Int) = factorTail(num, 1)

  @tailrec private def factorTail(num: Int, acc: BigInt): BigInt = {
    (num, acc) match {
      case (0, a) => a
      case (n, a) => factorTail(n - 1, n * a)
    }
  }
}

Console Output

factorial for 20 is 2432902008176640000
factorial for 18 is 6402373705728000
factorial for 32 is 263130836933693530167218012160000000
factorial for 28 is 304888344611713860501504000000
factorial for 22 is 1124000727777607680000
factorial for 42 is 1405006117752879898543142606244511569936384000000000
factorial for 55 is 12696403353658275925965100847566516959580321051449436762275840000000000000
factorial for 48 is 12413915592536072670862289047373375038521486354677760000000000

Great, we got the same results while taking advantage of Tail Recursion. This might not be a big win now, but it will be in just a short bit.

Entering the Parallel Universe

Now that we know how to best calculate our factorials with Scala, lets do this efficiently with Akka. After setting our factorials value, make a new ActorSystem. This system value will be used to spawn a new FactorialCollector Actor. Notice how newly spawned Actors can also take parameters when constructed.

Next, lets define our FactorialCollector Actor. As we are using Akka, we can keep our state in check and not worry about Race Conditions. The list variable is initially set to an empty, or Nil list of BigInt numbers. This is where our results will be stored as they are ready. The size variable is also used to keep track of how many factorials are left to process. The collector will then use for-comprehension to spawn a new FactorialCalculator Actor for each number. By spawning a new Actor for each number, our FactorialCollector Actor is able to quickly move work to a group of parallel processors that it supervises. This concept is what makes building parallel software in Akka both very easy an incredibly efficient.

The receive method just waits for each newly spawned FactorialCalculator to phone in with a tuple of the number and calculated factorial, and shuts the system down when no work is left to complete. Finally, just drop our tail call optimized factorial method group into our Actor that will take a number in and send an answer out. When done, run the program and check the output.

Factorial.scala

import scala.annotation.tailrec

import akka.actor.{Actor, ActorLogging, ActorSystem, Props}

object Factorial extends App {
  val factorials = List(20, 18, 32, 28, 22, 42, 55, 48)

  val system = ActorSystem("factorial")

  val collector = system.actorOf(Props(new FactorialCollector(factorials)), "collector")
}

class FactorialCollector(factorials: List[Int]) extends Actor with ActorLogging {
  var list: List[BigInt] = Nil
  var size = factorials.size

  for (num <- factorials) {
    context.actorOf(Props(new FactorialCalculator)) ! num
  }

  def receive = {
    case (num: Int, fac: BigInt) => {
      log.info(s"factorial for $num is $fac")

      list = num :: list
      size -= 1

      if (size == 0) {
        context.system.shutdown()
      }
    }
  }
}

class FactorialCalculator extends Actor {
  def receive = {
    case num: Int => sender ! (num, factor(num))
  }

  private def factor(num: Int) = factorTail(num, 1)

  @tailrec private def factorTail(num: Int, acc: BigInt): BigInt = {
    (num, acc) match {
      case (0, a) => a
      case (n, a) => factorTail(n - 1, n * a)
    }
  }
}

Console Output

[INFO] [akka://factorial/user/collector] factorial for 18 is 6402373705728000
[INFO] [akka://factorial/user/collector] factorial for 20 is 2432902008176640000
[INFO] [akka://factorial/user/collector] factorial for 32 is 263130836933693530167218012160000000
[INFO] [akka://factorial/user/collector] factorial for 28 is 304888344611713860501504000000
[INFO] [akka://factorial/user/collector] factorial for 22 is 1124000727777607680000
[INFO] [akka://factorial/user/collector] factorial for 42 is 1405006117752879898543142606244511569936384000000000
[INFO] [akka://factorial/user/collector] factorial for 55 is 12696403353658275925965100847566516959580321051449436762275840000000000000
[INFO] [akka://factorial/user/collector] factorial for 48 is 12413915592536072670862289047373375038521486354677760000000000

That was quick, but maybe a little too quick. Lets make this a bit more CPU intensive and see parallel execution in action.

Raising The Bars

If you are able to see the usage of your CPU cores on your computer, you probably notice that often a single bar will spike up when you run a processor intensive program. If it is only one bar, then that specific algorithm was only programmed to operate sequentially. With Akka however, making things parallel is easy.

In the Factorial.scala file, change the factorials value to a list of much large numbers, such as:

List(200000, 180000, 320000, 280000, 220000, 420000, 550000, 480000)

Then, comment out the log.info on line 23, as the results will be far to large to just output onto your console. When you are done, go ahead and run the program with SBT and look at your CPU cores in action. If you have 8 cores in your machine, you should see every one spike up. If you have more then 8 cores, go ahead and add a couple more numbers to the list and run it again. You can see the before and after results in the images below.

Before Running

CPU Low

While Running

CPU High

Summary

Building software that runs in parallel can be very tricky. However with Akka, it is much simpler and just as efficient. In this tip, we learned how to spawn and supervise new Actors when we needed them. We also learned about tail recursion and how to keep large computations flowing through our system with the least amount of overhead. These concepts are fundamental to making high performance software that is both safe and easy to refactor.