Digest::MurmurHashリリース - スペクトラム

現在「とりあえずDBMを作ってみようプロジェクト」をやっていて、効率はとりあえず無視してDBMの根本的な機能(get,set,delete)だけを実装するならすぐに出来てしまうので時間効率・空間効率をどれだけ高められるかの勝負になってきます。

そこで時間効率・空間効率向上させるためにバケット空間を作ってインデックスを作ることにしました。参考は(Tokyo|Kyoto) Cabinet。バケットに散らすためには文字列を数値化してできるだけまんべんなく散り、衝突が少なくなるようなハッシュ関数を使います。ここも(Tokyo|Kyoto) Cabinetを参考にMurmurHashをRubyで書いていました。

そうだ、ハッシュ関数を書こう

早速プロファイラで調べるとこのMurmurHashを計算している部分がボトルネックになっているようなので(予想はしてたけど)ここを高速化させるためCで書かれたものを使うことにしました。

Rubyではこういったハッシュ関数は標準添付のDigestモジュールにまとめられていて、MD5やらSHA1なんかはすぐに使うことができます。

Rubyに敬意を払い、この標準添付の形式でDigest::MurmurHashとして使おうと、というかまあすでに誰かが作っているだろうと思ってgemを探してみてもなかったので書きました。

https://github.com/ksss/digest-murmurhash

書くときにハマった点は以下の通り。

CRuby上でのDigest APIが使いにくい
すでに存在するclassの内、継承されたclassはオープンクラスとして制限がある

CRuby上でのDigest APIが使いにくい

CRubyではDigestモジュール群は独自のインターフェースを持ちます。それは以下3つの関数を定義するだけでDigest::Baseの各種APIを持ったclassを作成できるというもの。

Init(ptr): 初期化
Update(ptr, string, length): digest化する元になる文字列の追加
Finish(ptr, result): digest値を出力

これはMD5やSHA1などdigest化する元になる文字列を一定bit毎に分割して計算するアルゴリズムの場合うまく実装できます。

しかし、MurmurHashのような元文字列の最終的な長さを用いてdigest値を決定するアルゴリズムの場合、Updateで無限長の文字列を入力してFinishまで文字(byte)列のまま持ち越さなければなりません。そのためにはUpdateでは以下の方法を取らなければなりません。

marllocでメモリ確保
Rubyオブジェクトに追記

最初にmarllocを使用する方法を考えたのですがこの場合インスタンスオブジェクトを作成する際にmalloc、GCで回収される際にfreeとしなければメモリーリークの元になることがわかりました。しかしその変更はこのAPIの範疇を超えています。

次にメモリ管理はCRubyにまかせてRubyオブジェクトにどんどん追記していく方法をとりました。テストも通ってうまくいくかと思ったのですが、極稀にテストでセグフォることがわかりました。InitでRubyオブジェクトを作成していたのですが、これがGCによって回収されていたようです。GCに回収されないようにalloc時にマークを付ければ……これもAPIの範疇を超えています。

どちらの方法もうまくいかずもっと僕に知恵があれば……と思ったのですが、結局CRubyのインターフェースは順守せずRubyのインターフェースは順守する方法を取りました。

CRuby上のインターフェースではInit,Update,Finishの関数をmetadataとして定義しなければならず、その定義しなければならない仕組みはDigest::Baseクラスのメソッド定義でmetadataが定義されているかチェックして登録されている関数を呼び出す方法を採っていたので、このmetadataを使用しているallocを含む全てのメソッドを上書いてmetadataを使わないように塗りつぶして通常のCRubyでclassを定義する方法と同じインターフェースで書きました。

これによりインスタンス作成(alloc)時にメモリを確保して(またメモリ管理を書くのが面倒だったのでRubyオブジェクトを使用)ちゃんとGC用にマークさせてGC発動時にマークされていればそのまま、マークがなければ回収させるように書くことが出来ました。

すでに存在するclassの内、継承されたclassはオープンクラスとして制限がある

考えてみれば当然ではあるのですが、

class A < Array; end
class A; end

は動作するのですが、

class A; end
class A < Array; end

はエラーを吐きます(Ruby上だとTypeError、CRuby上だとNameErrorだった……)。

なのでrakeでコンパイルとrspecが走るようにしていたのですが、rakeでのテストは通るのにbundle exec rakeだと通らないという事態に。bundle execの場合だと、Rakefileでxxx.gemspecの内容を読み込むようにしていた場合、xxx.gemspec内でロードしていたversion用のファイルが先に読ませて何も継承していないclassが先に定義され、rspec時に作ったclass(別のクラスを継承している)をロードすると上記例の後者の場合にあたってしまうためNameError(rb_define_class_id_under()の提供)を吐くことになります。

結局この問題は保留してxxx.gemspec内でのバージョン数字は直書きすることに。なにかいい方法は無いのだろうか……。