Почему Scala hashmap медленный?

И что можно сделать с этим?

Я провел несколько тестов, и кажется, что 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
Длинные (60), Java (93), Open (170), MutableSc (243), ImmutableSc (317)

ключи объекта объекта, n = 20
Java (195), AnyRef (230)

Ответы

Ответ 1

Прежде всего: выполнение тестов JVM с использованием nanoTime чрезвычайно подвержено ошибкам. Используйте инфраструктуру microbenchmarking, такую ​​как Thyme, Caliper или JMH

Во-вторых: вы сравниваете изменчивую карту хэша java с неизменяемой картой хэша scala. Неизменяемые коллекции могут быть замечательно быстрыми, но есть случаи, когда они никогда не будут такими быстрыми, как изменяемые структуры данных.

Вот правильный микрообъект изменчивой хэш-карты java и неизменяемой картой хэша scala: https://gist.github.com/rklaehn/26c277b2b5666ec4b372

Как вы можете видеть, неизменяемая карта scala немного быстрее, чем измененная java-карта. Обратите внимание, что это не так, если вы перейдете на более крупные карты, потому что неизменная структура данных должна сделать некоторые компромиссы, чтобы включить структурный обмен. Я бы предположил, что в обоих случаях доминирующей проблемой производительности является бокс ints для Integer.

Обновление: если вы действительно хотите изменить hash hap с помощью ints в качестве ключей, правильный выбор из библиотеки коллекций scala scala.collection.mutable.LongMap. Это использует длинный ключ и имеет гораздо лучшую производительность, чем общая карта, потому что она не должна указывать значение. См. Результаты из текста.

Обновление 2: Если ваш ключ простирается от AnyRef (например, String), лучшим вариантом для высокопроизводительной изменчивой карты является scala.collection.mutable.AnyRefMap

Ответ 2

Вместо вызова apply i.e 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 (не могу найти ссылку, хотя)

Ответ 3

Scala 2.13 (июнь 2019 г.) представляет новые, более быстрые реализации HashMap/Set

И неизменяемая (d5ae93e), и изменяемая (# 7348) версии были полностью заменены. - Они существенно превосходят старые реализации в большинстве сценариев. - Изменяемые версии теперь работают наравне с реализациями стандартной библиотеки Java.

Для неизменных HashSet и HashMap:

Переопределения основаны на деревьях префиксированных сжатых хэш-массивов (CHAMP).

См. Статью "Оптимизация картографических попыток с использованием хеш-массива для быстрых и постных неизменных коллекций JVM" Steindorfer и Vinju (OOPSLA'15) для получения дополнительной информации и описания низкоуровневых оптимизаций производительности (доступна предварительная печать статьи).