Apa teknik loop inversi?

89

Saya sedang membaca dokumen yang berbicara tentang teknik pengoptimalan just-in-time compiler (JIT) untuk Java. Salah satunya adalah "loop inversion". Dan dokumen itu mengatakan:

Anda mengganti whileloop biasa dengan do-whileloop. Dan do-whileloop diatur dalam ifklausa. Penggantian ini menyebabkan dua lompatan lebih sedikit.

Bagaimana cara kerja loop inversi dan bagaimana cara mengoptimalkan jalur kode kita?

NB: Akan sangat bagus jika seseorang dapat menjelaskan dengan contoh kode Java dan bagaimana JIT mengoptimalkannya ke kode asli dan mengapa itu optimal dalam prosesor modern.

Mencoba
sumber
2
Ini bukan sesuatu yang akan Anda lakukan pada kode sumber Anda. Itu terjadi di tingkat kode asli.
Marko Topolnik
2
@ MarkoTopolnik saya tahu. Tetapi saya ingin tahu bagaimana JIT melakukan ini di tingkat kode asli. Terima kasih.
Mencoba
1
oh keren, ada halaman wikipedia tentang ini dengan banyak contoh en.wikipedia.org/wiki/Loop_inversion . Contoh C sama validnya di Java.
Benjamin Gruenbaum
Beberapa waktu yang lalu terinspirasi oleh salah satu pertanyaan tentang SO. Saya telah melakukan penelitian singkat tentang masalah ini, mungkin hasilnya akan membantu Anda: stackoverflow.com/questions/16205843/java-loop-efficiency/…
Adam Siemion
Apakah ini sama dengan kondisi loop yang biasanya diletakkan di akhir (terlepas dari apakah akan ada lebih sedikit lompatan yang dilakukan), hanya sehingga instruksi lompatan lebih sedikit (1 vs 2 per iterasi)?
extremeaxe5

Jawaban:

108
while (condition) { 
  ... 
}

Alur Kerja:

  1. periksa kondisi;
  2. jika salah, lompat ke luar loop;
  3. menjalankan satu iterasi;
  4. lompat ke atas.

if (condition) do {
  ...
} while (condition);

Alur Kerja:

  1. periksa kondisi;
  2. jika salah, lompat ke luar loop;
  3. menjalankan satu iterasi;
  4. periksa kondisi;
  5. jika benar, lompat ke langkah 3.

Membandingkan keduanya, Anda dapat dengan mudah melihat bahwa yang terakhir mungkin tidak melakukan lompatan sama sekali, asalkan ada tepat satu langkah melalui loop, dan umumnya jumlah lompatan akan menjadi satu kurang dari jumlah iterasi. Mantan harus melompat kembali untuk memeriksa kondisinya, hanya untuk melompat keluar dari lingkaran ketika kondisinya salah.

Lompatan pada arsitektur CPU pipelined modern bisa jadi sangat mahal: karena CPU sedang menyelesaikan eksekusi pemeriksaan sebelum lompatan, instruksi di luar lompatan itu sudah ada di tengah pipeline. Semua pemrosesan ini harus dibuang jika prediksi cabang gagal. Eksekusi lebih lanjut ditunda saat pipa sedang ditegur.

Menjelaskan prediksi cabang yang disebutkan : untuk setiap jenis lompatan bersyarat, CPU memiliki dua instruksi, masing-masing termasuk taruhan pada hasilnya. Misalnya, Anda akan meletakkan instruksi yang mengatakan " lompat jika bukan nol, bertaruh bukan nol " di akhir putaran karena lompatan harus dilakukan pada semua iterasi kecuali yang terakhir. Dengan cara itu CPU mulai memompa pipeline-nya dengan instruksi yang mengikuti target lompat, bukan yang mengikuti instruksi lompat itu sendiri.

Catatan penting

Jangan tidak mengambil ini sebagai contoh bagaimana mengoptimalkan pada tingkat kode sumber. Itu akan salah kaprah karena, seperti yang sudah jelas dari pertanyaan Anda, transformasi dari bentuk pertama ke bentuk kedua adalah sesuatu yang dilakukan oleh compiler JIT sebagai masalah rutin, sepenuhnya sendiri.

