Digest::StringBuffer v0.0.2リリース

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倍早くなっていますが長い文字列の場合遅くなってますね。

お後がよろしいようで。