Pertanyaan Apakah

Saya sedang membaca buku di mana penulis mengatakan itu if( a < 901 ) lebih cepat daripada if( a <= 900 ).

Tidak persis seperti dalam contoh sederhana ini, tetapi ada sedikit perubahan kinerja pada kode kompleks lingkaran. Saya kira ini harus melakukan sesuatu dengan kode mesin yang dihasilkan dalam hal itu bahkan benar.


1372
2017-08-27 02:10


asal


Jawaban:


Tidak, itu tidak akan lebih cepat pada kebanyakan arsitektur. Anda tidak menentukan, tetapi pada x86, semua perbandingan integral biasanya akan diterapkan dalam dua instruksi mesin:

  • SEBUAH test atau cmp instruksi, yang mengatur EFLAGS
  • Dan a Jcc (lompat) instruksi, tergantung pada tipe perbandingan (dan tata letak kode):
    • jne - Melompat jika tidak sama -> ZF = 0
    • jz - Langsung jika nol (sama) -> ZF = 1
    • jg - Melompat jika lebih besar -> ZF = 0 and SF = OF
    • (dll ...)

Contoh (Diedit untuk singkatnya) Disusun dengan $ gcc -m32 -S -masm=intel test.c

    if (a < b) {
        // Do something 1
    }

Berkompilasi ke:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jge     .L2                          ; jump if a is >= b
    ; Do something 1
.L2:

Dan

    if (a <= b) {
        // Do something 2
    }

Berkompilasi ke:

    mov     eax, DWORD PTR [esp+24]      ; a
    cmp     eax, DWORD PTR [esp+28]      ; b
    jg      .L5                          ; jump if a is > b
    ; Do something 2
.L5:

Jadi satu-satunya perbedaan antara keduanya adalah a jg versus a jge petunjuk. Keduanya akan mengambil jumlah waktu yang sama.


Saya ingin menyampaikan komentar yang tidak mengindikasikan bahwa instruksi lompatan yang berbeda mengambil jumlah waktu yang sama. Yang ini agak sulit untuk dijawab, tetapi inilah yang bisa saya berikan: Di Referensi Instruksi Intel Instruction, mereka semua dikelompokkan bersama di bawah satu instruksi umum, Jcc (Langsung jika kondisi terpenuhi). Pengelompokan yang sama dibuat bersama di bawah Manual Referensi Optimasi, di Appendix C. Latency dan Throughput.

Latensi - Jumlah siklus jam yang diperlukan untuk   inti eksekusi untuk menyelesaikan eksekusi semua μops yang terbentuk   sebuah instruksi.

Throughput - Jumlah clock cycle yang diperlukan   tunggu sebelum port masalah bebas untuk menerima instruksi yang sama   lagi. Untuk banyak instruksi, throughput instruksi bisa   secara signifikan kurang dari latensinya

Nilai untuk Jcc adalah:

      Latency   Throughput
Jcc     N/A        0.5

dengan catatan kaki berikut Jcc:

7) Pemilihan instruksi melompat bersyarat harus didasarkan pada rekomendasi bagian Bagian 3.4.1, "Optimalisasi Prakiraan Cabang," untuk meningkatkan prediktabilitas cabang. Ketika cabang diprediksi berhasil, latensi jcc secara efektif nol.

Jadi, tidak ada dokumen Intel yang pernah memperlakukannya Jcc instruksi yang berbeda dari yang lain.

Jika seseorang berpikir tentang sirkuit aktual yang digunakan untuk mengimplementasikan instruksi, dapat diasumsikan bahwa akan ada gerbang AND / OR sederhana pada bit yang berbeda di EFLAGS, untuk menentukan apakah kondisi terpenuhi. Maka, tidak ada alasan bahwa instruksi pengujian dua bit harus mengambil lebih banyak atau lebih sedikit waktu dari satu pengujian hanya satu (Mengabaikan perlambatan propagasi gerbang, yang jauh lebih sedikit daripada periode jam.)


Edit: Titik Mengambang

Ini berlaku untuk x87 floating point juga: (Cukup banyak kode yang sama seperti di atas, tetapi dengan double dari pada int.)

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS
        fstp    st(0)
        seta    al                     ; Set al if above (CF=0 and ZF=0).
        test    al, al
        je      .L2
        ; Do something 1
.L2:

        fld     QWORD PTR [esp+32]
        fld     QWORD PTR [esp+40]
        fucomip st, st(1)              ; (same thing as above)
        fstp    st(0)
        setae   al                     ; Set al if above or equal (CF=0).
        test    al, al
        je      .L5
        ; Do something 2
.L5:
        leave
        ret

1570
2017-08-27 02:13



