7

私はこの非常に単純な Rust 関数を書きました:

fn iterate(nums: &Box<[i32]>) -> i32 {
    let mut total = 0;
    let len = nums.len();
    for i in 0..len {
        if nums[i] > 0 {
            total += nums[i];
        } else {
            total -= nums[i];
        }
    }

    total
}

順序付けられた配列とシャッフルされた配列を使用してメソッドを呼び出す基本的なベンチマークを作成しました。

fn criterion_benchmark(c: &mut Criterion) {
    const SIZE: i32 = 1024 * 1024;

    let mut group = c.benchmark_group("Branch Prediction");

    // setup benchmarking for an ordered array
    let mut ordered_nums: Vec<i32> = vec![];
    for i in 0..SIZE {
        ordered_nums.push(i - SIZE/2);
    }
    let ordered_nums = ordered_nums.into_boxed_slice();
    group.bench_function("ordered", |b| b.iter(|| iterate(&ordered_nums)));

    // setup benchmarking for a shuffled array
    let mut shuffled_nums: Vec<i32> = vec![];
    for i in 0..SIZE {
        shuffled_nums.push(i - SIZE/2);
    }
    let mut rng = thread_rng();
    let mut shuffled_nums = shuffled_nums.into_boxed_slice();
    shuffled_nums.shuffle(&mut rng);
    group.bench_function("shuffled", |b| b.iter(|| iterate(&shuffled_nums)));

    group.finish();
}

criterion_group!(benches, criterion_benchmark);
criterion_main!(benches);

2 つのベンチマークのランタイムがほぼ同じであることに驚いていますが、Java の同様のベンチマークでは、おそらくシャッフルされた場合の分岐予測の失敗が原因で、2 つの明確な違いが示されています。

条件付き移動命令についての言及を見てきましたがotool -tv、実行可能ファイル (Mac で実行している) の場合、iterateメソッドの出力には何も表示されません。

Rust で順序付けされたケースと順序付けられていないケースの間にパフォーマンスの違いが認識できない理由を誰かが明らかにすることはできますか?

4

1 に答える 1

11

概要cmov: LLVM は、命令または SIMD 命令の非常に巧妙な組み合わせを使用して、分岐を削除/非表示にすることができました。

Godbolt を使用して完全なアセンブリを表示しました( を使用-C opt-level=3)。組み立ての重要な部分を以下に説明します。

次のように始まります。

        mov     r9, qword ptr [rdi + 8]         ; r9 = nums.len()
        test    r9, r9                          ; if len == 0
        je      .LBB0_1                         ;     goto LBB0_1
        mov     rdx, qword ptr [rdi]            ; rdx = base pointer (first element)
        cmp     r9, 7                           ; if len > 7
        ja      .LBB0_5                         ;     goto LBB0_5
        xor     eax, eax                        ; eax = 0
        xor     esi, esi                        ; esi = 0
        jmp     .LBB0_4                         ; goto LBB0_4

.LBB0_1:
        xor     eax, eax                        ; return 0
        ret

ここで、関数は 3 つの異なる「状態」を区別します。

  • スライスが空 → すぐに 0 を返す
  • スライスの長さが ≤ 7 → 標準の順次アルゴリズムを使用 ( LBB0_4)
  • スライスの長さが > 7 → SIMD アルゴリズムを使用 ( LBB0_5)

それでは、2 種類のアルゴリズムを見てみましょう。


標準順次アルゴリズム

rsi( esi) とrax( eax) が 0 に設定されており、それrdxがデータへのベース ポインターであることを思い出してください。

.LBB0_4:
        mov     ecx, dword ptr [rdx + 4*rsi]    ; ecx = nums[rsi]
        add     rsi, 1                          ; rsi += 1
        mov     edi, ecx                        ; edi = ecx
        neg     edi                             ; edi = -edi
        cmovl   edi, ecx                        ; if ecx >= 0 { edi = ecx }
        add     eax, edi                        ; eax += edi
        cmp     r9, rsi                         ; if rsi != len
        jne     .LBB0_4                         ;     goto LBB0_4
        ret                                     ; return eax

