RustにおけるNRVO

以前こちらの記事で、Rustで構造体を実体化して返すケースでもコストを調べました。結果はC++でいうRVO(Return Value Optimization)と同じようなコピー省略の最適化が効いているというものでしたが、前回は右辺値を返すケースだけだったので、左辺値(変数)を返す場合にも最適化(C++でいうNRVO - Named Return Value Optimization)が効くのかも調べてみました。

前回と同様、逆アセンブル結果を見るのもいいのですが、面倒なのと、同じことをやっても面白みがないのでrustcが生成している中間コード(MIR)をみることで確認していこうと思います。

MIRとはMid-level Intermediate Representationの略でrustcにおけるLLVM IRを生成する一歩手前の中間表現になります。以下のページを見るとどのようなものかイメージしやすいのではないかと思います。

https://blog.rust-lang.org/2016/04/19/MIR.html

Rustにおいて、NRVOの最適化はこのMIRのレベルで行われているので(*1)、MIRを見ることで最適化が行われたかどうかを確認することができます。

なお、rustcのバージョンは 1.63.0を使っています。

MIRの確認の仕方

MIRを出力するには、 rustc --emit=mir src/main.rs のように-emit=mirオプションを指定します。これで、.mirファイルにMIRが出力されます。

面倒くさい場合は https://play.rust-lang.org/ でソースコードを入力して、左上のRUNボタンをMIRに切り替えて実行すれば同じことができます。

前回の記事で使ったソースコードを使ってMIRを見てみましょう。

オブジェクトを生成して返す関数

#[derive(Debug)]
struct User {
    username: String,
    age: u32,
}

// オブジェクトを生成して返す関数
fn create_user() -> User {
    User {
        username: String::from("test"),
        age: 32,
    }
}

fn main() {
    let user = create_user();
    println!("{:?}", user);
}

生成されたMIRを見てみます。create_user()関数のものだけ抜き出しています。

生成されたMIR

fn create_user() -> User {
    let mut _0: User;                    // return place in scope 0 at src/main.rs:7:21: 7:25
    let mut _1: std::string::String;     // in scope 0 at src/main.rs:9:19: 9:39

    bb0: {
        _1 = <String as From<&str>>::from(const "test") -> bb1; // scope 0 at src/main.rs:9:19: 9:39
                                         // mir::Constant
                                         // + span: src/main.rs:9:19: 9:31
                                         // + user_ty: UserType(0)
                                         // + literal: Const { ty: fn(&str) -> String {<String as From<&str>>::from}, val: Value(Scalar(<ZST>)) }
                                         // mir::Constant
                                         // + span: src/main.rs:9:32: 9:38
                                         // + literal: Const { ty: &str, val: Value(Slice(..)) }
    }

    bb1: {
        Deinit(_0);                      // scope 0 at src/main.rs:8:5: 11:6
        (_0.0: std::string::String) = move _1; // scope 0 at src/main.rs:8:5: 11:6
        (_0.1: u32) = const 32_u32;      // scope 0 at src/main.rs:8:5: 11:6
        return;                          // scope 0 at src/main.rs:12:2: 12:2
    }
}

MIRに関する説明は https://rustc-dev-guide.rust-lang.org/mir/index.html にありますので、ここでは、今回の解説に最低限必要な事項だけを説明します。

まず先頭で関数内で使われるローカル変数が定義されます。

    let mut _0: User;
    let mut _1: std::string::String;

ここでは、作成するUserオブジェクトを格納するための変数と、Userに設定するStringの一時変数が定義されています。

MIRの段階では変数名は存在せず、_0,_1のようなインデックスで識別されます。最終的にアセンブラレベルでは、これらの変数は関数のスタックフレーム上に置かれることになります。 _0だけはreturn placeと呼ばれる特別なもので、関数の返り値を返す場所を示しており、これは、呼び出し元関数のスタックフレーム上に配置されます(図1)。

つまり、NRVOが適用されているかどうかは _0 がどのように構築されているのかを見れば判断できることになります。