Secara historis (kita berbicara tahun 1980-an dan awal 1990-an), ada beberapa arsitektur di mana ini benar. Masalah root adalah bahwa perbandingan integer secara inheren diimplementasikan melalui pengurangan bilangan bulat. Ini menimbulkan kasus-kasus berikut.

Comparison     Subtraction
----------     -----------
A < B      --> A - B < 0
A = B      --> A - B = 0
A > B      --> A - B > 0

Sekarang, kapan A < B pengurangan harus meminjam bit-tinggi agar pengurangannya menjadi benar, sama seperti Anda membawa dan meminjam ketika menambahkan dan mengurangkan dengan tangan. Bit "pinjaman" ini biasanya disebut sebagai membawa sedikit dan akan diuji dengan instruksi cabang. Bit kedua disebut sedikit nol akan ditetapkan jika pengurangan itu identik nol yang menyiratkan kesetaraan.

Biasanya ada setidaknya dua instruksi cabang bersyarat, satu untuk bercabang di carry bit dan satu pada bit nol.

Sekarang, untuk mendapatkan inti dari masalah ini, mari kita memperluas tabel sebelumnya untuk memasukkan hasil carry dan nol bit.

Comparison     Subtraction  Carry Bit  Zero Bit
----------     -----------  ---------  --------
A < B      --> A - B < 0    0          0
A = B      --> A - B = 0    1          1
A > B      --> A - B > 0    1          0

Jadi, menerapkan cabang untuk A < B dapat dilakukan dalam satu instruksi, karena membawa sedikit jelas hanya dalam hal ini,, yaitu,

;; Implementation of "if (A < B) goto address;"
cmp  A, B          ;; compare A to B
bcz  address       ;; Branch if Carry is Zero to the new address

Namun, jika kita ingin melakukan perbandingan yang kurang dari atau sama, kita perlu melakukan pemeriksaan tambahan terhadap bendera nol untuk menangkap kasus kesetaraan.

;; Implementation of "if (A <= B) goto address;"
cmp A, B           ;; compare A to B
bcz address        ;; branch if A < B
bzs address        ;; also, Branch if the Zero bit is Set

Jadi, pada beberapa mesin, menggunakan perbandingan "kurang dari" mungkin menyimpan satu instruksi mesin. Ini relevan di era kecepatan prosesor sub-megahertz dan rasio kecepatan CPU-ke-memori 1: 1, tetapi hampir tidak relevan hari ini.


555
2017-08-27 17:53



Dengan asumsi kita berbicara tentang jenis bilangan bulat internal, tidak ada cara yang mungkin orang bisa lebih cepat daripada yang lain. Mereka jelas identik secara semantis. Mereka berdua meminta compiler untuk melakukan hal yang persis sama. Hanya compiler yang sangat rusak akan menghasilkan kode inferior untuk salah satunya.

Jika ada beberapa platform di mana < lebih cepat dari <= untuk tipe integer sederhana, kompilator harus selalu mengubah <= untuk < untuk konstanta. Setiap kompilator yang tidak hanya menjadi penyusun yang buruk (untuk platform itu).


85
2017-08-27 02:31



Saya melihat bahwa tidak ada yang lebih cepat. Compiler menghasilkan kode mesin yang sama di setiap kondisi dengan nilai yang berbeda.

if(a < 901)
cmpl  $900, -4(%rbp)
jg .L2

if(a <=901)
cmpl  $901, -4(%rbp)
jg .L3

Contoh saya if adalah dari GCC pada platform x86_64 di Linux.

Penulis kompilator adalah orang-orang yang cukup pintar, dan mereka memikirkan hal-hal ini dan banyak lainnya yang sebagian besar dari kita menerima begitu saja.

Saya perhatikan bahwa jika tidak konstan, maka kode mesin yang sama dihasilkan dalam kedua kasus.

int b;
if(a < b)
cmpl  -4(%rbp), %eax
jge   .L2

if(a <=b)
cmpl  -4(%rbp), %eax
jg .L3

67
2017-08-27 02:16



Untuk kode titik mengambang, <= perbandingan mungkin memang lebih lambat (oleh satu instruksi) bahkan pada arsitektur modern. Inilah fungsi pertama:

int compare_strict(double a, double b) { return a < b; }

Pada PowerPC, pertama ini melakukan perbandingan titik apung (yang diperbarui cr, register kondisi), kemudian memindahkan register kondisi ke GPR, menggeser "dibandingkan kurang dari" sedikit ke tempatnya, dan kemudian kembali. Dibutuhkan empat instruksi.

Sekarang perhatikan fungsi ini sebagai gantinya:

int compare_loose(double a, double b) { return a <= b; }

