Mengapa ada dampak kinerja yang besar ketika mengulang array dengan 240 atau lebih elemen?

Saat menjalankan jumlah loop di atas array di Rust, saya perhatikan penurunan performa yang sangat besar ketika CAPACITY> = 240. CAPACITY= 239 sekitar 80 kali lebih cepat.

Apakah ada optimasi kompilasi khusus yang dilakukan Rust untuk array "pendek"?

Disusun dengan 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());
}

Ringkasan : di bawah 240, LLVM sepenuhnya membuka gulungan lingkaran dalam dan yang membuatnya melihat itu dapat mengoptimalkan loop berulang, melanggar patokan Anda.

Anda menemukan ambang ajaib di atas mana LLVM berhenti melakukan optimasi tertentu . Ambang adalah 8 byte * 240 = 1920 byte (array Anda adalah array usizes, oleh karena itu panjangnya dikalikan dengan 8 byte, dengan asumsi x86-64 CPU). Dalam tolok ukur ini, satu optimasi khusus - hanya dilakukan untuk panjang 239 - bertanggung jawab atas perbedaan kecepatan yang sangat besar. Tapi mari kita mulai dengan lambat:

(Semua kode dalam jawaban ini dikompilasi dengan -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
}

Kode sederhana ini akan menghasilkan kira-kira perakitan yang diharapkan: loop menambahkan elemen. Namun, jika Anda mengubah 240ke 239, yang dipancarkan perakitan berbeda cukup banyak. Lihat di Godbolt Compiler Explorer . Ini adalah bagian kecil dari majelis:

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

Inilah yang disebut loop unrolling : LLVM menempelkan loop body beberapa waktu untuk menghindari keharusan menjalankan semua "instruksi manajemen loop", yaitu menambah variabel loop, memeriksa apakah loop telah berakhir dan lompatan ke awal loop .

Jika Anda bertanya-tanya: paddqinstruksi dan sejenisnya adalah instruksi SIMD yang memungkinkan menjumlahkan beberapa nilai secara paralel. Selain itu, dua register SIMD 16-byte ( xmm0dan xmm1) digunakan secara paralel sehingga paralelisme level-instruksi dari CPU pada dasarnya dapat mengeksekusi dua instruksi ini secara bersamaan. Bagaimanapun, mereka independen satu sama lain. Pada akhirnya, kedua register ditambahkan bersama-sama dan kemudian dijumlahkan secara horizontal ke hasil skalar.

CPU x86 mainstream modern (bukan Atom berdaya rendah) benar-benar dapat melakukan 2 beban vektor per jam ketika mereka menekan cache L1d, dan paddqthroughput juga minimal 2 per jam, dengan latensi 1 siklus pada sebagian besar CPU. Lihat https://agner.org/optimize/ dan juga T&J ini tentang beberapa akumulator untuk menyembunyikan latensi (dari FP FMA untuk produk titik) dan kemacetan pada throughput sebagai gantinya.

LLVM membuka gulungan kecil beberapa saat tidak sepenuhnya membuka gulungan, dan masih menggunakan beberapa akumulator. Jadi biasanya, bandwidth front-end dan bottleneck latensi back-end bukan masalah besar untuk loop yang dihasilkan LLVM bahkan tanpa membuka gulungan penuh.

Tetapi loop membuka gulungan tidak bertanggung jawab atas perbedaan kinerja faktor 80! Paling tidak tidak membuka gulungannya sendirian. Mari kita lihat kode tolok ukur yang sebenarnya, yang menempatkan satu loop di dalam yang lain:

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
}

( Pada Penjelajah Kompiler Godbolt )

Perakitan untuk CAPACITY = 240terlihat normal: dua loop bersarang. (Pada awal fungsi ada beberapa kode hanya untuk inisialisasi, yang akan kita abaikan.) Namun, untuk 239, tampilannya sangat berbeda! Kita melihat bahwa loop inisialisasi dan loop dalam mendapat gulungan: sejauh ini sangat diharapkan.

Perbedaan penting adalah bahwa untuk 239, LLVM mampu mengetahui bahwa hasil dari loop dalam tidak tergantung pada loop luar! Sebagai akibatnya, LLVM memancarkan kode yang pada dasarnya pertama-tama hanya mengeksekusi loop dalam (menghitung jumlah) dan kemudian mensimulasikan loop luar dengan menambahkan sumbeberapa kali!

Pertama kita melihat rakitan yang hampir sama seperti di atas (rakitan yang mewakili lingkaran dalam). Setelah itu kita melihat ini (saya berkomentar untuk menjelaskan pertemuan; komentar dengan *sangat penting):

        ; 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`

Seperti yang Anda lihat di sini, hasil dari loop dalam diambil, ditambahkan sesering loop luar akan berlari dan kemudian dikembalikan. LLVM hanya dapat melakukan optimasi ini karena ia mengerti bahwa loop dalam tidak tergantung pada loop luar.

Ini berarti perubahan runtime dari CAPACITY * IN_LOOPSmenjadiCAPACITY + IN_LOOPS . Dan ini bertanggung jawab atas perbedaan kinerja yang sangat besar.

Catatan tambahan: dapatkah Anda melakukan sesuatu tentang ini? Tidak juga. LLVM harus memiliki ambang ajaib seperti itu tanpa mereka LLVM-optimasi dapat berlangsung selamanya untuk menyelesaikan kode tertentu. Tetapi kita juga bisa sepakat bahwa kode ini sangat palsu. Dalam praktiknya, saya ragu bahwa perbedaan besar akan terjadi. Perbedaannya karena loop penuh membuka gulungan biasanya bahkan tidak faktor 2 dalam kasus ini. Jadi tidak perlu khawatir tentang kasus penggunaan nyata.

Sebagai catatan terakhir tentang kode Rust idiomatik: arr.iter().sum()adalah cara yang lebih baik untuk merangkum semua elemen array. Dan mengubah ini dalam contoh kedua tidak menyebabkan perbedaan penting dalam perakitan yang dipancarkan. Anda harus menggunakan versi pendek dan idiomatis kecuali Anda mengukur bahwa itu merugikan kinerja.

Selain jawaban Lukas, jika Anda ingin menggunakan iterator, coba ini:

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

pub fn bar() -> usize {
    (0..CAPACITY).sum::<usize>() * IN_LOOPS
}

Terima kasih @ Chris Morgan untuk saran tentang pola rentang.

The dioptimalkan perakitan cukup baik:

example::bar:
        movabs  rax, 14340000000
        ret