rust
RustDay 5

ベクタのすべての要素に先頭から順にアクセスする

これは,「Rust Advent Calendar 2018」5日目の記事です.

はじめに

Rust初心者です.
ベクタのすべての要素に先頭から順にアクセスしたいのですが,調べたらいろいろ方法がありました.なるべく速く動いてくれるものがいいのですが,どれがいいのかよくわからなかったので,計測してみることにしました.

実験方法

以下のコードで計測.

use std::time::Instant;
fn main() {
    let mut sum: usize = 0;
    let v: Vec<usize> = vec![1; 100_000_000];
    let start = Instant::now();

    for i in 0..v.len() {sum += v[i];} // ここをいろいろ変えて計測

    let end = start.elapsed();
    println!("{}.{:09} sec elapsed", end.as_secs(), end.subsec_nanos());
    println!("{}", sum);
}

問題の部分については,以下の9通りの方法を試しました.
1. for i in 0..v.len() {sum += v[i];}:index番号をインクリメントしていく,伝統的なfor文.
2. for i in v{sum += i;}:iでvの各要素を直接取り出せる.
3. for i in &v {sum += i;}:vを参照で持つ.
4. for i in &v {sum += *i;}:自動の参照外しに頼らず明示的に外す.少し速くなるのではないかと予想.
5. for i in v.into_iter() {sum += i;}:vの値のコレクションとしてイテレータを作る.
6. for i in v.iter() {sum += i;}:vの参照のコレクションとしてイテレータを作る.
7. for i in v.iter() {sum += *i;}:明示的に参照外し.
8. loop:loopです.
9. while:whileです.8と9の部分コードは以下.

    // loop
    let mut i = 0;
    loop {
        if i >= v.len() {break;}
        sum += v[i]:
        i += 1;
    }

    // while
    let mut i = 0;
    while i < v.len() {
        sum += v[i];
        i += 1;
    }

なお,ベクタにおける2. 3. 4.をそれぞれイテレータに対応させたものが5. 6. 7.です.

環境

Intel® CoreTM i5-6267U CPU at 2.90GHz, 8GB RAM, Arch Linux (Kernel 4.19.4)
Rust ver 1.30.1

実行

1〜9の各方法について,次の2通りでコンパイル:

  • rustc
  • rustc -C opt-level=3

それぞれについて10回ずつ測定し平均を算出.

実験結果

方法 rustc rustc (opt=3)
1 4.938866634 0.038664556
2 1.247660342 0.089174220
3 1.964327827 0.040404473
4 1.733304570 0.039753678
5 1.265719581 0.087085704
6 1.961762533 0.040603875
7 1.700209579 0.039441419
8 2.141913327 0.040518572
9 2.128384941 0.039724081

単位はsec.各列について上位2つを青文字,下位2つを赤文字,最良・最悪を太字で表示しています.

追記:以降の解釈や考察には誤りがあるようです.コメント欄に詳しく指摘をいただいたので(ありがとうございます!)併せてご覧下さい.

まず,最適化オプションの有無で最良/最悪ケースが互いに逆転したので驚きました.特に1.のindex番号で回すfor文の変貌ぶりはすごいですね.C言語では今回のように繰り返しの中の処理が非常に簡単なものの場合,最適化オプションをつけると賢すぎるコンパイラがループやジャンプを使わない別の構造に変換し,実質的に繰り返し処理をしないコードを生成し爆速になるという話を聞いたことがあります(だいぶうろ覚えなので,違うかもしれません)が,Rustにもそのような機能があるのでしょうか.
2.や5.のような,コレクション実体のコピーを作って回すようなfor文は,最適化オプション付きのほうでは予想通り遅くなりました.オプションなしではなぜ最速を独占しているのかわかりませんが…….参照系が遅すぎて相対的に速いだけかもしれません.
参照といえば,参照外しについては予想通り,明示的に行ったほうが若干速くなりました(4.は3.の,7.は6.の参照外しをそれぞれ明示的に行ったもの).
個人的に一番知りたかったのが,4.と7.の差です(そもそもこの2つでどちらを使えばいいのかわからなくてこんな計測をはじめました).イテレータである7.のほうが若干速いですが,参照外しをサボるとベクタである3.のほうが速くなっています.for文で使うときはどちらでも大して変わらないという結論で良さそうです.
おまけとして,最適化オプションをつけることで15~100倍以上速くなることもわかりました(計測しているのはあくまで繰り返し処理の部分だけですが).

おわりに

ベクタのすべての要素に先頭から順にアクセスする9つの方法について,実行速度計測を行いました.たいていのRustプログラムは最終的に最適化オプションつきでコンパイルされると思うので,結論としては,

  • for i in vfor i in v.into_iter() のようなコレクションの実体をコピーするようなものはできるだけ使わないほうがよい.
  • 参照外しは明示的に行ったほうがよい.
  • for i in &vfor i in v.iter() の速度は同じくらい.
  • whileのほうがloopよりちょっとだけ速い.
  • レンジで回すfor文は速い.

というところでしょうか(注:この結論には誤りがあります.詳しくはコメント欄を参照).
個人的には,4.や7.のようにベクタの要素自体で回るfor文は洗練されていてかっこいいと思うのですが,1.の泥くさいindex番号for文に速度負けしてしまったので少し残念でした.

参考

https://doc.rust-jp.rs/the-rust-programming-language-ja/1.6/book/loops.html
http://dawn.hateblo.jp/entry/2017/07/24/165933
https://qnighy.hatenablog.com/entry/2017/05/02/070000