Mengapa (a * b! = 0) lebih cepat daripada (a! = 0 && b! = 0) di Jawa?

Saya sedang menulis beberapa kode di Jawa di mana, di beberapa titik, aliran program ditentukan oleh apakah dua variabel int, "a" dan "b", bukan nol (catatan: a dan b tidak pernah negatif, dan tidak pernah dalam rentang overflow integer).

Saya dapat mengevaluasinya dengan

if (a != 0 && b != 0) { /* Some code */ }

Atau sebagai alternatif

if (a*b != 0) { /* Some code */ }

Karena saya berharap potongan kode itu akan berjalan jutaan kali per kali, saya bertanya-tanya mana yang akan lebih cepat. Saya melakukan percobaan dengan membandingkannya pada array besar yang dihasilkan secara acak, dan saya juga ingin tahu bagaimana sparsity array (fraksi data = 0) akan mempengaruhi hasil:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

Dan hasilnya menunjukkan bahwa jika Anda mengharapkan "a" atau "b" sama dengan 0 lebih dari ~ 3% dari waktu, a*b != 0lebih cepat dari a!=0 && b!=0:

Saya ingin tahu mengapa. Adakah yang bisa menjelaskan? Apakah itu kompiler atau di tingkat perangkat keras?

Sunting: Karena penasaran ... sekarang saya belajar tentang prediksi cabang, saya bertanya-tanya apa yang akan ditampilkan perbandingan analog untuk OR b adalah nol:

Kami memang melihat efek yang sama dari prediksi cabang seperti yang diharapkan, yang menarik grafik agak membalik sepanjang sumbu X.

Memperbarui

1- Saya menambahkan !(a==0 || b==0)analisis untuk melihat apa yang terjadi.

2- Saya juga termasuk a != 0 || b != 0, (a+b) != 0dan (a|b) != 0ingin tahu, setelah belajar tentang prediksi cabang. Tapi mereka tidak logis setara dengan ungkapan lain, karena hanya ATAU b perlu non-nol untuk kembali benar, sehingga mereka tidak dimaksudkan untuk dibandingkan untuk efisiensi pengolahan.

3 - Saya juga menambahkan benchmark aktual yang saya gunakan untuk analisis, yang hanya mengulangi variabel int arbitrer.

4 - Beberapa orang menyarankan untuk memasukkan a != 0 & b != 0sebagai bertentangan dengan a != 0 && b != 0, dengan prediksi bahwa itu akan berperilaku lebih dekat a*b != 0karena kami akan menghapus efek prediksi cabang. Saya tidak tahu yang &bisa digunakan dengan variabel boolean, saya pikir itu hanya digunakan untuk operasi biner dengan bilangan bulat.

Catatan: Dalam konteks yang saya pertimbangkan semua ini, int overflow bukan merupakan masalah, tapi itu jelas merupakan pertimbangan penting dalam konteks umum.

CPU: Intel Core i7-3610QM @ 2.3GHz

