A proposal and implementation of a fast hash table algorithm which suppresses decrease in search performance that is caused by repeating addition and deletion of elements (C/C++) August 2015 - January 2017
Abstract
Although the hash table of the Open Addressing method shows high search performance, the search performance is decreased by repeating addition and deletion of elements. And the hash table of the Closed Addressing method doesn't change search performance, although search performance is low because of its pointer connections make cache miss. Therefore, I developed an algorithm that embeds a doubly linked list in the Open Addressing hash table. When a load factor is 50%, this algorithm is 2.18 times for insertion, 1.23 to 1.44 times for search and 1.80 times for deletion faster than std::unordered_map in Microsoft Visual C++ 2015 respectively. Moreover, by adopting the doubly linked list, Unlike the conventional Open Addressing type hash table, decreases of search performance due to addition and deletion of elements is suppressed under 6%. The suppression of decrease in search performance is due to the ability to insert elements in the place where is little need to seek by adopting the doubly linked list. (Added on March 10, 2017)
従来の Open Addressing 方式のハッシュテーブルは， 検索性能は高いものの，要素の追加と削除を繰り返すことで， 検索性能が低下することが知られています． また， 要素の追加と削除により，検索性能が変化しない， Closed Addressing 方式のハッシュテーブルは， 検索性能が低いことが知られています． この投稿では，高速な Open Addressing 方式のハッシュテーブルに， 双方向リスト構造 (鎖型構造) を埋め込むアルゴリズムを開発し， key: UINT64，value: UINT64 のペアについて， Microsoft Visual C++ 2015 に実装されている std::unorderd_map ※1 と比較して， 挿入 2.18 倍，検索 1.23~1.44 倍，削除 1.80 倍の性能を達成しました． また， 双方向リスト構造の採用により， 従来の Open Addressing 型のハッシュテーブルと異なり， 要素の追加と削除による検索性能の低下を 6% 以内に抑えました ※2．
従来の Open Addressing 方式のハッシュテーブルは， 検索性能は高いものの，要素の追加と削除を繰り返すことで， 検索性能が低下することが知られています． また， 要素の追加と削除により，検索性能が変化しない， Closed Addressing 方式のハッシュテーブルは， 検索性能が低いことが知られています． この投稿では，高速な Open Addressing 方式のハッシュテーブルに， 双方向リスト構造 (鎖型構造) を埋め込むアルゴリズムを開発し， key: UINT64，value: UINT64 のペアについて， Microsoft Visual C++ 2015 に実装されている std::unorderd_map ※1 と比較して， 挿入 2.18 倍，検索 1.23~1.44 倍，削除 1.80 倍の性能を達成しました． また， 双方向リスト構造の採用により， 従来の Open Addressing 型のハッシュテーブルと異なり， 要素の追加と削除による検索性能の低下を 6% 以内に抑えました ※2．
Introduction
ハッシュテーブルは，辞書のように，ある key に対応する value の挿入・取得および削除を，O(1) (定数時間) で実現するためのアルゴリズムです．例えば，次の単語をハッシュテーブルに格納し検索するとき，
ハッシュテーブルの主な方式には， Closed Addressing (別名，Open Hash) と Open Addressing (別名，Closed Hash) があり，代表的な実装として，Chain Hash と Linear Probing があげられます．
Chain Hash では，要素の追加や削除を行っても性能が安定していますが， ポインタにより要素を接続するため，キャッシュミスが発生しやすく，速度は低速です． 一方， Linear Probing では， 連続したメモリ空間に要素を挿入するため， 検索は高速です． しかし， 要素削除時に要素をそのまま削除すると検索不能となるため， 削除マークの付加を削除と見なします． したがって，削除マークに対しても key の一致を確認せざるを得ないため，検索速度は低下します． (このとき，テーブル要素が削除マークだらけになることを，クラスタリングと呼びます)
現在，ハッシュテーブルには， 「キャッシュミスをせず高速」かつ「削除をしても性能低下が発生しない (クラスタリングせず，リハッシュによる検索性能の維持・管理が不要な)」 アルゴリズムが求められています．
そして，これを解決するアルゴリズムとして，Hopscotch hashing が 2008 年に提案されました [3][4]． この Hopscotch hashing では，要素の接続を 4 or 8 Byte のビット値として表現し，4 Byte なら 31 個先の要素まで，8 Byte なら 63 個先の要素まで表現することができます (アルゴリズムは [2][3][4] 参照のこと)．
現在，Hopscotch hashing では，要素の接続情報をビット値として扱っていますが， 整数値として扱えば，4 Byte の情報量で，$2^{8\times4} - 1 = 4294967295$ 要素先まで， 8 Byte では，$2^{8\times8} - 1 = 18446744073709551615$ 要素先まで表現可能です．
この投稿では，Hopscotch hashing の提案する「4 or 8 Byte のビット値」ではなく「1 Byte 整数値」として， 要素の接続をハッシュテーブル上の構造体に持たせ，要素の付加情報を削減しました． また，Chain Hash のような鎖構造 (双方向リスト構造) を，連続したアドレス空間上 (ハッシュテーブル上) に作成し， クラスタリングを起こさず，かつ，Linear Probing のようにキャッシュミスが少ない， 高速なハッシュテーブルを作成しましす．(※ただし，Hopscotch hashing 自身は，使い方がよくわからなかったので，std::unorderd_map との比較のみ)
干物妹（ひもうと） 家の中では様々な事を面倒くさがり、適当に済ませてしまう妹。 「家でのうまるは――だ」 《類義語》干物女 集英社「妹辞典」より [1]索引となる「ひもうと」が key となり，「家の中では様々な事を面倒くさがり、適当に済ませてしまう妹。」が value となります． ハッシュテーブルでは， ハッシュ関数に通した key の値を，value の格納されているテーブルアドレスと対応させることで， 定数時間による検索を可能とします． 各ハッシュテーブルアルゴリズムの説明は，参考資料 [2] に譲ります．
ハッシュテーブルの主な方式には， Closed Addressing (別名，Open Hash) と Open Addressing (別名，Closed Hash) があり，代表的な実装として，Chain Hash と Linear Probing があげられます．
Chain Hash では，要素の追加や削除を行っても性能が安定していますが， ポインタにより要素を接続するため，キャッシュミスが発生しやすく，速度は低速です． 一方， Linear Probing では， 連続したメモリ空間に要素を挿入するため， 検索は高速です． しかし， 要素削除時に要素をそのまま削除すると検索不能となるため， 削除マークの付加を削除と見なします． したがって，削除マークに対しても key の一致を確認せざるを得ないため，検索速度は低下します． (このとき，テーブル要素が削除マークだらけになることを，クラスタリングと呼びます)
Chain Hash
|
Linear Probing
| |
|---|---|---|
| 検索速度 | 遅い | 速い |
| 管理 | 不要 | 削除を繰り返すと性能が低下 -> リハッシュ ※3 が必要 |
現在，ハッシュテーブルには， 「キャッシュミスをせず高速」かつ「削除をしても性能低下が発生しない (クラスタリングせず，リハッシュによる検索性能の維持・管理が不要な)」 アルゴリズムが求められています．
そして，これを解決するアルゴリズムとして，Hopscotch hashing が 2008 年に提案されました [3][4]． この Hopscotch hashing では，要素の接続を 4 or 8 Byte のビット値として表現し，4 Byte なら 31 個先の要素まで，8 Byte なら 63 個先の要素まで表現することができます (アルゴリズムは [2][3][4] 参照のこと)．
現在，Hopscotch hashing では，要素の接続情報をビット値として扱っていますが， 整数値として扱えば，4 Byte の情報量で，$2^{8\times4} - 1 = 4294967295$ 要素先まで， 8 Byte では，$2^{8\times8} - 1 = 18446744073709551615$ 要素先まで表現可能です．
この投稿では，Hopscotch hashing の提案する「4 or 8 Byte のビット値」ではなく「1 Byte 整数値」として， 要素の接続をハッシュテーブル上の構造体に持たせ，要素の付加情報を削減しました． また，Chain Hash のような鎖構造 (双方向リスト構造) を，連続したアドレス空間上 (ハッシュテーブル上) に作成し， クラスタリングを起こさず，かつ，Linear Probing のようにキャッシュミスが少ない， 高速なハッシュテーブルを作成しましす．(※ただし，Hopscotch hashing 自身は，使い方がよくわからなかったので，std::unorderd_map との比較のみ)
Algorism
ハッシュテーブルを整理しながら，挿入と削除を行うには，テーブル上に双方向リストを実現する必要があります．(片方向リストによっても似たようなことは可能ですが，今回は双方向リストとして実現しました．(旧ブログに片方向を模索した手書きの pdf があります))
このとき，ひと続きのハッシュテーブル上で，双方向リストを実現するためには，挿入および削除操作を場合分けする必要があります．ここでは，その場合分けの一例と，テーブル要素のデータ構造を示します．
Data structure (データ構造)
下記にkey value ペア 1 要素のデータ構造を示します．
struct HashStruct{
UINT64 key; // key
void* value; // value
UINT8 previous; // 前の要素へのシフト数．(0: チェーンの先頭，1~254: 接続距離，255: 空の要素)
UINT8 next; // 次の要素へのシフト数．
};
Insertion (挿入)
本アルゴリズムの大きな特徴として，要素挿入時に可能な限り連続したアドレスに，新規挿入を行うことが上げられます．
また，本来のアドレスに挿入できなかったため，
周辺のアドレスにチェーンして挿入された要素のアドレスが，
新規に挿入する要素のアドレスと重複する場合，
新規に挿入する要素が，周辺を走査することなく検索可能となるように，
要素の整理を行いながら挿入されます．
このような操作は，
双方向リスト構造を埋め込むことによって始めて実現可能となります．
このとき発生する余分な挿入コストは，
実際のところ，
教科書通りの Linear Probing を実装した際にも発生する空き要素の走査コストに加えて，
要素のつなぎ替えコストが余分に必要となります．
要素削除時においては，
新しく発生した空き要素に，
同一チェーン内の要素を移動することで，
先頭からの距離が短縮される場合，
最も遠い要素を空いている近い要素へ移動させます．
これにより，要素の追加と削除を繰り返すことで引き起こされる性能低下を緩和します．
■Insertion: Case 1 (挿入の場合分け: ①)
■Insertion: Case 2 (挿入の場合分け: ②)
■Insertion: Case 3 (挿入の場合分け: ③)
■Insertion: Case 4 (挿入の場合分け: ④)
■Insertion: Case 5 (挿入の場合分け: ⑤)
■Insertion: Case 6 (挿入の場合分け: ⑥)
■Insertion: Case 7 (挿入の場合分け: ⑦)
■Insertion: Case 8 (挿入の場合分け: ⑧)
■Insertion: Case 9 (挿入の場合分け: ⑨)
■Insertion: Case 10 (挿入の場合分け: ⑩)
■Insertion: Case 11 (挿入の場合分け: ⑪)
■Insertion: Case 2 (挿入の場合分け: ②)
■Insertion: Case 3 (挿入の場合分け: ③)
■Insertion: Case 4 (挿入の場合分け: ④)
■Insertion: Case 5 (挿入の場合分け: ⑤)
■Insertion: Case 6 (挿入の場合分け: ⑥)
■Insertion: Case 7 (挿入の場合分け: ⑦)
■Insertion: Case 8 (挿入の場合分け: ⑧)
■Insertion: Case 9 (挿入の場合分け: ⑨)
■Insertion: Case 10 (挿入の場合分け: ⑩)
■Insertion: Case 11 (挿入の場合分け: ⑪)
Deletion (削除)
■Deletion: Case 1 (削除の場合分け: ①)
■Deletion: Case 2 (削除の場合分け: ②)
■Deletion: Case 3 (削除の場合分け: ③)
■Deletion: Case 4 (削除の場合分け: ④)
■Deletion: Case 2 (削除の場合分け: ②)
■Deletion: Case 3 (削除の場合分け: ③)
■Deletion: Case 4 (削除の場合分け: ④)
Benchmarks
計測はそれぞれ 50 回行い，その平均をプロットしています．エラーバーは，50 回の測定における標準偏差を示します．(いずれのグラフも，縦軸の値が大きいほど，性能が高いことを示します)
■測定環境
■Maximum load factor
次に，実行速度を std::unordered_map と比較しました．縦軸は [query/ms] で，1 [ms] あたりに何件の query を処理できたかを，横軸はハッシュテーブルの load factor (座席占有率) を，それぞれ表します．
■Insertion speed
■Find speed: Case 1
■Find speed: Case 2
■Erase speed
■測定環境
・Microsoft Windows 8.1 x64
・Microsoft Visual C++ 2015 (Release，x64，でビルド)
・Intel Core i5-5200U CPU @ 2.20GHz
・DDR3 SDRAM 4.0GB
・ハッシュ関数: FNV-1
まず，メモリ効率 (Maximum load factor) を測定しました．・Microsoft Visual C++ 2015 (Release，x64，でビルド)
・Intel Core i5-5200U CPU @ 2.20GHz
・DDR3 SDRAM 4.0GB
・ハッシュ関数: FNV-1
■Maximum load factor
Figure 1. に ICHashT のメモリ効率の測定結果を示します．テーブルサイズ $6\times10^{2}$ 前後で，
Maximum load factor が低下しているのは，
接続距離 (シフト数) の最大値が ${\rm UINT8} - 1$ の $(2^6-1)-1=(256-1)-1=254$ となっており，
見かけ上のテーブルサイズより，254 要素分多く確保しているためです．
次に，実行速度を std::unordered_map と比較しました．縦軸は [query/ms] で，1 [ms] あたりに何件の query を処理できたかを，横軸はハッシュテーブルの load factor (座席占有率) を，それぞれ表します．
■Insertion speed
Figure 2. に ICHashT および std::unorderd_map の挿入速度を示します．Load factor 50 % のとき，ICHashT は，std::unorderd_map より，2.18 倍高速に動作します ※．
※
※
Load factor 50 % のとき，ICHashT: 6450 [query/ms], std::unorderd_map: 2965 [query/ms]
■Find speed: Case 1
Figure 3. に ICHashT および std::unorderd_map の，挿入されていない要素に対する検索速度を示します．
つまり，ハッシュテーブル中に存在しない要素を検索し，存在しないことの確認を行っています ※．
Load factor 50 % のとき，ICHashT は，std::unorderd_map より，要素削除前で 1.24 倍，要素削除後で 1.23 倍，高速に動作します ※．
また，要素削除前と削除後における速度変化は，ICHashT で 0.98 倍，std::unorderd_map で 0.99 倍です．
Load factor が低い場合は，std::unorderd_map の方が非常に高速に動作しますが，
メモリ効率の問題から，ハッシュテーブルは，通常 Load factor 50 % 以下で運用されることは少ないと考えられるため，
低い Load factor で高い性能が引き出せることは，それほど重要ではありません．
※
※
※
例えば，仮にある検索エンジンが，一つの検索リクエストを何台かのマシン上に展開されているハッシュテーブルを利用して処理する場合，
全てのテーブル上に一致するキーワードが存在するとは限りません．このような場合を想定してます)
※
Load factor 50 % のとき，要素削除前，ICHashT: 11932 [query/ms], std::unorderd_map: 9655 [query/ms]
Load factor 50 % のとき，要素削除後，ICHashT: 11717 [query/ms], std::unorderd_map: 9536 [query/ms]
Load factor 50 % のとき，要素削除後，ICHashT: 11717 [query/ms], std::unorderd_map: 9536 [query/ms]
■Find speed: Case 2
Figure 4. に ICHashT および std::unorderd_map の，挿入されている要素に対する検索速度を示します．
つまり，ハッシュテーブル中に存在する要素に対してのみ検索を行います．
Load factor 50 % のとき，ICHashT は，std::unorderd_map より，要素削除前で 1.43 倍，要素削除後で 1.44 倍，高速に動作します ※．
また，要素削除前と削除後における速度変化は，ICHashT で 0.95 倍，std::unorderd_map で 0.94 倍です．
※
※
Load factor 50 % のとき，要素削除前，ICHashT: 13019 [query/ms], std::unorderd_map: 9097 [query/ms]
Load factor 50 % のとき，要素削除後，ICHashT: 12333 [query/ms], std::unorderd_map: 8592 [query/ms]
Load factor 50 % のとき，要素削除後，ICHashT: 12333 [query/ms], std::unorderd_map: 8592 [query/ms]
■Erase speed
Figure 5. に ICHashT および std::unorderd_map の削除速度を示します．Load factor 50 % のとき，ICHashT は，std::unorderd_map より，1.80 倍高速に動作します ※．
※
※
Load factor 50 % のとき，ICHashT: 6100 [query/ms], std::unorderd_map: 3398 [query/ms]
Summary
■Open Addressing 方式のハッシュテーブルに，双方向リスト構造 (鎖型構造) を埋め込むアルゴリズムを提案した．
■Microsoft Visual C++ 2015 に実装されている std::unorderd_map と比較して，挿入で 2.18 倍，検索で 1.23~1.44 倍，削
除で 1.80 倍 (いずれも Load factor 50 % 時)，それぞれ高速に動作することを確認した．また，要素の追加と削除による検索
性能の低下を 6% 以下に抑えた．
■Microsoft Visual C++ 2015 に実装されている std::unorderd_map と比較して，挿入で 2.18 倍，検索で 1.23~1.44 倍，削
除で 1.80 倍 (いずれも Load factor 50 % 時)，それぞれ高速に動作することを確認した．また，要素の追加と削除による検索
性能の低下を 6% 以下に抑えた．
Future work
■ Unix 環境を用意して，g++ における std::string との実装速度を比較する．(仮想環境では上手く測定できなかったため)
■ 既存の仕様の明確なハッシュテーブルと比較し，ハッシュ値のテーブル長除算値が衝突しない限り，追加のテーブル走査が不要なため，高速化に寄与していることを確認する．
■データ構造の要素接続を，テーブルサイズに応じて，UINT8 と UINT16 を動的に切り替えるようにする．(付加情報の増加によ
りキャッシュミスも増えるが，より高い Load factor まで動くようになる)
-> Microsoft Visual C++ 2015 がクラス内に定義したテンプレート関数への関数ポインタを処理できない (未定義またはコン
パイラのバグ) ため，難航中．(クラス外で処理すればコンパイルできるが，クラス内変数へのアクセスで引数が増えすぎる
ので，クラス内変数をすべて構造体にまとめるなどの工夫が必要．(ただし，ここまでやると，オブジェクト指向とは？にな
る))
■次の <key, value> ペアのサポート
- <UINT64, std::string>
- <UINT64, std::string>
- <std::string, std::string>
- <std::string, std::string>
■Hopscotch との性能比較
■計算量の数学的考察
■次の断片化防止処理を組み込み，要素削除後の検索速度の低下がどの程度防がれるかと，要素削除コストの上昇幅を確認する．
■ 既存の仕様の明確なハッシュテーブルと比較し，ハッシュ値のテーブル長除算値が衝突しない限り，追加のテーブル走査が不要なため，高速化に寄与していることを確認する．
■データ構造の要素接続を，テーブルサイズに応じて，UINT8 と UINT16 を動的に切り替えるようにする．(付加情報の増加によ
りキャッシュミスも増えるが，より高い Load factor まで動くようになる)
-> Microsoft Visual C++ 2015 がクラス内に定義したテンプレート関数への関数ポインタを処理できない (未定義またはコン
パイラのバグ) ため，難航中．(クラス外で処理すればコンパイルできるが，クラス内変数へのアクセスで引数が増えすぎる
ので，クラス内変数をすべて構造体にまとめるなどの工夫が必要．(ただし，ここまでやると，オブジェクト指向とは？にな
る))
@ADMIS_Walker? (おどおど) あどみす (@ADMIS_Walker) 2016年12月30日
class A{
public:
template<T>T plus(T a,T b);
void PL();
};
void A::PL(){
int (*pl)(int,int) = plus<int>;
}
は不可よりplusは外に出すか
- <UINT64, std::string>
- <UINT64, std::string>
- <std::string, std::string>
- <std::string, std::string>
■Hopscotch との性能比較
■計算量の数学的考察
■次の断片化防止処理を組み込み，要素削除後の検索速度の低下がどの程度防がれるかと，要素削除コストの上昇幅を確認する．
要素削除後に，下記の処理を，接続距離 (シフト数) が ${\rm UINT8} - 1$ の $(2^6-1)-1=(256-1)-1=254$ の範囲に収まり，かつ，連鎖的に発生する空の要素に，詰める対象がなくなるまで繰り返す．
□Prevention of fragmentation: Case 1 (断片化防止処理: ①)
□Prevention of fragmentation: Case 2 (断片化防止処理: ②)
□Prevention of fragmentation: Case 1 (断片化防止処理: ①)
Source code
今回作成したハッシュテーブルのソースコードを GitHub に上げておきます．このハッシュテーブルは，現在 key: UINT64，value: UINT64 or void* にのみ対応しています．
std::string などには，対応していませんので，例えば，void* の先に std::string などを接続すると，ポインタ接続になるためキャッシュミスが増加し，std::unoreded_map<UINT64, std::string> と比較して，大幅に速度が落ちます．GCC でのコンパイルは行っていませんが，大きな変更なくコンパイルできるはずです．また，ライセンスは MIT です．
References
[1]「干物妹!うまるちゃん」冒頭.
[2] あなたの知らないハッシュテーブルの世界: スライド ・YouTube.
[3] en.wikipedia.org Hopscotch hashing.
[4] Hopscotch Hashing Maurice Herlihy, Nir Shavit and Moran Tzafrir in 2008.
[2] あなたの知らないハッシュテーブルの世界: スライド ・YouTube.
[3] en.wikipedia.org Hopscotch hashing.
[4] Hopscotch Hashing Maurice Herlihy, Nir Shavit and Moran Tzafrir in 2008.
※1.
Microsoft Visual C++ 2015 で実装されている std::unorderd_map が Closed Addressing 型 か Open Addressing 型かの記述は発見できませんでした．
※2.
削除マークを使用しないため，クラスタリングは発生しません．
しかし，
削除処理において，要素の断片化防止処理が再帰的に必要となるケースを省略したため，
挿入した要素を削除した場合，挿入前と全く同じテーブル構造となるわけではありません．
また，
6 % 以内となっているのは，要素の挿入と削除を一往復行ったの場合となります．
複数回に渡る要素の挿入と削除の反復が，
極端な性能低下を引き起こすとは考えにくいですが，
このような複雑な条件での実測は行っていません．
※3.
リハッシュはハッシュテーブルを再構成することです．
ハッシュテーブルでは，リハッシュのコストが非常に膨大です．少ないメモリで，なるべくリハッシュしないように，高い Load Factor (座席占有率) まで，稼働することが求められます．
ハッシュテーブルでは，リハッシュのコストが非常に膨大です．少ないメモリで，なるべくリハッシュしないように，高い Load Factor (座席占有率) まで，稼働することが求められます．
※この記事は，昔の記事の刷り直しです．致命的なバグの修正と，std::unorderd_map との比較が主な進捗となります．
0 件のコメント:
コメントを投稿