[解決済み】240以上の要素を持つ配列に対してループ処理を行うと、パフォーマンスに大きな影響があるのはなぜですか？

質問

Rustで配列に対してsumループを実行する際、以下のような場合にパフォーマンスが大きく低下することに気づきました。 CAPACITY >= 240です。 CAPACITY = 239は約80倍の速さです。

Rustは、quot;short"配列に対して特別なコンパイル最適化を行っているのでしょうか？

でコンパイルします。 rustc -C opt-level=3 .

use std::time::Instant;

const CAPACITY: usize = 240;
const IN_LOOPS: usize = 500000;

fn main() {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }
    let mut sum = 0;
    let now = Instant::now();
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }
    println!("sum:{} time:{:?}", sum, now.elapsed());
}

解決方法は？

概要 240以下では、LLVMは内部ループを完全に展開し、繰り返しループを最適化することができることに気づき、ベンチマークを破壊します。

LLVMが特定の最適化を実行しなくなる魔法の閾値が見つかりました。 . この閾値は 8 バイト * 240 = 1920 バイトです（あなたの配列は usize のため、x86-64のCPUを想定して8バイトを乗じた長さになります)。このベンチマークでは、ある特定の最適化 - 長さ239に対してのみ実行 - が、大きな速度差の原因となっています。しかし、ゆっくり始めてみましょう。

(この解答のコードはすべて -C opt-level=3 )

pub fn foo() -> usize {
    let arr = [0; 240];
    let mut s = 0;
    for i in 0..arr.len() {
        s += arr[i];
    }
    s
}

この単純なコードは、おおよそ期待される組み立て、すなわち、要素を追加していくループを生成します。しかし、もし 240 を 239 というように、生成されるアセンブリはかなり異なります。 Godbolt Compiler Explorerで見る . 以下は、そのアセンブリのごく一部です。

movdqa  xmm1, xmmword ptr [rsp + 32]
movdqa  xmm0, xmmword ptr [rsp + 48]
paddq   xmm1, xmmword ptr [rsp]
paddq   xmm0, xmmword ptr [rsp + 16]
paddq   xmm1, xmmword ptr [rsp + 64]
; more stuff omitted here ...
paddq   xmm0, xmmword ptr [rsp + 1840]
paddq   xmm1, xmmword ptr [rsp + 1856]
paddq   xmm0, xmmword ptr [rsp + 1872]
paddq   xmm0, xmm1
pshufd  xmm1, xmm0, 78
paddq   xmm1, xmm0

というものです。 ループアンローリング : LLVMは、ループ変数のインクリメント、ループの終了チェック、ループの開始へのジャンプなど、すべてのquot;ループ管理命令"を実行する必要がないように、ループ本体を何度も貼り付けます。

因みに paddq などは、複数の値を並列に合計することができるSIMD命令です。さらに、16バイトのSIMDレジスタが2つ( xmm0 と xmm1 )が並列に使われているので、CPUの命令レベル並列処理では、基本的にこれらの命令を2つ同時に実行することができます。結局のところ、これらは互いに独立しているのです。最終的には、両方のレジスタを加算し、水平方向に合計したものがスカラー結果となります。

最近の主流のx86 CPU（低消費電力のAtomではない）は、L1dキャッシュにヒットすると、本当に1クロックあたり2つのベクトルロードが可能であり paddq スループットも最低でも1クロックあたり2個、レイテンシは1サイクルのCPUがほとんどです。 参照 https://agner.org/optimize/ また このQ&A 複数のアキュムレータを使用することで、（ドット積のFP FMAの）レイテンシを隠し、代わりにスループットをボトルネックにしています。

LLVMは小さなループをアンロールする いくつか でないときは 十分に のアンロールを行い、なおかつ複数のアキュムレータを使用します。そのため、通常、LLVMで生成されたループでは、完全なアンロールを行わなくても、フロントエンドのバンド幅とバックエンドのレイテンシーのボトルネックは大きな問題ではありません。

しかし、ループのアンロールは、80倍の性能差の原因にはならないのです! 少なくともループアローリングだけではありません。実際のベンチマークコードを見てみましょう。あるループを別のループの中に入れています。

const CAPACITY: usize = 239;
const IN_LOOPS: usize = 500000;

pub fn foo() -> usize {
    let mut arr = [0; CAPACITY];
    for i in 0..CAPACITY {
        arr[i] = i;
    }

    let mut sum = 0;
    for _ in 0..IN_LOOPS {
        let mut s = 0;
        for i in 0..arr.len() {
            s += arr[i];
        }
        sum += s;
    }

    sum
}

( Godbolt コンパイラエクスプローラについて )

のアセンブリは CAPACITY = 240 は普通に見えます。2つのネストしたループです。(関数の最初に、初期化のためのコードがありますが、これは無視します)。しかし、239の場合はまったく違っています。初期化ループと内部ループがアンロールされたことがわかります。

重要な違いは、239の場合、LLVMは内側のループの結果が外側のループに依存しないことを理解することができたということです その結果、LLVMは基本的にまず内側のループだけを実行し（合計を計算する）、次に外側のループをシミュレートするコードを出力します。 sum を何度も繰り返すのです!

まず、上記とほぼ同じアセンブリ（内部ループを表すアセンブリ）が表示されます。その後、このようになります（アセンブリを説明するためにコメントを付けました。 * は特に重要です）。

        ; at the start of the function, `rbx` was set to 0

        movq    rax, xmm1     ; result of SIMD summing up stored in `rax`
        add     rax, 711      ; add up missing terms from loop unrolling
        mov     ecx, 500000   ; * init loop variable outer loop
.LBB0_1:
        add     rbx, rax      ; * rbx += rax
        add     rcx, -1       ; * decrement loop variable
        jne     .LBB0_1       ; * if loop variable != 0 jump to LBB0_1
        mov     rax, rbx      ; move rbx (the sum) back to rax
        ; two unimportant instructions omitted
        ret                   ; the return value is stored in `rax`

ここでわかるように、内側のループの結果が取り出され、外側のループが実行されるのと同じ回数だけ足し算されて、返されるのです。LLVMがこの最適化を行えるのは、内側のループが外側のループから独立していることを理解しているからに他ならない。

つまり、ランタイムが CAPACITY * IN_LOOPS から CAPACITY + IN_LOOPS . そして、これが大きな性能差の原因となっています。

補足：これってどうにかならないの？そうでもありません。LLVMはこのような魔法の閾値を持っていなければ、LLVM最適化があるコードで完了するのに永遠にかかる可能性があるからです。しかし、このコードが非常に人工的なものであることにも同意できます。実際には、このような大きな差が出るとは思えません。フルループアンロールによる差は、このような場合、通常、ファクター2にもなりません。だから、実際のユースケースについて心配する必要はない。

Rustの慣用的なコードについて、最後のメモとして。 arr.iter().sum() は、配列の全要素を合計するためのより良い方法です。そして、2番目の例でこれを変更しても、生成されるアセンブリに顕著な違いは生じません。パフォーマンスを低下させると判断した場合を除き、短い慣用句を使用する必要があります。