build.sbt

scalaVersion := "2.10.1"

libraryDependencies += "com.github.axel22" %% "scalameter" % "0.4"

testFrameworks += new TestFramework("org.scalameter.ScalaMeterFramework")

parallelExecution in Test := false

MirrorBenchmark.scala

import org.scalameter.api._
import scala.util.Random
import scala.collection.mutable
import scala.collection.mutable.Builder

object MirrorBenchmark extends PerformanceTest.Quickbenchmark {
  val sizes = Gen.range("size")(100, 500, 100)
  val maps = for (sz <- sizes) yield {
    val r = (0 until sz)
    val random = new Random()
    r.map(x => x -> r.map(_ => random.nextInt()).toSet).toSet
  }

  performance of "Set" in {
    measure method "+=" in {
      using(maps) in { xs =>
        var r = Map[Set[Int], Set[Int]]()
        for ((k, v) <- xs) {
          r += (v -> (r.getOrElse(v, Set[Int]()) + k))
        }
        r.toMap
      }
    }
  }

  performance of "Builder" in {
    measure method "+=" in {
      using(maps) in { xs =>
        val r = mutable.Map[Set[Int], Builder[Int, Set[Int]]]()
        for ((k, v) <- xs) {
          r.getOrElseUpdate(v, Set.newBuilder[Int]) += k
        }
        r.mapValues(_.result()).toMap
      }
    }
  }

  performance of "Map" in {
    measure method "groupBy" in {
      using(maps) in { xs =>
        xs.groupBy(_._2).mapValues(_.map(_._1)).view.force
      }
    }
  }

}

output.txt

::Benchmark Set.+=::
Parameters(size -> 10): 0.032
Parameters(size -> 20): 0.056
Parameters(size -> 30): 0.085
Parameters(size -> 40): 0.127
Parameters(size -> 50): 0.196
Parameters(size -> 60): 0.233
Parameters(size -> 70): 0.291
Parameters(size -> 80): 0.35
Parameters(size -> 90): 0.45
Parameters(size -> 100): 0.484

::Benchmark Builder.+=::
Parameters(size -> 10): 0.033
Parameters(size -> 20): 0.064
Parameters(size -> 30): 0.126
Parameters(size -> 40): 0.192
Parameters(size -> 50): 0.298
Parameters(size -> 60): 0.354
Parameters(size -> 70): 0.464
Parameters(size -> 80): 0.551
Parameters(size -> 90): 0.648
Parameters(size -> 100): 0.932

::Benchmark Map.groupBy::
Parameters(size -> 10): 0.051
Parameters(size -> 20): 0.091
Parameters(size -> 30): 0.161
Parameters(size -> 40): 0.228
Parameters(size -> 50): 0.367
Parameters(size -> 60): 0.486
Parameters(size -> 70): 0.597
Parameters(size -> 80): 0.719
Parameters(size -> 90): 0.898
Parameters(size -> 100): 1.211







[info] Running MirrorBenchmark 
::Benchmark Set.+=::
Parameters(size -> 100): 0.372
Parameters(size -> 200): 2.112
Parameters(size -> 300): 6.585
Parameters(size -> 400): 11.716
Parameters(size -> 500): 20.023

::Benchmark Builder.+=::
Parameters(size -> 100): 0.91
Parameters(size -> 200): 6.204
Parameters(size -> 300): 15.557
Parameters(size -> 400): 36.073
Parameters(size -> 500): 59.388

::Benchmark Map.groupBy::
Parameters(size -> 100): 1.237
Parameters(size -> 200): 9.505
Parameters(size -> 300): 21.529
Parameters(size -> 400): 47.332
Parameters(size -> 500): 79.376