Каков самый быстрый способ обновления LongMap, HashMap или TrieMap для Scala 2.13 миллионами обновлений?

Question

Цель

У меня есть изменяемая карта [Long, Long] с миллионами записей. Мне нужно сделать много итераций обновлений с миллионами обновлений. Я хотел бы сделать это как можно быстрее.

Задний план

В настоящее время самый быстрый метод - использовать однопоточный mutable.LongMap[Long]. Этот тип оптимизирован для использования в качестве ключа типа Long.

Другие типы карт кажутся медленнее, но, возможно, я реализовал их неправильно, так как безуспешно пытался выполнять обновления одновременно и / или параллельно. Возможно, что параллельное обновление карты на самом деле не происходит или невозможно в Scala.

В порядке от самого быстрого к самому медленному:

1. LongMap[Long] (сверху)
2. TrieMap[Long, Long]
3. ParTrieMap[длинный, длинный]
4. HashMap[Long, Long]
5. ParHashMap[Long, Long]
6. ParMap[Long, Long]

Ничего страшного, если более быстрый метод не изменяем, но я не думаю, что это так. Изменяемая карта, вероятно, лучше всего подходит для этого варианта использования.

Код для генерации тестовых данных и времени теста

import java.util.Calendar
import scala.collection.mutable

object DictSpeedTest2 {

  //helper constants
  val million: Long = 1000000
  val billion: Long = million * 1000

  //config
  val garbageCollectionWait = 3
  val numEntries: Long = million * 10 //may need to increase JVM memory with something like: -Xmx32g
  val maxValue: Long = billion * million // max Long = 9223372036854775807L
                                         // this is       1000000000000000L

  def main(args: Array[String]): Unit = {
    //generate random data; initial entries in a; updates in b
    val a = genData(numEntries, maxValue, seed = 1000)
    val b = genData(numEntries, maxValue, seed = 9999)

    //initialization
    val dict = new mutable.LongMap[Long]()
    a.foreach(x => dict += (x._1 -> x._2))

    //run and time test
    println("start test: " + Calendar.getInstance().getTime)
    val start = System.currentTimeMillis
    b.foreach(x => dict += (x._1 -> x._2)) //updates
    val end = System.currentTimeMillis

    //print runtime
    val durationInSeconds = (end - start).toFloat / 1000 + "s"
    println("end test:  " + Calendar.getInstance().getTime + " -- " + durationInSeconds)
  }

  def genData(n: Long, max: Long, seed: Long): Array[(Long, Long)] = {
    val r = scala.util.Random
    r.setSeed(seed) //deterministic generation of arrays
    val a = new Array[(Long, Long)](n.toInt)
    a.map(_ => (r.nextInt(), r.nextInt()) )
  }
}

Текущее время

LongMap[Long] с приведенным выше кодом завершается в следующее время на моем MacBook Pro 2018:

• ~ 3,5 секунды с numEntries = 10 миллионов
• ~100 секунд с numEntries = 100 миллионов

Answer 1

Если вы не ограничены использованием только карт Scala/Java, то для исключительной производительности вы можете просмотреть сторонние библиотеки, в которых есть карты, специализированные для пар ключ / значение Long/Long.

Вот уже не столь устаревший обзор такого рода библиотек с результатами тестов для пар Int/Int.