Tuesday, June 25, 2013

Performance of Scala Iterators

Objective
The Scala programming language provides software developers with several options to iterate through the elements of a collection:

• for,while loops
• foreach ( x => f(x)) that iterates through a collection
• map[Y] { f: X => Y) : Collection[Y] that creates a new collection by applying a function f to each element of the collection
• foldLeft[Y] (y : Y)(f : (Y,X)=>Y) : Y) (resp. foldRight[Y] (y : Y)(f : (X,Y)=>Y) : Y) that applies a binary operator to each element of this collection starting left to right (resp. right to left)
This post attempts to quantify the overhead of the most commonly used iterative methods in Scala. One approach is to run those tests without any operation on elements. A more elaborate and time consuming benchmark consists of running multiple tests using several boolean (< !=..) and numeric (+, *, x => sin(x) ..) operators and computes the normalize mean and variance.

Summation test
The test runs are executed on a 'plain vanilla' dual core i3 2.1 Ghz running Linux CentOs 6.0. The first test consists of comparing compare the performance of the different options to traverse a list of Double with size varies from 200,000 to 1,800,000 elements then apply an operation += z to each of its members.
val rGen = new scala.util.Random(System.currentTimeMillis)
var data = List.fill(size)(rGen.nextDouble)
var sum = 0.0
data.foreach( x => sum += z)

sum = 0.0
for ( i <- 0 until data.size)
sum += data(i)

sum = 0.0
var k = 0
while( k < data.size) {
sum += data(k)
k += 1
}

sum = data.foldLeft(0.0)( (x, z) => x + z)

The test is repeated 25 times in order to reduce variance and noise generated by the garbage collector. The first 5 iterations are discarded to avoid the overhead of the initialization of the JVM. The mean value of the execution time for each method is computed for different size of the list from 400,000 to 1,800,000 floating point values. The results of the test are plotted in the graph below. As expected the for loop as the first performance because it is a closure that implements a flatMap and Map (Monad). Although significant faster than the for loop, the while loop is not performing that well. The unit of time on the Y-coordinate is milliseconds

The second test evaluates the overhead of the foreach, map, leftFold and for iterators by traversing the list without any operation
val newList1 = data.foreach( x => x)
val newList2 = data map { x => x}
val newList3 = data.foldLeft[Int](0) ((x : Int,z : Int) => z)
for(i <- 0 until size) { data(i) }

The performance of each relative methods for initializing a list is similar to the operation on large arrays. Once again map is the laggard while the two other functional iterator, foreach and foldLeft have similar performance as for loop. The benchmark is similar to the previous test and time is recorded as the average execution for a variable size of the list in milliseconds.

In summary, the for loop which as a different meaning as in C or Java, should be avoided as an iterative counter and used as a for-comprehensive construct.The fold and reduce are ideal for operations on large data sets. Although very efficient the foreach iterator is not appropriate for this case as it updates a variable (not value) as a side effect.

References
Scala for the Impatient - C. Horstman - Addison-Wesley 2012
github.com/prnicolas

1. your "for-loop" is a very bad example, it is no normal C loop. If you realy wanted to compare C loops against scala iterators you would have to use a while.

like this:
var i = 0
while(i < data.length()){ ...; i += 1}