これは、 のすべての要素を反復する単純なループですnum。ただし、ループの本体にはちょっとしたトリックがあります。元の elementecxから、否定された値が に格納されediます。を使用するとcmovl、元の値が正の場合ediは元の値で上書きされます。つまり、常に正の値になります (つまり、元の要素の絶対値が含まれます)。次に、(最後に返される) に追加されます。edieax

したがって、あなたのブランチは命令ifに隠されていました。このベンチマークcmovでわかるように、命令の実行に必要な時間は、条件の確率とは無関係です。それはかなり素晴らしい指示です！cmov


SIMD アルゴリズム

SIMD バージョンはかなりの数の命令で構成されているため、ここでは完全には貼り付けません。メインループは一度に 16 個の整数を処理します!

        movdqu  xmm5, xmmword ptr [rdx + 4*rdi]
        movdqu  xmm3, xmmword ptr [rdx + 4*rdi + 16]
        movdqu  xmm0, xmmword ptr [rdx + 4*rdi + 32]
        movdqu  xmm1, xmmword ptr [rdx + 4*rdi + 48]

これらはメモリからレジスタxmm0、xmm1、xmm3およびにロードされますxmm5。これらの各レジスタには 4 つの 32 ビット値が含まれていますが、簡単に理解できるように、各レジスタに 1 つの値が含まれていると想像してください。以下のすべての命令は、これらの SIMD レジスタの各値に対して個別に動作するため、メンタル モデルは問題ありません。以下の私の説明は、あたかもxmmレジスタに 1 つの値しか含まれていないかのようにも聞こえます。

主なトリックは次の命令にあります (これは を処理しますxmm5):

        movdqa  xmm6, xmm5      ; xmm6 = xmm5 (make a copy)
        psrad   xmm6, 31        ; logical right shift 31 bits (see below)
        paddd   xmm5, xmm6      ; xmm5 += xmm6
        pxor    xmm5, xmm6      ; xmm5 ^= xmm6

論理右シフトは、「空の上位ビット」(左側に「シフトイン」されたもの) を符号ビットの値で埋めます。31 シフトすることで、すべての位置に符号ビットのみが表示されます。したがって、正の数は 32 個のゼロになり、負の数は 32 個の 1 になります。そのため、 (ifが正の場合) または(ifが負の場合)xmm6のいずれかになります。000...000xmm5111...111xmm5

次に、このアーティフィシャルxmm6が に追加されxmm5ます。xmm5正の場合xmm6は 0 なので、追加しても変化しませんxmm5。xmm5ただし、 が負の場合は、 111...1111 を引くのと同じように加算します。最後に、 と xorxmm5しxmm6ます。繰り返しますが、最初に肯定的だった場合、影響を与えないものxmm5と xor します。000...000が最初に負の場合xmm5、 で xor し111...111ます。つまり、すべてのビットを反転します。したがって、両方のケースで：

  • 要素が正の場合、何も変更しません ( addandxorは何の効果もありませんでした)。
  • 要素が負の場合、1 を減算し、すべてのビットを反転します。これは 2 の補数の否定です。

したがって、これらの 4 つの命令でxmm5!の絶対値を計算しました。ここでも、このちょっとしたトリックのために分岐はありません。実際には 4 つの整数が含まれていることを覚えておいてxmm5ください。非常に高速です。

この絶対値はアキュムレータに追加されxmm、スライスからの値を含む他の 3 つのレジスタでも同じことが行われます。(残りのコードについては詳しく説明しません。)


AVX2 を使用した SIMD

-C target-feature=+avx2LLVM が ( 経由で) AVX2 命令を発行できるpabsdようにすると、4 つの「ハック」命令の代わりに命令を使用することもできます。

vpabsd  ymm2, ymmword ptr [rdx + 4*rdi]

メモリから値を直接ロードし、絶対値を計算してymm2、1 つの命令で格納します。また、ymmレジスタはレジスタの 2 倍の大きさであることに注意してxmmください (8 つの 32 ビット値に適合)。

于 2020-01-04T10:39:46.077 に答える