0xDEADBEEF

[RSS]
««« »»»

Scala, mapy a čítače

21. 5. 2019

Před­stavte si ná­sle­du­jící si­tu­aci: Máte nějaký kód ve Scale (nebo Javě, na tom moc ne­sejde), který počítá frek­vence prvků. Všechno fun­guje, jen vás hlu­boko v mozku začala hlodat otázka: Jak je to vlastně rychlé a šlo by to pří­padně udělat rych­leji?

Ve Scale se po­čí­tání frek­vence dá nej­jed­no­du­šeji spáchat tak, že nejdřív vy­tvo­řím Ha­shMapu s vý­chozí hod­no­tou 0:

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

Pak můžu jed­no­duše in­kre­men­to­vat čítače:

map(key) += 1

To je syn­tak­tický cukr pro:

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

Celé to fun­guje z důvodu, že metoda apply v pří­padě ne­e­xis­tu­jí­cího klíče vrátí vý­chozí hod­notu na­místo vy­ho­zení vý­jimky.

Uka­zuje se ale, že ve Scale 2.12.8 (na ope­n­JDK 11.0.3) tohle, z důvodů, které ne­do­kážu vy­svět­lit, není vůbec nej­rych­lejší.

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

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

Po­u­žití withDefaultValue je z ně­ja­kého důvodu velice pomalé. Snažil jsem se zjis­tit proč, ale ne­při­šel jsem na žádné vy­svět­lení. Navíc jeho výkon se po­stupně zhor­šuje. Za­hří­vací ite­race JHM začnou na po­lo­vič­ním čase (±60μs), pak se pro­pad­nou na fi­nál­ních 137μs.

Volání metody withDefaultValue vy­tvoří in­stanci mapy collection.mutable.WithDefault, která obalí naší mutable.HashMap, na níž de­le­guje vět­šinu metod, od­chytí jen ně­které, aby vra­cely vý­chozí hod­noty.

mutable.WithDefault im­ple­men­tuje apply pomocí ge­ne­rické metody get alo­ku­jící Option na­místo efek­tivn­šj­ších způ­sobů. Mnohem rych­lejší va­ri­anta, ale po­u­žívá getOrElse, které také alo­kuje Option, takže tohle ne­vy­svět­luje nic. Navíc pro­fi­lo­vání GC ak­ti­vity v JMH uka­zuje, že alo­kace nej­po­ma­lejší va­ri­anty ne­vy­bo­čují z nor­málu. Kdy­bych se měl vsadit, ti­po­val bych, že pes je za­ko­paný v JITu. WithDefault zna­mená další extra úroveň abs­trakce a JIT se jespíš roz­hodl ne­in­li­no­vat ně­kte­rou metodu, pro­tože byla příliš hlu­boko. Rozdíl mezi si­tu­ací, kdy JIT udělal správná roz­hod­nutí a kdy je ne­u­dě­lal, je značný zvláště v pří­padě těs­ných smyček.


V nad­chá­ze­jící verzi Scaly (2.13.0-RC1), která při­nesla značné zlep­šení ha­shmap, jsou vý­sledky ná­sle­du­jí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 rych­lejší, ale withDefaultValue je stále z ně­ja­kého důvodu nej­po­ma­lejší, ale ne o moc než java.util.HashMap.


Ben­chmarky:

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
}
píše k47 (@kaja47, k47)