Rust の Index bounds check の性能影響を調べてみた

Rust の配列 (Vec<T> や [T] など) では、インデックスアクセス時に境界チェック (index bounds check) が常に行われます。 常に行われる、というのはビルドの種類 (リリースビルド・デバッグビルド) に依存しないという意味です。 とにかく安全性を重視する Rust らしい仕様であると言えます。

他のプログラミング言語に目を向けて見ると、常にチェックが行われるシステムプログラミング言語というのも珍しい気がします。 すべてがプログラム作成者の責任になる C では当然何のチェックも行われませんし、 安全なシステムプログラミング言語という意味で Rust と立ち位置が近い D では、デバッグビルドの場合のみ境界チェックが行われます (リリースビルドでは行われない)。

配列の境界チェックは実行時の処理になるため、普通に考えると Rust の方がチェック処理の分だけ実行性能が落ちてしまうことになります。境界チェックが行われない配列アクセス手段が用意されている とはいえ、配列アクセスが遅いのであれば Rust で書かれる様々なプログラムの実行性能も遅くなってしまわないか心配になってしまいます。

というわけで、Rust の配列アクセス性能を測定してみました。

tl;dr

Index bounds check のコストが支配的になるケースは少なそう。

注意

以下で出てくるベンチマーク結果は、仮想マシン上の Linux で測定したものなので実マシン上とは異なる結果になっている可能性があります。 また、筆者はアセンブリが読めず、CPUの気持ちも分からないため、コンパイル結果に関する見解は多くの誤りが含まれている可能性があります。 もし変な記述があれば、コメント等頂けると大変助かります。

テストに利用したソースコード一式は、以下Gistからどうぞ。

https://gist.github.com/gifnksm/9a792feff8567067b2d272c86258c2d4

利用したコンパイラは、nightly (2016/5/30) です。

$ rustc --version
rustc 1.11.0-nightly (a967611d8 2016-05-30)

テスト1: 配列先頭からシーケンシャルアクセスする

まずは、シンプルなケースから。いくつかの関数について性能を比較します。

1. インデックスアクセスその1 (D index)

#[inline(never)]
pub fn direct_index(arr: &[u64]) -> u64 {
    let mut sum = 0;
    for i in 0..arr.len() {
        sum += arr[i];
    }
    sum
}

libcoreのソース によると、arr[i] へのアクセスで arr.len() との比較により index bounds check が行われます (assert! はリリースモードでも消えずに残ります)

arr.len() との比較は Range::next() でも行われている ため、コンパイラの最適化により arr[i] の index bounds check は除去されるかもしれません

2. インデックスアクセスその2 (D index_len)

#[inline(never)]
pub fn direct_index_len(arr: &[u64], len: usize) -> u64 {
    let mut sum = 0;
    for i in 0..len {
        sum += arr[i];
    }
    sum
}

i の範囲を引数で渡すように変更したものです。arr[i] の index bounds check が除去されずに残ることが期待値です。

3. イテレータでのアクセス (D iter)

#[inline(never)]
pub fn direct_iter(arr: &[u64]) -> u64 {
    let mut sum = 0;
    for &n in arr {
        sum += n;
    }
    sum
}

std::slice::Iter::next の実装によると、イテレータを使った場合はインデックスアクセスの場合と異なり、Cと同等の性能になることが期待されます。

4. C プログラム (D c)

uint64_t direct_c(const uint64_t *arr, size_t len)
{
    uint64_t sum =  0;
    for (size_t i = 0; i < len; i++) {
        sum += arr[i];
    }
    return sum;
}

テスト1の測定結果

$ cargo bench
test tests::D_c         ... bench:      26,372 ns/iter (+/- 362)
test tests::D_index     ... bench:      26,389 ns/iter (+/- 373)
test tests::D_index_len ... bench:      59,863 ns/iter (+/- 602)
test tests::D_iter      ... bench:      26,386 ns/iter (+/- 465)

1, 3, 4 (index, iter, c) はほぼ性能は同じです。objdump -d の結果を見ると 1, 4 (index, c) はほぼ同じアセンブリが出力されていましたが、 3 (iter) は少し長めのアセンブリでした。

1, 2 の結果を比較すると、1の場合は想定通り、 arr[i] の index bounds check は除去されているように思えます。

テスト1のまとめ

配列をシーケンシャルに先頭からアクセスしていく場合、 index bounds check のコストは無視して良いと思います。

先頭からアクセスする場合、多くのケースではイテレータを使うことが多いでしょう。また、スライスを渡す場合でも、スライスと len をペアで渡すよりも、&[..len] のように slice を slicing して渡すような書き方をする方が、引き渡す引数の数を減らすことができ、インタフェースがシンプルになるなどのメリットがあるためです。 slicing した場合、1と同じような性能になることが予想されます。

テスト2: 外部から指定された順序でインデックスアクセスする

配列先頭からシーケンシャルアクセスするのではなく、ランダムな順番など関数外から渡される順番に基づいて間接的 (?) にアクセスするケースについて測定します。

1. index bounds check ありの間接アクセス (I iter, R iter)

#[inline(never)]
fn indirect_iter(arr: &[u64], idx: &[usize]) -> u64 {
    let mut sum = 0;
    for &i in idx {
        sum += arr[i];
    }
    sum
}

2. index bounds check なしの間接アクセス (I iter_nc, R iter_nc)

#[inline(never)]
unsafe fn indirect_iter_uc(arr: &[u64], idx: &[usize]) -> u64 {
    let mut sum = 0;
    for &i in idx {
        sum += *arr.get_unchecked(i);
    }
    sum
}

1 の index bounds check を行わない版です。

3. C プログラム (I c, R c)

uint64_t indirect_c(const uint64_t *arr, const size_t *idx, size_t idx_len)
{
    uint64_t sum =  0;
    for (size_t i = 0; i < idx_len; i++) {
        sum += arr[idx[i]];
    }
    return sum;
}

テスト1の測定結果

$ cargo bench
test tests::I_c         ... bench:      60,888 ns/iter (+/- 1,113)
test tests::I_iter      ... bench:      69,746 ns/iter (+/- 1,124)
test tests::I_iter_uc   ... bench:      69,355 ns/iter (+/- 633)
test tests::R_c         ... bench:     162,968 ns/iter (+/- 14,711)
test tests::R_iter      ... bench:     169,162 ns/iter (+/- 1,470)
test tests::R_iter_uc   ... bench:     163,944 ns/iter (+/- 1,850)

I_XXX はシーケンシャルにアクセスする場合、R_XXX はランダムアクセスする場合です。 どちらのケースでも c, iter_uc, iter の順で高速です。 _iter と _iter_uc で実行速度に差はあるのですが、Cと差が生じているのは別の理由によるのかもしれません。

テスト2のまとめ

この例のように配列のインデックスを間接アクセスするケースは、配列の要素をランダムアクセスすることが多いと思いますが、その場合、 index bounds check ではない別の原因で大きく性能が落ちてしまう (キャッシュ関連？) ようです。 ですので、index bounds check だけをことさら取り上げる必要もないのかなぁ、と思います。

まとめ

考察が雑。