RustのHashMapをRubyから使えるようにしてみたが……

RustのHashMapをRubyから使えるようにしてみた。
https://github.com/irxground/rust_hashmap_gem
RustのHashMapはかなり速度に力を入れているので、置き換えるだけで速くなったら面白いなーと思ってやってみた。

→ もう少し速くしました

結果

そんなわけで、適当なベンチマークを拾ってきて試してみた。insert以外全部負けてますね

$ ruby benchmark.rb --rust --seed 1
Hash: Rust
Seed: 1
       user     system      total        real
values  1.885191   0.164441   2.049632 (  2.052237)
keys    1.461595   0.054283   1.515878 (  1.516320)
find   11.256652   0.002255  11.258907 ( 11.261749)
insert 15.286804   0.013948  15.300752 ( 15.305879)
delete  7.310167   0.001280   7.311447 (  7.312999)

$ ruby benchmark.rb --seed 1
Hash: Original
Seed: 1
       user     system      total        real
values  1.100674   0.150917   1.251591 (  1.258886)
keys    0.526004   0.042145   0.568149 (  0.570534)
find    2.607541   0.002803   2.610344 (  2.616013)
insert 17.317054   0.012727  17.329781 ( 17.335842)
delete  3.717545   0.000869   3.718414 (  3.719866)

実装の話

RustのHashMapに格納するには Eq traitと Hash traitを実装する必要がある。
これはRubyも同じで、Hashのキーとして適切に扱うには Object#hash と Object#eql? を適切に実装する必要がある。
となると、Rubyと挙動を合わせるにはそのtraitをそのメソッドを使って実装する必要がある。
今回は Hashable という構造体で VALUE をラップして作ることにした。

感想

keys, values が遅いのはどうやらRubyのHashはそもそも内部的に配列で持っているらしい。であればどう頑張っても同じ速度にすることは難しそう。

extern "C" fn keys(self_: Value) -> Value {
    let map: &Map = unsafe { &*check_typeddata(self_, &RUBY_TYPE) };
    let ary = ary_new_capa(map.len());
    if map.len() > 0 {
        ary_store(ary, (map.len() - 1) as isize, NIL);
        let ptr = ary_ptr_use_start(ary);
        let slice = unsafe { std::slice::from_raw_parts_mut(ptr, map.len()) };
        for (item, (key, _)) in slice.iter_mut().zip(map.iter()) {
            *item = key.0;
        }
    }
    ary
}

keysの実装はこのようになっていて先に必要なサイズを持ったRubyの配列を作成し、先頭のポインタを受け取って値を順に格納しているのでこれ以上は速くならなさそう。

find, delete が遅いのは、おそらくオーバーヘッドが大きすぎるから。

extern "C" fn get(self_: Value, key: Value) -> Value {
    let map: &Map = unsafe { &*check_typeddata(self_, &RUBY_TYPE) };
    match map.get(&Hashable(key)) {
        Some(val) => *val,
        None => NIL,
    }
}

getの部分はこうなっていて、だれが書いてもこうなるしこれ以上速くはできなさそう。
問題はHashableの方で以下のように実装している。

use crate::ruby;
use std::hash::{Hash, Hasher};

#[derive(Copy, Clone)]
#[repr(transparent)]
pub struct Hashable(pub ruby::Value);

impl PartialEq for Hashable {
    fn eq(&self, other: &Self) -> bool {
        let val = ruby::fun_call(self.0, "eql?", &[other.0]);
        val != ruby::FALSE
    }
}
impl Eq for Hashable {}

impl Hash for Hashable {
    fn hash<H: Hasher>(&self, state: &mut H) {
        let val = ruby::fun_call(self.0, "hash", &[]);
        val.to_raw().hash(state);
    }
}

ハッシュ値を取得するのに、Rubyのメソッドが動的に呼び出され、Rustのhash関数も実行されている。
さらに Eqの時もRubyのメソッドが動的に呼び出されている。
Rubyからメソッド呼び出しする場合は普通はメソッドをキャッシュしておくので次の呼び出しは速くなるが、CやRustから呼ばれる場合は毎回メソッドテーブルから探しに行く必要があって、とても遅い。

Rustの場合はHasherに何を選ぶかでHashMapのパフォーマンスが変わるくらいhashアルゴリズムは重要なので、これだけのことをしていたらこれだけ遅いのもおかしくない。逆に insert はこのオーバーヘッドを払ってでも速いので、相当速い。

あとは、RustからRubyの関数を呼ぶ場合、共有ライブラリの関数を呼んでいるので関数の境界を越えた最適化（インライン化を含む）ができない。