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
while
loop biasa dengando-while
loop. Dando-while
loop diatur dalamif
klausa. 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.
java
jvm
jit
machine-instruction
Mencoba
sumber
sumber
Jawaban:
while (condition) { ... }
Alur Kerja:
if (condition) do { ... } while (condition);
Alur Kerja:
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.
sumber
do-while
kode sumber tertentu tidak relevan, karena kami sebenarnya tidak menulisnya. Kami menuliswhile
loop dan membiarkan kompiler dan JIT bersekongkol untuk memperbaikinya bagi kami (melalui inversi loop) jika / seperlunya.Ini dapat mengoptimalkan loop yang selalu dijalankan setidaknya sekali.
Putaran biasa
while
kemudian 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-while
loop 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); }
sumber
boolean b = true; while(b){ b = maybeTrue();}
untukboolean b;do{ b = maybeTrue();}while(b);
harus cukup.Mari kita telusuri mereka:
The
while
Versi:void foo(int n) { while (n < 10) { use(n); ++n; } done(); }
n
dan lompat kedone();
jika kondisinya tidak benar.n
.done()
.The
do-while
Versi:(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(); }
n
dan lompat kedone();
jika kondisinya tidak benar.n
.done()
.Jadi misalnya, jika
n
mulai menjadi9
, kita tidak pernah melompat sama sekali dalamdo-while
versi, sedangkan dalamwhile
versi kita harus melompat kembali ke awal, melakukan pengujian, dan kemudian melompat kembali ke akhir ketika kita melihat itu tidak benar .sumber
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.
sumber