Scala, mapy a čítače

21. 5. 2019 #Scala #benchmark

Představte si následující situaci: Máte nějaký kód ve Scale (nebo Javě, na tom moc nesejde), který počítá frekvence prvků. Všechno funguje, jen vás hluboko v mozku začala hlodat otázka: Jak je to vlastně rychlé a šlo by to případně udělat rychleji?

Ve Scale se počítání frekvence dá nejjednodušeji spáchat tak, že nejdřív vytvořím HashMapu s výchozí hodnotou 0:

val map = mutable.Map[Int, Int]() withDefaultValue 0

Pak můžu jednoduše inkrementovat čítače:

map(key) += 1

To je syntaktický cukr pro:

map.update(key, map.apply(key)+1)

Celé to funguje z důvodu, že metoda apply v případě neexistujícího klíče vrátí výchozí hodnotu namísto vyhození výjimky.

Ukazuje se ale, že ve Scale 2.12.8 (na openJDK 11.0.3) tohle, z důvodů, které nedokážu vysvětlit, není vůbec nejrychlejší.

MapIntRef.array                        598,122 ±   0,399  ns/op
MapIntRef.mutableMapDefault         137100,051 ± 125,853  ns/op
MapIntRef.mutableMapDefaultMethod    27599,936 ± 230,587  ns/op
MapIntRef.mutableMap                 36735,429 ± 258,422  ns/op
MapIntRef.javaMap                    16322,510 ±   3,052  ns/op
MapIntRef.mapRef                      9922,872 ±   8,423  ns/op

array nepoužívá hash tabulku, ale pole. Je tu zahrnutý jako teoretický strop rychlosti kterému se chceme přiblížit.
mutableMapDefault odpovídá kódu načrtnutému výše.
mutableMapDefaultMethod je podobný jako mutableMapDefault, ale výchozí hodnota není nastavena voláním withDefaultValue, ale přetížením metody default.
mutableMap používá map(k) = map.getOrElse(k, 0)+1
javaMap používá java.util.HashMap
mapRef je pak speciální případ, který se snaží vyhnout boxingu integerů.

Kód všech testů je na konci článku.

Použití withDefaultValue je z nějakého důvodu velice pomalé. Snažil jsem se zjistit proč, ale nepřišel jsem na žádné vysvětlení. Navíc jeho výkon se postupně zhoršuje. Zahřívací iterace JHM začnou na polovičním čase (±60μs), pak se propadnou na finálních 137μs.

Volání metody withDefaultValue vytvoří instanci mapy collection.mutable.WithDefault, která obalí naší mutable.HashMap, na níž deleguje většinu metod, odchytí jen některé, aby vracely výchozí hodnoty.

mutable.WithDefault implementuje apply pomocí generické metody get alokující Option namísto efektivnšjších způsobů. Mnohem rychlejší varianta, ale používá getOrElse, které také alokuje Option, takže tohle nevysvětluje nic. Navíc profilování GC aktivity v JMH ukazuje, že alokace nejpomalejší varianty nevybočují z normálu. Kdybych se měl vsadit, tipoval bych, že pes je zakopaný v JITu. WithDefault znamená další extra úroveň abstrakce a JIT se jespíš rozhodl neinlinovat některou metodu, protože byla příliš hluboko. Rozdíl mezi situací, kdy JIT udělal správná rozhodnutí a kdy je neudělal, je značný zvláště v případě těsných smyček.

V nadcházející verzi Scaly (2.13.0-RC1), která přinesla značné zlepšení hashmap, jsou výsledky následující:

MapIntRef.array                       486,011 ±  10,883  ns/op
MapIntRef.mutableMapDefault         17809,997 ±  30,587  ns/op
MapIntRef.mutableMapDefaultMethod    8448,601 ±  11,251  ns/op
MapIntRef.mutableMap                 8148,648 ± 183,043  ns/op
MapIntRef.javaMap                   15859,614 ± 107,549  ns/op
MapIntRef.mapRef                     7594,568 ±  84,688  ns/op

Všechna řešení ve Scale jsou mnohem rychlejší, ale withDefaultValue je stále z nějakého důvodu nejpomalejší, ale ne o moc než java.util.HashMap.

Benchmarky:

def array = {
  val arr = new Array[Int](32)
  var i = 0; while (i < 1024) {
    arr(i % 32) += 1
    i += 1
  }
  arr
}

def javaMap = {
  val map = new java.util.HashMap[Int, Int]()
  var i = 0; while (i < 1024) {
    val k = i % 32
    val v = map.get(k)
    map.put(k, if (v == null) 1 else v+1)
    i += 1
  }
  map
}

def mutableMapDefault = {
  val map = collection.mutable.Map[Int, Int]() withDefaultValue 0
  var i = 0; while (i < 1024) {
    map(i % 32) += 1
    i += 1
  }
  map
}

def mutableMapDefaultMethod = {
  val map = new collection.mutable.HashMap[Int, Int]() { override def default(key: Int) = 0 }
  var i = 0; while (i < 1024) {
    map(i % 32) += 1
    i += 1
  }
  map
}

def mutableMap = {
  val map = collection.mutable.Map[Int, Int]()
  var i = 0; while (i < 1024) {
    val k = i % 32
    map(k) = map.getOrElse(k, 0)+1
    i += 1
  }
  map
}

class IntRef(var value: Int)

def mapRef = {
  val map = collection.mutable.Map[Int, IntRef]()
  var i = 0; while (i < 1024) {
    map.getOrElseUpdate(i % 32, new IntRef(0)).value += 1
    i += 1
  }
  map
}

0xDEADBEEF

Scala, mapy a čítače