Cuckoo HashingをRubyで作る(その2)

Rubyの標準ライブラリのうちRubyで書いてあるもののトークンの数を数えるプログラムでいろいろCuckoo Hashingの挙動を調べてみました。

組み込みのHashを使うものと、Cuckoo Hashingのもののベンチマークを取ってみました。
トークンの切り出しにかなり時間が掛かるので、トークンの切り出しだけを行う処理の時間も測りました。

                user     system      total        real
ScanOnly  57.046000   1.546000  58.592000 ( 59.649000)
Hash      65.328000   1.750000  67.078000 ( 67.651000)
Cukoo     92.937000   1.719000  94.656000 ( 95.439000)

それぞれScanOnlyの分を引くと次のようになります。

               user           real
Hash       8.282000    (  8.002000)
Cukoo     35.891000    ( 35.790000)

userの方が、realより大きいのはおかしいですが、誤差の範囲だと思います。Rubyで書いたものがCで書いたものの4倍強で収まるということで、この問題に対してはCuckoo Hashingは有効じゃないかと思います。
もっとも、切り出したトークンは4,269,036個で60,946種類です。挿入処理が入る確率が1.417% とかなりCukoo Hashingに有利な条件です。

トークンを数える問題について、ハッシュバケットの使用率をいろいろハッシュ関数を替えて調べてみたのですが、どの関数もTable1が60% 前後、Table2が40%前後でした。Table2が使用率の足を引っ張っているようなので、Table1とTable2でサイズを変えてみるといいような気がします。

ベンチマークのリストです

require 'find'
require 'ripper'
require 'benchmark'
require 'cuckoo'


def token_scan
  Find.find('c:/cygwin/usr/local/lib/ruby/') do |f|
    if File.file?(f) and /\.rb$/ =~ f then
      Ripper.tokenize(File.read(f)).each do |token|
      end
    end
  end
end

def token_count(table)
  tot = 0
  uni = 0
  Find.find('c:/cygwin/usr/local/lib/ruby/') do |f|
    if File.file?(f) and /\.rb$/ =~ f then
      Ripper.tokenize(File.read(f)).each do |token|
        if table[token] == nil
          table[token] = 0
        end
        table[token] += 1
      end
    end
  end
end

Benchmark.bm(9) do |x|
  x.report("ScanOnly "){ token_scan}
  x.report("Hash "){ token_count(Hash.new)}
  x.report("Cukoo"){ token_count(CuckooHash.new)}
end