パフォーマンス比較: ループVSイテレータ

ループを使うべきかイテレータを使うべきか決定するために、search関数のうち、どちらのバージョンが速いか知る必要があります: 明示的なforループがあるバージョンと、イテレータのバージョンです。

サー・アーサー・コナン・ドイル(Sir Arthur Conan Doyle)の、 シャーロックホームズの冒険(The Adventures of Sherlock Homes)全体をStringに読み込み、 そのコンテンツでtheという単語を検索することでベンチマークを行いました。 こちらが、forを使用したsearch関数のバージョンと、イテレータを使用したバージョンに関するベンチマーク結果です。

test bench_search_for  ... bench:  19,620,300 ns/iter (+/- 915,700)
test bench_search_iter ... bench:  19,234,900 ns/iter (+/- 657,200)

イテレータバージョンの方が(いささ)か高速ですね!ここでは、ベンチマークのコードは説明しません。 なぜなら、要点は、2つのバージョンが等価であることを証明することではなく、 これら2つの実装がパフォーマンス的にどう比較されるかを大まかに把握することだからです。

より理解しやすいベンチマークには、いろんなサイズの様々なテキストをcontentsとして、異なる単語、異なる長さの単語をqueryとして、 他のあらゆる種類のバリエーションを確認するべきです。重要なのは: イテレータは、 高度な抽象化にも関わらず、低レベルのコードを自身で書いているかのように、ほぼ同じコードにコンパイルされることです。 イテレータは、Rustのゼロ代償抽象化の一つであり、これは、抽象化を使うことが追加の実行時オーバーヘッドを生まないことを意味しています。 このことは、C++の元の設計者であり実装者のビャーネ・ストロヴストルップ(Bjarne Stroustrup)が、 ゼロオーバーヘッドを「C++の基礎(2012)」で定義したのと類似しています。

一般的に、C++の実装は、ゼロオーバーヘッド原則を遵守します: 使用しないものには、支払わなくてよい。 さらに: 実際に使っているものに対して、コードをそれ以上うまく渡すことはできない。

別の例として、以下のコードは、オーディオデコーダから取ってきました。デコードアルゴリズムは、 線形予測数学演算を使用して、以前のサンプルの線形関数に基づいて未来の値を予測します。このコードは、 イテレータ連結をしてスコープにある3つの変数に計算を行っています: bufferというデータのスライス、 12のcoefficients(係数)の配列、qlp_shiftでデータをシフトする量です。この例の中で変数を宣言しましたが、 値は与えていません; このコードは、文脈の外では大して意味を持ちませんが、 それでもRustが高レベルな考えを低レベルなコードに翻訳する簡潔で現実的な例になっています:

let buffer: &mut [i32];
let coefficients: [i64; 12];
let qlp_shift: i16;

for i in 12..buffer.len() {
    let prediction = coefficients.iter()
                                 .zip(&buffer[i - 12..i])
                                 .map(|(&c, &s)| c * s as i64)
                                 .sum::<i64>() >> qlp_shift;
    let delta = buffer[i];
    buffer[i] = prediction as i32 + delta;
}

predictionの値を算出するために、このコードは、coefficientsの12の値を繰り返し、zipメソッドを使用して、 係数値を前のbufferの12の値と組にします。それから各組について、その値をかけ合わせ、結果を全て合計し、 合計のビットをqlp_shiftビット分だけ右にシフトさせます。

オーディオデコーダのようなアプリケーションの計算は、しばしばパフォーマンスに最も重きを置きます。 ここでは、イテレータを作成し、2つのアダプタを使用し、それから値を消費しています。 このRustコードは、どんな機械語コードにコンパイルされるのでしょうか?えー、執筆時点では、 手作業で書いたものと同じ機械語にコンパイルされます。coefficientsの値の繰り返しに対応するループは全く存在しません: コンパイラは、12回繰り返しがあることを把握しているので、ループを「展開」します。 ループの展開は、ループ制御コードのオーバーヘッドを除去し、代わりにループの繰り返しごとに同じコードを生成する最適化です。

係数は全てレジスタに保存されます。つまり、値に非常に高速にアクセスします。実行時に配列の境界チェックをすることもありません。 コンパイラが適用可能なこれらの最適化全てにより、結果のコードは究極的に効率化されます。このことがわかったので、 もうイテレータとクロージャを恐れなしに使用することができますね!それらのおかげでコードは、高レベルだけれども、 そうすることに対して実行時のパフォーマンスを犠牲にしないようになります。

まとめ

クロージャとイテレータは、関数型言語の考えに着想を得たRustの機能です。低レベルのパフォーマンスで、 高レベルの考えを明確に表現するというRustの能力に貢献しています。クロージャとイテレータの実装は、 実行時のパフォーマンスが影響されないようなものです。これは、ゼロ代償抽象化を提供するのに努力を惜しまないRustの目標の一部です。

今や入出力プロジェクトの表現力を改善したので、プロジェクトを世界と共有するのに役に立つcargoの機能にもっと目を向けましょう。