HAMT: 実装してみた感想等
HAMT(Hash Array Mapped Trie) - sileの日記の続き。
前よりはちゃんとしたものを実装したので、それをうけての感想など。
作成物: hamt-0.2.0
前回からの相違点
基本的には『Ideal Hash Trees』*1に合わせた実装に修正*2。
変更点を挙げると、
- HAMTのエントリ列(key/value及びamt-node構造体)用のアロケータを作成
- エントリ列(simple-vector)のプールを作成してそれを使いまわすように
- HAMTは基本的に挿入毎に新たなエントリ列を要求する(かつ古いものは捨てる)ので、その度に新規作成(make-array)するのは非効率
- ルートではAMTノードの代わりにハッシュテーブルを用いるように変更
- これはただのハッシュテーブル。配列の各要素はAMTノードのエントリと同様。
- 効率のため
- ルートのハッシュテーブルのリサイズに対応
- これによって検索/挿入処理のオーダーが要素数に対してO(1)に ※ 前回はO(log 要素数)
- ルートハッシュテーブルは、要素数がテーブルサイズの32倍*3になったら、要素分のサイズにリサイズされる ※ この際、リハッシュは不要
- リサイズ直後は、(ハッシュ関数が理想的だと仮定すれば)全ての要素がルートハッシュテーブルに格納されることになるので、検索/挿入は要素数に対してO(1)で行える
- リサイズ直前は、(理想的には)全ての要素がルートハッシュテーブルかその一段階下のAMTノード(各ノードは最大32個のエントリを有する)に格納されているので、検索/挿入処理はルートハッシュテーブルとAMTノードをそれぞれ一回ずつ参照すれば終了することになる。つまりO(1)。
- つまり「ルートハッシュテーブルサイズが要素数の1/32以下にならない」という不変式が維持されてさえいれば、HAMTの検索/挿入処理は要素数に対してはO(1)となる。
- lazyなリサイズ
- リサイズ処理のトリガーは、ルートハッシュテーブルのサイズが要素数の1/32になったらだが、新旧のテーブルでの要素の以降を一度には行わない
- トリガー発動後の要素挿入毎に、一つずつ古いテーブルから新らしいテーブルに、エントリを移動する。旧テーブルサイズ分の挿入がなされた後に、新旧のテーブルが完全に置き換わる。
- このため、リサイズ処理によって挿入処理が大幅に止まってしまうことはない
- これによって検索/挿入処理のオーダーが要素数に対してO(1)に ※ 前回はO(log 要素数)
HAMTの利点
common lisp(sbcl)で実装してみた感じでは、基本的には普通のハッシュテーブルとリンクリストを組み合わせたようなハッシュマップの方が効率が良さそう。
それを踏まえた上で、HAMTの利点だと思うところは、
SBCLのハッシュテーブルとの比較例
sbclのハッシュテーブルといくつかの実行例を比べてみる。
sbclのハッシュテーブルがどのように実装されているかが分かっていないので、あまり意味がないけど、参考までに。
※ 自分は、多分普通(?)のハッシュテーブルだと勝手に考えている
;; sbcl-1.0.40 (require :hamt) (hamt:make) --> #S(HAMT:HAMT :ROOT-ENTRIES #(NIL NIL NIL NIL NIL NIL NIL NIL) ; デフォルトでは初期ルートテーブルサイズは8 :NEW-ROOT-ENTRIES #() :ROOT-BITLEN 3 :TEST #<FUNCTION EQUAL> :HASH #<FUNCTION HAMT::HASH> :RESIZE-BORDER 256 :ENTRY-COUNT 0) ;;;;;;;;;;;;;;;;; ;;;; 比較用の準備 ;; シャッフルされた0〜sizeまでの数値のリストを返す (defun gen-num-keys (size) (let ((ary (coerce (loop FOR i FROM 0 BELOW size COLLECT i) 'vector))) (loop REPEAT 2 DO (loop FOR i FROM 0 BELOW size DO (rotatef (aref ary i) (aref ary (random size))))) (coerce ary 'list))) ;; 整数のリストをキーとして用意する (defvar *100num* (gen-num-keys 100)) ; 百 (defvar *10000num* (gen-num-keys 10000)) ; 一万 (defvar *1000000num* (gen-num-keys 1000000)) ; 百万 (defvar *1000000num* (gen-num-keys 5000000)) ; 五百万 ;; 計時用マクロ ;; - keyset: 入力キーセット ;; - hash-make: ハッシュマップ作成関数 ;; - hash-get: ハッシュマップのキー検索関数 ;; - loop-count: ループ数 ;; - search-keyset: 検索用キーセット (defmacro hash-time (keyset hash-make hash-get &key (loop-count 1) (search-keyset keyset)) `(let ((h ,hash-make)) (declare (optimize (speed 3) (safety 0) (debug 0))) ;; 挿入時間 (format t "~%;;;; INSERT~%") (time (loop REPEAT ,loop-count DO (dolist (k ,keyset) (setf (,hash-get k h) t)))) ; 値はtに固定 ;; 検索時間(成功 (format t ";;;; SEARCH~%") (time (loop REPEAT ,loop-count DO (count-if (lambda (k) (,hash-get k h)) ,search-keyset))) 'done))
;;;;;;;;;;;;; ;;;; 実行結果 ;;;;;;;;;;;;;;;;;; ;;; 百要素を一万回 ;; hamt (hash-time *100num* (hamt:make) hamt:get :loop-count 10000) ;;;; INSERT Evaluation took: 0.066 seconds of real time 0.064004 seconds of total run time (0.064004 user, 0.000000 system) 96.97% CPU 131,121,646 processor cycles 4,096 bytes consed ;;;; SEARCH Evaluation took: 0.071 seconds of real time 0.072004 seconds of total run time (0.072004 user, 0.000000 system) 101.41% CPU 142,654,855 processor cycles 159,744 bytes consed --> DONE ;; hash-table (hash-time *100num* (make-hash-table) gethash :loop-count 10000) ;;;; INSERT Evaluation took: 0.057 seconds of real time 0.060004 seconds of total run time (0.060004 user, 0.000000 system) 105.26% CPU 114,459,210 processor cycles 7,696 bytes consed ;;;; SEARCH Evaluation took: 0.070 seconds of real time 0.068004 seconds of total run time (0.068004 user, 0.000000 system) 97.14% CPU 141,067,812 processor cycles 159,744 bytes consed --> DONE ;;;;;;;;;;;;;;;;;; ;;; 一万要素を百回 ;; hamt (hash-time *10000num* (hamt:make) hamt:get :loop-count 100) ;;;; INSERT Evaluation took: 0.066 seconds of real time 0.064004 seconds of total run time (0.064004 user, 0.000000 system) 96.97% CPU 131,004,843 processor cycles 396,272 bytes consed ;;;; SEARCH Evaluation took: 0.066 seconds of real time 0.068005 seconds of total run time (0.068005 user, 0.000000 system) 103.03% CPU 130,776,582 processor cycles 0 bytes consed --> DONE ;; hash-table (hash-time *10000num* (make-hash-table) gethash :loop-count 100) ;;;; INSERT Evaluation took: 0.064 seconds of real time 0.064004 seconds of total run time (0.064004 user, 0.000000 system) 100.00% CPU 127,641,558 processor cycles 650,904 bytes consed ;;;; SEARCH Evaluation took: 0.064 seconds of real time 0.064004 seconds of total run time (0.064004 user, 0.000000 system) 100.00% CPU 127,919,073 processor cycles 0 bytes consed --> DONE ;;;;;;;;;;;;;;;;;; ;;; 百万要素を一回 ;; hamt (hash-time *1000000num* (hamt:make) hamt:get :loop-count 1) ;;;; INSERT Evaluation took: 0.695 seconds of real time 0.692043 seconds of total run time (0.660041 user, 0.032002 system) [ Run times consist of 0.348 seconds GC time, and 0.345 seconds non-GC time. ] 99.57% CPU 1,385,840,301 processor cycles 38,115,240 bytes consed ;;;; SEARCH Evaluation took: 0.461 seconds of real time 0.456029 seconds of total run time (0.456029 user, 0.000000 system) 98.92% CPU 920,135,692 processor cycles 0 bytes consed --> DONE ;; hash-table (hash-time *1000000num* (make-hash-table) gethash :loop-count 1) ;;;; INSERT Evaluation took: 0.381 seconds of real time 0.380023 seconds of total run time (0.360022 user, 0.020001 system) [ Run times consist of 0.097 seconds GC time, and 0.284 seconds non-GC time. ] 99.74% CPU 759,033,664 processor cycles 41,934,936 bytes consed ;;;; SEARCH Evaluation took: 0.239 seconds of real time 0.236015 seconds of total run time (0.236015 user, 0.000000 system) 98.74% CPU 475,039,236 processor cycles 0 bytes consed --> DONE ;;;;;;;;;;;;;;;;;; ;;; 不成功検索が多い場合 ;; hamt (hash-time *10000num* (hamt:make) hamt:get :loop-count 1 :search-keyset *5000000num*) ; 検索キーの内の499万個は存在しない ;;;; INSERT Evaluation took: 0.004 seconds of real time 0.004000 seconds of total run time (0.004000 user, 0.000000 system) 100.00% CPU 8,293,254 processor cycles 392,512 bytes consed ;;;; SEARCH Evaluation took: 0.243 seconds of real time 0.244015 seconds of total run time (0.244015 user, 0.000000 system) 100.41% CPU 485,394,333 processor cycles 0 bytes consed --> DONE ;; hash-table (hash-time *10000num* (make-hash-table) gethash :loop-count 1 :search-keyset *5000000num*) ;;;; INSERT Evaluation took: 0.003 seconds of real time 0.004000 seconds of total run time (0.004000 user, 0.000000 system) 133.33% CPU 5,091,256 processor cycles 647,680 bytes consed ;;;; SEARCH Evaluation took: 0.301 seconds of real time 0.300019 seconds of total run time (0.300019 user, 0.000000 system) 99.67% CPU 599,936,676 processor cycles 0 bytes consed --> DONE
上の例にだけ関して云うなら、(アルゴリズムではなく実装の方の)hamtは、要素数が中くらい(数万程度？)までなら挿入/検索ともに、hash-tableに比べて若干遅い程度。
要素数が大きくなると性能は劣化するけど、不成功探索ではhash-tableよりも良い、といった感じ。
hamtも、もう少しチューニングすれば性能は向上するかもしれないけど、汎用的なハッシュマップとしては既存のもので十分かな。
*1:Bagwell, P. (2001) Ideal Hash Trees. Technical Report, 2001
*2:論文のそれとの主な相違点は以下の二つ。
1] メモリアロケーション部分が独自実装(3.3節)
2] キーの挿入及び検索の最悪の場合の処理時間を抑える方法が3.8節で示唆されているけど、特に気にしないで実装。そのため挿入するキーセットとハッシュ関数の組み合わせによっては、検索/挿入処理が終わらない可能性もある(あくまでも可能性としては、だけど)
*3:この32はAMTノードのビットマップのサイズ
*4:キーから算出したハッシュ値が、既存のキーと重複している場合は、そのハッシュ値を消費した後に、異なるハッシュ関数で別のハッシュ値が算出されることになる。そのため、ハッシュ値算出のコストが、キーの比較と同程度の場合は、必ずしもHAMTの方が効率的とは限らない。ただし、通常のハッシュテーブルの場合は、ハッシュ値の最大値はテーブルサイズに制限されるが、HAMTではint値(32bit)がフルに利用されるので、衝突率自体は低くなることが期待される。
