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
}
13. 5. 2019Další novinky ve Scale 2.13
14. 4. 2019Parciální funkce ve Scale a dvojité vyhodnocování
10. 4. 2019Minimalistické zvýrazňování syntaxe
13. 3. 2019Jak rychlý je čas (v Javě)?
21. 2. 2019Really simple RSS
26. 1. 2019Java, Scala a regulární výrazy #6 - znovupoužití Matcher objektu
12. 1. 2019Poznámky ke slajdům k přednášce, kterou jsem nikdy nepřednášel
4. 1. 2019Minifikace HTML5
24. 12. 2018Java IO & NIO - jak nejrychleji načíst soubor z disku
3. 11. 2018Průnik množin ve Scale
23. 10. 2018Čím nahradit Scala.XML
11. 10. 2018Novinky kolekcí ve Scale 2.13
4. 8. 2018Co vlastně benchmarkujete?
28. 7. 2018Java, Scala a regulární výrazy #5 - posesivní regexy a StackOverflowError
26. 7. 2018EDGE, TRIPS a hon za vyšším ILP
24. 6. 2018Striktní a líné jazyky
21. 6. 2018Syntéza datových struktur a programů
9. 6. 2018ISPC, SPMD a SIMD
6. 4. 2018Konec Intelu, konec Moorova zákona, konec světa takového jaký známe
31. 1. 2018Meltdown, Spectre a branch prediction
28. 12. 2017Poznámky k výkonu
19. 12. 2017Java, Scala a regulární výrazy #4 - líné regexy a StackOverflowError
5. 12. 2017Java, Scala a regulární výrazy #3 - rychlost
27. 11. 2017Java, Scala a regulární výrazy #2 - rychlost
26. 11. 2017Java, Scala a regulární výrazy
21. 11. 2017Java - zostřování obrázků
7. 10. 2017Koherence cache a atomické operace
5. 10. 2017Nejrychlejší hashmapa pod sluncem
23. 9. 2017Dekódování x86 instrukcí
21. 9. 2017Energetická efektivita programovacích jazyků
19. 9. 2017Programming and Performance podcast
17. 9. 2017B-stromy, persistence, copy-on-write a Btrfs
15. 9. 2017Rust a parsery
13. 9. 2017Velké stránky paměti
11. 9. 2017Deanonymizace agregovaných dat
9. 9. 2017Optimalizující kompilátor
7. 9. 2017Identifikace zašifrovaných videí
5. 9. 2017Heterogenní persistentní kolekce
3. 9. 2017JVM Anatomy Park
1. 9. 2017Datacentrum z mobilů
30. 8. 2017Propustnost pamětí
28. 8. 2017Branch prediction (implementace v procesorech)
Starší články byly publikovány na funkcionálně.cz.
píše k47 (@kaja47, k47)