Scala's .map() function on a immutable and mutable maps

Question

When calling .map() on a map of a large length, which will be faster

1. Calling it on a mutable map
2. Calling it on a immutable map
3. Or it will not make a difference

Answer 1

Let's just check it (of course, microbenchmark results should always be taken with a grain of salt).

Using Scalameter:

// build.sbt

scalaVersion := "2.11.4"

libraryDependencies ++= Seq(
    "com.storm-enroute" %% "scalameter" % "0.6"
)

// src/main/scala/main.scala

import org.scalameter.api._
import scala.collection.immutable
import scala.collection.mutable

object RangeBenchmark extends PerformanceTest.Quickbenchmark {
  val sizes = Gen.range("size")(100000, 500000, 100000)

  val immutableMaps = for {
    size <- sizes
  } yield immutable.Map((0 until size).map(n => n -> (size-n)).toSeq: _*)

  val mutableMaps = for {
    size <- sizes
  } yield mutable.Map((0 until size).map(n => n -> (size-n)).toSeq: _*)

  performance of "immutable.Map" in {
    measure method "map" in {
      using(immutableMaps) in { m => m.map { case (k, v) => (k+1, v+1) } }
    }
  }

  performance of "mutable.Map" in {
    measure method "map" in {
      using(mutableMaps) in { m => m.map { case (k, v) => (k+1, v+1) } }
    }
  }
}

Running (sbt run):

... lots of output ...

::Benchmark immutable.Map.map::
cores: 4
jvm-name: OpenJDK 64-Bit Server VM
jvm-vendor: Oracle Corporation
jvm-version: 24.65-b04
os-arch: amd64
os-name: Linux
Parameters(size -> 100000): 40.95331
Parameters(size -> 200000): 90.12223
Parameters(size -> 300000): 139.716564
Parameters(size -> 400000): 208.114459
Parameters(size -> 500000): 254.876849

... lots of output ...

::Benchmark mutable.Map.map::
cores: 4
jvm-name: OpenJDK 64-Bit Server VM
jvm-vendor: Oracle Corporation
jvm-version: 24.65-b04
os-arch: amd64
os-name: Linux
Parameters(size -> 100000): 24.004582
Parameters(size -> 200000): 52.941946
Parameters(size -> 300000): 66.036803
Parameters(size -> 400000): 113.575799
Parameters(size -> 500000): 119.544183

Apparently, mutable map is almost exactly two times faster. My guess is that this happens because of a difference in map Builders: immutable map builder is a var which is updated with each added element, while mutable map builder is the mutable map itself. Consequently, with large map sizes, immutable map builder causes more allocations. This is really a wild guess, so maybe someone more knowledgeable would give the correct reason.