Jesteś tutaj

Koszt niezmienności - mini benchmark map w Scali

Karty podstawowe

Kolekcje w bibliotece standardowej Scali można podzielić z grubsza na dwie grupy: modyfikowalne (ang. mutable) i niezmienne (ang. immutable). Modyfikowalne to takie, których stan można dowolnie zmieniać, a niezmienne to takie, które raz utworzone zawsze mają dokładnie taką samą zawartość. Główną zaletą kolekcji niezmiennych jest to, że można ich używać w środowisku wielowątkowym bez żadnej synchronizacji (służą tylko do odczytu). Główną ich wadą natomiast jest to, że nie jest tak łatwo je aktualizować (aktualizacja polega na utworzeniu nowej kolekcji, która zawiera starą kolekcję powiększoną/pomniejszoną o dodatkowe/zbędne elementy). Wady tej nie mają kolekcje modyfikowalne, no ale nie mają też wspomnianej zalety dotyczącej wielowątkowości. Postanowiłem sprawdzić, jaki jest koszt niezmienności.

Mój mały eksperyment polegał na zmierzeniu czasu, jaki jest potrzebny do zapełnienia HashMapy 100.000 wartościami typu Int, a następnie odczytu tych wartości. Pod uwagę wziąłem trzy kolekcje:

  • scala.collection.mutable.HashMap
  • scala.collection.immutable.HashMap
  • java.util.HashMap

Czynność testowa została powtórzona 70 razy, z czego pierwsze 20 wyników zostało odrzuconych - to po to, żeby optymalizator bytecodu zrobił użytek ze statystyk wykonania programu (nie wiem co prawda, czy zrobił, ale to już inna historia).

Program testowy został odpalony z następującymi parametrami:


-server -Xms1024M -Xmx1024M -Xmn512M -XX:-PrintGC

Kilka razy upewniałem się, że Garbage Collection nie przeprowadza pełnego odśmiecania z zatrzymaniem świata (-verbose:gc) - nie przeprowadził. Wyniki testu:

----------------put only----------------
Mutable took 1539, immutable took 3169, java took: 1908
Mutable is 2.06x faster than immutable.
Mutable is 1.24x faster than java.
Java is 1.66x faster than immutable.
----------------put & get----------------
Mutable took 2127, immutable took 5332, java took: 2554
Mutable is 2.51x faster than immutable.
Mutable is 1.20x faster than java.
Java is 2.09x faster than immutable.
----------------get----------------
Mutable took 1450, immutable took 1896, java took: 1506
Mutable is 1.31x faster than immutable.
Mutable is 1.04x faster than java.
Java is 1.26x faster than immutable.

Wychodzi na to, że implementacja niezmiennej HashMapy w Scali jest ponad 2 razy wolniejsza od swojego modyfikowalnego odpowiednika przy zapisie. Odczyt z takiej mapy jest o ~25% wolniejszy niż z modyfikowalnej. Jest to w sumie świetny wynik wynikający z zastosowania algorytmu hash trie i unikania kopiowania całej struktury przy każdej zmianie. Modyfikowalna HashMapa Scali wypadła w tym teście lepiej niż java.util.HashMap (dla dużych map, dla małych map javowa hashmapa wypada szybciej).

Co z tego wynika?

Scala nie jest typowym językiem funkcyjnym. Kilka typowych dla tego podejścia zasad można w Scali złamać (patrz: var, collection.mutable). Jak widać na przykładzie HashMapy złamanie sztywnych zasad paradygmatu funkcyjnego może skutkować zwiększeniem wydajności. Oczywiście, źle zastosowane kolekcje modyfikowalne mogą również skutkować błędami i nieprzewidywalnymi wynikami w środowisku wielowątkowym... no ale jak mawiał Spiderman: "With great power comes great responsibility". Dobrze natomiast, moim zdaniem, że mamy możliwość wyboru.