Ini membutuhkan pekerjaan yang sama dengan compare_strict di atas, tetapi sekarang ada dua bit yang menarik: "kurang dari" dan "sama dengan." Ini membutuhkan instruksi tambahan (cror- Condition register bitwise OR) untuk menggabungkan dua bit ini menjadi satu. Begitu compare_loose membutuhkan lima instruksi, sementara compare_strict membutuhkan empat.

Anda mungkin berpikir bahwa kompiler dapat mengoptimalkan fungsi kedua seperti:

int compare_loose(double a, double b) { return ! (a > b); }

Namun ini akan salah menangani NaNs. NaN1 <= NaN2 dan NaN1 > NaN2 perlu keduanya mengevaluasi ke salah.


48
2017-08-27 18:32



Mungkin penulis buku tanpa nama itu telah membaca itu a > 0 berjalan lebih cepat dari a >= 1 dan berpikir itu benar secara universal.

Tetapi itu karena a 0 terlibat (karena CMP dapat, tergantung pada arsitektur, diganti mis. dengan OR) dan bukan karena <.


34
2017-08-27 13:05



Paling tidak, jika ini benar, kompiler dapat dengan mudah mengoptimalkan <= b ke! (A> b), dan bahkan jika perbandingan itu sendiri sebenarnya lebih lambat, dengan semua tetapi kompilator yang paling naif Anda tidak akan melihat perbedaan .


29
2017-08-27 09:23



Mereka memiliki kecepatan yang sama. Mungkin dalam beberapa arsitektur khusus apa yang dikatakannya benar, tetapi di keluarga x86 setidaknya saya tahu mereka sama. Karena untuk melakukan hal ini CPU akan melakukan substraksi (a - b) dan kemudian memeriksa bendera-bendera register bendera. Dua bit register itu disebut ZF (Flag nol) dan SF (tanda bendera), dan itu dilakukan dalam satu siklus, karena akan melakukannya dengan satu operasi mask.


15
2017-08-27 08:25



Ini akan sangat tergantung pada arsitektur yang mendasari bahwa C dikompilasi. Beberapa prosesor dan arsitektur mungkin memiliki instruksi eksplisit yang sama dengan, atau kurang dari dan sama dengan, yang dijalankan dalam jumlah siklus yang berbeda.

Itu akan sangat tidak biasa, karena kompiler bisa mengatasinya, membuatnya tidak relevan.


13
2017-08-27 02:15



Jawaban lainnya terkonsentrasi pada x86 arsitektur, dan saya tidak tahu LENGAN arsitektur (yang tampaknya contoh assembler Anda) cukup baik untuk berkomentar secara khusus pada kode yang dihasilkan, tetapi ini adalah contoh dari a optimasi mikro yang aku s sangat spesifik arsitektur, dan kemungkinan akan menjadi anti-optimasi karena itu menjadi optimasi.

Dengan demikian, saya akan menyarankan bahwa ini semacam optimasi mikro adalah contoh dari kultus kargo pemrograman daripada praktik rekayasa perangkat lunak terbaik.

Mungkin ada beberapa arsitektur di mana ini merupakan pengoptimalan, tetapi saya tahu setidaknya ada satu arsitektur yang sebaliknya mungkin benar. Yang terhormat Transputer arsitektur hanya memiliki instruksi kode mesin untuk sama dengan dan lebih dari atau sama dengan, jadi semua perbandingan harus dibangun dari primitif ini.

Bahkan kemudian, dalam hampir semua kasus, kompiler dapat memerintahkan instruksi evaluasi sedemikian rupa sehingga dalam praktiknya, tidak ada perbandingan yang memiliki kelebihan dibanding yang lain. Namun, yang terburuk mungkin perlu menambahkan instruksi balik (REV) untuk menukar dua item teratas di operan stack. Ini adalah instruksi byte tunggal yang mengambil satu siklus untuk dijalankan, jadi memiliki biaya overhead terkecil yang mungkin.

Apakah atau tidak optimasi mikro seperti ini adalah sebuah pengoptimalan atau sebuah anti-optimasi tergantung pada arsitektur khusus yang Anda gunakan, jadi biasanya ide yang buruk untuk membiasakan diri menggunakan arsitektur mikro-optimasi tertentu, jika tidak Anda mungkin secara naluriah menggunakannya saat tidak tepat untuk melakukannya, dan sepertinya ini persis apa buku yang sedang Anda baca sedang menganjurkan.


10
2017-08-31 18:33



Anda seharusnya tidak dapat melihat perbedaan bahkan jika ada. Selain itu, dalam praktiknya, Anda harus melakukan tambahan a + 1 atau a - 1 untuk membuat kondisi berdiri kecuali Anda akan menggunakan beberapa konstanta sihir, yang merupakan praktik yang sangat buruk dengan segala cara.


6
2017-08-27 02:17