Manu Chadha Manu Chadha - 17 days ago 6
Scala Question

Scala - performance comparison of aggregate vs foldLeft

My understanding is that /: is same as foldLeft and also that aggregate is a faster version of foldLeft if the list is converted into parallel collection using 'par'. If I am correct, why does the following code show that :/ and foldLeft are faster than aggregate used with 'par' on the list.

I am calculating the sum of elements and number of elements of a large list and storing the result in a tuple [Double,Double].

//initial tuple2 (sum,count)

val tsc:Tuple2[Double,Double] = Tuple2(0.0,0.0)

//create a large list
val largeList = List.tabulate(500000)(n=>n*n)

//note time
val time1 = System.currentTimeMillis

//using aggregate without par
largeList.aggregate(tsc) ((tsc,elem) => (tsc._1+elem, tsc._2+1), (tsc1, tsc2)=>((tsc1._1+tsc2._1), (tsc1._2+tsc2._2)))

//note time
val time2 = System.currentTimeMillis

//use aggregate with par

largeList.par.aggregate(tsc) ((tsc,elem) => (tsc._1+elem, tsc._2+1), (tsc1, tsc2)=>((tsc1._1+tsc2._1), (tsc1._2+tsc2._2)))

//note time
val time3 = System.currentTimeMillis

//use /:
(tsc /: largeList)((tsc,elem)=>(tsc._1+elem, tsc._2+1))

//note time
val time4 = System.currentTimeMillis

//use foldLeft
largeList.foldLeft(tsc)((tsc,elem)=>(tsc._1+elem, tsc._2+1))

//note time
val time5 = System.currentTimeMillis

//calcualte time difference
println ("Time without par (millisecond)"+(time2-time1))

println ("Time with par (millisecond)"+(time3-time2))

println ("Time with /: (millisecond)"+(time4-time3))

println ("Time with FoldLeft (millisecond)"+(time5-time4)


I got the following result

result on 1st run

Time without par (millisecond)1198
Time with par (millisecond)1479
Time with /: (millisecond)626
Time with FoldLeft (millisecond)661


result on 2nd run

Time without par (millisecond)703
Time with par (millisecond)581
Time with /: (millisecond)435
Time with FoldLeft (millisecond)423


I am running this in windows 10 using cmd. /: and FoldLeft seem similar in performance and are considerably better than aggregate. Aggregate with par was actually more time consuming in 1st run. Could it be an issue due to 'cmd' (console) in window not being able to leverage multi-threading (just guessing here)

Answer

Several problems. Your data set is really quite small (so the overhead of parallelizing and thread management is significant). Using List means the merge step of your aggregate is O(N) - this seems to be the most significant factor once you increase the dataset size.

Switching to Vector and using a Vector 10 times as large, I get:

Time without par (millisecond)271
Time with par (millisecond)297
Time with /: (millisecond)216
Time with FoldLeft (millisecond)274

which is less dramatic. I was just doing one run, in a Scala worksheet, so seeing a lot of variability in these figures

(I only have a two-core system so the overhead of parallelization is significant compared to the gains, it seems)

Comments