mrubyのハッシュ

直してプルリしたら受け付けられたので喜びのメモ。ハッシュについて。
https://github.com/mruby/mruby/commit/00353a3c42e0a65fbf2e2b355535ff6fce2e872a#include/mruby/khash.h

Rubyではインスタンス変数やメソッドのテーブルはハッシュテーブルとして保持されている。理論的には配列でもいいが、名前で検索する必要があるから、データが多くなるとハッシュのほうが効率がいい。mrubyでは配列を使うようにコンパイルすることもできる。
ハッシュは格納するキーから算出したハッシュ値を使って書き込む位置を決めるわけだが、完全ハッシュにできるわけもないので、違うキーを同じ位置に書き込もうとすることがよくある。この問題の解決策として代表的なアルゴリズムはチェイン法とオープンアドレス法で、mrubyはオープンアドレス法で実装されている。
オープンアドレス法では書き込もうとした位置が他のキーで埋まっていたら次の候補を試して、空いてるところに格納するように動作する。全部埋まると書き込めなくなってしまうのでその前に拡張して再作成する。読み出すときはハッシュ値から位置を定めて読み出してみるが、そこに入っているものが読もうとしたキーでない場合がありえるので、比較して、違ったら次を読みにいく。一致するキーがあればデータを読み、格納されていないところまで進んだ場合は該当なしとなる。
オープンアドレス法は埋まっていた場合の次の格納候補位置の算出方法は一定なので、書くときと読むときで必ず同じところを見に行く。じゃないと読めないからだが、たとえば同じハッシュ値になるオブジェクトが3つ入っていた場合に、2つ目を削除してしまうと、そこで検索が終わってしまって3つ目がアクセスできなくなる。これを回避するために「入ってない状態」を表すemptyと、「削除された状態」を表すdelというフラグを持つ。読み出し時はdelのものは存在しててもスルーし、emptyが発見されたらデータ無しとなるし、書き込み時はdelもしくはemptyの位置に書き込みに行く。

mrubyのハッシュアルゴリズムはkhash.hで実装されていて、いろんなデータに対応できるように全体がマクロになっている。
修正箇所はemptyのフラグとdelのフラグの持ち方で、元は1発のmallocで確保した領域の前半をempty、後半をdelに使っていたが、emptyとdelのビットを交互に配置するようにした。フラグのメモリ使用量は変わらないが、delフラグのポインタが必要なくなるのでテーブルあたり4byte減っているはずだ。
それとは別に、この修正による速度改善効果は以下の2点となる。
・emptyとdelが離れた位置にあるとデータキャッシュのラインが分かれる可能性があるが、同じアドレスに配置されるのでそれが無くなる。
・__ac_iseitherマクロでdelとemptyの両方を同時にチェックするときに、フラグメモリのアクセスが1回ですむ。
__ac_iseitherマクロはkh_existマクロで使われていて、これは何かデータがある場合に取得するという処理で使う。具体的にはGCのハッシュテーブル全探索で、インスタンス変数やメソッドテーブルを見るときに大量に発行される。つまり、主にGCが速くなる。
ao-render.rbを128指定にして動かした結果が99秒→96〜97秒になったので、だいたい2%台の改善といったところか。リスク無しで速くなるんだからいいんじゃないかな。