κeenのHappy Hacκing Blog | Lispエイリアンの狂想曲

Rustのゼロコスト抽象化

κeenです。今日Twitter上でのやりとりから少し面白いことが分かったのでそれについて。

最近1.0が出たKotlinについて、水島さんがツイートしてました。

それについて私が無関係なツイートを。

これはRustのnomiconに書かれています。

repr(Rust)

そうすると水島さんからお返事が。

確かにそうなると面白そう。ということで少し調べてみました。

まず、上記の話をまとめると、RustのOptionに対するmap

pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> {
    match self {
        Some(x) => Some(f(x)),
        None => None,
    }
}

xがポインタ型だった時に以下と同値です。

pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> {
    if (self != nullPointer ) {
        f(x)
    }
}

さらに、mapはインライン宣言されているので以下のコード

let opt = Some(&v);
opt.map(|x| x + 1);

は以下と同値です。

let opt = &v;
if (opt != nullPointer) {
  (|x| x + 1)(opt)
};

さて、ここで無名関数がどうコンパイルされるかという問題が出てきますが、クロージャのドキュメントによるとこういう雰囲気のコードになるらしいです。

let opt = &v;
struct AnonymousType;

impl FnOnce<(&i32)> for AnonymousType {
    type Output = i32;
    fn call_once(self, args: (&i32)) -> Self::Output {
        args + 1
    }
}

if (opt != nullPointer) {
    let fn_once: FnOnce = AnonymousType;
    fn_once.call_once(opt)
};

思ったよりも複雑…。さて、問題はlet fn_once: FnOnce = AnonymousType;としているので一旦元の無名関数の情報が抜けてしまいそうな気がします。 となるとコンパイル時に具体的なメソッドを決定出来ないのでfn_once.call_once(opt);は以下のような雰囲気のコードになってしまいます。

let call_once_fn = fn_once.get_call_once_fn();
call_once_fn(opt);

毎回呼び出すべき関数の取得が入るのは面倒ですね。

しかしなががらクロージャのドキュメントをよく読むと無名関数は静的ディスパッチされると書いてあります。つまり、

let call_once_fn = fn_once.get_call_once_fn();
call_once_fn(opt);

と2段ではなく

the_call_once_fn_of_AnonymousType(opt);

とコンパイルされ、

よって

let opt = Some(&v);
opt.map(|x| x + 1);

fn the_call_once_fn_of_AnonymousType(x: &i32) -> i32 {
    x + 1
}


let opt = &v;
if (opt != nullPointer) {
  the_call_once_fn_of_AnonymousType(opt)
};

と同値ということです。

ここからは私の推測ですが、the_call_once_fn_of_AnonymousTypeは本体が小さい上に1回しか呼ばれないのでインライン化されるのではないかと思います。 よってこの推測が正しければ

let opt = Some(&v);
opt.map(|x| x + 1);

let opt = &v;
if (opt != nullPointer) {
  opt + 1
};

となる筈です。

ゼロコスト抽象化すごい!

Written by κeen