Dictionaryは遅い？
吉里吉里のDictionaryの作成がやたらめったら遅いという話を
方々で見かけたので、こちらのサイトを参考に原因を探ってみた。
※有用な情報を公開されている先人の方々に感謝いたします。
掲載されているテストスクリプトを実行してみると…
配列作成中 ...完了。
ary作成時間は93msです。
hash作成時間は5562msです。
ary検索時間は2msです。
hash検索時間は63msです。
確かに書かれているような結果になった。
しかし吉里吉里のソースコードを見ながら原因を探っていくうちに
どうもこのテストスクリプトにはいくつか複雑な問題があることがわかった。
Dictionaryの仕組み
Dictionaryクラスは連想配列(辞書配列)の一種で『ハッシュテーブル』という仕組みで実装されている。
通常の配列は整数値をインデックスとして使いその値の位置にデータを格納するが、
連想配列は文字列などの任意の値をキーとして使いデータを格納する。
Dictionaryクラスは文字列をキーとするハッシュテーブルである。
ハッシュテーブルの構造は基本的にはただの配列だ。
ハッシュテーブルではキーからハッシュ値を計算し、
そのハッシュ値をインデックスとして配列に値を格納する。
通常の配列に比べて余計な手間がかかっているように思うかもしれないが
このようにすることでキーに整数以外の値を使うことができるし、
要素の挿入・削除・検索を通常の配列よりもずっと高速に行うことができる。
ハッシュテーブルの落とし穴
しかしハッシュテーブルには2つの大きな落とし穴がある。
1つ目の落とし穴は異なるキーであってもハッシュ値が同じ値になる場合があるということである。
これはすなわちテーブルの同じ位置に2つ以上の要素が入る可能性があることを意味する。
Dictionaryではテーブルに格納される要素を連結リストにして複数の値を格納できるようにしている。
2つ目の落とし穴は、テーブルとなる配列を十分な大きさで確保しておかなければならないという点だ。
キーから計算されたハッシュ値はテーブルのサイズに合わせて切り取って使われる。
しかしテーブルのサイズが小さすぎると、切り取られたハッシュ値が高い頻度で重複するようになる。
ハッシュ値が頻繁に重複すると、テーブルの各要素のリストがどんどん伸びていくような形になる。
最悪の場合、ただのリストとほとんど変わらなくなり、連想配列である恩恵が失われてしまう。
かと言って、使うかもわからないの巨大なテーブルを常に用意しておくのもそれはそれで無駄だ。
キャッシュ効率が悪くなり逆に遅くなってしまう場合もある。
すなわちハッシュテーブルを効果的に使うには、適切なテーブルのサイズをいかに決めるか。
そこが肝心なのである。
Array.findが速すぎる
ハッシュテーブルについて理解したところで、さっきのテストスクリプトの結果を見てみよう。
1つ明らかに不可解な点がある。
配列の検索に比べて辞書の検索が遅すぎるのだ。
辞書の検索は配列に比べて高速になるはずである。
というかよくよく考えてみると辞書の検索が遅いわけではなく、むしろ…
配列の検索が爆速すぎる！
いくらなんでも速過ぎである。
吉里吉里のソースコードを見てみると原因は明らかだった。
tjsArray.cpp
findの実装は877行目あたり(2013/2/28現在)
Array.findは、戻り値を返す先がないと何も処理しないような実装になってる！
つまりそもそも検索処理は一切行われていない。
爆速なのは当たり前だ。
正しく検索されるようにするには
var temp = ary.find("hash_number_is_" + "%06d".sprintf(chknums[i]));
のようにして、返り値の受け取り先を用意する必要がある。
このようにして実行しなおすと…
配列作成中 ...完了。
ary作成時間は94msです。
hash作成時間は5520msです。
ary検索時間は5350msです。
hash検索時間は37msです。
期待通り(？)激遅になった！
辞書検索が速くなっているが、これはおそらくキャッシュ効率の影響だろう。
辞書作成が重い原因
そしてもう1つ不可解な点がある。
それは辞書作成の遅さに対して辞書検索が速すぎる点だ。
数値が小さいのは試行回数が少ないからだが、それにしてもちょっと速い。
不可解じゃない？いやいや不可解なのである。
なぜ不可解なのか説明するには、
そもそも辞書作成がなぜこんなに遅くなってるのかについてまず言及する必要があるだろう。
吉里吉里のDictionaryのソースコードはこちら。
tjsDictionary.cpp
辞書作成が遅い原因をずばり言おう。
辞書作成が遅いのは、辞書に追加する要素数に対して
ハッシュテーブルが小さすぎるせいである。
ハッシュテーブルが小さいとどういうことが起こるのか。
それはさっき述べた通りだ。
ハッシュ値の重複が頻繁に起き、ハッシュテーブル内の同じ位置に要素がどんどん追加されていく。
同ハッシュ値の要素はリストとして繋がれていく。
ハッシュテーブルが小さく、追加する要素数がものすごく多い場合、
このリストはものすごい長さになってしまう。
ただ…要素をリストに繋ぐ処理の負荷は軽微なもので、それ自体はさほどたいした負荷ではない。
重さの原因になっているのは、リストに新しく要素を繋ぐ際に、
リスト内に同じキーの要素がないか検索する処理の部分だ。
特に前出のサンプルスクリプトのようなケースの場合、
リスト内に同じキーの要素があるはずがないので
処理上最悪のケース…すなわちリストの頭から末尾まで毎回毎回検索が行われる。
この処理による負荷は膨大なものになる。
すなわちハッシュテーブルが小さいことによって、
辞書検索処理が極めて重くなってしまっているというのが、
辞書作成が異常に重くなる真相である。
辞書検索が速すぎる
これを理解すると、さっき辞書検索が速すぎる！と言った意味がわかるだろう。
むちゃくちゃ速いというわけではないが、なんだか想像より速い。
辞書検索処理はハッシュテーブルが小さいことによってかなり重くなってるはずなのだ。
配列の時のように検索処理自体が行われなくなっているわけでもない。
検索はキッチリ行われている！
どういうことなのか。
これはソースコードを注意深く見ると理由がわかる。
辞書検索を速くしているのは、RebuildHashという仕組みだ。
1.5秒ごとに発生するイベントによって辞書にRebuildHashフラグが立てられ、
このフラグが立った辞書を参照するとハッシュテーブルの再構築が行われるという
トリッキーな仕組みである。
ハッシュテーブルの再構築とは、辞書に格納されている要素数に応じて
ハッシュテーブルのサイズを調整するという処理だ。
この処理によってハッシュテーブルが拡張され同一要素のリストが十分に短くなる。
同一要素のリストが十分に短くなれば、リスト検索の負荷もほとんどなくなる。
ゆえに速くなるのである。
ハッシュテーブルの再構築の効果
ここでまたテストスクリプトを振り返ってみよう。
このテストスクリプトの2つめの問題は
辞書を作成した後に「完了。」と表示を行っている部分にある。
それこそが辞書検索が速くなっている鍵なのだ！
吉里吉里はイベントシステムであり、溜まったイベントはシステムに処理が返った時に実行される。
つまり『1.5秒ごとに発生するイベント』は、システムに処理を返した時に初めて実行される。
そう、「完了。」と表示している部分、そこでシステムに処理が返りイベントが実行されているのである。
これにより次に辞書を参照した時、最初に辞書の再構築が実施される。
この動作を確認するために、試しに辞書検索速度を計測する前に
1回だけ辞書検索する処理を入れて計測してみよう。
配列作成中 ...完了。
ary作成時間は94msです。
hash作成時間は5861msです。
ary検索時間は5497msです。
hash検索時間は1msです。
辞書検索が爆速！
実は30ms以上かかっていたのはハッシュテーブルの再構築の処理であり、
辞書検索自体はこれだけ高速なのである。
ただしハッシュテーブルが適切な大きさならば、だ。
次に完了と表示している部分を削除して実行してみよう。
これで、ハッシュテーブルが再構築されなかった場合の辞書検索の速度がわかる。
配列作成中 ...
ary検索時間は5354msです。
hash検索時間は90msです。
再構築処理分を加味した値よりちょっと重い。
再構築された場合と比べると…尋常じゃなく重い！
これがハッシュテーブルのサイズが適切でない場合の辞書検索の重さである。
辞書作成時にはこの負荷が大きくのしかかっているのだ。
ということで辞書作成がなぜ重いのか、原因が明確になった。
この問題を解決する方法についてはまた次回～
