Pourquoi Scala HashMap est-il lent?

Et que peut-on faire à ce sujet?

J'ai exécuté quelques tests et il semble que Scala Hashmap soit beaucoup plus lent qu'un HashMap Java. Merci de me prouver le contraire!

Pour moi, tout le but de Hashmap est d'obtenir un accès rapide à une valeur à partir d'une clé donnée. Je me retrouve donc à utiliser un HashMap Java lorsque la vitesse compte, ce qui est un peu triste. Je ne suis pas assez expérimenté pour dire à coup sûr mais il semble que plus vous mélangez Java et Scala plus vous risquez de problèmes face.

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

Est-ce que je manque quelque chose?

Résumé Des Réponses

A partir de Maintenant, lorsque L'on compare Java 8 à Scala 2.11, il semble que Java HashMap est particulièrement plus rapide lors des recherches (pour un faible nombre de clés) que les offres Scala - à l'exception de LongMap (si vos clés sont Ints/Longs).

La différence de performance n'est pas si grande qu'elle devrait avoir de l'importance dans la plupart des cas d'utilisation. Espérons que Scala améliorera la vitesse de leurs cartes. Dans le même temps, si vous avez besoin d' les performances (avec des clés non entières) utilisent Java.

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

Cas des clés d'objet, n=20
Java(195), AnyRef(230)

23
demandé sur MS-H 2015-02-26 17:27:58

2 réponses

Tout d'abord: faire des benchmarks JVM en utilisant nanoTime est extrêmement sujet aux erreurs. Utiliser un microbenchmarking cadre comme Thym, Étrier de ou JMH

Deuxièmement: vous comparez une carte de hachage java mutable avec une carte de hachage scalaimmuable . Les collections immuables peuvent être remarquablement rapides, mais il y a des cas où elles ne seront jamais aussi rapides que les structures de données mutables.

Voici un microbenchmark approprié de java mutable carte de hachage vs. carte de hachage Scala immuable: https://gist.github.com/rklaehn/26c277b2b5666ec4b372

Comme vous pouvez le voir, la carte immuable scala est un peu plus rapide que la carte mutable java. Notez que ce ne sera pas le cas une fois que vous allez sur des cartes plus grandes, car une structure de données immuable doit faire des compromis pour activer partage structurel . Je suppose que dans les deux cas, le problème de performance dominant est la boxe des ints en entier.

Update: si vous avez vraiment vous voulez un hachage hap mutable avec ints comme clés, le bon choix de la bibliothèque de collections scala est scala.collection.mutable.LongMap . Cela utilise une clé long as, et a de bien meilleures performances que la carte générique car elle n'a pas à boxer la valeur. Voir les résultats de l'essentiel.

Update 2: Si votre clé s'étend de AnyRef (comme par exemple une chaîne), votre meilleur pari pour une carte mutable haute performance est scala.collection.mutable.AnyRefMap

28
répondu Rüdiger Klaehn 2015-02-26 16:36:01

Au lieu d'appeler apply c'est-à-dire scalaMap(i), Si vous le faites scalaMap.get(i) alors il est aussi rapide que javaMap.get(i)

De source , le code pour apply est 


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

Qui montre que la méthode apply appelle d'abord la méthode get, puis le modèle correspond à celle-ci. Avoir un saut supplémentaire pour chaque appel dans le cas d'un option a une pénalité de performance et a déjà été discuté sur SO (ne peut pas trouver le lien cependant)

11
répondu mohit 2015-02-26 14:58:08