大体よく分かるscala.collection.immutable.HashMap ~ Compressed Hash-Array Mapped Prefix-tree (CHAMP) ~

Scalaわいわい勉強会 #6 https://scala-tokyo.connpass.com/event/371493/ の資料です。

Transcript

1. 大 体よく分かるscala.collection.immutable.HashMap ~ Compressed Hash-Array Mapped Pre fi x-tree (CHAMP) ~ ScalaΘ͍Θ͍ษڧձ #6 2025/11/27 @matsu_chara
2. @matsu_chara - 所属: 株式会社FOLIO - 仕事: chatGPTの出 力 をコンフルに貼る - 最近気になるRDBMS: PreemptDB 自己 紹介
3. - イミュータブルなHashMap - 要素を更新するとインスタンスが毎回作られる - 毎回全体をコピーする実装だと当然遅い scala> scala.collection.immutable.HashMap(1 -> "x", 2 -> "y", 3 -> "z") scala.collection.immutable.HashMap
4. - 更新された部分以外は共有する - immutableなので安全 大 量コピーを避けるために
5. この 手 のデータ構造を永続データ構造という 今 日 は「 木 でやりたい」という認識でOK Persistent Data Structure 詳しくはPFDS参照
6. scala.collection.immutable.HashMap の中 身
7. CHAMP Compressed Hash-Array Mapped Pre fi x-tree Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections (Steindorfer , OOPSLA 2015) HAMTの改良版 Hashed Array Mapped Trie Ideal Hash Trees(Bagwell, 2001) ※ 単に Map() で作成したMapはCHAMPとは限らない(e.g. EmptyMap, Map1, Map2,..)な ど 色 々あるが本筋ではないので割愛 正体はCHAMP GitHub: scala/scala3
8. CHAMPを説明しようとするとHAMTの説明が９割くらいになる 以前、ブログに仕組みを書いた ScalaのHashMapに関する論 文 (Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIOを開催した | だいたいよくわからないブログ が！図が 一 切無くて難しすぎるので 今回は図解 CHAMPの難しさ
9. HAMT
10. の前に
11. 伏線
12. popcount (population count) bit列中の1の個数を 高 速に数える専 用 命令 e.g. 111011101101000111110100110110 なら 19 ※ 専 用 命令がなくてもbit演算でO(1)実装可（専 用 命令でSIMD等使えるとさらに 高 速化が可能） 本 日 のおもしろCPU命令
13. Integer.bitCount で呼べる scala> Integer.bitCount(1001684278) val res0: Int = 19 -XX:+UsePopCountInstruction が制御フラグ(多くの環境で有効) $ jcmd <pid> VM. fl ags -all | grep UsePopCountInstruction bool UsePopCountInstruction = true {product} {default} popcount in JVM
14. HAMT
15. - Hash値をKeyとしてValueを保存したい（そもそもHashMapでやりたいこと) - Hash値は32bitのbit列 scala> "%32s".format(new {}.hashCode.toBinaryString).replace(' ', '0') res1: String = 111011101101000111110100110110 HAMTでやりたいこと
16. 説明のために 4bitのbit列をHash値だと思って、 2bit区切りでtrieに 入 れてみる。 ※本来は32bitを5bit区切りにする = 最 大 深さが7段の32分 木 (= 2^5)になる 何故5bit区切りなのかは後述 ナイーブにtrieに保存してみる 先頭から2bit 目 までの様 子
17. ナイーブにtrieに保存してみる {key=0001, value="AAA"} {key=1001, value="CCC"} {key=0011, value="BBB"}
18. 保存 方 法のイメージ {key=0001, value="AAA"} {key=0011, value="BBB"} 内部では配列にchild nodeへのpointer or valueをもたせて表現 ※ idxは便宜上記載しただけで配列上にはない ※ 例の都合でrootにしかptrがないがどの配列でもpointer/value両 方入 りうる ※ 右半分略 root
19. HashMapなのでスカスカな事が多い 全nodeを真 面 目 に 用 意するとnullまみれの配列を 大 量に 用 意することになる
20. null多すぎ
21. 値がないノードを削除 {key=0001, value="AAA"} {key=1001, value="CCC"} {key=0011, value="BBB"}
22. 不要な中間ノードも削除
23. 不要な中間ノードも削除 {key=0001, value="AAA"} {key=1001, value="CCC"} {key=0011, value="BBB"}
24. まだnull多い
25. 配列の圧縮
26. データ配列の圧縮 非 null要素のみを保持
27. 非 null要素しか保持しないと ある要素が00に対応するのか01に 対応するのか不明 どこの要素か分からなくなる
28. GET: key=0010 1. 第 一 階層を00で検索 2. 第 二 階層を10で検索 3. 無いのでnullを返す 最終的に深さ7の32分 木 にしたい = 32要素の配列を階層ごとに7回探索 性能的に物 足 りない 解法1: indexを持たせて探索 🤔
29. 配列のどこに値が 入 っているかを bitmapで表現 右図なら[1,0,1,0] - bitmap[0] = 1 - bitmap[1] = 0 - bitmap[2] = 1 - bitmap[3] = 0 ※ bitmapはintで保持するが並び順を考慮するのが 面 倒なので配列で記載 解法2: bitmapを利 用 ✅ bitmap[0] idx=00 bitmap[1] idx=01 bitmap[2] idx=10 bitmap[3] idx=11
30. GET idx=00 bitmap[0] にアクセス = ある idx=00は 一 番左の要素 content配列の先頭はidx=00の物な気がする content[0]にアクセス 圧縮されたデータ配列からの取得 bitmap[0] idx=00 bitmap[1] idx=01 bitmap[2] idx=10 bitmap[3] idx=11 content[0] content[1] bitmap[0] idx=00 bitmap[1] idx=01 bitmap[2] idx=10 bitmap[3] idx=11
31. GET idx=10 bitmap[2] にアクセス = ある content[???]にアクセス ※ 圧縮済みなのでcontent[2]ではない 圧縮されたデータ配列からの取得 bitmap[0] idx=00 bitmap[1] idx=01 bitmap[2] idx=10 bitmap[3] idx=11 content[0] content[1] bitmap[0] idx=00 bitmap[1] idx=01 bitmap[2] idx=10 bitmap[3] idx=11
32. 結論: bitmap[i]に対応するcontent配列の添字 j は bitmap上でiより左にある1の数になる ※ BitVectorのrank1 (i)操作 - 例1. [1, 0, 1, 0]なら1個あるcontent[1]が取得すべき要素 - 例2. [1, 0, 1, 1, 0, 1, 0, 1]ならcontent[4]が取得すべき要素 圧縮されたデータ配列からの取得
33. 例: 自 分より左に1が1個あるならcontent[1]が取得すべき要素 bitmap = [1, 0, 1, 0] or [0, 1, 1, 0] 圧縮されたデータ配列からの取得
34. 例: 自 分より左に1が4個あるならcontent[4]が取得すべき要素 bitmap = [1, 0, 1, 1, 0, 1, 0, 1] 圧縮されたデータ配列からの取得
35. 非 null要素(bitmap[i]=1の要素)がある度に content配列の要素が埋まるので 自 分より左の1の数を数える つまり bit列に含まれる1の数を 高 速に数えることができれば 圧縮済み配列に素早くアクセスできる 圧縮されたデータ配列からの取得
36. bit列に含まれる1の数を 高 速に数える
37. popcount (population count) bit列中の1の個数を 高 速に数える専 用 命令 e.g. 111011101101000111110100110110 なら 19 適当にbit演算してpopcountするだけで ループで配列を探索することなく 高 速に圧縮済みの配列からデータを取得できる ここでpopcount
38. - 32bit Hash値をtrieに詰めた - 保持配列を圧縮 - 圧縮した分、探索が必要だが popcountで 高 速に可能 HAMTまとめ
39. - bitmapはintで持つ - Object[] にはポインタか値が 入 る 補 足 : HAMTの実装イメージ Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections より
40. 4bit区切り16分 木 , 5bit区切り32分 木 , 6 bit区切り64分 木 になる トレードオフ - 分岐数が少ないと 木 が深くなる（メモリアクセス増） - 分岐数が多いと空きスロットが多くなる(メモリの無駄） 32分 木 だとbitmapをint32で保持できるので都合が良い等の理由もあり 5bit区切りが採 用 されている 補 足 : HAMTが5bit区切りにしている理由
41. めでたし
42. ここまでがHAMT
43. CHAMP
44. 改善点1
45. HAMTͰͷcontentArray͸ѹॖ͞Ε͍ͯͯޮ཰త͕ͩɺ ࣮͸ʢJVM࣮૷Ͱ͸ʣ ແବ͕͋Δ データとノードでbitmapを分ける
46. HAMTʢͷJVM࣮૷ʣͰ͸ •value͕ೖ͍ͬͯΔ৔߹
 contentArrayʹ͸ʢkey, value)͕ೖΔ
 ※ contentArrayΛ2ཁૉར༻͍ͯ͠Δ
 ※ hashিಥͷ৔߹ʹ΋ਖ਼͍͠ཁૉΛฦͨ͢Ίʹkeyͷอଘ͸ඞཁ
 •pointer͕ೖ͍ͬͯΔ৔߹
 contentArrayʹ͸(null, pointer)͕ೖΔ
 ※ contentArrayΛ2ཁૉར༻͍ͯ͠Δ データとノードでbitmapを分ける https://www.youtube.com/watch?v=pUXeNAeyY34 より
