Mengapa jika (variable1% variable2 == 0) tidak efisien?

Saya baru mengenal java, dan menjalankan beberapa kode tadi malam, dan ini benar-benar mengganggu saya. Saya sedang membangun program sederhana untuk menampilkan setiap output X dalam loop untuk, dan saya melihat penurunan besar-besaran dalam kinerja, ketika saya menggunakan modulus sebagai variable % variablevs variable % 5000atau yang lainnya. Dapatkah seseorang menjelaskan kepada saya mengapa ini dan apa yang menyebabkannya? Jadi saya bisa lebih baik ...

Ini kode "efisien" (maaf jika saya salah sintaks, saya tidak ada di komputer dengan kode itu sekarang)

long startNum = 0;
long stopNum = 1000000000L;

for (long i = startNum; i <= stopNum; i++){
    if (i % 50000 == 0) {
        System.out.println(i);
    }
}

Ini adalah "kode tidak efisien"

long startNum = 0;
long stopNum = 1000000000L;
long progressCheck = 50000;

for (long i = startNum; i <= stopNum; i++){
    if (i % progressCheck == 0) {
        System.out.println(i);
    }
}

Pikiran Anda, saya punya variabel tanggal untuk mengukur perbedaan, dan setelah itu menjadi cukup lama, yang pertama mengambil 50 ms sementara yang lain mengambil 12 detik atau sesuatu seperti itu. Anda mungkin harus menambah stopNumatau mengurangi progressCheckjika PC Anda lebih efisien daripada milik saya atau tidak.

Saya mencari pertanyaan ini di web, tetapi saya tidak dapat menemukan jawaban, mungkin saya hanya tidak menanyakannya dengan benar.

EDIT: Saya tidak berharap pertanyaan saya begitu populer, saya menghargai semua jawaban. Saya melakukan benchmark pada setiap setengah waktu yang diambil, dan kode yang tidak efisien memakan waktu lebih lama, 1/4 detik vs 10 detik. Memang mereka menggunakan println, tetapi mereka berdua melakukan jumlah yang sama, jadi saya tidak akan membayangkan itu akan banyak condong, terutama karena perbedaannya berulang. Adapun jawabannya, karena saya baru di Jawa, saya akan membiarkan suara memutuskan untuk sekarang jawaban mana yang terbaik. Saya akan mencoba mengambilnya pada hari Rabu.

EDIT2: Saya akan membuat tes lain malam ini, di mana alih-alih modulus, itu hanya menambah variabel, dan ketika mencapai progressCheck, itu akan melakukan satu, dan kemudian mengatur ulang variabel itu ke 0. untuk opsi ke-3.

EDIT3.5:

Saya menggunakan kode ini, dan di bawah ini saya akan menunjukkan hasil saya .. Terima kasih SEMUA untuk bantuan yang luar biasa! Saya juga mencoba membandingkan nilai pendek dari panjang ke 0, jadi semua cek baru saya terjadi "65536" kali sehingga sama dengan pengulangan.

public class Main {


    public static void main(String[] args) {

        long startNum = 0;
        long stopNum = 1000000000L;
        long progressCheck = 65536;
        final long finalProgressCheck = 50000;
        long date;

        // using a fixed value
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if (i % 65536 == 0) {
                System.out.println(i);
            }
        }
        long final1 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        //using a variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % progressCheck == 0) {
                System.out.println(i);
            }
        }
        long final2 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();

        // using a final declared variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % finalProgressCheck == 0) {
                System.out.println(i);
            }
        }
        long final3 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        // using increments to determine progressCheck
        int increment = 0;
        for (long i = startNum; i <= stopNum; i++) {
            if (increment == 65536) {
                System.out.println(i);
                increment = 0;
            }
            increment++;

        }

        //using a short conversion
        long final4 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if ((short)i == 0) {
                System.out.println(i);
            }
        }
        long final5 = System.currentTimeMillis() - date;

                System.out.println(
                "\nfixed = " + final1 + " ms " + "\nvariable = " + final2 + " ms " + "\nfinal variable = " + final3 + " ms " + "\nincrement = " + final4 + " ms" + "\nShort Conversion = " + final5 + " ms");
    }
}

Hasil:

• tetap = 874 ms (biasanya sekitar 1000 ms, tetapi lebih cepat karena kekuatannya 2)
• variabel = 8590 ms
• variabel akhir = 1944 ms (Apakah ~ 1000ms saat menggunakan 50.000)
• kenaikan = 1904 ms
• Konversi Pendek = 679 ms

Tidak cukup mengejutkan, karena kurangnya pembagian, Konversi Pendek 23% lebih cepat daripada cara "cepat". Ini menarik untuk dicatat. Jika Anda perlu menunjukkan atau membandingkan sesuatu setiap 256 kali (atau sekitar sana) Anda dapat melakukan ini, dan gunakan

