Friday, January 31, 2014

Performance Evaluation of Scala Maps

Target audience: Beginner

Overview

The Scala programming language API provides developers with a set of short immutable maps of predefined length, Map1, .. Map4,  Set. I thought it would be worthwhile to evaluate the performance of those short,  dedicated collections compare to their generic counterpart.
A second test consists of comparing HashMap with TreeMap for sorting a hash table by key.

Note: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted


Benchmark short maps

The benchmark consists of a very simple methods calls on immutable Map and Map4 instances as well as a mutable HashMap as defined in the code snippet below. 

val map4 = new Map4("0"-> 0, "1" ->1, "2 ->,2, "3"-> 3)

val map0 = Map[String, Int]("0" -> 0, "1" -> 1, "2" -> 2, "3"-> 3)

val hMap = HashMap[String, Int]("0" -> 0, "1" -> 1, "2" -> 2, "3" -> 3)


We evaluate the time needed to execute 10 million iterations of a map, get and sum methods as follows: 

aMap map { kv => kv._2 + 2 }
aMap get("2")
aMap values sum

The results of the performance test is shown in the table below. As expected the "short" collection is faster that the immutable Map and the mutable HashMap. However the performance improvement is not very significant.
Methods immutable.Map.Map4 immutable.Map mutable.HashMap
get 0.835 s 0.879 s 1.091 s
map 7.462 s 7.566 s 1.106 s
foldLeft 3.444 s 3.621 s 4.782 s


Sorting tables: TreeMap vs. sortBy

The second test consists of sorting a very large list or array of tuple (String, Float) by using maps. There are few options to sort a table among them:
  • Creating, populating and sorting a scala.collection.mutable.HashMap
  • Creating and populating a scala.collection.immutable.TreeMap
The test is set-up by creating pseudo-random key by concatenating the name of a city with an unique id. The values in the map are completely random. 

 // Hashmap to be sorted 
val hMap = Range(0, sz)./:(new mutable.HashMap[String, Float])(
  (h, n) =>
      h += (s"${cities(Random.nextInt(cities.size))}_$n", Random.nextFloat )
)
val sortedByKey = hMap.toSeq.sortBy(_._1)

   // TreeMap
val treeMap = Range(0, sz)./:(new immutable.TreeMap[String, Float])(
    (h, n) => 
       h + ((s"${cities(Random.nextInt(cities.size))}_$n",  Random.nextFloat))
)

val sorted = sortedByKey.toSeq


The test is run with map which size varies between 10,000,00 and 90,000,00 entries


Sorting a tuple (String, Float) using TreeMap is roughly 40% faster than populating a HashMap and sort by key.

References

Posted by No comments:
Labels: , , , ,

Monday, January 6, 2014

Scala Zip vs. Zipped

Target audience: Beginner
Estimated reading time: 3'

Overview

It is not unusual that Scala developers struggle in re-conciliating elegant functional programming style with efficient and fast execution. High order collection methods are conducive to very expressive constructs at the cost of poor performance. the zip method is no exception.
   def GenIterable.zip[B](that: GenIterable[B]): CC[(A, B)]
Fortunately, the authors of the Scala library have been diligent enough to provide us with an alternative in the case of the array of pairs (type Tuple2).

Note: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted

scala.Tuple2.zipped

Contrary to the GenIterable.zip method, Tuple2.zipped is a method unique and customized to the class Tuple2.

Let's evaluate the performance of the zipped relative to the ubiquitous zip. To this purpose, let's create a benchmark class to access elements on a zipped array. The first step is to create a function to access the first and last element for zipped arrays.
The first method zip exercises the GenIterable.zip method (line 2). The second method tzipped wraps the Tuple2.zip method (line 7). 

1
2
3
4
5
6
7
8
9
def tzip(x: Array[Double], y: Array[Double]): (Double, Double) = {
    val z = x.zip(y)
   (z.head._1, z.last._2)
}
  
def tzipped(x: Array[Double], y: Array[Double]): (Double, Double) = {
    val z = (x, y).zipped
    (z.head._1, z.last._2)
}

Next we need to create a method that executes the two wrappers _zip and _zipped and measure the duration of their execution. We arbitrary select to sum the first element and the product of the last element of the zipped array.
The function zipTest has three arguments
  • A dataset of type Array[Double] x (line 2)
  • A second dataset y (line 3)
  • A function argument f for the wrapper methods tzip and tzipped (line 4)
The computation consists of computing the sum of elements for the first element of the tuple (line 12) and the product of the second element in the tuple (line 13). 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def zipTest(
  x: Array[Double], 
  y: Array[Double], 
  f: (Array[Double], Array[Double]) => (Double, Double)
): Unit = {
  var startTime = System.currentTimeMillis
  
  var sum = 0.0
  var prod = 1.0
  Range(0, 50).foreach( _ => {
      val res = f(x, y)
      sum += res._1
      prod *= res._2
  })

  println(s"sum=$sum prod=$prod in ${(System.currentTimeMillis - startTime)}")


The last step is to invoke the benchmark method zipTest for different length of arrays. The element of the arrays are random floating point values.. 

1
2 
3
4
5
6
def zipTest(len: Int): Unit = {
    val x =  Array.tabulate(len)(_ => Random.nextDouble)
    val y = x.clone
    zipTest(x, y, _zip)
    zipTest(x, y, _zipped)
}


Performance Results

The test is performed on a single 8-core i7 32-Gbyte host. 

val step = 1000000
val initial = step
Range(0, 6).foreach(n => zipTest(initial + n*step) )


















The results shows that the performance of Array.zip decreases exponentially compared to Tuple2.zipped which has a linear degradation. For 50 iterations on 1 million element arrays, Tuple2.zipped is 17% faster than Array.zip but 280% faster for 8 million elements.

Posted by No comments:
Labels:
Subscribe to: Posts (Atom)