Digest::StringBufferというgemをリリースしました。
経緯
Digest::MurmurHashを書いていて、これがCRuybでbuilt-inのDigest::Baseを継承するように書いていたのですが、殆どのメソッドを上書きしているため「継承する意味ねぇ……」と思ったのでこれをやめました。
ここでDigestモジュールの関係を確認すると
Digest::Base < Digest::Instance < Digest::Class < Object < Kernel < BasicObject
となっています(Digest::ClassはDigest::Instanceをincludeしている)。
Digest::Baseの機能は以前に見たとおり簡易実装APIの提供。Digest::ClassはDigest::Instanceのclassラッパー。Digest::InstanceはこのモジュールをインクルードするとDigest系のメソッドがツカエルードってな感じとなっています。
要するに全部APIの提供をしているだけである種Digestフレームワークになっているわけです。
見えてきたもの
ここで2つの視点があることに気づきます。
言語提供側と言語ユーザー。
言語提供側はある程度の信念の則って機能やインターフェースを提供する立場。Rubyの場合なんどもスピードよりコーディングの楽しさ・楽さを提供すると公言しています。よって機能の提供が第一であってスピードを求めるのは二の次という考えがじわじわわかってきます。
しかし言語ユーザー側はどうでしょう?ユーザー側もある程度の信念に則って実装しているとは考えられません。 もっと便利な表現力を求める人もいればシンプルでもいいから早さがほしい。でもCでは書きたくなくてRubyで書きたい等のユーザーの多様性が存在すると思います。
こんなユーザー側の立場のニーズを満たすものがライブラリ、つまりGemなんだと思います。欲しけりゃ自分で書けるというわけです。
というわけで書いてみた
前提はここまでで話を戻すと、built-inのDigest::XXXは継承を前提として柔軟な機能を提供するものであるため、Rubyのメソッド呼び出しが多くなっています。MurmurHashのような「ただこれだけを素早くやってくれればいいんだ」みたいなuse caseには向いてないものと思われます(だからdigest-xxxなライブラリは少ないのかな……)。
またメッセージダイジェストとして有名なMD5やSHA1などは文字列を固定長毎に切り出して計算するため文字列を追加するたびにハッシュ値を計算しますが、MurmurHashなどの単純なハッシュ関数の場合は最終的な全文字列だけが必要です。そんな単純なハッシュ関数のためだけに特化すれば必要ない処理を省いて高速化が期待できます。
そんなわけで柔軟性を大きく削減し、継承をあまり考慮しないスピードを求めるためのライブラリーDigest::StringBufferを書きました。これは元Digest::MurmurHash内にあったコードを別のGemとして切り出したものです。Digest下にあるのは意味的な関係性でしかなく、継承して動作を変更できるメソッドも大きく減らしてスピードを追求しています。機能もただ文字列をメモリにストックするだけで、digest
内でfinish
メソッドを呼ぶのですが、Digest::StringBuffer自体ではロジックが無いので、継承させてfinish
メソッドを書く必要があります。
なんでv0.0.2?
v0.0.1の時にextconf.rbがバグってたからです。
gem install
してもrequireできない問題の解決に4時間かかりました。コード書いてる時間より長えよ。
使ってみた
こんな感じで使えます。
文字列を一文字ずつ31倍して合計値をハッシュ値としています。
finish
関数だけを書けばとりあえず動きます。
buffer
は今溜めている文字列だけを取り出す内部APIです。
finish
の返り値はString型にすべきです。
module Digest class Prime31 < StringBuffer def initialize @prime = 31 end def finish result = 0 buffer.unpack("C*").each do |c| result += (c * @prime) end [result & 0xffffffff].pack("N") end end end p Digest::Prime31.hexdigest("abc" * 1000) #=> "008b1190"
肝心のスピードを見てみます。
Digest::ClassとDigest::StringBufferそれぞれを継承させた同じロジック(文字列長 % 256)でメッセージダイジェストを行う場合を計測しました。
「long string」は3MBの文字列を、「meny times」は100万回3Bの文字列をそれぞれダイジェスト値を計算させています。
$ bundle exec ruby spec/bench.rb user system total real Digest::Class long string 0.010000 0.000000 0.010000 ( 0.004192) Digest::Buffer long string 0.010000 0.000000 0.010000 ( 0.011864) Digest::Class meny times 3.900000 0.020000 3.920000 ( 3.919907) Digest::Buffer meny times 1.780000 0.020000 1.800000 ( 1.808954)
……短い文字の場合なら約2倍早くなっていますが長い文字列の場合遅くなってますね。
お後がよろしいようで。
リンク
https://github.com/ksss/digest-stringbuffer
https://github.com/ksss/digest-stringbuffer/blob/master/spec/bench.rb
https://rubygems.org/gems/digest-stringbuffer
http://docs.ruby-lang.org/ja/2.0.0/class/Digest=3a=3aBase.html