if ((byte)integer == 0) {'Perform progress check code here'}

SATU FINAL MENARIK CATATAN, menggunakan modulus pada "Final menyatakan Variabel" dengan 65536 (bukan angka cantik) adalah setengah kecepatan (lebih lambat) dari nilai tetap. Di mana sebelumnya, benchmarking mendekati kecepatan yang sama.

Anda mengukur rintisan OSR (on-stack replacement) .

OSR stub adalah versi khusus dari metode yang dikompilasi yang ditujukan khusus untuk mentransfer eksekusi dari mode yang ditafsirkan ke kode yang dikompilasi ketika metode sedang berjalan.

Rintisan OSR tidak seoptimal metode biasa, karena mereka membutuhkan tata letak bingkai yang kompatibel dengan kerangka yang ditafsirkan. Saya sudah menunjukkan ini dalam jawaban berikut: 1 , 2 , 3 .

Hal serupa juga terjadi di sini. Sementara "kode tidak efisien" menjalankan loop panjang, metode ini dikompilasi khusus untuk penggantian on-stack tepat di dalam loop. Status ditransfer dari frame yang ditafsirkan ke metode yang dikompilasi OSR, dan status ini termasuk progressCheckvariabel lokal. Pada titik ini JIT tidak dapat menggantikan variabel dengan konstanta, dan dengan demikian tidak dapat menerapkan optimasi tertentu seperti pengurangan kekuatan .

Secara khusus ini berarti JIT tidak menggantikan pembagian integer dengan perkalian . (Lihat Mengapa GCC menggunakan perkalian dengan angka ganjil dalam mengimplementasikan divisi integer? Untuk trik asm dari kompiler yang lebih dulu, ketika nilainya adalah konstanta waktu kompilasi setelah inlining / propagasi konstan, jika optimasi tersebut diaktifkan . Sebuah hak literal integer dalam %ekspresi juga akan dioptimalkan oleh gcc -O0, mirip dengan di sini di mana itu dioptimalkan oleh JITer bahkan dalam rintisan OSR.)

Namun, jika Anda menjalankan metode yang sama beberapa kali, yang kedua dan selanjutnya akan menjalankan kode biasa (non-OSR), yang sepenuhnya dioptimalkan. Berikut ini adalah tolok ukur untuk membuktikan teorinya ( menggunakan JMH ):

@State(Scope.Benchmark)
public class Div {

    @Benchmark
    public void divConst(Blackhole blackhole) {
        long startNum = 0;
        long stopNum = 100000000L;

        for (long i = startNum; i <= stopNum; i++) {
            if (i % 50000 == 0) {
                blackhole.consume(i);
            }
        }
    }

    @Benchmark
    public void divVar(Blackhole blackhole) {
        long startNum = 0;
        long stopNum = 100000000L;
        long progressCheck = 50000;

        for (long i = startNum; i <= stopNum; i++) {
            if (i % progressCheck == 0) {
                blackhole.consume(i);
            }
        }
    }
}

Dan hasilnya:

# Benchmark: bench.Div.divConst

# Run progress: 0,00% complete, ETA 00:00:16
# Fork: 1 of 1
# Warmup Iteration   1: 126,967 ms/op
# Warmup Iteration   2: 105,660 ms/op
# Warmup Iteration   3: 106,205 ms/op
Iteration   1: 105,620 ms/op
Iteration   2: 105,789 ms/op
Iteration   3: 105,915 ms/op
Iteration   4: 105,629 ms/op
Iteration   5: 105,632 ms/op


# Benchmark: bench.Div.divVar

# Run progress: 50,00% complete, ETA 00:00:09
# Fork: 1 of 1
# Warmup Iteration   1: 844,708 ms/op          <-- much slower!
# Warmup Iteration   2: 105,893 ms/op          <-- as fast as divConst
# Warmup Iteration   3: 105,601 ms/op
Iteration   1: 105,570 ms/op
Iteration   2: 105,475 ms/op
Iteration   3: 105,702 ms/op
Iteration   4: 105,535 ms/op
Iteration   5: 105,766 ms/op

Iterasi pertama divVarmemang jauh lebih lambat, karena rintisan OSR yang dikompilasi secara tidak efisien. Tetapi segera setelah metode dijalankan kembali dari awal, versi baru yang tidak dibatasi dijalankan yang memanfaatkan semua optimisasi kompiler yang tersedia.

Sebagai tindak lanjut dari komentar @ phuclv , saya memeriksa kode yang dihasilkan oleh JIT ¹ , hasilnya adalah sebagai berikut:

untuk variable % 5000(pembagian dengan konstan):