Versi Java: 1.8.0_45
Java (TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot (TM) 64-Bit Server VM (build 25.45-b02, mode campuran)

Saya mengabaikan masalah yang menjadi tolok ukur Anda mungkin cacat, dan mengambil hasilnya dengan nilai nominal.

Apakah itu kompiler atau di tingkat perangkat keras?

Yang terakhir, saya pikir:

  if (a != 0 && b != 0)

akan dikompilasi ke 2 beban memori dan dua cabang bersyarat

  if (a * b != 0)

akan dikompilasi menjadi 2 beban memori, cabang multiply dan satu kondisional.

Penggandaan cenderung lebih cepat daripada cabang kondisional kedua jika prediksi cabang tingkat perangkat keras tidak efektif. Saat Anda meningkatkan rasio ... prediksi cabang menjadi kurang efektif.

Alasan bahwa cabang bersyarat lebih lambat adalah bahwa mereka menyebabkan pipa eksekusi instruksi terhenti. Prediksi cabang adalah tentang menghindari kios dengan memperkirakan ke mana cabang akan pergi dan secara spekulatif memilih instruksi berikutnya berdasarkan itu. Jika prediksi gagal, ada penundaan saat instruksi untuk arah lain dimuat.

(Catatan: penjelasan di atas terlalu disederhanakan. Untuk penjelasan yang lebih akurat, Anda perlu melihat literatur yang disediakan oleh pabrikan CPU untuk pembuat kode bahasa rakitan dan penulis penyusun. Halaman Wikipedia tentang Prediktor Cabang adalah latar belakang yang bagus.)

Namun, ada satu hal yang perlu Anda perhatikan dengan optimasi ini. Apakah ada nilai di mana a * b != 0akan memberikan jawaban yang salah? Pertimbangkan kasus di mana penghitungan produk menghasilkan bilangan bulat bilangan bulat.

MEMPERBARUI

Grafik Anda cenderung mengkonfirmasi apa yang saya katakan.

• Ada juga efek "prediksi cabang" dalam a * b != 0kasus cabang bersyarat , dan ini muncul dalam grafik.

• Jika Anda memproyeksikan kurva melebihi 0,9 pada sumbu X, sepertinya 1) mereka akan bertemu pada sekitar 1,0 dan 2) titik pertemuan akan berada pada nilai Y kira-kira sama seperti untuk X = 0,0.

PEMBARUAN 2

Saya tidak mengerti mengapa kurva berbeda untuk kasus a + b != 0dan a | b != 0kasus. Mungkin ada sesuatu yang pintar dalam logika prediktor cabang. Atau itu bisa menunjukkan sesuatu yang lain.

(Perhatikan bahwa hal semacam ini dapat spesifik untuk nomor model chip tertentu atau bahkan versi. Hasil benchmark Anda mungkin berbeda pada sistem lain.)

Namun, keduanya memiliki keuntungan bekerja untuk semua nilai non-negatif dari adan b.

Saya pikir tolok ukur Anda memiliki beberapa kelemahan dan mungkin tidak berguna untuk menyimpulkan tentang program nyata. Inilah pikiran saya:

• (a|b)!=0dan (a+b)!=0uji jika salah satu nilai tidak nol, sedangkan a != 0 && b != 0dan (a*b)!=0uji apakah keduanya non-nol. Jadi, Anda tidak membandingkan waktu aritmatika saja: jika kondisinya benar lebih sering, itu menyebabkan lebih banyak eksekusi iftubuh, yang membutuhkan lebih banyak waktu juga.

• (a+b)!=0 akan melakukan hal yang salah untuk nilai positif dan negatif yang berjumlah nol, sehingga Anda tidak dapat menggunakannya dalam kasus umum, bahkan jika itu berfungsi di sini.

• Demikian pula, (a*b)!=0akan melakukan hal yang salah untuk nilai yang meluap. (Contoh acak: 196608 * 327680 adalah 0 karena hasil sebenarnya adalah 2 ³² , sehingga rendahnya 32 bit adalah 0, dan hanya itu yang Anda dapatkan jika ini adalah intoperasi.)

• VM akan mengoptimalkan ekspresi selama beberapa putaran pertama dari fractionloop luar ( ), kapan fraction0, ketika cabang hampir tidak pernah diambil. Pengoptimal dapat melakukan hal yang berbeda jika Anda mulai fractiondari 0,5.

• Kecuali VM mampu menghilangkan beberapa cek batas array di sini, ada empat cabang lain dalam ekspresi hanya karena pemeriksaan batas, dan itu merupakan faktor yang menyulitkan ketika mencoba untuk mencari tahu apa yang terjadi pada level rendah. Anda mungkin mendapatkan hasil yang berbeda jika Anda membagi array dua dimensi menjadi dua array datar, mengubah nums[0][i]dan nums[1][i]ke nums0[i]dan nums1[i].

