为什么Scala hashmap变慢？

Question

那可以做些什么呢？

我已经运行了一些测试,似乎Scala Hashmap比Java HashMap慢得多.请证明我错了!

对我来说,Hashmap的重点是快速访问给定键的值.因此,当速度很重要时,我发现自己会使用Java HashMap,这有点让人伤心.我没有足够的经验肯定地说,但似乎你混合Java和Scala越多,你可能面临的问题就越多.

test("that scala hashmap is slower than java") {
    val javaMap = new util.HashMap[Int,Int](){
      for (i <- 1 to 20)
      put(i,i+1)
    }

    import collection.JavaConverters._
    val scalaMap = javaMap.asScala.toMap

    // check is a scala hashmap
    assert(scalaMap.getClass.getSuperclass === classOf[scala.collection.immutable.HashMap[Int,Int]])

    def slow = {
      val start = System.nanoTime()
      for (i <- 1 to 1000) {
        for (i <- 1 to 20) {
          scalaMap(i)
        }
      }
      System.nanoTime() - start
    }

    def fast = {
      val start = System.nanoTime()
      for (i <- 1 to 1000) {
        for (i <- 1 to 20) {
          javaMap.get(i)
        }
      }
      System.nanoTime() - start
    }

    val elapses: IndexedSeq[(Long, Long)] = {
      (1 to 1000).map({_ => (slow,fast)})
    }

    var elapsedSlow = 0L
    var elapsedFast = 0L
    for ((eSlow,eFast) <- elapses) {
      elapsedSlow += eSlow
      elapsedFast += eFast
    }

    assert(elapsedSlow > elapsedFast)

    val fraction : Double = elapsedFast.toDouble/elapsedSlow
    println(s"slower by factor of: $fraction")
}

我错过了什么吗？

答案摘要

截至目前,在将Java 8与Scala 2.11进行比较时,看起来Java HashMap在查找速度方面(对于少量密钥)的速度明显快于Scala产品 - 除了LongMap(如果你的密钥是Ints/Longs).

性能差异不是很大,在大多数用例中应该都很重要.希望Scala能够提高地图的速度.同时,如果您需要性能(使用非整数键),请使用Java.

Int键,n = 20
Long(60),Java(93),Open(170),MutableSc(243),ImmutableSc(317)

case对象键,n = 20
Java(195),AnyRef(230)

Answer 1

首先:使用nanoTime执行JVM基准测试非常容易出错.使用微基准测试框架,如百里香,卡尺或JMH

第二:您正在将可变的 Java哈希映射与不可变的 scala哈希映射进行比较.不可变集合可以非常快,但在某些情况下它们永远不会像可变数据结构那样快.

这是一个可变的java哈希映射与不可变的scala哈希映射的适当微基准测试:https://gist.github.com/rklaehn/26c277b2b5666ec4b372

如您所见,scala不可变映射比java可变映射快一点.请注意,一旦您转到较大的地图,情况就不会这样了,因为不可变数据结构必须做一些妥协才能实现结构共享.我猜想在这两种情况下,主要的性能问题是将整数加入整数.

更新:如果你真的想要一个带有int作为键的mutable hash hap,那么scala集合库中的正确选择就是scala.collection.mutable.LongMap.这使用long作为键,并且具有比通用Map更好的性能,因为它不必包装该值.查看要点的结果.

更新2:如果您的密钥从AnyRef扩展(例如String),那么高性能可变映射的最佳选择是scala.collection.mutable.AnyRefMap

Answer 2

而不是调用applyie scalaMap(i),如果你这样做,scalaMap.get(i)那就快了javaMap.get(i)

从源代码来看,申请代码是

def apply(key: A): B = get(key) match {
    case None => default(key)
    case Some(value) => value
  }

这表明apply方法首先调用该get方法,然后对其进行模式匹配.如果遇到option性能损失,每次调用都有一个额外的跳,并且已经在SO上讨论过了(虽然找不到链接)