Kod benchmarku

  1. import scala.util.Random
  2. import scala.collection.mutable.ArrayBuffer
  3.  
  4. object MapBenchmark {
  5.  
  6. val count = 100000
  7. val rampup = 20
  8. val iterations = 50
  9.  
  10. def main(args: Array[String]): Unit = {
  11. val data = createData
  12.  
  13. benchmark("put only",
  14. mutableHashMapTest(data, false),
  15. immutableHashMapTest(data, false),
  16. javaHashMapTest(data, false),
  17. rampup, iterations)
  18.  
  19. benchmark("put & get",
  20. mutableHashMapTest(data, true),
  21. immutableHashMapTest(data, true),
  22. javaHashMapTest(data, true),
  23. rampup, iterations)
  24.  
  25. var immutableMap = new scala.collection.immutable.HashMap[Int, Int]()
  26. for (i <- data) immutableMap += (i -> i)
  27.  
  28. val mutableMap = new scala.collection.mutable.HashMap[Int, Int]()
  29. for (i <- data) mutableMap += (i -> i)
  30.  
  31. val javaMap = new java.util.HashMap[Int, Int]()
  32. for (i <- data) javaMap.put(i, i)
  33.  
  34. def readImmutable = for (i <- data) immutableMap(i)
  35. def readMutable = for (i <- data) mutableMap(i)
  36. def readJava = for (i <- data) javaMap.get(i)
  37.  
  38. benchmark("get", readMutable, readImmutable, readJava, rampup, iterations)
  39. }
  40.  
  41. def measure[T](a: => T): (T, Long) = {
  42. val t1 = System.currentTimeMillis()
  43. val result = a
  44. (result, System.currentTimeMillis() - t1)
  45. }
  46.  
  47. def benchmark(title: String,
  48. mutableTest: => Any,
  49. immutableTest: => Any,
  50. javaTest: => Any,
  51. rampup: Int,
  52. iterations: Int) {
  53.  
  54. var sumMutable = 0L
  55. var sumImmutable = 0L
  56. var sumJava = 0L
  57. var sumMemMutable = 0L
  58. var sumMemImmutable = 0L
  59. var sumMemJava = 0L
  60. for (i <- 0 until rampup + iterations) {
  61. val (_, t0) = measure(mutableTest)
  62. val (_, t1) = measure(immutableTest)
  63. val (_, t2) = measure(javaTest)
  64. if (i > rampup) {
  65. val factor = (t1.toDouble / t0.toDouble)
  66. sumMutable += t0
  67. sumImmutable += t1
  68. sumJava += t2
  69. }
  70. }
  71. println("----------------" + title + "----------------")
  72. println("Mutable took %d, immutable took %d, java took: %d".format(sumMutable, sumImmutable, sumJava))
  73. (sumMutable, sumImmutable) match {
  74. case (s1, s2) if s1 < s2 => println("Mutable is %.2fx faster than immutable.".format(s2.toFloat / s1))
  75. case (s1, s2) if s1 > s2 => println("Immutable is %.2fx faster than mutable.".format(s1.toFloat / s2))
  76. case (s1, s2) if s1 == s2 => println("Immutable is on par with mutable.")
  77. }
  78. (sumMutable, sumJava) match {
  79. case (s1, s2) if s1 < s2 => println("Mutable is %.2fx faster than java.".format(s2.toFloat / s1))
  80. case (s1, s2) if s1 > s2 => println("Java is %.2fx faster than mutable.".format(s1.toFloat / s2))
  81. case (s1, s2) if s1 == s2 => println("Java is on par with mutable.")
  82. }
  83. (sumImmutable, sumJava) match {
  84. case (s1, s2) if s1 < s2 => println("Immutable is %.2fx faster than java.".format(s2.toFloat / s1))
  85. case (s1, s2) if s1 > s2 => println("Java is %.2fx faster than immutable.".format(s1.toFloat / s2))
  86. case (s1, s2) if s1 == s2 => println("Java is on par with immutable.")
  87. }
  88. }
  89.  
  90. def createData = {
  91. val data = new ArrayBuffer[Int](count)
  92. for (i <- 0 until count) {
  93. data += Random.nextInt()
  94. }
  95. data
  96. }
  97.  
  98. def mutableHashMapTest(data: Seq[Int], doGet: Boolean = false) = {
  99. import scala.collection.mutable.HashMap
  100. val map = new HashMap[Int, Int]()
  101. for (i <- data) map(i) = i
  102. if (doGet) for (i <- data) map(i)
  103. map
  104. }
  105.  
  106. def javaHashMapTest(data: Seq[Int], doGet: Boolean = false) = {
  107. import java.util.HashMap
  108. val map = new HashMap[Int, Int]()
  109. for (i <- data) map.put(i, i)
  110. if (doGet) for (i <- data) map.get(i)
  111. map
  112. }
  113.  
  114. def immutableHashMapTest(data: Seq[Int], doGet: Boolean = false) = {
  115. import scala.collection.immutable.HashMap
  116. var map = new HashMap[Int, Int]()
  117. for (i <- data) map += (i -> i)
  118. if (doGet) for (i <- data) map(i)
  119. map
  120. }
  121. }

etykiety: 

Odpowiedzi

cześć,
dzięki za podzielenie się ciekawymi wynikami testów!
Nie do końca rozumiem powiązanie między testami jakie przeprowadziłeś, a wnioskami jakie wynosisz. Jaki jest cel stosowania "immutable" w testach intensywnego zapisu ("put" i "put & get")?
Najciekawszy jest wynik testu "get" wskazujący że "mutable" jest szybsze od "immutable", bo na intuicję to mapy modyfikowalne powinny być bardziej skomplikowane i wolniejsze, a niemodyfikowalne powinny być prostsze a więc i szybsze. Czy wiesz może z czego wynika gorszy wynik odczytu immutable?
W teście ukrył się też mały błąd w linii 36 - przez co wyniki readJava i readMutable są takie same. Po poprawieniu "def readJava = for (i <- data) mutableMap(i)" na "def readJava = for (i <- data) javaMap.get(i)", standardowe hashmapy javowe uzyskują przewagę and tymi scalowymi. Na moim kalkulatorze kieszonkowym poprawiony test wypadł tak:

----------------get----------------
Mutable took 1539, immutable took 1965, java took: 1253
Mutable is 1.28x faster than immutable.
Java is 1.23x faster than mutable.
Java is 1.57x faster than immutable.

Dzięki za czujność! Na moim komputerze jednak wyniki zmieniły się tylko nieznacznie na korzyść Javy. Dość to dziwne. Używam standardowego jre na OSX.

O wydajności: owszem, wydawałoby się, że niemodyfikowalne kolekcje są prostsze w konstrukcji, ale to tylko pozory :) W językach funkcyjnych kolekcje przeważnie są "persistent" (zobacz: Persistent data structure. Nie mogę znaleźć źródła, ale gdzieś mi się obiło, że immutable.HashMap spełnia ten warunek. Czyli w efekcie kolekcja immutable to wielka sieć zależnych od siebie instancji niemodyfikowalnych map. Nie wiem jednak, czy to ta właściwość decydująco wpływa na prędkość - jedynie podejrzewam, że tak.

A wnioski? Wiele języków funkcyjnych, nazwijmy je czystymi, nie oferuje w ogóle kolekcji modyfikowalnych (np. Erlang, Haskel) i czy to zasadne czy nie zawsze musisz płacić cenę za niezmienność danych. W Scali mamy wybór, z czego się cieszę.