• Prediktor cabang CPU mendeteksi pola pendek dalam data, atau menjalankan semua cabang yang diambil atau tidak diambil. Data benchmark yang dibuat secara acak adalah skenario terburuk untuk prediktor cabang . Jika data dunia nyata memiliki pola yang dapat diprediksi, atau memiliki nilai all-zero dan all-non-zero yang berjalan lama, cabang-cabangnya bisa lebih murah.

• Kode tertentu yang dieksekusi setelah kondisi terpenuhi dapat mempengaruhi kinerja mengevaluasi kondisi itu sendiri, karena hal itu mempengaruhi hal-hal seperti apakah loop dapat dibuka atau tidak, register CPU mana yang tersedia, dan jika ada nilai yang diambil numsperlu digunakan kembali setelah mengevaluasi kondisinya. Hanya menambah penghitung dalam tolok ukur bukanlah pengganti yang sempurna untuk apa yang akan dilakukan kode nyata.

• System.currentTimeMillis()pada kebanyakan sistem tidak lebih akurat dari +/- 10 ms. System.nanoTime()biasanya lebih akurat.

Ada banyak ketidakpastian, dan selalu sulit untuk mengatakan sesuatu yang pasti dengan optimasi mikro semacam ini karena trik yang lebih cepat pada satu VM atau CPU dapat lebih lambat pada yang lain. Jika menjalankan HotSpot JVM 32-bit, daripada versi 64-bit, ketahuilah bahwa ia datang dalam dua rasa: dengan VM "Klien" memiliki optimasi (lebih lemah) yang berbeda dibandingkan dengan VM "Server".

Jika Anda dapat membongkar kode mesin yang dihasilkan oleh VM , lakukan itu daripada mencoba menerka apa fungsinya!

Jawabannya bagus, meskipun saya punya ide yang dapat memperbaiki keadaan.

Karena dua cabang dan prediksi cabang terkait adalah kemungkinan penyebabnya, kami mungkin dapat mengurangi percabangan menjadi cabang tunggal tanpa mengubah logika sama sekali.

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

Ini juga bisa dilakukan

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

Alasannya, menurut aturan hubungan arus pendek, jika boolean pertama salah, yang kedua tidak harus dievaluasi. Itu harus melakukan cabang tambahan untuk menghindari mengevaluasi nums[1][i]apakah nums[0][i]itu salah. Sekarang, Anda mungkin tidak peduli yang nums[1][i]akan dievaluasi, tetapi kompiler tidak dapat memastikan bahwa itu tidak akan membuang jangkauan atau null ref ketika Anda melakukannya. Dengan mengurangi blok if ke bools sederhana, kompiler mungkin cukup pintar untuk menyadari bahwa mengevaluasi boolean kedua yang tidak perlu tidak akan memiliki efek samping negatif.

Ketika kita mengambil perkalian, bahkan jika satu angka adalah 0, maka produknya adalah 0. Saat menulis

    (a*b != 0)

Ini mengevaluasi hasil produk sehingga menghilangkan beberapa kejadian pertama dari iterasi mulai dari 0. Sebagai hasilnya perbandingan kurang dari itu ketika kondisinya

   (a != 0 && b != 0)

Di mana setiap elemen dibandingkan dengan 0 dan dievaluasi. Makanya waktu yang dibutuhkan lebih sedikit. Tetapi saya percaya bahwa kondisi kedua mungkin memberi Anda solusi yang lebih akurat.

Anda menggunakan data input acak yang membuat cabang tidak bisa diprediksi. Dalam praktiknya, cabang seringkali (~ 90%) dapat diprediksi sehingga dalam kode nyata, kode branchful cenderung lebih cepat.

Itu kata. Saya tidak melihat bagaimana a*b != 0bisa lebih cepat daripada (a|b) != 0. Multiplikasi bilangan bulat umumnya lebih mahal daripada bitwise OR. Tetapi hal-hal seperti ini terkadang menjadi aneh. Lihat misalnya contoh "Contoh 7: Kompleksitas perangkat keras" dari Galeri Efek Cache Prosesor .