Marko Topolnik
sumber
51
Catatan itu pada akhirnya adalah hal yang sangat, sangat penting.
TJ Crowder
2
@AdamSiemion: Bytecode yang dibuat untuk do-whilekode sumber tertentu tidak relevan, karena kami sebenarnya tidak menulisnya. Kami menulis whileloop dan membiarkan kompiler dan JIT bersekongkol untuk memperbaikinya bagi kami (melalui inversi loop) jika / seperlunya.
TJ Crowder
1
@TJCrowder +1 untuk hal di atas, ditambah catatan untuk Adam: jangan pernah mempertimbangkan bytecode saat memikirkan tentang pengoptimalan kompiler JIT. Bytecode lebih mirip dengan kode sumber Java daripada kode yang dikompilasi JIT yang sebenarnya sedang dieksekusi. Faktanya, tren dalam bahasa modern tidak memiliki bytecode sama sekali sebagai bagian dari spcefication bahasa.
Marko Topolnik
1
Akan lebih informatif catatan Penting dijelaskan sedikit lebih. Mengapa itu sepenuhnya salah arah?
arsaKasra
2
@arsaKasra Salah kaprah karena secara umum keterbacaan dan stabilitas mengalahkan pengoptimalan dalam kode sumber. Terutama dengan wahyu bahwa JIT melakukan ini untuk Anda, Anda tidak boleh mencoba pengoptimalan (sangat mikro) sendiri.
Radiodef
24

Ini dapat mengoptimalkan loop yang selalu dijalankan setidaknya sekali.

Putaran biasa whilekemudian akan selalu melompat kembali ke awal setidaknya sekali dan melompat ke akhir sekali di akhir. Contoh loop sederhana yang berjalan satu kali:

int i = 0;
while (i++ < 1) {
    //do something
}  

Sebuah do-whileloop di sisi lain akan melewatkan lompatan pertama dan terakhir. Berikut adalah loop yang setara dengan loop di atas, yang akan berjalan tanpa lompatan:

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
Keppil
sumber
+1 karena benar dan pertama, harap pertimbangkan untuk menambahkan contoh kode. Sesuatu seperti boolean b = true; while(b){ b = maybeTrue();}untuk boolean b;do{ b = maybeTrue();}while(b);harus cukup.
Benjamin Gruenbaum
Jangan khawatir. Ini seperti membatalkan kalimat pembuka jawaban, fwiw. :-)
TJ Crowder
@TJ Yah, itu masih tidak akan mengoptimalkan loop yang tidak masuk, akan ada satu lompatan dalam kedua kasus.
Keppil
Ah iya. Maaf, saya membaca itu berarti Anda tidak dapat menerapkannya ke loop yang tidak melakukan loop setidaknya satu kali (bukannya tidak membantu mereka). Denganmu sekarang. :-)
TJ Crowder
@Keppil Anda mungkin harus menjelaskan bahwa dalam kasus di mana kami memiliki banyak iterasi X, maka kami hanya akan menyimpan satu lompatan di antara X yang.
Manuel Selva
3

Mari kita telusuri mereka:

The whileVersi:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. Pertama kita uji ndan lompat ke done();jika kondisinya tidak benar.
  2. Kemudian kami menggunakan dan meningkatkan n.
  3. Sekarang kita kembali ke kondisi tersebut.
  4. Bilas, ulangi.
  5. Ketika kondisinya tidak lagi benar, kami melompat ke done().

The do-whileVersi:

(Ingat, kita sebenarnya tidak melakukan ini di kode sumber [yang akan menyebabkan masalah pemeliharaan], kompilator / JIT melakukannya untuk kita.)

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}
  1. Pertama kita uji ndan lompat ke done();jika kondisinya tidak benar.
  2. Kemudian kami menggunakan dan meningkatkan n.
  3. Sekarang kami menguji kondisinya dan melompat kembali jika itu benar.
  4. Bilas, ulangi.
  5. Ketika kondisinya tidak lagi benar, kita mengalir (bukan melompat) ke done().

Jadi misalnya, jika nmulai menjadi 9, kita tidak pernah melompat sama sekali dalam do-whileversi, sedangkan dalam whileversi kita harus melompat kembali ke awal, melakukan pengujian, dan kemudian melompat kembali ke akhir ketika kita melihat itu tidak benar .

TJ Crowder
sumber
3

Loop inversi adalah teknik pengoptimalan kinerja yang meningkatkan kinerja karena prosesor dapat mencapai hasil yang sama dengan instruksi yang lebih sedikit. Ini sebagian besar akan meningkatkan kinerja dalam kondisi batas.

Tautan ini memberikan contoh lain untuk inversi loop. Dalam beberapa arsitektur di mana penurunan dan perbandingan diimplementasikan sebagai satu set instruksi, masuk akal untuk mengubah perulangan for menjadi sementara dengan operasi pengurangan dan perbandingan.

Wikipedia memiliki contoh yang sangat bagus dan saya menjelaskannya lagi di sini.

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

akan diubah oleh kompilator menjadi

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

Bagaimana ini diterjemahkan menjadi kinerja? Ketika nilai i adalah 99, prosesor tidak perlu melakukan GOTO (yang diperlukan dalam kasus pertama). Ini meningkatkan kinerja.

Anirudhan J
sumber