Scala’s immutable collections can be slow as a snail

6 min readOct 6, 2016

The mutable collections are often faster than the immutable ones because we are working on the same memory addresses. Thus, data will not be copied over and over. In Scala, this problem can be mitigated by reusing objects like some operations in List.

val a = 1 :: Nil
val b = 2 :: a
val c = 3 :: b //List(3, 2, 1)

There is only one instance of list holding the numbers 3, 2, 1. The value `a` has a reference pointed to the last element of the list, and the value `c` has a reference pointed to the head element of the list. Because List is immutable, we cannot alter the value of the list which makes it safe to share the same list to all 3 different values (they just see different part of the list).

Two common data structures that we use almost every day are map and list. Scala Array is mutable; so, we will not talk about it since it is just a sugar-coated Java array.

I used Scalameter for micro benchmark because it is very easy to set up. Here’s the configuration.

val standardConfig = config(
  Key.exec.minWarmupRuns -> 100,
  Key.exec.maxWarmupRuns -> 300,
  Key.exec.benchRuns -> 2000
) withWarmer(new Warmer.Default)

Map

Suppose that we have two case classes holding immutable maps and mutable maps respectively.

case class MapImm(m1: Map[Int, Int], m2: Map[Int, Int], m3: Map[Int, Int])
case class MapMut(m1: mutable.Map[Int, Int], m2: mutable.Map[Int, Int], m3: mutable.Map[Int, Int])

Let’s create a range “val range = (1 to 1000)”, and use foldLeft to put each number in the range to the maps.

val timeMap1 = standardConfig measure {
  range.foldLeft(MapImm(Map.empty, Map.empty, Map.empty)) { 
    (o, i) => MapImm(o.m1 + (i -> i), 
                     o.m2 + (i -> (i + 1)), 
                     o.m3 + (i -> (i + 2)))
  }
}val timeMap2 = standardConfig measure {
  val l1 = mutable.Map.empty[Int, Int]
  val l2 = mutable.Map.empty[Int, Int]
  val l3 = mutable.Map.empty[Int, Int]
  range.foreach { i =>
    l1 += (i -> i)
    l2 += (i -> (i + 1))
    l3 += (i -> (i + 2))
  }
  MapMut(l1, l2, l3)
}val timeMap3 = standardConfig measure {
  val l1 = mutable.Map.empty[Int, Int]
  val l2 = mutable.Map.empty[Int, Int]
  val l3 = mutable.Map.empty[Int, Int]
  range.foreach { i =>
    l1 += (i -> i)
    l2 += (i -> (i + 1))
    l3 += (i -> (i + 2))
  }
  MapImm(l1.toMap, l2.toMap, l3.toMap)
}

You can tell that the mutable one is faster than the immutable one. We just want to know whether it is significantly faster. The interesting one is timeMap3 which uses mutable data, and converts to immutable at the end.

Immutable Map (timeMap1): 0.4476 ms
Mutable Map (timeMap2): 0.1412 ms
Immutable Map converted from Mutable Map (timeMap3): 0.6572 ms

Obviously, we should use immutable map even though it is 3 times slower than the mutable map. 0.3 ms difference is too small to consider. If you’re developing a real-time system, this number is not considered small. But, seriously, if you’re working on a real-time where 0.3 ms is considered significant, you should not pick Scala in the first place. The toMap function costs 0.5 ms which makes the total time higher than operating on the immutable map.
If you look into the implementation of toMap function, you will see that it creates a brand new immutable Map. That’s why it took 0.5 ms.

def toMap[T, U](implicit ev: A <:< (T, U)): immutable.Map[T, U] = {
  val b = immutable.Map.newBuilder[T, U]
  for (x <- self)
    b += x
  b.result()
}

List

Let’s take a look at List, another commonly used data structure.

