¿Por qué es lento el hashmap de Scala?

java-8 scala-2.11

Question

¿Y qué se puede hacer al respecto?

He realizado algunas pruebas y parece que Scala Hashmap es mucho más lento que un Java HashMap. ¡Por favor demuéstreme que estoy equivocado!

Para mí, el objetivo principal de Hashmap es obtener acceso rápido a un valor desde una clave determinada. Así que me encuentro recurriendo al uso de un HashMap de Java cuando la velocidad importa, lo cual es un poco triste. No tengo la suficiente experiencia como para decirlo con seguridad, pero parece que cuanto más mezcle Java y Scala, más problemas tendrá.

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")
}

¿Me estoy perdiendo de algo?

Resumen de respuestas

A partir de ahora, al comparar Java 8 con Scala 2.11, parece que Java HashMap es notablemente más rápido en las búsquedas (para un número bajo de claves) que en las ofertas de Scala, con la excepción de LongMap (si sus claves son Ints / Longs).

La diferencia de rendimiento no es tan grande como debería ser importante en la mayoría de los casos de uso. Esperemos que Scala mejore la velocidad de sus mapas. Mientras tanto, si necesita rendimiento (con claves no enteras) use Java.

Teclas int, n = 20
Largo (60), Java (93), Abierto (170), MutableSc (243), ImmutableSc (317)

claves de objetos de caso, n = 20
Java (195), AnyRef (230)

Answer 1

En lugar de llamar a apply es decir, scalaMap(i) , si haces scalaMap.get(i) es tan rápido como javaMap.get(i)

Desde la source , el código para aplicar es

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

lo que muestra que el método de aplicación primero llama al método de get y luego el patrón coincide con él. Tener un salto adicional para cada llamada en caso de que una option tenga una penalización de rendimiento y ya se haya discutido en SO (aunque no puedo encontrar el enlace)

Answer 2

En primer lugar: hacer pruebas de rendimiento de JVM utilizando nanoTime es extremadamente propenso a errores. Utilice un marco de microbenchmarking como Thyme , Caliper o JMH

Segundo: estás comparando un mapa hash java mutable con un mapa hash scala inmutable . Las colecciones inmutables pueden ser notablemente rápidas, pero hay algunos casos en los que nunca serán tan rápidas como las estructuras de datos mutables.

Aquí hay una marca microbiológica adecuada del mapa hash java mutable frente al mapa hash scala inmutable: https://gist.github.com/rklaehn/26c277b2b5666ec4b372

Como puede ver, el mapa inmutable de Scala es un poco más rápido que el mapa mutable de Java. Tenga en cuenta que este no será el caso una vez que vaya a mapas más grandes, porque una estructura de datos inmutables tiene que hacer algunos compromisos para permitir el intercambio estructural . Supongo que en ambos casos, el problema de rendimiento dominante es el boxeo de los ints a Integer.

Actualización: si realmente desea un hash hap mutable con ints como claves, la opción correcta de la biblioteca de colecciones de scala es scala.collection.mutable.LongMap . Esto usa un largo como clave y tiene un rendimiento mucho mejor que el Mapa genérico porque no tiene que encerrar el valor. Ver resultados de la esencia.

Actualización 2: si su clave se extiende desde AnyRef (como, por ejemplo, una cadena), su mejor apuesta para un mapa mutable de alto rendimiento es scala.collection.mutable.AnyRefMap