ListMap and ListSet benchmarks

benchmark.scala

import scala.collection.immutable._
import scala.util.Random

def benchmark[A](desc: String)(block: => A): Option[A] = {
  val t = System.currentTimeMillis()
  try {
    val res = block
    println(s"$desc: took ${System.currentTimeMillis() - t} ms")
    Some(res)
  } catch {
    case e: Throwable =>
      println(s"$desc: ${e.getClass.getSimpleName} thrown after ${System.currentTimeMillis() - t} ms")
      None
  }
}

val dim = 50000
val ops = 500

def createListMap() = benchmark("Create ListMap") {
  ListMap((0 until dim).map(i => (i, i)): _*)
}

def createListSet() = benchmark("Create ListSet") {
  ListSet(0 until dim: _*)
}

val map = createListMap().get
val set = createListSet().get

println(map.take(10))
println(set.take(10))

val toSearch = List.fill(ops)(Random.nextInt(dim * 2))
val toDel = List.fill(ops)(Random.nextInt(dim))

def searchListMap() = benchmark("Search ListMap") {
  toSearch.foreach(map.contains)
}

def searchListSet() = benchmark("Search ListSet") {
  toSearch.foreach(set.contains)
}

def delListMap() = {
  benchmark("Delete ListMap") { toDel.foldLeft(map)(_ - _) }
}

def delListSet() = {
  benchmark("Delete ListSet") { toDel.foldLeft(set)(_ - _) }
}

searchListSet()
searchListMap()
delListSet()
delListMap()

results.txt

Before:

Create ListMap: took 21515 ms
Create ListSet: took 68 ms
Map(0 -> 0, 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5, 6 -> 6, 7 -> 7, 8 -> 8, 9 -> 9)
ListSet(49990, 49991, 49992, 49993, 49994, 49995, 49996, 49997, 49998, 49999)
Search ListSet: took 64 ms
Search ListMap: took 127 ms
Delete ListSet: StackOverflowError thrown after 4 ms
Delete ListMap: took 198 ms

After:

Create ListMap: took 312 ms
Create ListSet: took 59 ms
Map(49990 -> 49990, 49991 -> 49991, 49992 -> 49992, 49993 -> 49993, 49994 -> 49994, 49995 -> 49995, 49996 -> 49996, 49997 -> 49997, 49998 -> 49998, 49999 -> 49999)
ListSet(49990, 49991, 49992, 49993, 49994, 49995, 49996, 49997, 49998, 49999)
Search ListSet: took 80 ms
Search ListMap: took 110 ms
Delete ListSet: took 377 ms
Delete ListMap: took 327 ms