Scala and Akka actors with Prime Sieves

I had the chance to develop the problem of prime sieves in Scala. I took two approaches; (1) Scala Actors and (2) Akka Actors in Scala. The code for both is quite similar.

Scala version

import scala.actors.Actor

case class sieve(n: Int)
case class finish(n: Int)

class Sieve(val p: Int) extends Actor {

  var next: Sieve = null

  def _sieve(n: Int) = {
    if (isPrime(n)) {
      if (next != null) {
        next ! sieve(n)
      } else {
        next = new Sieve(n)
        next.start
        //println(n + " is prime")
      }
    }
  }

  private def isPrime(n: Int): Boolean = {
    val d = n / p
    val r = n - d * p
    if (r != 0) true else false
  }

  def act = {
   loop {
   react {
case sieve(n: Int) => _sieve(n)
case finish(n: Int) => {
if (next != null) {
next ! finish(n)
} else {
val time = System.currentTimeMillis - Main.start
println(n + "," + time)
// System.exit(0)
}
}
   }
   }
  }

}

object Generator {

  def generate(n: Int): Unit = {
    val p2 = new Sieve(2)
    p2.start
    for (i <- 3 to n) {
     p2 ! sieve(i)
    }
    p2 ! finish(n)
  }
}

object Main {

  var start = System.currentTimeMillis

  def main(args: Array[String]): Unit = {
for (i <- 1 to 10) {
start = System.currentTimeMillis
Generator.generate(i * 20000)
}
  }
}

Akka version

import akka.actor._
import akka.actor.Actor._

case class sieve(n: Int)
case class finish(n: Int)

class SieveAkka(val p: Int) extends Actor {

  var next: ActorRef = null

  def _sieve(n: Int) = {
    if (isPrime(n)) {
      if (next != null) {
        next ! sieve(n)
      } else {
        next = actorOf(new SieveAkka(n))
        next.start
        // println(n + " is prime")
      }
    }
  }

  private def isPrime(n: Int): Boolean = {
    val d = n / p
    val r = n - d * p
    if (r != 0) true else false
  }

  def receive = {
    case sieve(n: Int) => _sieve(n)
    case finish(n: Int) => {
     if (next != null) {
     next ! finish(n)
     } else {
     val time = System.currentTimeMillis - MainAkka.start
     println(n + "," + time)
     // System.exit(0)
     }
    }
    
  }

}

object GeneratorAkka {

  def generate(n: Int): Unit = {
    val p2 = actorOf(new SieveAkka(2))
    p2.start
    for (i <- 3 to n) {
     p2 ! sieve(i)
    }
    p2 ! finish(n)
  }
}

object MainAkka {

var start = System.currentTimeMillis

def main(args: Array[String]): Unit = {
for (i <- 10 to 10) {
start = System.currentTimeMillis
GeneratorAkka.generate(i * 20000)
}
}
}

Then I performed executions of the applications for n = 20`000-200`000. I used a dual core machine with 2GB of main memory. The performance of Akka is quite interesting. I also monitored the executions with VisualVM and it turned out for the execution Akka uses at most 28 threads for all the actors.

Scala vs Akka in prime sievesIt’s very interesting to see how this can be explained that the time for computations gradually converge. I think this is an observation on how Scala/Akka actors are scalable; i.e. when the number of actors increase, the cost of resources/computations are affected in the same order.

Update on 02/21/2012. I took another approach in running the examples. Instead of having a main loop to generate all the prime sieves, each time the program was passed an argument to generate the prime sieves for. It turned out that the results now make more sense, however, I have no idea on how this could change this behavior. A snapshot of the Akka performance is as follows which complies with being close to exponential growth.

Akka performance for prime sieves with N=3.8M

Leave a Reply

Your email address will not be published. Required fields are marked *