Для Scala 2.13, какой самый быстрый способ обновления LongMap, HashMap или TrieMap с миллионами обновлений? - PullRequest
Новая
       42

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

1 голос
/ 17 октября 2019

Цель

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

Фон

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

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

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

  1. LongMap [Long] (сверху)
  2. TrieMap [Long, Long]
  3. ParTrieMap [Long, Long]
  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 миллионов

1 Ответ

2 голосов
/ 18 октября 2019

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

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

...