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

本記事について

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

表題の論文は Scalaの immutable.HashMap に使われているCHAMPについての提案ですがベースとなるHAMTについて理解があったほうが読みやすいのでHAMTについて解説します。

※ Trie木については本記事では解説しないので必要に応じて別のサイトなどを参照してください。

以下の解説は Introduction to HAMT — Idea of the day に自分なりのメモを加えたものです。図を見てもらったほうがわかりやすいと思います。

Hash値をTrieに格納する

8bitのbit列 00000000, 11111110, 11111111 をHash値だと思うことにする。

これを2bit区切りのTrie木に入れると以下のようになる。(※ ここでは例のために先頭2bitくぎりにしてるけど好きなbit数で区切ってよい)

第1階層(1~2bit目担当): {00 => value: 00000000, 11 => 次階層へのpointer}
第2階層(3~4bit目担当): {11 => 次階層へのpointer}
第3階層(5~6bit目担当): {11 => 次階層へのpointer}
第4階層(7~8bit目担当): {10 => value: 11111110, 11 => value: 11111111}

naiveなデータの持ち方

上記で概念的なTrieの構造について考えたので、具体的なデータの持ち方について考えてみる。まずは配列を使ったnaiveなアイデアを考える。

要素数が2bitの場合とりうる値は4通り（00, 01, 10, 11) になるので、データを持つとしたらtrie木内のそれぞれの階層について以下のようなlength=4なarrayを持てば良い。

[00用slot, 01用slot, 10用slot, 11用slot]

最初のHash値の例でいうと以下のようになる。

第1階層(左から1~2bit目担当): [value: 00000000, null, null, 次階層へのpointer]
第2階層(左から3~4bit目担当): [null, null, null, 次階層へのpointer]
第3階層(左から5~6bit目担当): [null, null, null, 次階層へのpointer]
第4階層(左から7~8bit目担当): [null, null, value: 11111110, value: 11111111]