変数定義の次にbbX:と呼ばれるものが続きます。 bbとはBasic Blockの略で、関数内の処理を格納したものになります。条件分岐があると別のBasic Blockに分割され、関数のBasic Blockは複数のBasic Blockがグラフ構造をとったものになります。

例えば、以下のような処理があった場合、図2に示すような、Basic Blockのグラフが生成されます。実際には不要になったオブジェクトの解放処理が入ったりするので、元のソースコードよりずっと複雑なフローになる場合もあります。

fn create_user() -> User {
    何らかの処理1
    if xxx {
        何らかの処理2
    } else {
        何らかの処理3
    }
    何らかの処理4
}

このBasic BlockのグラフはControl Flow Graphと呼ばれ、コンパイラの最適化処理などに使われますが、今回の記事には関係ないので触れません。今回は return place(_0) を構築しているBasic Blockを探して、最適化されているかどうかを確認することになります。

MIRで実際に _0 の構築箇所を見てみましょう。該当Basic Blockはbb1になります。

bb1: {
        // _0に対して直接オブジェクトを構築している(コピーは発生していない)
        Deinit(_0);
        (_0.0: std::string::String) = move _1;
        (_0.1: u32) = const 32_u32;
        return;
    }

MIRの正確な見方は置いておくとして、return place(_0)に直接オブジェクトが構築されているのがわかると思います。

一方、最適化が効いていない場合は以下のようなMIRになります。

fn create_user() -> User {
    let mut _0: User;
    let _1: User;
    let mut _2: std::string::String;

    --- 略 ---

    bb1: {
        // 一旦_1にオブジェクトを構築
        Deinit(_1);
        (_1.0: std::string::String) = move _2;
        (_1.1: u32) = const 32_u32;
        // _1を_0(return place)にmove
        // オブジェクトの各フィールドのコピーが発生する
        _0 = move _1;
        return;
    }
}

一旦、_1にUserオブジェクトを構築したあと、_0にmoveしているのがわかります。move動作においてオブジェクト各フィールドがmove先にコピーされるので、フィールド数が多いオブジェクトにおいてはそれなりのコストが発生します。

NRVOが効くケース効かないケース

MIRの見方がわかったところで、左辺値(変数)を返すケースでNRVOが効くかどうかを見ていきましょう。

(1) 変数に格納してから返すケース

作成したオブジェクトを一旦変数に格納してから返すケースです。このような処理はわりと普通にやるでしょう。

fn create_user(code: &str) -> User {
    let mut u = User {
        username: String::from("test"),
        age: 32,
    };
    u.username.push_str(code);
    u
}

出力されたMIRは以下のようになります(関連するところだけ抜粋)。

