Kapan, jika pernah, apakah loop unrolling masih berguna?

Saya telah mencoba untuk mengoptimalkan beberapa kode yang sangat kritis terhadap kinerja (algoritma pengurutan cepat yang disebut jutaan dan jutaan kali di dalam simulasi monte carlo) dengan membuka gulungan berulang. Inilah loop dalam yang saya coba percepat:

// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}

Saya mencoba membuka gulungan ke sesuatu seperti:

while(true) {
    if(myArray[++index1] < pivot) break;
    if(myArray[++index1] < pivot) break;
    // More unrolling
}


while(true) {
    if(pivot < myArray[--index2]) break;
    if(pivot < myArray[--index2]) break;
    // More unrolling
}

Ini sama sekali tidak membuat perbedaan jadi saya mengubahnya kembali ke bentuk yang lebih mudah dibaca. Saya memiliki pengalaman serupa di lain waktu saya mencoba membuka gulungan loop. Mengingat kualitas prediktor cabang pada perangkat keras modern, kapan, jika pernah, apakah pembukaan gulungan masih merupakan pengoptimalan yang berguna?

Loop unrolling masuk akal jika Anda dapat memutuskan rantai ketergantungan. Ini memberikan CPU yang rusak atau super skalar kemungkinan untuk menjadwalkan hal-hal dengan lebih baik dan dengan demikian berjalan lebih cepat.

Contoh sederhana:

for (int i=0; i<n; i++)
{
  sum += data[i];
}

Di sini rantai ketergantungan argumen sangat pendek. Jika Anda mendapatkan stall karena Anda memiliki cache-miss pada data-array, cpu tidak dapat melakukan apapun selain menunggu.

Di sisi lain kode ini:

for (int i=0; i<n; i+=4)
{
  sum1 += data[i+0];
  sum2 += data[i+1];
  sum3 += data[i+2];
  sum4 += data[i+3];
}
sum = sum1 + sum2 + sum3 + sum4;

bisa berlari lebih cepat. Jika Anda mendapatkan cache miss atau stall lain dalam satu kalkulasi, masih ada tiga rantai dependensi lain yang tidak bergantung pada stall. CPU yang rusak dapat menjalankan ini.

Itu tidak akan membuat perbedaan karena Anda melakukan jumlah perbandingan yang sama. Inilah contoh yang lebih baik. Dari pada:

for (int i=0; i<200; i++) {
  doStuff();
}

menulis:

for (int i=0; i<50; i++) {
  doStuff();
  doStuff();
  doStuff();
  doStuff();
}

Meskipun demikian, hampir pasti tidak akan menjadi masalah tetapi Anda sekarang melakukan 50 perbandingan, bukan 200 (bayangkan perbandingannya lebih kompleks).

Putaran manual membuka gulungan secara umum sebagian besar merupakan artefak sejarah. Ini adalah salah satu dari daftar hal-hal yang terus bertambah yang akan dilakukan kompiler yang baik untuk Anda ketika itu penting. Misalnya, kebanyakan orang tidak repot-repot menulis x <<= 1atau x += xsebaliknya x *= 2. Anda tinggal menulis x *= 2dan kompilator akan mengoptimalkannya untuk Anda untuk apa pun yang terbaik.

Pada dasarnya, kebutuhan untuk menebak-nebak kompiler Anda semakin berkurang.

Terlepas dari prediksi cabang pada perangkat keras modern, sebagian besar kompiler tetap melakukan loop unrolling untuk Anda.

Akan bermanfaat untuk mengetahui seberapa banyak pengoptimalan yang dilakukan kompiler Anda untuk Anda.

Saya menemukan presentasi Felix von Leitner sangat mencerahkan tentang subjek ini. Saya sarankan Anda membacanya. Ringkasan: Kompiler modern SANGAT pintar, jadi pengoptimalan tangan hampir tidak pernah efektif.

Sejauh yang saya pahami, kompiler modern sudah membuka gulungan loop yang sesuai - contohnya adalah gcc, jika diteruskan, tanda pengoptimalan, manual mengatakan itu akan:

Unroll loop yang jumlah iterasinya dapat ditentukan pada waktu kompilasi atau saat masuk ke loop.

Jadi, dalam praktiknya, kemungkinan kompilator Anda akan melakukan kasus-kasus sepele untuk Anda. Oleh karena itu, terserah Anda untuk memastikan bahwa sebanyak mungkin loop Anda mudah bagi kompiler untuk menentukan berapa banyak iterasi yang diperlukan.

Loop unrolling, entah itu hand unrolling atau compiler unrolling, seringkali tidak produktif, terutama dengan CPU x86 yang lebih baru (Core 2, Core i7). Intinya: tolok ukur kode Anda dengan dan tanpa loop unrolling pada CPU apa pun yang Anda rencanakan untuk menerapkan kode ini.

Mencoba tanpa mengetahui bukanlah cara untuk melakukannya.
Apakah jenis ini membutuhkan persentase waktu keseluruhan yang tinggi?

Semua loop unrolling yang dilakukan adalah mengurangi overhead loop dari incrementing / decrementing, membandingkan kondisi stop, dan jumping. Jika apa yang Anda lakukan dalam loop membutuhkan lebih banyak siklus instruksi daripada overhead loop itu sendiri, Anda tidak akan melihat banyak peningkatan dalam persentase.

Berikut contoh cara mendapatkan performa maksimal.

Loop unrolling dapat membantu dalam kasus tertentu. Keuntungan hanya tidak melewatkan beberapa tes!

Ini dapat misalnya memungkinkan penggantian skalar, penyisipan prapengambilan perangkat lunak yang efisien ... Anda akan terkejut betapa bermanfaatnya hal itu (Anda dapat dengan mudah mendapatkan kecepatan 10% pada sebagian besar loop bahkan dengan -O3) dengan membuka gulungan secara agresif.

Seperti yang dikatakan sebelumnya, ini sangat bergantung pada loop dan kompiler serta eksperimen diperlukan. Sulit untuk membuat aturan (atau heuristik kompiler untuk membuka gulungan akan sempurna)

Pembukaan loop sepenuhnya tergantung pada ukuran masalah Anda. Itu sepenuhnya tergantung pada algoritma Anda untuk dapat mengurangi ukuran menjadi kelompok kerja yang lebih kecil. Apa yang Anda lakukan di atas tidak terlihat seperti itu. Saya tidak yakin apakah simulasi monte carlo bahkan dapat dibuka gulungannya.

Saya skenario yang baik untuk membuka gulungan loop akan memutar gambar. Karena Anda dapat merotasi kelompok kerja yang terpisah. Agar ini berfungsi, Anda harus mengurangi jumlah iterasi.

Loop unrolling masih berguna jika ada banyak variabel lokal baik di dalam maupun dengan loop. Untuk menggunakan kembali register tersebut lebih banyak daripada menyimpannya untuk indeks loop.

Dalam contoh Anda, Anda menggunakan sejumlah kecil variabel lokal, tidak terlalu sering menggunakan register.

Perbandingan (ke ujung loop) juga merupakan kelemahan utama jika perbandingannya berat (yaitu non-test instruksi), terutama jika itu tergantung pada fungsi eksternal.

Loop unrolling membantu meningkatkan kesadaran CPU untuk prediksi cabang juga, tetapi itu tetap terjadi.