Program Java berikut ini berjalan rata-rata antara 0,50 detik dan 0,55 detik:
public static void main(String[] args) {
long startTime = System.nanoTime();
int n = 0;
for (int i = 0; i < 1000000000; i++) {
n += 2 * (i * i);
}
System.out.println((double) (System.nanoTime() - startTime) / 1000000000 + " s");
System.out.println("n = " + n);
}
Jika saya ganti 2 * (i * i)
dengan 2 * i * i
, dibutuhkan antara 0,60 dan 0,65 detik untuk menjalankan. Bagaimana bisa?
Saya menjalankan setiap versi program 15 kali, bergantian antara keduanya. Inilah hasilnya:
2*(i*i) | 2*i*i
----------+----------
0.5183738 | 0.6246434
0.5298337 | 0.6049722
0.5308647 | 0.6603363
0.5133458 | 0.6243328
0.5003011 | 0.6541802
0.5366181 | 0.6312638
0.515149 | 0.6241105
0.5237389 | 0.627815
0.5249942 | 0.6114252
0.5641624 | 0.6781033
0.538412 | 0.6393969
0.5466744 | 0.6608845
0.531159 | 0.6201077
0.5048032 | 0.6511559
0.5232789 | 0.6544526
Jalankan tercepat 2 * i * i
memakan waktu lebih lama dari lari paling lambat 2 * (i * i)
. Jika mereka memiliki efisiensi yang sama, kemungkinan terjadinya ini akan kurang dari 1/2^15 * 100% = 0.00305%
.
java
performance
benchmarking
bytecode
jit
Stefan
sumber
sumber
2 * i * i
lebih lambat. Saya akan mencoba berlari dengan Graal juga.i * i * 2
lebih cepat daripada2 * i * i
? " Untuk kejelasan yang lebih baik bahwa masalahnya ada pada urutan operasi.Jawaban:
Ada sedikit perbedaan dalam pemesanan bytecode.
2 * (i * i)
:vs
2 * i * i
:Pada pandangan pertama ini seharusnya tidak membuat perbedaan; jika ada versi kedua lebih optimal karena menggunakan satu slot kurang.
Jadi kita perlu menggali lebih dalam ke level yang lebih rendah (JIT) 1 .
Ingat bahwa JIT cenderung membuka gulungan kecil dengan sangat agresif. Memang kami mengamati 16x membuka gulungan untuk
2 * (i * i)
kasus ini:Kita melihat bahwa ada 1 register yang "tumpah" ke stack.
Dan untuk
2 * i * i
versinya:Di sini kami mengamati lebih banyak "tumpahan" dan lebih banyak akses ke tumpukan
[RSP + ...]
, karena hasil yang lebih menengah yang perlu dipertahankan.Dengan demikian jawaban atas pertanyaannya sederhana:
2 * (i * i)
lebih cepat daripada2 * i * i
karena JIT menghasilkan kode perakitan yang lebih optimal untuk kasus pertama.Tetapi tentu saja jelas bahwa versi pertama maupun kedua tidak ada gunanya; loop benar-benar bisa mendapat manfaat dari vektorisasi, karena x86-64 CPU memiliki setidaknya dukungan SSE2.
Jadi ini masalah optimizer; seperti yang sering terjadi, itu membuka gulungan terlalu agresif dan menembak dirinya sendiri di kaki, sambil kehilangan berbagai peluang lainnya.
Faktanya, CPU x86-64 modern memecah instruksi lebih lanjut menjadi micro-ops (µops) dan dengan fitur-fitur seperti pengubahan nama register, cache µop dan buffer loop, optimisasi loop membutuhkan jauh lebih banyak keahlian daripada membuka gulungan sederhana untuk kinerja optimal. Menurut panduan optimasi Agner Fog :
Mengenai waktu muat tersebut - bahkan hit L1D tercepat memakan biaya 4 siklus , register ekstra dan µop, jadi ya, bahkan beberapa akses ke memori akan melukai kinerja dalam loop ketat.
Tetapi kembali ke peluang vektorisasi - untuk melihat seberapa cepatnya, kita dapat mengkompilasi aplikasi C yang mirip dengan GCC , yang langsung membuat vektorisasi (AVX2 ditunjukkan, SSE2 serupa) 2 :
Dengan waktu berjalan:
1 Untuk mendapatkan output perakitan yang dihasilkan JIT, dapatkan JVM debug dan jalankan bersama
-XX:+PrintOptoAssembly
2 Versi C dikompilasi dengan
-fwrapv
flag, yang memungkinkan GCC untuk memperlakukan overflow bilangan bulat yang ditandatangani sebagai pembungkus dua komplemen.sumber
ret
instruksi, atau memancarkan label dan tidak ada instruksi ret sehingga eksekusi hanya gagal. GCC sebenarnya berperilaku ini kadang-kadang ketika bertemu UB. Misalnya: mengapa ret menghilang dengan optimasi? . Anda pasti ingin mengkompilasi kode yang terbentuk dengan baik untuk memastikan asm itu waras.mov
/add-immediate
. misalnyamovl RBX, R9
/addl RBX, #8
seharusnyaleal ebx, [r9 + 8]
, 1 uop untuk menyalin dan menambahkan. Atauleal ebx, [r9 + r9 + 16]
melakukanebx = 2*(r9+8)
. Jadi ya, membuka gulungan sampai tumpah adalah bodoh, dan begitu juga codegen braindead naif yang tidak mengambil keuntungan dari identitas integer dan matematika integer asosiatif.Ketika multiplikasi adalah
2 * (i * i)
, JVM mampu memfaktorkan keluar perkalian dengan2
dari loop, menghasilkan kode yang setara tetapi lebih efisien ini:tetapi ketika multiplikasi adalah
(2 * i) * i
, JVM tidak mengoptimalkannya karena perkalian dengan konstanta tidak lagi tepat sebelum penambahan.Berikut adalah beberapa alasan mengapa saya pikir inilah masalahnya:
if (n == 0) n = 1
pernyataan pada awal loop menghasilkan kedua versi menjadi efisien, karena memfaktorkan perkalian tidak lagi menjamin bahwa hasilnya akan sama2 * (i * i)
versiBerikut adalah kode tes yang saya gunakan untuk menarik kesimpulan ini:
Dan inilah hasilnya:
sumber
n *= 2000000000;
2*1*1 + 2*2*2 + 2*3*3
. Jelas bahwa menghitung1*1 + 2*2 + 3*3
dan mengalikan dengan 2 adalah benar, sedangkan mengalikan dengan 8 tidak akan.2(1²) + 2(2²) + 2(3²) = 2(1² + 2² + 3²)
. Itu sangat sederhana dan saya hanya lupa karena kenaikan loop.2 * (i * i)
tetapi bukan dari(2 * i) * i
? Saya akan berpikir mereka setara (itu mungkin asumsi saya yang buruk). Jika demikian, bukankah JVM akan mengkanoniskan ekspresi sebelum mengoptimalkan?Kode byte: https://cs.nyu.edu/courses/fall00/V22.0201-001/jvm2.html Kode byte Penampil: https://github.com/Konloch/bytecode-viewer
Di JDK saya (Windows 10 64 bit, 1.8.0_65-b17) saya dapat mereproduksi dan menjelaskan:
Keluaran:
Jadi kenapa? Kode byte adalah ini:
Perbedaannya adalah: Dengan kurung (
2 * (i * i)
):Tanpa tanda kurung (
2 * i * i
):Memuat semua pada tumpukan dan kemudian bekerja kembali lebih cepat daripada beralih antara meletakkan di atas tumpukan dan mengoperasikannya.
sumber
Kasperd bertanya dalam komentar tentang jawaban yang diterima:
Saya tidak memiliki reputasi yang cukup untuk menjawab ini di komentar, tetapi ini adalah ISA yang sama. Perlu ditunjukkan bahwa versi GCC menggunakan logika integer 32-bit dan versi kompilasi JVM menggunakan logika integer 64-bit secara internal.
R8 hingga R15 hanyalah register X86_64 baru . EAX ke EDX adalah bagian bawah register tujuan umum RAX ke RDX. Bagian penting dalam jawabannya adalah bahwa versi GCC tidak terbuka. Ini hanya menjalankan satu putaran loop per loop kode mesin yang sebenarnya. Sementara versi JVM memiliki 16 putaran loop dalam satu loop fisik (berdasarkan jawaban rustyx, saya tidak menafsirkan ulang perakitan). Ini adalah salah satu alasan mengapa ada lebih banyak register yang digunakan karena loop body sebenarnya 16 kali lebih lama.
sumber
*2
keluar dari loop. Meskipun dalam kasus ini, itu bahkan bukan kemenangan untuk melakukan itu, karena melakukannya secara gratis dengan LEA. Pada Intel CPU,lea eax, [rax+rcx*2]
memiliki latensi 1c yang sama denganadd eax,ecx
. Namun, pada CPU AMD indeks skala mana pun meningkatkan latensi LEA menjadi 2 siklus. Jadi rantai ketergantungan loop-carry memanjang menjadi 2 siklus, menjadi hambatan pada Ryzen. (imul ecx,edx
throughput adalah 1 per jam pada Ryzen, dan pada Intel).Meskipun tidak terkait langsung dengan lingkungan pertanyaan, hanya untuk keingintahuan, saya melakukan tes yang sama pada .NET Core 2.1, x64, mode rilis.
Ini adalah hasil yang menarik, mengkonfirmasikan phonomena serupa (sebaliknya) terjadi di sisi gelap gaya. Kode:
Hasil:
2 * (i * i)
2 * i * i
sumber
Saya mendapat hasil yang serupa:
Saya mendapat hasil SAMA jika kedua loop berada di program yang sama, atau masing-masing dalam file .java terpisah .class, dieksekusi pada menjalankan yang terpisah.
Akhirnya, inilah
javap -c -v <.java>
dekompilasi dari masing-masing:vs.
FYI -
sumber
-XX:+PrintOptoAssembly
. Atau cukup gunakan vtune atau sama.Pengamatan menarik menggunakan Java 11 dan mematikan loop membuka gulungan dengan opsi VM berikut:
Pengulangan dengan
2 * (i * i)
ekspresi menghasilkan kode asli 1 yang lebih ringkas :dibandingkan dengan
2 * i * i
versi:Versi Java:
Hasil patok banding:
Kode sumber patokan:
1 - Opsi VM yang digunakan:
-XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0
sumber
i
sebelum menyalinnya untuk menghitung2*i
, ia melakukannya setelah itu sehingga membutuhkanadd r11d,2
instruksi tambahan . (Plus ia melewatkanadd same,same
lubang intip bukanshl
oleh 1 (tambahkan berjalan di lebih banyak port). Ia juga merindukan lubang intip LEA untukx*2 + 2
(lea r11d, [r8*2 + 2]
) jika itu benar-benar ingin melakukan hal-hal dalam urutan itu untuk beberapa alasan penjadwalan instruksi gila. Kita sudah bisa melihat dari versi membuka gulungan yang kehilangan LEA adalah biaya banyak uops, sama seperti keduanya loop di sinilea eax, [rax + r11 * 2]
akan menggantikan 2 instruksi (di kedua loop) jika kompiler JIT punya waktu untuk mencari optimasi dalam loop yang berjalan lama. Kompilator masa depan yang baik mana pun akan menemukannya. (Kecuali mungkin menyetel hanya untuk AMD, di mana LEA skala indeks memiliki 2 siklus latensi jadi mungkin tidak sepadan.)Saya mencoba JMH menggunakan pola dasar default: Saya juga menambahkan versi yang dioptimalkan berdasarkan penjelasan Runemoro .
Hasilnya ada di sini:
Di PC saya ( Core i7 860 - tidak ada artinya selain membaca di smartphone saya):
n += i*i
lalun*2
yang pertama2 * (i * i)
adalah yang kedua.JVM jelas tidak mengoptimalkan dengan cara yang sama dengan manusia (berdasarkan jawaban Runemoro).
Sekarang, baca bytecode:
javap -c -v ./target/classes/org/sample/MyBenchmark.class
Saya bukan ahli bytecode, tetapi kita
iload_2
sebelum kitaimul
: di situlah Anda mendapatkan perbedaan: Saya dapat menganggap bahwa JVM mengoptimalkan pembacaani
dua kali (i
sudah ada di sini, dan tidak perlu memuatnya lagi) sementara di2*i*i
dalamnya bisa ' t.sumber
Lebih dari sebuah tambahan. Saya melakukan repro percobaan menggunakan Java 8 JVM terbaru dari IBM:
Dan ini menunjukkan hasil yang sangat mirip:
(hasil kedua menggunakan 2 * i * i).
Cukup menarik, ketika berjalan di mesin yang sama, tetapi menggunakan Oracle Java:
hasilnya rata-rata sedikit lebih lambat:
Singkat cerita: bahkan nomor versi kecil masalah HotSpot di sini, karena perbedaan halus dalam implementasi JIT dapat memiliki efek penting.
sumber
Dua metode penambahan memang menghasilkan kode byte yang sedikit berbeda:
Untuk
2 * (i * i)
vs:Untuk
2 * i * i
.Dan saat menggunakan tolok ukur JMH seperti ini:
Perbedaannya jelas:
Apa yang Anda amati benar, dan bukan hanya anomali dari gaya pembandingan Anda (yaitu, tidak ada pemanasan, lihat Bagaimana cara saya menulis pembandingan mikro yang benar di Jawa? )
Berlari lagi dengan Graal:
Anda melihat bahwa hasilnya jauh lebih dekat, yang masuk akal, karena Graal adalah kompiler yang berkinerja lebih baik, lebih modern, secara keseluruhan.
Jadi ini benar-benar hanya seberapa baik kompiler JIT dapat mengoptimalkan sepotong kode tertentu, dan tidak selalu memiliki alasan logis untuk itu.
sumber