ScalaのHashMapに関する論文(Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections)輪読会 in FOLIO メモその３ CHAMP編

本記事について

FOLIOでやった輪読会のメモです。

Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections で提案されている Scalaの immutable.HashMap に使われているCHAMPについてまとめます。

目次

CHAMPとは

  • HAMTの進化系。
  • Scalaのimmutable.HashMapに採用されている
  • データレイアウトが変わって効率が良くなったりJVMに優しくなったりしている。削除時のパフォーマンスもアップした。

工夫1: データレイアウト変えた

bitmapをnodemap, datamapに分けた (int32のbitmapが2つ)ことで元のマッピングの無駄を解消した。

HAMT CHAMP
論文より
https://www.youtube.com/watch?v=pUXeNAeyY34 18:38より

HAMTでのcontentArrayも圧縮されていて効率的だが、valueが入っている場合と下位nodeへのpointerが入っている場合の具体的な値に着目すると無駄が見えてくる。

  • valueが入っている場合、contentArrayには実際には（key, value)が入っている。
    • ※ contentArrayを2要素利用している
    • ※ nodeを辿っていけばkeyは分かるのでは？と思うかもしれないが、trieでは要素が特定できるところまでしかnodeが作成されないのでnodeを辿っていってもkeyは特定できない。
  • pointerが入っている場合、contentArrayには実際には(null, pointer)が入っている。
    • ※ contentArrayを2要素利用している
    • ※ nullを入れる必要は無いのでは？と思うかもしれないが、bitmapを使った配列の圧縮を行うためには利用するslot数が揃っている必要があるのでnullを入れる必要がある。

上記のようにcontentが下位nodeへのpointerになっている時、key要素が必ずnullになってvalueにpointerが入っている構成だった。nullの分が無駄になりメモリフットプリントがよろしく無い。

CHAMPではcontentArrayの構成を [key, value, key, value, ….., pointer, pointer, pointer]のように後半にpointerを集めるようにし、bitmapをnodemap(下位nodeへのポインタが入っている要素一覧)とdatamap(key,valueが入っている要素一覧)に分けている。

上記の構成により以下のメリットを得ている。

  • 配列中のnullがなくなる
  • メモリフットプリント削減
  • valueかpointerかを見分けるためのinstanceOfも要らなくなる
  • pointerを読み飛ばす必要がないので処理量削減 & 局所参照性向上が見込める
    • valueのiterationや等号比較が早くなる
    • O(下位nodeへの参照 + item) => O(item) になった。

なおC/C++の実装では空slotをunion typesなどを使って有効活用しているらしい（詳細は不明）

工夫2: 正準形を定義し、delete時にも正準系が維持されるようにした。

HAMTでは要素がdeleteされると形が最適ではなくなってしまう問題があった。

そこで不変量を定義し、各部分木が不変量をkeepするように操作することでdelete時も最適な形に出来るようにした。

これによりdeleteを重ねた木に対してもlookupの速度などが向上し、メモリ消費量も削減された。

Canolical Formについて

不変量を考えていき、その不変量が維持されることをもってcanonical formとよぶ。

HAMTでもinsertについては不変量が維持されるが, deleteすると維持されなくなる。

例えば下図で ”C” を消してもHAMTとしてvalidだが、中間のnodeは無駄になってしまう。

論文 Figure1より

本来はこのようになっていてほしい。

論文 Figure1より

具体的なdeleteアルゴリズムについては論文を読んでもらうとして不変量について解説する。

不変量で使う値

  • Arity (local):
    • 外向きのエッジの数
    • CHAMPでは以下の2つがある
      • 下位nodeへのarity
      • payloadへのarity
    • 合計すればarityになる。それぞれはnodemap, datamapの1が立っているbit数を数えれば計算出来る
  • Branch Size (non-local)
    • ブランチサイズはノードから推移的に到達可能な要素の数
    • 実際にノードを辿らないと計算できない（non-localな値)ので近似値の計算が後で紹介されるらしい

CHAMP 不変量

branchSize ≥ 2 * nodeArity + payloadArity

  • 全ての部分木がこの条件を満たすようにする
  • この不変量はarityが2未満の部分木を許可しないということを述べている
  • 1要素しか持たないnodeはinline化される。
  • 下位nodeへのpointerしかもたないnodeは破棄される

不変量の例

論文Figure1より

(a)

  • 1層目
    • nodeArity = 0
    • payloadAirty = 2
    • branchSize = 2 # A, B
    • 2 >= 2 * 0 + 2 # OK

(b)

  • 3層目
    • (a)と同じ構成なのでOK
  • 2層目
    • nodeArity = 1
    • payloadAirty = 0
    • branchSize = 2 # B, C
    • 2 >= 2 * 1 + 0 # OK
  • 1層目
    • nodeArity = 1
    • payloadAirty = 1
    • branchSize = 3 # A,B,C
    • 3 >= 2 * 1 + 1 # OK

(b) からCを単純に消した違法CHAMP

  • 3層目
    • nodeArity = 0
    • payloadAirty = 1
    • branchSize = 1 # B
    • 1 >= 2 * 0 + 1 # OK (第３階層だけを考えるとvalidなnodeになっているのでこれでよい)
  • 2層目
    • nodeArity = 1
    • payloadAirty = 0
    • branchSize = 1 # B
    • 1 >= 2 * 1 + 0 # NG
  • 1層目
    • ※ 下位部分木が不変量を満たしてない = 前提条件がおかしいのでそもそも考えなくて良い
    • nodeArity = 1
    • payloadAirty = 1
    • branchSize = 2 # A, B
    • 2 >= 2 * 1 + 1 # NG

(c)

  • 3層目
    • (a)と同じ構成なのでOK
  • 2層目
    • nodeArity = 1
    • payloadAirty = 1
    • branchSize = 3 # D, B, C
    • 3 >= 2 * 1 + 1 # OK
  • 1層目
  • nodeArity = 1
  • payloadAirty = 1
  • branchSize = 4 # A, D, B,C
  • 4 >= 2 * 1 + 1 # OK