fn create_user(_1: &str) -> User {
    let mut _0: User;
    let mut _2: std::string::String;
    let _3: ();
    let mut _4: &mut std::string::String;
    let mut _5: &str;

    --- 略 ---

    bb1: {
        // _0に直接構築している(NRVOが効いている)
        Deinit(_0);
        (_0.0: std::string::String) = move _2;
        (_0.1: u32) = const 32_u32;
        _4 = &mut (_0.0: std::string::String);
        _5 = _1;
        _3 = String::push_str(move _4, move _5) -> [return: bb2, unwind: bb3];
    }

    bb2: {
        return;
    }

bb1において_0が直接構築されているので、NRVOが効いていることがわかります。

(2) 別変数にmoveしてから返すケース

次は、変数を一旦別の変数にコピー(Rustの意味的にはmoveですが)してから返してみましょう。

fn create_user() -> User {
    let u = User {
        username: String::from("test"),
        age: 32,
    };
    let u2 = u;
    u2
}

出力されたMIR...

fn create_user() -> User {
    let _1: User;
    let mut _2: std::string::String;

略

    bb1: {
        Deinit(_1);
        (_1.0: std::string::String) = move _2;
        (_1.1: u32) = const 32_u32;
        _0 = move _1;
        return;
    }

_1を構築してから_0にmoveしています。moveの過程でUserの各フィールドが_1 → _0にコピーされることになります。NRVOは効いていません。

NRVOの最適化をしているcompiler/rustc_mir_transform/src/nrvo.rsを見ても以下のようなコメントがあります。

For now, this pass is very simple and only capable of eliminating a single copy.

まだ、比較的単純なケースしか対応していないようです。そもそも、上記例のように別の変数に引き回すようなことはあまりしないと思いますが、気をつけておいた方がよさそうです。

(3) 複数のオブジェクトを作成しどれかを返すケース

複数のオブジェクトを構築し、条件によってどれかを返すようなケースです。

fn create_user(flag: bool) -> User {
    let u = User {
        username: String::from("test"),
        age: 32,
    };
    let u2 = User {
        username: String::from("test2"),
        age: 32,
    };

    if flag {
        return u;
    } else {
        return u2;
    }
}

出力されたMIR...

fn create_user(_1: bool) -> User {
    let mut _0: User;
    let _2: User;
    let mut _3: std::string::String;
    let mut _5: std::string::String;
    let mut _6: bool;


    bb3: {
        _8 = const false;
        _0 = move _2;
        goto -> bb5;
    }

    bb4: {
        _7 = const false;
        _0 = move _4;
        goto -> bb5;
    }

C++になれた人ならMIRを見るまでもないと思いますが、bb3,bb4をみても _0 はmoveによって設定されているため、NRVOは効いていません。

これは、コンパイル時にどのオブジェクトを返すか決められないせいで最適化できません。C++においてもNRVOが効かない例として有名なものです。

(4) 複数オブジェクトを返す場合でもrvalueであれば問題ない

最後におまけで、NRVOではありませんが、(3)のケースの左辺値を右辺値にしてオブジェクトを直接返すケースを見てみましょう。

fn create_user(flag: bool) -> User {
    if flag {
        return User {
            username: String::from("test"),
            age: 32,
        };
    } else {
        return User {
            username: String::from("test2"),
            age: 32,
        };
    }
}

出力されたMIR...

    bb2: {
        Deinit(_0);
        (_0.0: std::string::String) = move _3;
        (_0.1: u32) = const 32_u32;
        goto -> bb5;
    }

略

    bb4: {
        Deinit(_0);
        (_0.0: std::string::String) = move _4;
        (_0.1: u32) = const 32_u32;
        goto -> bb5;
    }

    bb5: {
        return;
    }

bb2, bb4において_0が直接構築されているので、RVO(*2)が効いていることがわかります。

このあたりの挙動もC++と同じですね。

まとめ

MIR経由でNRVOの動作を確認しました。

nrvo.rsには「非常に単純最適化していない」とはありますが、十分問題ないレベルで最適化が効くようです。このあたり、いくつかpull requestも出ているようなので、より高度なものになっていくのかもしれません。

おまけ - MIRの最適化レベル

rustcはopt-levelによる最適化レベル以外にもMIRの最適化レベルも個別に指定できます。

# rustc -Z mir-opt-level=0 src/main.rs

のように-Zオプションで最適化レベルを指定することができます。mir-opt-levelのデフォルト値は1ですが、上記のように0を指定すると、nrvo.rsの最適化を外すことができます(*3)。

ただし、-Zオプションはnightly snapshot版でしか使えないようになっています。

(*1) NRVOの最適化はcompiler/rustc_mir_transform/src/nrvo.rsで行われています。

(*2) 返しているのが右辺値なのでNRVOではなくRVO。nrvo.rsの最適化処理とは別の話になります。

(*3) NRVOが無効になるだけでRVOは効きます。

[参考サイト]

rustcについては、https://rustc-dev-guide.rust-lang.org/ が非常に参考になります。

特に今回の記事に関係のあるページは以下になります。

投稿日:2022/08/30 21:09

タグ: プログラミング Rust

ブログ