Java と Scala の mutable/immutable Map パフォーマンス比較

MapCompetition.scala

import scala.collection._
import java.util._

val maxItems = 0x10000  // スケール調整: 1024,0x10000,0x100000
val div = 32
val random = new scala.util.Random
val loop = 100

def point(i:Int):Boolean = if(i <=1024){
  i % (1024 / div) == 0
} else if(i <= 0x10000){
  i % (0x10000 / div) == 0
} else {
  i % (maxItems / div) == 0
}

case class Case[T](title:String, init:()=>T, len:(T)=>Int, get:(T,Int)=>String, set:(T,Int,String)=>T, add:(T,Int,String)=>T, del:(T,Int)=>T){
  def pfm(op:(T,Int,String)=>Long):Unit = {
    var m = init()
    val h = (0 to maxItems).flatMap{ i =>
      if(len(m) != i){
        throw new IllegalStateException(s"map items count is expected $i, but ${len(m)}");
      }
      m = add(m, i, i.toString)
      if(point(i)){
        System.gc()
        Some((0 to loop).map{ _ =>
          val id = random.nextInt(i+1)
          val v = id.toString
          op(m, id, v)
        }.drop(1).sum / loop.toDouble / 1000.0)
      } else {
        None
      }
    }.mkString(",")
    println(s"$title,$h")
  }
  def pfmGet():Unit = pfm{ (m,i,v) =>
    val t0 = System.nanoTime()
    get(m, i)
    System.nanoTime() - t0
  }
  def pfmSet():Unit = pfm{ (m,i,v) =>
    val t0 = System.nanoTime()
    set(m, i, v)
    System.nanoTime() - t0
  }
  def pfmAdd():Unit = pfm{ (m,i,v) =>
    val m1 = del(m, i)
    val t0 = System.nanoTime()
    add(m1, i, v)
    System.nanoTime() - t0
  }
  def pfmDel():Unit = pfm{ (m,i,v) =>
    val t0 = System.nanoTime()
    val m1 = del(m, i)
    val t = System.nanoTime() - t0
    add(m1, i, v)
    t  
  }
}

// どの組み合わせを比較するか適当にコメントアウト
val cases = Seq(
  Case[java.util.Map[Int,String]]("Java HashMap", ()=>new HashMap[Int,String](), m=>m.size,
    {(m,i)=>m.get(i)}, {(m,i,v)=>m.put(i,v);m}, {(m,i,v)=>m.put(i,v);m}, {(m,i)=>m.remove(i);m}),
  Case[java.util.Map[Int,String]]("Java LinkedHashMap", ()=>new LinkedHashMap[Int,String](), m=>m.size,
    {(m,i)=>m.get(i)}, {(m,i,v)=>m.put(i,v);m}, {(m,i,v)=>m.put(i,v);m}, {(m,i)=>m.remove(i);m}),
  Case[java.util.Map[Int,String]]("Java TreeMap", ()=>new TreeMap[Int,String](), m=>m.size,
    {(m,i)=>m.get(i)}, {(m,i,v)=>m.put(i,v);m}, {(m,i,v)=>m.put(i,v);m}, {(m,i)=>m.remove(i);m}),
  Case[mutable.Map[Int,String]]("Scala mutable.HashMap", ()=>new mutable.HashMap[Int,String](), m=>m.size,
    {(m,i)=>m(i)}, {(m,i,v)=>m.update(i,v);m}, {(m,i,v)=>m.update(i,v);m}, {(m,i)=>m.remove(i);m}),
  Case[mutable.Map[Int,String]]("Scala mutable.LinkedHashMap", ()=>new mutable.LinkedHashMap[Int,String](), m=>m.size,
    {(m,i)=>m(i)}, {(m,i,v)=>m.update(i,v);m}, {(m,i,v)=>m.update(i,v);m}, {(m,i)=>m.remove(i);m}),
  Case[mutable.Map[Int,String]]("Scala mutable.OpenHashMap", ()=>new mutable.OpenHashMap[Int,String](), m=>m.size,
    {(m,i)=>m(i)}, {(m,i,v)=>m.update(i,v);m}, {(m,i,v)=>m.update(i,v);m}, {(m,i)=>m.remove(i);m}),
  Case[immutable.Map[Int,String]]("Scala immutable.HashMap", ()=>new immutable.HashMap[Int,String](), m=>m.size,
    {(m,i)=>m(i)}, {(m,i,v)=>m + ((i,v))}, {(m,i,v)=>m + ((i,v))}, {(m,i)=>m - i}),
  Case[immutable.Map[Int,String]]("Scala immutable.TreeMap", ()=>new immutable.TreeMap[Int,String](), m=>m.size,
    {(m,i)=>m(i)}, {(m,i,v)=>m + ((i,v))}, {(m,i,v)=>m + ((i,v))}, {(m,i)=>m - i})
/*
  // O(n) LinkMap
  Case[mutable.Map[Int,String]]("ListMap", ()=>new mutable.ListMap[Int,String](), m=>m.size,
    {(m,i)=>m(i)}, {(m,i,v)=>m.update(i,v);m}, {(m,i,v)=>m.update(i,v);m}, {(m,i)=>m.remove(i);m})
  // Copied Pseudo-Immutable HashMap
  Case[java.util.Map[Int,String]]("Java HashMap*", ()=>new HashMap[Int,String](), m=>m.size,
    {(m,i)=>m.get(i)}, {(m,i,v)=>val t=new HashMap[Int,String](m);t.put(i,v);Collection.unmodifiableMap(t)}, {(m,i,v)=>val t=new HashMap[Int,String](m);t.put(i,v);Collection.unmodifiableMap(t)}, {(m,i)=>val t=new HashMap[Int,String](m);t.remove(i);Collection.unmodifiableMap(t)})
*/
)

println(s"GET,${(0 to maxItems).filter{ i => point(i) }.mkString(",")}")
cases.foreach{ _.pfmGet() }
println()
println(s"SET,${(0 to maxItems).filter{ i => point(i) }.mkString(",")}")
cases.foreach{ _.pfmSet() }
println()
println(s"ADD,${(0 to maxItems).filter{ i => point(i) }.mkString(",")}")
cases.foreach{ _.pfmAdd() }
println()
println(s"DEL,${(0 to maxItems).filter{ i => point(i) }.mkString(",")}")
cases.foreach{ _.pfmDel() }