mrubyのkhashとHashの高速化
mrubyカテゴリあったほうがいいかなーとか思うが、そんなに書くこともないからいらんかも。増えるようなら考える。
khashをどうにかして高速化できないかなーと細かい修正を入れてみて、ついでにHashが遅いらしいので書き込みを高速化してみたのでそれをネタに。
https://github.com/mirichi/mruby/tree/opt_hash
khash
mrubyのkhash.cは全体がマクロになってて、ちょっとコードを増やすとハッシュテーブルの種類ぶんだけ複製されて増えてしまうのであんまりよろしくないのだが、実行コードが増えるぶんにはROMにでも置いておけばーって感じでたいした問題は無いかもしれないし、あるかもしれない。とりあえず、動的なメモリ確保が増えてなければ問題は比較的軽いほうだろう。
修正したのはハッシュテーブル生成時の処理と、put、resizeの処理。ちょっとずつ無駄を削っていった感じで、これにより以下のコードを動かした結果は16.125s→14.75sになった。
before = Time.now 2000.times do |i| hash = {} 2000.times do |j| hash[(i*100+j).to_s] = i*100+j end 2000.times do |j| raise if hash[(i*100+j).to_s] != i*100+j end end p Time.now - before
ほんとにちょっとずつの積み上げだから、どれかひとつの修正を取り出してみても誤差のせいでどんだけ速くなったのかよくわからんくて、それぞれ別々に効果があるのかないのか調べるのは大変である。まあ、一山いくらって感じで。ひょっとしたら中には遅くなってる修正もあったりするかもしれんが。
mrb_hash_set
mrubyのHashは遅いとかいう話があって、特に文字列をキーにした書き込みがとても遅い。原因はkh_getしてからkh_putするというハッシュ値生成が2回必要なアルゴリズムにあって、文字列のハッシュ値生成がまた大変遅いのでダブルで遅いという状態なのである。
なぜgetしてからputするかというと、追加時にHashの格納順保証の処理をするために、同じキーが格納済かどうかを事前にチェックする必要があって、チェック手段がkh_getしかないから、という話だ。
従って、この事前チェックの方法をどうにかしてやればハッシュの書き込みが速くなる。
今回は書き込み位置の算出と実際の書き込みをkh_search/kh_writeという関数に分割して、kh_searchで返ってきた場所をmrb_hash_set内でkh_existして追加か上書きかを判定するようにしてみた。これにより追加時のハッシュ値計算が1回に減るので速くなるんじゃないか、と。この修正もgithubのopt_hashブランチのコードに入っている。
修正後、上記ベンチは14.75s→10.75sになった。こいつは驚きの効果である。しかしこれだと実行時間のほとんどは文字列のハッシュ計算してるということになるのだが。ほんまか。
真の問題はそっちかもしれん。