Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Poor performance of Array.map(f: A => B) in Scala

Please can someone explain to me, why Array.map(f: A=> B) method is implemented in a such way that it is more than 5 times slower than this code:

val list = Array(1, 2, 3, 4, 5, 6, 7, 8, 9)
val newList = new Array[Int](size)

var j = 0  
while (j < size) {
  newList(j) = list(j)
  j += 1
}

The method map(f: A=> B) in the Array class, which is provided by TraversableLike trait, uses Scala 'for loop' for iterating over the elements of input Array object, which of course is much slower than using 'while loop'.

Scala version: 2.9.2 Java: jdk1.6.0_23 64bit windows

like image 774
Daniel Korzekwa Avatar asked Oct 21 '12 16:10

Daniel Korzekwa


People also ask

What does map () do in Scala?

map() method is a member of TraversableLike trait, it is used to run a predicate method on each elements of a collection. It returns a new collection.

Which is faster array or map?

Also, although the map is O(log N), the big-O conceals a relatively large constant factor, at least for the std::map implementation, in my experience. I would not be surprised to find that the array approach is faster in this case, but again the only way to know for sure is to measure.

How do I convert a list to map in Scala?

To convert a list into a map in Scala, we use the toMap method. We must remember that a map contains a pair of values, i.e., key-value pair, whereas a list contains only single values. So we have two ways to do so: Using the zipWithIndex method to add indices as the keys to the list.


1 Answers

map is a generic operation (and not specialized (yet)). So you have to box/unbox the operations on the way in and out of the function. Unsurprisingly, it's much slower. This, rather than the style of loop used, is the culprit.

The reason it's done this way is for consistency and ease of maintenance of the code. With infinite numbers of infinitely carefully people working on the code, each method would be hand-crafted for optimal speed while still being generic. Generic utility has been favored over speed, as you can always get speed back by writing the while loop by hand, but if it's not generic and you need it to be, you're stuck.

Improving the performance of Scala with operations on primitive collections is a goal, but probably not the very top goal of the team working on Scala. For now, if you need speed, use the while loop.

like image 119
Rex Kerr Avatar answered Oct 05 '22 22:10

Rex Kerr