Saya sedang mengerjakan beberapa kode Java yang perlu sangat dioptimalkan karena akan berjalan di fungsi panas yang dipanggil di banyak titik dalam logika program utama saya. Bagian dari kode ini melibatkan mengalikan doublevariabel dengan 10menaikkan ke non-negatif int exponents sembarang . Salah satu cara cepat (edit: tapi bukan yang tercepat mungkin, lihat Update 2 di bawah) untuk mendapatkan nilai dikalikan adalah untuk switchpada exponent:
double multiplyByPowerOfTen(final double d, final int exponent) {
switch (exponent) {
case 0:
return d;
case 1:
return d*10;
case 2:
return d*100;
// ... same pattern
case 9:
return d*1000000000;
case 10:
return d*10000000000L;
// ... same pattern with long literals
case 18:
return d*1000000000000000000L;
default:
throw new ParseException("Unhandled power of ten " + power, 0);
}
}Elips yang dikomentari di atas menunjukkan bahwa case intkonstanta terus bertambah 1, sehingga benar-benar ada 19 casedetik dalam cuplikan kode di atas. Karena saya tidak yakin apakah saya akan benar-benar membutuhkan semua kekuatan 10 dalam casepernyataan 10melalui 18, saya menjalankan beberapa microbenchmark membandingkan waktu untuk menyelesaikan 10 juta operasi dengan switchpernyataan ini versus switchdengan hanya cases 0melalui 9(dengan batas exponent9 atau kurang untuk hindari melanggar pared-down switch). Saya mendapatkan hasil yang agak mengejutkan (bagi saya, setidaknya!) Bahwa semakin lama switchdengan lebih banyak casepernyataan benar-benar berjalan lebih cepat.
Pada lark, saya mencoba menambahkan lebih banyak lagi caseyang baru saja mengembalikan nilai-nilai dummy, dan menemukan bahwa saya bisa beralih untuk berjalan lebih cepat dengan sekitar 22-27 yang dinyatakan cases (walaupun kotak-kotak boneka itu tidak pernah benar-benar mengenai saat kode sedang berjalan ). (Sekali lagi, caseditambahkan dengan cara yang berdekatan dengan menambah casekonstanta sebelumnya dengan 1). Perbedaan waktu eksekusi ini tidak terlalu signifikan: untuk acak exponentantara 0dan 10, switchpernyataan empuk selesai menyelesaikan 10 juta eksekusi dalam 1,49 detik dibandingkan 1,54 detik untuk yang tidak diadili versi, untuk penghematan total 5ns per eksekusi. Jadi, bukan hal yang membuat terobsesi padding out aswitchpernyataan sepadan dengan usaha dari sudut pandang optimasi. Tapi saya masih merasa penasaran dan kontra-intuitif bahwa switchtidak menjadi lebih lambat (atau mungkin lebih baik mempertahankan waktu O (1) konstan ) untuk dieksekusi karena lebih casebanyak ditambahkan ke dalamnya.
Ini adalah hasil yang saya peroleh dari menjalankan dengan berbagai batasan pada exponentnilai yang dihasilkan secara acak . Saya tidak termasuk hasil semua jalan ke 1untuk exponentbatas, namun bentuk umum dari kurva tetap sama, dengan punggung bukit sekitar tanda 12-17 kasus, dan lembah antara 18-28. Semua tes dijalankan di JUnitBenchmarks menggunakan wadah bersama untuk nilai acak untuk memastikan input pengujian yang identik. Saya juga menjalankan tes baik dalam urutan dari switchpernyataan terpanjang ke terpendek, dan sebaliknya, untuk mencoba dan menghilangkan kemungkinan masalah tes terkait pemesanan. Saya telah meletakkan kode pengujian saya di repo github jika ada yang ingin mencoba mereproduksi hasil ini.
Jadi, apa yang terjadi di sini? Beberapa keanehan arsitektur saya atau konstruksi patok mikro? Atau adalah Java switchbenar-benar sedikit lebih cepat untuk mengeksekusi dalam 18untuk 28 caserentang daripada dari 11atas ke 17?
repo uji github "beralih-percobaan"
UPDATE: Saya membersihkan perpustakaan benchmarking sedikit dan menambahkan file teks di / hasil dengan beberapa output di kisaran yang lebih luas dari exponentnilai yang mungkin . Saya juga menambahkan opsi dalam kode pengujian untuk tidak membuang Exceptiondari default, tetapi ini tampaknya tidak mempengaruhi hasil.
UPDATE 2: Menemukan beberapa diskusi yang cukup bagus tentang masalah ini dari tahun 2009 di forum xkcd di sini: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . Diskusi OP tentang penggunaan Array.binarySearch()memberi saya ide untuk implementasi berbasis pola array sederhana dari pola eksponensial di atas. Tidak perlu mencari biner karena saya tahu apa entri dalam array. Tampaknya berjalan sekitar 3 kali lebih cepat daripada menggunakan switch, jelas dengan mengorbankan beberapa aliran kontrol yang diberikan switch. Kode itu telah ditambahkan ke repo github juga.
sumber
switchpernyataan, karena itu jelas solusi yang paling optimal. : D (Tolong, jangan tunjukkan ini pada petunjuk saya.)lookupswitchke atableswitch. Membongkar kode Andajavapakan menunjukkan kepada Anda dengan pasti.Jawaban:
Seperti yang ditunjukkan oleh jawaban yang lain , karena nilai case bersebelahan (bukan sparse), bytecode yang dihasilkan untuk berbagai tes Anda menggunakan tabel switch (instruksi bytecode
tableswitch).Namun, begitu JIT memulai tugasnya dan mengkompilasi bytecode ke dalam assembly,
tableswitchinstruksi tidak selalu menghasilkan array pointer: kadang-kadang tabel switch ditransformasikan menjadi apa yang tampak sepertilookupswitch(mirip dengan strukturif/else if).Mengurai kumpulan yang dihasilkan oleh JIT (hotspot JDK 1.7) menunjukkan bahwa ia menggunakan suksesi if / else jika ketika ada 17 kasus atau kurang, sebuah array pointer ketika ada lebih dari 18 (lebih efisien).
Alasan mengapa angka ajaib 18 ini digunakan tampaknya turun ke nilai default dari
MinJumpTableSizebendera JVM (sekitar baris 352 dalam kode).Saya telah mengangkat masalah ini pada daftar kompiler hotspot dan sepertinya merupakan warisan dari pengujian sebelumnya . Perhatikan bahwa nilai default ini telah dihapus di JDK 8 setelah lebih banyak pembandingan dilakukan .
Akhirnya, ketika metode ini menjadi terlalu lama (> 25 kasus dalam pengujian saya), itu tidak diuraikan lagi dengan pengaturan JVM default - yang merupakan penyebab kemungkinan penurunan kinerja pada saat itu.
Dengan 5 case, kode yang didekompilasi terlihat seperti ini (perhatikan instruksi cmp / je / jg / jmp, assembly untuk if / goto):
Dengan 18 kasing, susunannya terlihat seperti ini (perhatikan susunan pointer yang digunakan dan menekan kebutuhan untuk semua perbandingan:
jmp QWORD PTR [r8+r10*1]melompat langsung ke perkalian yang benar) - itulah kemungkinan alasan peningkatan kinerja:Dan akhirnya perakitan dengan 30 kasus (di bawah) terlihat mirip dengan 18 kasus, kecuali untuk tambahan
movapd xmm0,xmm1yang muncul di bagian tengah kode, seperti yang terlihat oleh @cHao - namun alasan paling mungkin untuk penurunan kinerja adalah bahwa metode ini terlalu lama untuk disejajarkan dengan pengaturan JVM default:sumber
Switch - case lebih cepat jika nilai case ditempatkan dalam range sempit Eg.
Karena, dalam hal ini kompiler dapat menghindari melakukan perbandingan untuk setiap kasus dalam pernyataan switch. Kompiler membuat tabel lompatan yang berisi alamat tindakan yang akan diambil pada kaki yang berbeda. Nilai di mana saklar sedang dilakukan dimanipulasi untuk mengubahnya menjadi indeks ke
jump table. Dalam implementasi ini, waktu yang diambil dalam pernyataan switch jauh lebih sedikit daripada waktu yang diambil dalam kaskade pernyataan if-else-if yang setara. Juga waktu yang diambil dalam pernyataan sakelar tidak tergantung dari jumlah kaki sakelar dalam pernyataan sakelar.Seperti yang dinyatakan dalam wikipedia tentang pernyataan beralih di bagian Kompilasi.
sumber
Jawabannya terletak pada bytecode:
SwitchTest10.java
Bytecode yang sesuai; hanya bagian yang relevan yang ditampilkan:
SwitchTest22.java:
Bytecode yang sesuai; lagi, hanya bagian yang relevan yang ditampilkan:
Dalam kasus pertama, dengan rentang yang sempit, bytecode yang dikompilasi menggunakan a
tableswitch. Dalam kasus kedua, bytecode yang dikompilasi menggunakan alookupswitch.Dalam
tableswitch, nilai integer di bagian atas tumpukan digunakan untuk mengindeks ke dalam tabel, untuk menemukan target cabang / lompat. Lompatan / cabang ini kemudian dilakukan segera. Karenanya, ini adalahO(1)operasi.A
lookupswitchlebih rumit. Dalam hal ini, nilai integer perlu dibandingkan dengan semua kunci dalam tabel sampai kunci yang benar ditemukan. Setelah kunci ditemukan, target cabang / lompat (bahwa kunci ini dipetakan ke) digunakan untuk lompat. Tabel yang digunakanlookupswitchdiurutkan dan algoritma pencarian biner dapat digunakan untuk menemukan kunci yang benar. Performa untuk pencarian biner adalahO(log n), dan seluruh proses jugaO(log n), karena lompatan masihO(1). Jadi alasan kinerjanya lebih rendah dalam hal rentang jarang adalah bahwa kunci yang benar pertama-tama harus dilihat karena Anda tidak dapat mengindeks ke dalam tabel secara langsung.Jika ada nilai jarang dan Anda hanya
tableswitchperlu menggunakan, tabel pada dasarnya akan berisi entri dummy yang mengarah kedefaultopsi. Misalnya, dengan asumsi bahwa entri terakhir dalamSwitchTest10.javaadalah21bukan10, Anda mendapatkan:Jadi kompiler pada dasarnya membuat tabel besar ini yang berisi entri boneka di antara celah, menunjuk ke target cabang
defaultinstruksi. Bahkan jika tidak adadefault, itu akan berisi entri yang menunjuk ke instruksi setelah blok switch. Saya melakukan beberapa tes dasar, dan saya menemukan bahwa jika kesenjangan antara indeks terakhir dan yang sebelumnya (9) lebih besar daripada35, ia menggunakanlookupswitchalih - alih atableswitch.Perilaku
switchpernyataan didefinisikan dalam Java Virtual Machine Specification (§3.10) :sumber
lookupswitch?Karena pertanyaan sudah dijawab (kurang lebih), berikut adalah beberapa tip. Menggunakan
Kode itu menggunakan IC secara signifikan lebih sedikit (cache instruksi) dan akan selalu dimasukkan. Array akan berada dalam cache data L1 jika kodenya panas. Tabel pencarian hampir selalu menang. (khususnya pada microbenchmarks: D)
Sunting: jika Anda ingin metode ini menjadi hot-inlined, pertimbangkan jalur non-cepat seperti
throw new ParseException()sesingkat minimum atau pindahkan mereka ke metode statis yang terpisah (karenanya buatlah sesingkat minimum). Itu adalahthrow new ParseException("Unhandled power of ten " + power, 0);ide yang lemah b / c itu memakan banyak anggaran inlining untuk kode yang hanya bisa ditafsirkan - rangkaian string cukup bertele-tele dalam bytecode. Info lebih lanjut dan kasing nyata dengan ArrayListsumber