case class ListImm(l1: List[Int], l2: List[Int], l3: List[Int])
case class ListMut(l1: mutable.MutableList[Int], l2: mutable.MutableList[Int], l3: mutable.MutableList[Int])val timeList1 = standardConfig measure {
  range.foldLeft(ListImm(List.empty, List.empty, List.empty)) { 
    (o, i) =>
    ListImm(o.l1 :+ i, o.l2 :+ (i + 1), o.l3 :+ (i + 2))
  }
}val timeList2 = standardConfig measure {
  val l1 = mutable.MutableList.empty[Int]
  val l2 = mutable.MutableList.empty[Int]
  val l3 = mutable.MutableList.empty[Int]
  range.foreach { i =>
    l1 += i
    l2 += (i + 1)
    l3 += (i + 2)
  }
  ListMut(l1, l2, l3)
}val timeList3 = standardConfig measure {
  val l1 = mutable.MutableList.empty[Int]
  val l2 = mutable.MutableList.empty[Int]
  val l3 = mutable.MutableList.empty[Int]
  range.foreach { i =>
    l1 += i
    l2 += (i + 1)
    l3 += (i + 2)
  }
  ListImm(l1.toList, l2.toList, l3.toList)
}

Immutable List (timeList1): 15.8006 ms
Mutable List (timeList2): 0.0436 ms
Immutable List converted from Mutable List (timeList3) : 0.0871 ms

The immutable list performed slower than the mutable one 362 times. That’s scary when you know that N is just 1,000. How bad will it perform if we increase N to 2,000?

Immutable List: 67.1715 ms
Mutable List: 0.1117 ms
Immutable List converted from Mutable List: 0.2081 ms

Now the gap is even wider. The immutable list is slower than the mutable one by 610 times!!!

Rules of thumbs
When you are dealing with a big List, you probably want to use a mutable List and convert it to an immutable one at the end. Just make sure that you don’t share your mutable data.

The important thing I have to mention is that we did benchmark on the append operation. Scala List is implemented as singly linked list, the append operation costs linear time. If you want to learn about the runtime characteristics of Scala collections, this blog post, created by Li Haoyi, is very good and very detailed.

We know that the cons :: operation takes constant time. It’s lighting fast because we simply add the element to the head of the list. Based on this fact, let’s do something interesting.

We will benchmark the append function again. But, this time we will use :: (prepend) and reverse on the immutable List to get the same result as the append function. I’m pretty sure that the benchmark result will surprise you :)

val time1 = standardConfig measure {
  val l = mutable.MutableList.empty[Int]
  range.foreach { i => l += i}
  l
}
val time2 = standardConfig measure {
  val l = mutable.MutableList.empty[Int]
  range.foreach { i => l += i}
  l.toList
}
val time3 = standardConfig measure {
  range.foldLeft(List.empty[Int]){ (l, i) => l :+ i }
}
val time4 = standardConfig measure {
  range.foldLeft(List.empty[Int]){ (l, i) => i::l }.reverse
}

Mutable List (time1): 0.0166 ms
Immutable List converted from Mutable List (time2): 0.0211 ms
Immutable List (time3): 4.2307 ms
Immutable List (cons + reverse) (time4): 0.0285 ms

Note that the reverse function also uses :: operation. The implementation uses an imperative approach using while loop and two temporary variables for performance reasons. What it does is just changing the direction of pointers in the singly linked list. Even though the reverse operation takes O(n), the actual performance is amazingly good.

If you don’t want to call a reverse function, you can use foldRight instead.
range.foldRight(List.empty[Int]){ (i, l) => i::l }
Usually, we prefer foldLeft to foldRight if the order doesn’t matter because foldRight does reverse before calling foldLeft behind the scenes.
Here is the implementation of foldRight function.

def foldRight[B](z: B)(op: (A, B) => B): B =
  reversed.foldLeft(z)((x, y) => op(y, x))

Conclusion:
It’s not that Scala collections are slow, but the type of collection does really matter. Singly linked list takes O(n) for get and append operation. If you want a constant time for a random access (accessing by index), you probably want to use IndexedSeq instead of List or Seq. Scala cannot reuse the existing list when you do append. That’s another reason why the mutable one is much faster. Scala gives you the power of both worlds (functional and imperative), but it also lets you shoot yourself in the foot if you don’t know how to use it effectively and efficiently (this applies to almost anything actually).

Scala’s immutable collections can be slow as a snail

Map

List

Written by Hussachai Puripunpinyo

Responses (4)