Rustのゼロコスト抽象化

2016-03-01

Rust

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

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

nullableに対してはmapとかの高階関数を一切使えないのが痛い。 ?. でカバーできるケースは一部だけだ。zero-overhead null-safetyと唄っとるが、代わりにnullチェックお化けになるわけで、どこがzero-overheadだ #kotlin_dis
— 水島宏太(Klassic作成中) (@kmizu) 2016年2月29日

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

全く無関係だけどRustはOptionみたいな0-1の型をnull or valueに最適化するそうな。これこそがゼロコスト抽象かな https://t.co/5Y7cBEyrMe
— κeen (@blackenedgold) 2016年2月29日

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

repr(Rust)

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

@blackenedgold Rust詳しくないですけど、Optionにmapとかした場合インライン展開されるんですかね？だとしたらとても理想的。
— 水島宏太(Klassic作成中) (@kmizu) 2016年2月29日

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

まず、上記の話をまとめると、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
};

となる筈です。

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