当面はメモリを沢山積んだマシンでどうにかなってしまったのだけど、今後の事も考えてちょっとだけ深追いする事にした。
まず、既エントリーのキーであるかを参照するところがボトルネックであるようなので、とりいそぎハッシュ関数を疑ってみる。案の定 SHA1 を使っているので、そりゃ遅いだろう。ここは大体一様乱数になってればいいので、CRC32 にしてみる。ビット長を短くする分処理も簡単になるし、どうせ最後はエントリー数 m に合わせて %m してしまう。 簡単のため、最大エントリー数は十分に大きいという仮定をおくと以下のように BloomFilter をかける。
require 'bitset' require 'zlib' class BloomFilter def initialize(max_entries, num_hashes) @num_hashes = num_hashes @size = max_entries.to_i @bitmap = BitSet.new(@size) @mask = BitSet.new(@size) end def insert(key) mask = make_mask(key) @bitmap |= mask end def has?(key) mask = make_mask(key) return ((@bitmap & mask) == mask); end def make_mask(key) @mask.clear 1.upto(@num_hashes.to_i) do |i| hash = Zlib.crc32(key, i) # i = seed of CRC32 @mask.set(hash % @size, 1) end return @mask end end def main bf = BloomFilter.new(1000000, 4) num = 0 while line = ARGF.gets data = line.chomp.split(/\s+/) if !bf.has?(data[0]) num += 1 bf.insert(data[0]) end end print "#distinct elements = #{num}\n" end main
上記の場合、Bloomfilter そのものに使用するメモリ量は 1,000,000 bit (約122KB) で固定となる。ただしエントリー数はそれほど大きくない事を仮定している。
しかしこれでもどうも速度が遅すぎて困る。高々10,000エントリーを処理するのに22秒もかかってしまう。
% ruby simple-bf.rb test.dat 14.90s user 7.13s system 98% cpu 22.343 total #element = 9652
ruby -r profile の出力をみると以下のようになっている。
% cumulative self self total time seconds seconds calls ms/call ms/call name 23.16 8.45 8.45 20000 0.42 0.63 Integer#upto 16.88 14.61 6.16 10000 0.62 0.62 BitSet#& 12.55 19.19 4.58 10000 0.46 0.46 BitSet#| 8.74 22.38 3.19 10000 0.32 0.32 BitSet#<=> 6.58 27.36 2.40 20000 0.12 0.82 BloomFilter#make_mask 3.89 28.78 1.42 80000 0.02 0.02 Zlib.crc32 3.43 30.03 1.25 80000 0.02 0.02 BitSet#set 3.37 31.26 1.23 20001 0.06 0.06 BitSet#new 3.29 32.46 1.20 60148 0.02 0.02 Bignum#% 3.12 33.60 1.14 10000 0.11 1.92 BloomFilter#has? 2.19 34.40 0.80 10000 0.08 1.36 BloomFilter#insert 1.53 34.96 0.56 10000 0.06 0.38 Comparable.== 0.90 35.29 0.33 20000 0.02 0.02 Array#[] 0.66 35.53 0.24 10000 0.02 0.02 String#split 0.60 35.75 0.22 19852 0.01 0.01 Fixnum#% 0.60 35.97 0.22 20001 0.01 0.01 Integer#to_i 0.55 36.17 0.20 10000 0.02 0.02 String#chomp 0.44 36.33 0.16 10001 0.02 0.02 ARGF.gets 0.41 36.48 0.15 9652 0.02 0.02 Fixnum#+ 以下略
upto のところはハッシュを複数かけるところなのでどうしようもないのだけど、どうも BitSet がボトルネックになっているみたい。BitSet の中身はビットストリングをバイト単位でわけて、ビットの位置をしていするとバイトのインデックスとバイト内でのビットのインデックスをそれぞれ計算して、しかるべきビット演算するだけなのだけど、初期化のところや位置の指定方法によってビットマップをリサイズするという処理がどうも無駄だということがわかった。必要な演算は基本的に & と | だけなのでそれ以外の機能を省いてしまうのと、リサイズの処理が入らないようにデータ型を決めうちにする方が良さげ。これはいずれやるとして、それでも劇的に速度は変わらないような気もしている。基本的に新しいレコードを読み込むたびにハッシュを k 回かけてマスクを作り、フィルターとマッチをかけるという作業があるので、その処理が軽くならない限りどうにもならない。複数の位置に対して同時にビットを立てる/比較する技があると早くなるんだけどな。単純にビットの数を数える場合はこういうのがあるのだけど、なんかないだろうか？ハードウェアで実装する場合は並列で処理するロジックを組めばいいのだろうけど。