ただこの表現の場合は配列がnullだらけになる(sparseなarrayになる）のでメモリフットプリントが無駄に大きくなってしまう。

bitmap

HAMTではこれをbitmapで改善する。先程の第1階層を例に挙げる。

第1階層(1~2bit目担当): [value: 00000000, null, null, 次階層へのpointer]

このとき配列の非ヌル要素を1、ヌル要素を0で表現することにすると、第一階層は 1001 という4bitのbitmapで表現できる。それぞれ以下のようになる。

左から1bit目 = hash値の1~2bit目が00のslotに対応
左から2bit目 = hash値の1~2bit目が01のslotに対応
左から3bit目 = hash値の1~2bit目が10のslotに対応
左から4bit目 = hash値の1~2bit目が11のslotに対応

00, 01, 10, 11は10進法なら0,1,2,3なのだから普通にbitmap[0]とかbitmap[2]とかでアクセスすればslotに対応するbitmap中のbitにすぐアクセスすることができる。

このbitmapを使うとあるslotがnullか非nullかを判定することができる。第一階層1001を例にすると、

判定したいslotが10用であった場合は bitmap[2]を見ると値が存在しているかが分かる
- bitmap=1001 のとき bitmap[2] は 0 => 対応する要素はnull
判定したいslotが00用であった場合は bitmap[0]を見ると値が存在しているかが分かる
- bitmap=1001のとき bitmap[0] は 1 => 対応する要素は非null（valueかpointerが入っている）

bitmapは4つの枝の中からvalid branchをマークしているといえる。（see Bitwise trie with bitmap）

bitmap to mark every valid branch

配列の圧縮

前述のbitmapだけでは配列の対応する要素がnullか非nullかという確認しかできないので先程まで使っていた値を持つ配列は以前として必要である。

ここで、メモリフットプリントを改善するために先程まで使っていたlength=4なarrayを圧縮することにする。

nullだらけのarrayを持つのではなく非ヌル要素のみを持った配列（圧縮された配列）を持つことでメモリフットプリントを改善することを考える。

圧縮前: [value: 00000000, null, null, 次階層へのpointer]
圧縮後: [value: 00000000, 次階層へのpointer]

さきほどのmask = bitmapがあれば、以下で述べる手順で値を取得することができる。

データの取得方法

キーに対応する値の取得を行うためには、圧縮された配列の各要素と圧縮前の配列の各要素を対応付ける必要がある。

これはhash値の先頭2bitに対応するbitmapのslotを確認し、それより左側に何個１が立ってるのかをカウントすることで知ることが出来る。つまり圧縮前の配列[i] = 圧縮後の配列[bitmap[i]より左にある1の数] となる。

例えばbitmapが 1001の場合を考えると以下のようになる。

hash値の1~2bit目が 00 => bitmap[0]が対応する。bitmap[0]より左にある1の数をカウントすると0個なので配列[0]に値が入っている => value = “00000000”を取得できる
hash値の1~2bit目が 11 => bitmap[3]が対応する。bitmap[3]より左にある1の数をカウントすると1個なので配列[1]に値が入っている => pointerを取得できる

余談1: popcnt について

上記で利用した1をカウントする操作のことをpopulation count(pop count)という。この操作は専用のCPU命令が実装されていたりするので高速に動作する（らしい）。

Hash array mapped trie - Wikipedia
- > This operation is available in many instruction set architectures (中略). Although population count can be implemented in software in O(1) time using a series of shift and add instructions, doing so may perform the operation an order of magnitude slower.`
Hamming weight - Wikipedia
- > Intel Core processors introduced a POPCNT instruction with the SSE4.2 instruction set extension
- > The ARM architecture introduced the VCNT instruction as part of the Advanced SIMD (NEON) extensions.
Integer (Java Platform SE 8)
- Javaでは Integer.bitCount() で利用可能
Bitwise trie with bitmap - Wikipedia
- > CTPOP (count population) operation that determines the number of set bits, which is available as Long.bitCount() in Java.

さらに余談だがNTT Comが開発したソフトウェアルーターの実装でPoptrieというデータ構造が使われている。論文タイトルを見るとこれもPopulation Countと入っているのでpopcntベースのTrieという意味では似ているところがあるかもしれない。（未読）

HAMTの構造

最終的にHAMTの各階層は以下で構成される。

N bitのbitmap
各階層の非ヌル値のみを要素とする配列 (value か pointerのどちらかが入っている)

class Node {
  int bitmap; // 4byte = 32bit
  Object[] contents; // value or pointerが入る
}

以上により、trie木でHashMapを作成することができる。

HAMTの計算量

値を持つ配列を圧縮することでメモリフットプリントが向上しただけでなく値のtraversalもnullだらけの配列を走査するより早くなるといったことも特徴として挙げられる。

上記の解説ではhash値の2bitごとにtrie木の階層を作成していたが、論文や実際の実装では5bit区切りにすることがおおい。

bitmapのサイズは 2^{hash値の区切りbit数}なので

2桁区切りの場合は 2²で4bitのbitmap (00, 01, 10, 11)
5桁区切りの場合は 2⁵で32bitのbitmap (00000, 00001, 00010, 00011, 00100, ….)

となる。5桁区切りにするのは単にint32で格納できるので都合がよいからのようだ。

2bit区切りの場合はtrieは2分木になっていたが、5bit区切りの場合はtrieは32分木になる。

計算量は（32bit bitmapの場合）最大で hash値の桁数/5回だけpointerをたどればよい。全体としてはeffectively O(1) くらい。正確にはO(log_32(N))。

HAMT ~ イミュータブルで高速なハッシュマップ ~ | κeenのHappy Hacκing Blog
Ideal Hash Trees
- Insert, search and delete times are small and constant, independent of key set size, operations are O(1)
Immutable Collections - YouTube
- LookUp/Insert/Delete in O(log_32(N)) ≒ O(1)

注意点

本記事の例ではbitmapや値を持つarrayは階層ごとに一つずつのように見えていたが実際には木のnodeの分だけ必要になる。

第一階層が 00だったときの第二階層 10 に値がはいっているか？ (つまりhash値 = 0010...に値があるか）
第一階層が 10だったときの第二階層 10 に値がはいっているか？ (つまりhash値 = 1010...に値があるか）

はもちろん結果が異なるので第二階層用のbitmapや値を持つ配列もnodeの数だけ必要になる。（例だと子要素のnodeが必ず一つだったので木の深さとたまたま一致していた。）

https://www.youtube.com/watch?v=pUXeNAeyY34 6:59より

node数の分となると子要素・孫要素と進むたびに分岐が発生してものすごい数のbitmapが必要になるように思えるが、そもそも存在しないpathについてはbitmapを保持する必要がないので実際に必要になる数は限られる。

その他

hash値の衝突の場合はLinkedListでもいいしRedBlackTreeぶらさげてもいいし別のhash関数使ってもう一つHAMTをぶらさげてもいいらしい。

だいたいよくわからないブログ