47. bitmapͷா৲Λ߹ΘͤΔͨΊʹnull͕ඞཁ͕ͩͦͷ෼ແବ͕૿͑Δ = ϝϞϦϑοτϓϦϯτʹվળͷ༨஍͕͋Δ ͨͩ͠ ※ C/C++ͷ৔߹͸unionΛ࢖ͬͯଞͷσʔλΛͭΊͯΔͷͰ͜ͷϜμ͸ͳ͍ ※ HashSetͷ৔߹͸key=valueͳͷͰ͜ͷແବ͸ͳ͍ データとノードでbitmapを分ける
48. 補 足 C/C++でのHAMT mkirchner/hamt ※ READMEが 非 常に丁寧なのでおすすめです = bitmap = contentArray = node ※ kv or tableのどちらかをtagged pointerで識別 tagのつけ外しを少しでも減らすためにvalue => keyの順番で宣 言 （keyの 方 がよく参照される）
49. 補 足 の補 足 tagged pointer 8byte alignmentの関係で下位3bitが0になる (linux 64bit libc malloc等) 0000 0000 0000 0000 0111 1111 1111 1101 1000 1001 0010 0011 0010 1110 1100 1000 ポインタには余っているbitがある そこに好きな情報を詰め込むことができる(tagged） pointerとして使う場合はセットしたbitを0にして読み込む(untagged) ※C/C++実装の話です。JVM (< 32GB)だとCompressed OOPとかあって難しい
50. [key, value, key, value, ….., 
 pointer, pointer, pointer]
 ͷΑ͏ʹޙ൒ʹpointerΛूΊΔ contentArrayの改善 https://www.youtube.com/watch?v=pUXeNAeyY34 より
51. - datamap 
 key, value ͕ೖ͍ͬͯΔཁૉҰཡ - nodemap
 ϙΠϯλ͕ೖ͍ͬͯΔཁૉҰཡ bitmapを分割する改善 https://www.youtube.com/watch?v=pUXeNAeyY34 より
52. contentArrayの配置の 工 夫でnullが消える https://www.youtube.com/watch?v=pUXeNAeyY34 より
53. - (null, pointer) Ͱ͸ͳ͘pointerΛ௚઀֨ೲͰ͖Δ - ϝϞϦϑοτϓϦϯτҎ֎ʹ΋஋ͷྻڍɺMapಉ࢜ͷ౳߸ൺֱͳͲͰΩϟογϡώοτ཰ΛվળͰ͖Δ contentArrayの配置の 工 夫でnullが消える
54. 参考: Scalaでの実装 4DBMB࣮૷
55. 参考: Scalaでの実装 4DBMB࣮૷
56. Scala実装 4DBMB࣮૷
57. Scala実装 4DBMB࣮૷
58. 補 足 : BitVectorに拡張してMultiMapを作る提案もある To-Many or To-One? All-in-One! E ff i cient Purely Functional Multi-maps with Type-Heterogeneous Hash-Tries より - datamap, nodemapͱ෼͚ΔͳΒσʔλͷܕ͝ͱʹmapΛ࡞Ε͹ྑ͍ - ܕ͝ͱʹint32Λ૿΍͘͢Β͍ͳΒBitVectorͰྑ͍ͱ͍͏ྲྀΕ - ͜ͷ࢓૊ΈͳΒMapͷதʹValueͱList[Value]Λࠞࡏͨ͠ঢ়ଶͰޮ཰Α͘ѻ͑Δͱ͍͏ͷ͕ϙΠϯτ
59. 改善点2
60. HAMTでは要素がdeleteされると形が最適ではなくなって しまう問題があった。 ͦ͜ͰෆมྔΛఆٛ͠ɺ֤෦෼໦͕ෆมྔΛҡ࣋͢ΔΑ͏ ʹૢ࡞͢Δ͜ͱͰdelete࣌΋࠷దͳܗʹ͢Δɻ ࠓճ͸ͦ΋ͦ΋HAMTͷ࡟আΛ঺հͯ͠ͳ͍ͷͰུ 正準形を定義し、delete時にも正準系が維持されるようにした Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections Figure1ΑΓ
61. 補 足
62. HAMTͰ͸contentArrayΛObject[]Ͱ࣋ͭɻ •JVMͰ͸Array΋object •object΁ͷΞΫηε͸ࢀরΛͨͲͬͯղܾ͢Δ ◦ϝϞϦΛͨͲΔͷͰcache miss͢ΔՄೳੑ͕ߴ͍ ◦௥ՃͷΦʔόʔϔου͕͋Δ ◦objectΛอ࣋͢ΔͷͰobject༻ͷheader΋ଘࡏ͢Δ ◦ArrayΫϥε͸length fi eldΛ࣋ͬͨΓ͢ΔͷͰແବʹϝϞϦΛফඅ͢Δ 補 足 : JVMとC/C++の違いと 工 夫の例
63. 値とポインタを同じ配列上に分けて保存しているので どこからがポインタか？を 示 すオフセットが通常必要 しかしオフセットをフィールドに 入 れるとメモリの無駄になる CHAMP は配列の後ろ側にノード群を逆順配置する設計 [contentArray.length - 1 - index]で追加フィールドなしに オフセットを算出できる（lengthは既存情報なのでメモリ増加ゼロ） 補 足 : JVMとC/C++の違いと 工 夫の例
64. Scala実装 4DBMB࣮૷
65. - scala.collection.immutable.HashMapの中 身 はCHAMP - CHAMPの基礎はHAMT - その基礎はtrie - 何気なく使っている物も調べてみると 面白 い まとめ
66. 今回は省略したCompressed OOP (Ordinary Object Pointer) などの話もあるので気になる 人 は以下をチェック！ ScalaのHashMapに関する論 文 (Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIOを開催した | だいたいよくわからないブログ 宣伝
67. - Ideal Hash Trees(Bagwell, 2001) - Introduction to HAMT — Idea of the day (2012) - Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections (Steindorfer, OOPSLA 2015) - HAMT ~ イミュータブルで 高 速なハッシュマップ ~ | κeenのHappy Hacκing Blog (2016) - Immutable Collections (Michael Steindorfer, JVM Language Summit 2016) - E ffi cient Immutable Collections (Steindorfer, 2017) - Immutable Collections (Paul Sandoz, JavaOne 2017) - https://github.com/scala/collection-strawman | Explore using CHAMP (Compressed Hash-Array Mapped Pre fi x-tree) instead of trees #192 - https://github.com/scala/scala | Reimplementations of immutable HashSet and HashMap. - To-Many or To-One? All-in-One! E ffi cient Purely Functional Multi-maps with Type-Heterogeneous Hash-Tries (Steindorfer, PLDI 2018) - https://github.com/mkirchner/hamt - ScalaのHashMapに関する論 文 (Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIOを開催した | だいた いよくわからないブログ (2023) 参考 文 献