HAMT(もどき): Erlangへの応用
最近Erlang本を読んでいる関係もあってこことここで書いているHAMT(Hash Array Mapped Try)のErlangへの応用を試していた。
immutableでpersistentなハッシュマップをHAMTで効率的に実装できないかと。
その成果物: hashtrie-0.0.3
HAMT?
hashtrieを作ったもともとの動機は「HAMTをErlangで実装しよう」というものだけど、最終的にはほぼHAMTとは別物になってしまった。
HAMTは基本的にはAMT(Array Mapped Trie)というデータ構造から構成されている。
以下、AMTの特徴(今回に必要な分だけ + 自分理解)。
AMT(Array Mapped Trie): - トライの配列による実装の亜種 -- 配列による実装の、無駄な領域を多分に確保しなければならないという問題点を解決 - トライの各ノードの子ノードの可否を判断するためのビットマップと実際に子ノードを保持する配列からなる -- N番目の子ノードの存在判定は、ビットマップのN番目のビットが1か0かで行う -- 配列のサイズは、各時点での実際の子ノードの数の分だけ確保する ※ 領域の無駄使いがない -- ビットマップのM番目の1ビットに対応する子ノードは、配列のM番目に格納される => 一度ビットマップを介し、添字のマッピングを行うことで、存在しない子ノードのための領域が削減可能
AMTを操作するためには「N番目のビットが1かどうかの判定」や「ビットマップの特定の範囲に含まれる1ビットの数のカウント(CTPOP*1 )」、「子ノードの増減毎の配列のリサイズ*2」といった処理が必要となる。
これらの処理がErlangでは結構コストが高く効率的に実装することが難しく感じた*3ので、結局hashtrieはAMTを使わないで実装することになった。
では、どの部分がHAMTを参考にしているのか。
- キーのハッシュ値を求めて、そのNビット毎を用いてトライを構成しているところ
- 検索/挿入/削除のオーダーを抑える方法
- HAMTは上述の操作のオーダーは要素数に対してO(1)。
- hashtrieは、AMTの代わりに(ハッシュ値の衝突対策として)リンクリストを用いているが、ハッシュテーブルのリサイズは適宜行うため、リンクリストの要素の長さは平均して4以下*5に抑えられている。
- ただし、ハッシュテーブル(配列)のリサイズは、実際には行わない
などなど、もともとHAMTを実装していたものを修正したのがhashtrieなので、ところどころに(という程ではないけど)痕跡はあり。
その他の実装の詳細に関しては、末尾にソースコードのコメントを参照。
Erlangの組み込み類似モジュールとの比較
dictモジュール(多分ハッシュマップの一種*6 )とgb_treesモジュール(バランス木*7 )との簡単な比較。
挿入時間の計測等に使用している関数の定義に関しては、末尾のhashtrie_test.erlを参照。
%%%%%%%%%%%%%% %%% データ用意 %% キーが数字のデータ Num10 = hashtrie_test:gen_int_entries(0, 10). % 0〜9をキーとしたデータを用意 Num100 = hashtrie_test:gen_int_entries(0, 100). % 0〜99をキーとしてデータを用意 Num100000 = hashtrie_test:gen_int_entries(0, 100000). % 0〜99999をキーとしたデータを用意 %% キーが文字列のデータ %% "words"は、IPA辞書から抽出した単語のリストファイル %% "words.100000"は、"words"の先頭10万行を取り出したもの %% 作成方法は"http://d.hatena.ne.jp/sile/20101002/1286019830"を参照 Str100000 = hashtrie_test:gen_str_entries("words.100000"). % IPA辞書中の10万単語をキーとしてする Str300000 = hashtrie_test:gen_str_entries("words"). % IPA辞書中の全単語をキーとする ※ 約32万単語 %%%%%%%% %%% 比較 %% 10要素の挿入処理を一万回 hashtrie_test:store_time(Num10, hashtrie, 10000). % => 92710: hashtrie 0.093秒 hashtrie_test:store_time(Num10, dict, 10000). % => 148815: dict 0.149秒 hashtrie_test:store_time(Num10, gb_trees, 10000). % => 123755: gb_trees 0.124秒 %% 100要素の挿入処理を千回 hashtrie_test:store_time(Num100, hashtrie, 1000). % => 117424: hashtrie 0.117秒 hashtrie_test:store_time(Num100, dict, 1000). % => 176493: dict 0.176秒 hashtrie_test:store_time(Num100, gb_trees, 1000). % => 245199: gb_trees 0.245秒 %% 十万要素の挿入処理 hashtrie_test:store_time(Num100000, hashtrie). % => 249197: hashtrie 0.249秒 hashtrie_test:store_time(Num100000, dict). % => 1357519: dict 1.358秒 hashtrie_test:store_time(Num100000, gb_trees). % => 789571: gb_trees 0.790秒 %% 十万要素の挿入処理(バイナリ文字列) hashtrie_test:store_time(Str100000, hashtrie). % => 273806: hashtrie 0.274秒 hashtrie_test:store_time(Str100000, dict). % => 1502530: dict 1.503秒 hashtrie_test:store_time(Str100000, gb_trees). % => 1019702: gb_trees 1.020秒 %% 構築時のメモリ消費量 ※ 測定方法が適切かどうかが、かなり怪しい hashtrie_test:store_memory(Str300000, hashtrie). % => 52380536: hashtrie 52MB hashtrie_test:store_memory(Str300000, dict). % => 65475656: dict 65MB hashtrie_test:store_memory(Str300000, gb_trees). % => 52380536: gb_trees 52MB %% 検索のための準備(数値用) Tn = hashtrie_test:store_entries(Num100000, hashtrie), done. Dn = hashtrie_test:store_entries(Num100000, dict), done. Gn = hashtrie_test:store_entries(Num100000, gb_trees), done. %% 検索のための準備(バイナリ文字列用) Ts = hashtrie_test:store_entries(Str100000, hashtrie), done. Ds = hashtrie_test:store_entries(Str100000, dict), done. Gs = hashtrie_test:store_entries(Str100000, gb_trees), done. %% 十万要素の検索(成功検索のみ) hashtrie_test:find_time(Num100000, Tn, hashtrie). % => 101788: hashtrie 0.102秒 hashtrie_test:find_time(Num100000, Dn, dict). % => 135651: dict 0.136秒 hashtrie_test:find_time(Num100000, Gn, gb_trees). % => 122649: gb_trees 0.123秒 %% 三十万要素の検索(2/3は失敗検索) hashtrie_test:find_time(Str300000, Ts, hashtrie). % => 360975: hashtrie 0.361秒 hashtrie_test:find_time(Str300000, Ds, dict). % => 750383: dict 0.750秒 hashtrie_test:find_time(Str300000, Gs, gb_trees). % => 925136: gb_trees 0.925秒
簡単に作った割には結果が良すぎて怪しい気もするけど、今回試した限りでは、hashtrieはdictやgb_treesよりも全てのケースで検索および挿入の性能が良かった。
実装
コメントを抜かせば100行ちょっとくらいなので、現時点のソースコードも載せておく。
githubからも取得可能だけど、こっちの方がコメントが豊富で説明的。
hashtrie.erl
%% File : hashtrie.erl %% Description: ハッシュテーブルとトライの合の子のようなマップの実装 -module(hashtrie). -export([new/0, size/1, find/2, store/3, remove/2, foreach/2]). -vsn("0.0.3"). %% macro -define(EMPTY_TABLE, {[], [], [], [], [], [], [], [],[], [], [], [], [], [], [], []}). % 各次元のハッシュテーブルの初期値 ※1 -define(hash(Key), erlang:phash2(Key)). % ハッシュ関数 -define(index(HashCode), ((HashCode band 2#1111)+1)). % ハッシュ値からハッシュテーブル用の添字を取り出す -define(nth_index(HashCode,N), (((HashCode bsr (4*N)) band 2#1111)+1)). % ハッシュ値からN次元目のハッシュテーブル用の添字を取り出す -define(next(HashCode), (HashCode bsr 4)). % 次の次元用にハッシュ値をシフトする -define(resize(Idx,Tab,Dep,N), resize_impl(element(Idx, Tab), Dep-1,N)).% ハッシュテーブルリサイズ1。対応する関数呼び出しを短縮するだけ。 -define(relocate(Idx,Tab,N), relocate_entries(element(Idx, Tab), N)). % ハッシュテーブルリサイズ2。対応する関数呼び出しを短縮するだけ。 % ※1: 一般的には、このサイズを増やすと検索は効率的になるが(コピー量が増えるために)挿入/削除は非効率となる。逆も同様。 %% record: hashtrie -record(hashtrie, {count = 0 :: integer(), % 要素数 next_resize_trigger = 16*4 :: integer(), % 要素数がこの値に到達した場合に、リサイズが行われる ※2 root_depth = 0 :: integer(), root = ?EMPTY_TABLE :: tuple() }). -opaque hashtrie() :: #hashtrie{}. % ※2: 16*4の16は、各次元でのハッシュテーブルのサイズ。 % 4は、リサイズ直前時における要素を保持するリンクリストの平均的な長さ(要素数)に対応する。 ※ ハッシュ値が完全にキーを分散させると仮定した場合 % この値が小さいほど、(要素に対して十分なサイズのハッシュテーブルが用意されるため)キーの衝突は少なくなるが、 % リサイズ直後の領域の無駄も大きくなる。※ リサイズ直後のテーブルの使用率は、N/16。そのため16(以上)にした場合が、一番領域を節約できる %% function: new -spec new() -> hashtrie(). new() -> #hashtrie{}. %% function: size -spec size(hashtrie()) -> integer(). size(#hashtrie{count=Cnt}) -> Cnt. %% function: find -spec find(any(), hashtrie()) -> {value,any()} | false. find(Key, #hashtrie{root=Tab, root_depth=Dep}) -> % キーのハッシュ値が同じ要素のリストから、キーがKeyと等しい要素を検索する lists:keysearch(Key, 1, find_candidates(?hash(Key), Tab, Dep)). % ハッシュテーブルを辿って、キーのハッシュ値が衝突した要素のリストを取得する find_candidates(Hash, Tab, 0) -> element(?index(Hash), Tab); find_candidates(Hash, Tab, Dep) -> find_candidates(?next(Hash), element(?index(Hash),Tab), Dep-1). %% function: store -spec store(any(), any(), hashtrie()) -> hashtrie(). store(Key, Value, #hashtrie{count=Cnt,next_resize_trigger=Cnt}=Trie) -> store(Key, Value, resize(Trie)); % 要素数が一定数に達した場合、ハッシュテーブルをリサイズしてから挿入を行う store(Key, Value, #hashtrie{root=Tab, root_depth=Dep, count=Cnt}=Trie) -> {NewTab, NewCnt} = store_impl(Key, Value, ?hash(Key), Tab, Dep, Cnt), Trie#hashtrie{root=NewTab, count=NewCnt}. % 新しいテーブルと要素数をセットする % 要素の挿入: % - ハッシュテーブルを次元数分(リサイズした回数)だけ辿った後に要素を追加する % - 探索パスに含まれるテーブルは毎回コピーする必要がある store_impl(Key, Value, Hash, Tab, 0, Cnt) -> Idx = ?index(Hash), {NewEntries, NewCnt} = list_insert(Key, Value, element(Idx,Tab), [], Cnt), % リストに要素を追加 {setelement(Idx,Tab,NewEntries), NewCnt}; % 新しいリストをセットする store_impl(Key, Value, Hash, Tab, Dep, Cnt) -> Idx = ?index(Hash), {NewSubTab, NewCnt} = store_impl(Key, Value, ?next(Hash), element(Idx,Tab), Dep-1, Cnt), {setelement(Idx,Tab,NewSubTab), NewCnt}. % 新しいサブテーブルをセットする % 要素の追加: 既に同じキーがある場合は、その値を更新するだけにする list_insert(Key, Value, [{Key,_}|Entries], Acc, Count) -> {[{Key,Value}|Acc]++Entries, Count}; list_insert(Key, Value, [], Acc, Count) -> {[{Key,Value}|Acc], Count+1}; list_insert(Key, Value, [Head|Entries], Acc, Count) -> list_insert(Key, Value, Entries, [Head|Acc], Count). % ハッシュテーブルのリサイズ resize(#hashtrie{root=Tab,root_depth=Dep,next_resize_trigger=Size}=Trie) -> NewTab = resize_impl(Tab, Dep, Dep+1), Trie#hashtrie{root=NewTab, root_depth=Dep+1, next_resize_trigger=Size*16}. % 要素(のリスト)を格納するテーブルに達した場合: 一次元分テーブルを増やして、要素をそこに再分配する resize_impl(Tab, 0, N) -> {?relocate(01,Tab,N),?relocate(02,Tab,N),?relocate(03,Tab,N),?relocate(04,Tab,N), ?relocate(05,Tab,N),?relocate(06,Tab,N),?relocate(07,Tab,N),?relocate(08,Tab,N), ?relocate(09,Tab,N),?relocate(10,Tab,N),?relocate(11,Tab,N),?relocate(12,Tab,N), ?relocate(13,Tab,N),?relocate(14,Tab,N),?relocate(15,Tab,N),?relocate(16,Tab,N)}; % それ以外は単純に丸ごとコピーするだけ resize_impl(Tab, Dep, N) -> {?resize(01,Tab,Dep,N),?resize(02,Tab,Dep,N),?resize(03,Tab,Dep,N),?resize(04,Tab,Dep,N), ?resize(05,Tab,Dep,N),?resize(06,Tab,Dep,N),?resize(07,Tab,Dep,N),?resize(08,Tab,Dep,N), ?resize(09,Tab,Dep,N),?resize(10,Tab,Dep,N),?resize(11,Tab,Dep,N),?resize(12,Tab,Dep,N), ?resize(13,Tab,Dep,N),?resize(14,Tab,Dep,N),?resize(15,Tab,Dep,N),?resize(16,Tab,Dep,N)}. % ハッシュテーブルを新しく作成し、そこにリスト内の要素を分配する relocate_entries(Entries, N) -> lists:foldl(fun({K,_}=Entry, NewTab) -> Idx = ?nth_index(?hash(K),N), % リスト内のキーのハッシュ値の0〜N-1までの値は全て等しい(衝突していた)ので、N番目の値を用いて分配する setelement(Idx,NewTab,[Entry|element(Idx,NewTab)]) end, ?EMPTY_TABLE, % 新しく追加される空のハッシュテーブル Entries). %% function: remove %% TODO: 要素数がある程度少なくなったら、ハッシュテーブルを少ない方にリサイズした方が良さそう -spec remove(any(), hashtrie()) -> hashtrie(). remove(Key, #hashtrie{root=Tab, root_depth=Dep, count=Cnt}=Trie) -> {NewTab,NewCnt} = remove_impl(Key, ?hash(Key), Tab, Dep, Cnt), Trie#hashtrie{root=NewTab,count=NewCnt}. remove_impl(Key, Hash, Tab, 0, Cnt) -> Idx = ?index(Hash), {NewEntries, NewCnt} = list_remove(Key, element(Idx,Tab), [], Cnt), {setelement(Idx,Tab,NewEntries), NewCnt}; remove_impl(Key, Hash, Tab, Dep, Cnt) -> Idx = ?index(Hash), {NewSubTab, NewCnt} = remove_impl(Key, ?next(Hash), element(Idx,Tab), Dep-1, Cnt), {setelement(Idx,Tab,NewSubTab), NewCnt}. list_remove(_, [], Acc, Cnt) -> {Acc, Cnt}; list_remove(Key, [{Key,_}|Entries], Acc, Cnt) -> {Acc++Entries, Cnt-1}; list_remove(Key, [Head|Entries], Acc, Cnt) -> list_remove(Key, Entries, [Head|Acc], Cnt). %% function: foreach -spec foreach(function(), hashtrie()) -> done. foreach(Fn, #hashtrie{root=Tab, root_depth=Dep}) -> foreach_impl(Fn, Tab, 1, Dep). foreach_impl(Fn, Entries, _, -1) -> lists:foreach(Fn, Entries); foreach_impl(_, _, 33, _) -> done; foreach_impl(Fn, Tab, Idx, Dep) -> foreach_impl(Fn, element(Idx, Tab), 1, Dep-1), foreach_impl(Fn, Tab, Idx+1, Dep).
hashtrie_test.erl
%% File : hashtrie_test.erl %% Descriptoin : hashtrieモジュールとdictモジュールとgb_treesモジュールの性能比較用関数の集まり -module(hashtrie_test). -export([gen_int_entries/2, gen_str_entries/1]). -export([store_entries/2, store_entries/3, store_loop/4, find_entries/3]). -export([store_time/2, store_time/3, find_time/3]). -export([store_memory/2]). gen_int_entries(Start,End) -> lists:map(fun (X) -> {X,X} end, lists:seq(Start,End-1)). gen_str_entries(Filepath) -> {ok, In} = file:open(Filepath, read), read_lines(In,[],0). read_lines(In, Lines, LineNum) -> case file:read_line(In) of {ok, Line} -> BinaryLine = list_to_binary(string:strip(Line,right,$\n)), read_lines(In, [{BinaryLine,LineNum}|Lines], LineNum+1); eof -> lists:reverse(Lines) end. store_entries(Entries, InitObj, StoreFn) -> lists:foldl(fun ({K,V},T) -> StoreFn(K, V, T) end, InitObj, Entries). store_entries(Entries, hashtrie) -> hashtrie_test:store_entries(Entries, hashtrie:new(), fun hashtrie:store/3); store_entries(Entries, dict) -> hashtrie_test:store_entries(Entries, dict:new(), fun dict:store/3); store_entries(Entries, gb_trees) -> hashtrie_test:store_entries(Entries, gb_trees:empty(), fun gb_trees:insert/3). store_loop(_, _, _, 0) -> done; store_loop(Entries, InitObj, StoreFn, LoopCount) -> store_entries(Entries, InitObj, StoreFn), store_loop(Entries, InitObj, StoreFn, LoopCount-1). find_entries(Entries, Obj, FindFn) -> lists:foldl(fun ({K,_}, Cnt) -> case FindFn(K, Obj) of {_,_} -> Cnt+1; _ -> Cnt end end, 0, Entries). extract_time({Time,_}) -> Time. store_time(Entries, MapType) -> extract_time(timer:tc(?MODULE, store_entries, [Entries, MapType])). store_time(Entries, hashtrie, LoopCount) -> extract_time(timer:tc(?MODULE, store_loop, [Entries, hashtrie:new(), fun hashtrie:store/3, LoopCount])); store_time(Entries, dict, LoopCount) -> extract_time(timer:tc(?MODULE, store_loop, [Entries, dict:new(), fun dict:store/3, LoopCount])); store_time(Entries, gb_trees, LoopCount) -> extract_time(timer:tc(?MODULE, store_loop, [Entries, gb_trees:empty(), fun gb_trees:insert/3, LoopCount])). find_time(Entries, Trie, hashtrie) -> extract_time(timer:tc(?MODULE, find_entries, [Entries, Trie, fun hashtrie:find/2])); find_time(Entries, Dict, dict) -> extract_time(timer:tc(?MODULE, find_entries, [Entries, Dict, fun dict:find/2])); find_time(Entries, Tree, gb_trees) -> extract_time(timer:tc(?MODULE, find_entries, [Entries, Tree, fun gb_trees:lookup/2])). %% メモリ消費量を測るのはこれで良い？ %% - もっと良い方法がありそう store_memory(Entries, MapType) -> erlang:garbage_collect(), Before = erlang:memory(processes), _Map = store_entries(Entries, MapType), After = erlang:memory(processes), After-Before.
*1:Count Population
*2:ちょうど子ノード分だけの領域しか使われないようにするために、子ノードを保持する配列は、(要素の追加や削除による)子ノード増減の度に適切なサイズのものが新たに用意される。配列確保及び解放が頻繁に繰り返されるので、確保/解放自体のコストやGCのコストが結構掛かる。もともと参照した論文では、この配列のアロケート周りを自前で管理することでコストを抑えていた
*3:まだErlangは初心者なので、それが本当かどうかは分からないけど
*4:もしくはN回。Nは任意の定数値。
*5:この値はパラメータをいじることで変更可能。ソースコードを参照。
*6:R14Bのソースコードのコメントには"We use the dynamic hashing techniques by Per-
*7:R14Bのソースコードのコメントには"An efficient implementation of Prof. Arne Andersson's General Balanced Trees. These have no storage overhead compared to plain unbalanced binary trees, and their performance is in general better than AVL trees.