mov     rax,29f16b11c6d1e109h
imul    rbx
mov     r10,rbx
sar     r10,3fh
sar     rdx,0dh
sub     rdx,r10
imul    r10,rdx,0c350h    ; <-- imul
mov     r11,rbx
sub     r11,r10
test    r11,r11
jne     1d707ad14a0h

untuk variable % variable:

mov     rax,r14
mov     rdx,8000000000000000h
cmp     rax,rdx
jne     22ccce218edh
xor     edx,edx
cmp     rbx,0ffffffffffffffffh
je      22ccce218f2h
cqo
idiv    rax,rbx           ; <-- idiv
test    rdx,rdx
jne     22ccce218c0h

Karena pembagian selalu membutuhkan waktu lebih lama daripada perkalian, snipet kode terakhir kurang berkinerja.

Versi Java:

java version "11" 2018-09-25
Java(TM) SE Runtime Environment 18.9 (build 11+28)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

^{1 - Opsi VM yang digunakan: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main}

Seperti yang telah dicatat orang lain, operasi modulus umum memerlukan pembagian yang harus dilakukan. Dalam beberapa kasus, divisi dapat diganti (oleh kompiler) dengan perkalian. Namun keduanya bisa lambat dibandingkan dengan penambahan / pengurangan. Oleh karena itu, kinerja terbaik dapat diharapkan oleh sesuatu di sepanjang garis ini:

long progressCheck = 50000;

long counter = progressCheck;

for (long i = startNum; i <= stopNum; i++){
    if (--counter == 0) {
        System.out.println(i);
        counter = progressCheck;
    }
}

(Sebagai upaya minor optmiziation kami menggunakan pra-pengurangan down-counter di sini karena pada banyak arsitektur membandingkan 0segera setelah operasi aritmatika biaya tepat 0 instruksi / siklus CPU karena bendera ALU sudah ditetapkan dengan tepat oleh operasi sebelumnya. Pengoptimalan yang layak kompiler akan, bagaimanapun, melakukan optimasi itu secara otomatis walaupun Anda menulis if (counter++ == 50000) { ... counter = 0; }.)

Perhatikan bahwa seringkali Anda tidak benar-benar menginginkan / memerlukan modulus, karena Anda tahu bahwa penghitung putaran Anda (i ) atau apa pun yang hanya bertambah 1, dan Anda benar-benar tidak peduli dengan sisa aktual yang akan diberikan modulus kepada Anda, lihat saja jika penghitung yang bertambah satu demi satu bernilai.

'Trik' lain adalah menggunakan kekuatan / nilai dua batas, misalnya progressCheck = 1024;. Modulus kekuatan dua dapat dengan cepat dihitung melalui bitwise and, yaitu if ( (i & (1024-1)) == 0 ) {...}. Ini harus cukup cepat juga, dan mungkin pada beberapa arsitektur mengungguli eksplisit di counteratas.

Saya juga terkejut dengan melihat kinerja kode di atas. Ini semua tentang waktu yang diambil oleh kompiler untuk menjalankan program sesuai dengan variabel yang dideklarasikan. Dalam contoh kedua (tidak efisien):

for (long i = startNum; i <= stopNum; i++) {
    if (i % progressCheck == 0) {
        System.out.println(i)
    }
}

Anda sedang melakukan operasi modulus antara dua variabel. Di sini, kompiler harus memeriksa nilai stopNumdanprogressCheck untuk pergi ke blok memori spesifik yang terletak untuk variabel-variabel ini setiap kali setelah setiap iterasi karena merupakan variabel dan nilainya mungkin berubah.

Itu sebabnya setelah setiap kompilasi iterasi pergi ke lokasi memori untuk memeriksa nilai terbaru dari variabel. Oleh karena itu pada waktu kompilasi, kompiler tidak dapat membuat kode byte yang efisien.

Pada contoh kode pertama, Anda melakukan operator modulus antara variabel dan nilai numerik konstan yang tidak akan berubah dalam eksekusi dan kompiler tidak perlu memeriksa nilai nilai numerik itu dari lokasi memori. Itu sebabnya kompiler dapat membuat kode byte yang efisien. Jika Anda mendeklarasikan progressChecksebagai finalatau sebagai final staticvariabel, maka pada saat run-time / compile-time compiler tahu bahwa itu adalah variabel final dan nilainya tidak akan berubah, maka compiler ganti dengan progressCheckdengan 50000dalam kode:

for (long i = startNum; i <= stopNum; i++) {
    if (i % 50000== 0) {
        System.out.println(i)
    }
}

Sekarang Anda dapat melihat bahwa kode ini juga terlihat seperti contoh kode pertama (efisien). Kinerja kode pertama dan seperti yang kami sebutkan di atas kedua kode akan bekerja secara efisien. Tidak akan ada banyak perbedaan dalam waktu eksekusi dari salah satu contoh kode.