Lebih if( a < 901 )cepat dari if( a <= 900 ).

Tidak persis seperti pada contoh sederhana ini, tetapi ada sedikit perubahan kinerja pada kode kompleks loop. Saya kira ini harus melakukan sesuatu dengan kode mesin yang dihasilkan kalau-kalau itu benar.

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

• A testatau cmpinstruksi, yang mengaturEFLAGS
• Dan Jccinstruksi (lompatan) , tergantung pada jenis perbandingan (dan tata letak kode):
  • jne - Lompat jika tidak sama -> ZF = 0
  • jz - Lompat jika nol (sama) -> ZF = 1
  • jg - Lompat 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
    }

Kompilasi 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
    }

Kompilasi 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 instruksi jgversus jge. Keduanya akan mengambil jumlah waktu yang sama.

Saya ingin menyampaikan komentar bahwa tidak ada yang menunjukkan bahwa instruksi lompatan yang berbeda membutuhkan waktu yang sama. Yang ini agak sulit dijawab, tapi inilah yang bisa saya berikan: Dalam Referensi Set Instruksi Intel , mereka semua dikelompokkan bersama di bawah satu instruksi umum, Jcc(Lompat jika syarat terpenuhi). Pengelompokan yang sama dibuat bersama di bawah Manual Referensi Pengoptimalan , dalam Lampiran C. Latency dan Throughput.

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

Throughput - Jumlah siklus jam yang diperlukan untuk menunggu sebelum port masalah bebas untuk menerima instruksi yang sama lagi. Untuk banyak instruksi, throughput suatu instruksi dapat secara signifikan kurang dari latensi

Nilai untuk Jccadalah:

      Latency   Throughput
Jcc     N/A        0.5

dengan catatan kaki berikut Jcc:

7) Pemilihan instruksi lompat bersyarat harus didasarkan pada rekomendasi dari bagian 3.4.1, “Optimalisasi Prediksi Cabang,” untuk meningkatkan prediktabilitas cabang. Ketika cabang diprediksi berhasil, latensi jccefektif nol.

Jadi, tidak ada dalam dokumen Intel yang pernah memperlakukan satu Jccinstruksi secara berbeda dari yang lainnya.

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

Sunting: Floating Point

Ini berlaku untuk floating point x87 juga: (Hampir sama dengan kode di atas, tetapi dengan doublebukannya 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

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

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

Sekarang, ketika A < Bpengurangan harus meminjam bit tinggi agar pengurangan itu benar, sama seperti Anda membawa dan meminjam ketika menambah dan mengurangi dengan tangan. Bit "pinjaman" ini biasanya disebut sebagai bit carry dan akan diuji oleh instruksi cabang. Bit kedua yang disebut bit nol akan ditetapkan jika pengurangannya sama dengan nol yang menyiratkan kesetaraan.

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

Sekarang, untuk mendapatkan inti dari masalah ini, mari kita memperluas tabel sebelumnya untuk memasukkan carry dan hasil 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, mengimplementasikan cabang untuk A < Bdapat dilakukan dalam satu instruksi, karena carry bit hanya jelas 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

Tetapi, jika kita ingin melakukan perbandingan yang kurang dari atau sama, kita perlu melakukan pemeriksaan tambahan dari bendera nol untuk mengetahui 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 menghemat satu instruksi mesin . Ini relevan di era kecepatan prosesor sub-megahertz dan rasio kecepatan CPU-ke-memori 1: 1, tetapi saat ini hampir sama sekali tidak relevan.

Dengan asumsi kita sedang berbicara tentang tipe integer internal, tidak mungkin ada yang lebih cepat dari yang lain. Mereka jelas identik secara semantik. Mereka berdua meminta kompiler untuk melakukan hal yang persis sama. Hanya kompiler yang rusak parah akan menghasilkan kode yang lebih rendah untuk salah satunya.

Jika ada beberapa platform di mana <lebih cepat daripada <=untuk tipe integer sederhana, kompiler harus selalu dikonversi <=ke <untuk konstanta. Kompiler apa pun yang bukan hanya kompiler buruk (untuk platform itu).

Saya melihat bahwa tidak ada yang lebih cepat. Kompiler 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 ifadalah dari GCC pada platform x86_64 di Linux.

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

Saya perhatikan bahwa jika itu bukan konstanta, maka kode mesin yang sama dihasilkan di kedua kasus.

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

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

Untuk kode floating point, perbandingan <= mungkin memang lebih lambat (dengan 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 floating point (yang memperbarui cr, register kondisi), kemudian memindahkan register kondisi ke GPR, menggeser "dibandingkan kurang dari" bit ke tempatnya, dan kemudian kembali. Dibutuhkan empat instruksi.

Sekarang pertimbangkan fungsi ini sebagai gantinya:

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

Ini membutuhkan pekerjaan yang sama seperti di compare_strictatas, tetapi sekarang ada dua bagian yang menarik: "kurang dari" dan "sama dengan." Ini membutuhkan instruksi tambahan ( cror- register kondisi bitwise ATAU) untuk menggabungkan dua bit ini menjadi satu. Jadi compare_loosemembutuhkan lima instruksi, sedangkan compare_strictmembutuhkan empat.

Anda mungkin berpikir bahwa kompiler dapat mengoptimalkan fungsi kedua seperti:

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

Namun ini secara tidak benar akan menangani NaN. NaN1 <= NaN2dan NaN1 > NaN2perlu keduanya mengevaluasi ke false.

Mungkin penulis buku yang tidak disebutkan namanya itu telah membaca yang a > 0berjalan lebih cepat daripada a >= 1dan berpikir itu benar secara universal.

Tetapi itu karena a 0terlibat (karena CMPbisa, tergantung pada arsitektur, diganti misalnya dengan OR) dan bukan karena <.

Paling tidak, jika ini benar, sebuah kompiler dapat dengan sepele mengoptimalkan <= b to! (A> b), dan bahkan jika perbandingan itu sendiri lebih lambat, dengan semua kecuali kompiler yang paling naif Anda tidak akan melihat perbedaan .

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

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

Itu akan sangat tidak biasa, karena kompiler dapat bekerja di sekitarnya, membuatnya tidak relevan.

TL; DR jawab

Untuk sebagian besar kombinasi arsitektur, kompiler dan bahasa tidak akan lebih cepat.

Jawaban penuh

Jawaban lain telah berkonsentrasi pada x86 arsitektur, dan saya tidak tahu ARM arsitektur (yang tampaknya contoh assembler Anda untuk menjadi) cukup baik untuk berkomentar secara khusus mengenai kode yang dihasilkan, tapi ini adalah contoh dari mikro-optimasi yang adalah sangat arsitektur spesifik, dan kemungkinan menjadi anti-optimasi seperti halnya menjadi optimasi .

Karena itu, saya menyarankan bahwa optimasi mikro semacam ini adalah contoh pemrograman pemujaan kargo daripada praktik rekayasa perangkat lunak terbaik.

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

Bahkan kemudian, dalam hampir semua kasus, kompiler dapat memesan instruksi evaluasi sedemikian rupa sehingga dalam praktiknya, tidak ada perbandingan yang memiliki keunggulan dibandingkan yang lain. Kasus terburuk, mungkin perlu menambahkan instruksi terbalik (REV) untuk menukar dua item teratas pada tumpukan operan . Ini adalah instruksi byte tunggal yang membutuhkan siklus tunggal untuk dijalankan, sehingga memiliki overhead sekecil mungkin.

Apakah optimasi mikro seperti ini adalah optimasi atau anti-optimasi tergantung pada arsitektur spesifik yang Anda gunakan, sehingga biasanya merupakan ide yang buruk untuk membiasakan diri menggunakan arsitektur mikro optimasi tertentu, jika tidak, Anda mungkin secara naluriah gunakan satu ketika itu tidak pantas untuk melakukannya, dan sepertinya ini adalah apa buku yang Anda baca adalah advokasi.

Anda seharusnya tidak dapat melihat perbedaannya meskipun ada. Selain itu, dalam latihan, Anda harus melakukan tambahan a + 1atau a - 1membuat kondisi tetap kecuali Anda akan menggunakan beberapa konstanta sihir, yang merupakan praktik yang sangat buruk.

Anda bisa mengatakan bahwa baris itu benar di sebagian besar bahasa scripting, karena karakter tambahan menghasilkan pemrosesan kode yang sedikit lebih lambat. Namun, seperti yang ditunjukkan oleh jawaban teratas, seharusnya tidak berpengaruh pada C ++, dan apa pun yang dilakukan dengan bahasa scripting mungkin tidak terlalu mementingkan optimasi.

Ketika saya menulis jawaban ini, saya hanya melihat pertanyaan judul tentang <vs <= secara umum, bukan contoh spesifik konstan a < 901vs a <= 900. Banyak kompiler selalu mengecilkan besarnya konstanta dengan mengkonversi antara <dan <=, misalnya karena operan x86 langsung memiliki pengodean 1 byte yang lebih pendek untuk -128..127.

Untuk ARM dan terutama AArch64, kemampuan untuk menyandikan secara langsung tergantung pada kemampuan untuk memutar bidang sempit ke posisi apa pun dalam sebuah kata. Jadi cmp w0, #0x00f000akan dikodekan, sementara cmp w0, #0x00effffmungkin tidak. Jadi aturan make-it-lebih kecil untuk perbandingan vs konstanta waktu kompilasi tidak selalu berlaku untuk AArch64.

<vs. <= secara umum, termasuk untuk kondisi variabel runtime

Dalam bahasa rakitan pada kebanyakan mesin, perbandingan untuk <=memiliki biaya yang sama dengan perbandingan untuk <. Ini berlaku apakah Anda bercabang di atasnya, mendudukkannya untuk membuat integer 0/1, atau menggunakannya sebagai predikat untuk operasi pilih tanpa cabang (seperti x86 CMOV). Jawaban lain hanya menjawab bagian pertanyaan ini.

Tetapi pertanyaan ini adalah tentang operator C ++, input ke optimizer. Biasanya keduanya sama-sama efisien; saran dari buku ini terdengar sangat palsu karena kompiler selalu dapat mengubah perbandingan yang mereka terapkan dalam asm. Tetapi ada setidaknya satu pengecualian di mana menggunakan <=secara tidak sengaja dapat menciptakan sesuatu yang tidak dapat dioptimalkan oleh kompiler.

Sebagai kondisi loop, ada kasus-kasus di mana <=secara kualitatif berbeda dari <, ketika itu menghentikan kompiler membuktikan bahwa loop tidak terbatas. Ini dapat membuat perbedaan besar, menonaktifkan auto-vektorisasi.

Overflow unsigned didefinisikan dengan baik sebagai basis-2 membungkus, tidak seperti ditandatangani overflow (UB). Counter loop yang ditandatangani umumnya aman dari ini dengan kompiler yang dioptimalkan berdasarkan UB tidak masuk: tidak ada: ++i <= sizeakhirnya akan selalu salah. ( Apa Yang Harus Setiap C Programmer Ketahui Tentang Perilaku Tidak Terdefinisi )

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

Kompiler hanya dapat mengoptimalkan dengan cara yang menjaga perilaku (didefinisikan dan diamati secara hukum) dari sumber C ++ untuk semua nilai input yang mungkin , kecuali yang mengarah pada perilaku yang tidak terdefinisi.

(Sederhana juga i <= sizeakan menciptakan masalah, tetapi saya pikir menghitung batas atas adalah contoh yang lebih realistis untuk secara tidak sengaja memperkenalkan kemungkinan loop tak terbatas untuk input yang tidak Anda pedulikan tetapi yang harus dipertimbangkan oleh kompilator.)

Dalam hal ini, size=0mengarah ke upper_bound=UINT_MAX, dan i <= UINT_MAXselalu benar. Jadi loop ini tidak terbatas untuk size=0, dan kompiler harus menghargai bahwa meskipun Anda sebagai programmer mungkin tidak pernah bermaksud untuk lulus ukuran = 0. Jika kompiler dapat menguraikan fungsi ini ke dalam pemanggil di mana ia dapat membuktikan bahwa ukuran = 0 tidak mungkin, maka bagus, ia dapat mengoptimalkan seperti yang bisa dilakukan i < size.

Asm like if(!size) skip the loop; do{...}while(--size);adalah salah satu cara yang biasanya efisien untuk mengoptimalkan for( i<size )loop, jika nilai aktual itidak diperlukan di dalam loop ( Mengapa loop selalu dikompilasi menjadi gaya "do ... while" (tail jump)? ).

Tapi itu {} sementara tidak bisa tak terbatas: jika dimasukkan dengan size==0, kita mendapatkan 2 ^ n iterasi. ( Iterasi atas semua bilangan bulat tak bertanda dalam untuk loop C memungkinkan untuk mengekspresikan satu lingkaran atas semua bilangan bulat tak bertanda termasuk nol, tapi itu tidak mudah tanpa membawa bendera seperti di asm.)

Dengan kemungkinan loop counter sebagai kemungkinan, kompiler modern sering kali hanya "menyerah", dan tidak mengoptimalkan secara agresif.

Contoh: jumlah bilangan bulat dari 1 hingga n

Menggunakan i <= nkekalahan unsigned clang's pengakuan idiom yang mengoptimalkan sum(1 .. n)loop dengan bentuk tertutup berdasarkan n * (n+1) / 2rumus Gauss .

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

x86-64 asm dari clang7.0 dan gcc8.2 pada explorer compiler Godbolt

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

Tetapi untuk versi naif, kami hanya mendapatkan loop bodoh dari dentang.

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}

# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

GCC tidak menggunakan bentuk tertutup, jadi pilihan kondisi loop tidak terlalu menyakitkan ; itu secara otomatis melakukan vektorisasi dengan penambahan integer SIMD, menjalankan 4 inilai secara paralel dalam elemen register XMM.

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.

Ini juga memiliki loop skalar biasa yang saya pikir itu digunakan untuk sangat kecil n, dan / atau untuk kasus loop tak terbatas.

BTW, kedua loop ini membuang-buang instruksi (dan uop pada Sandybridge-family CPUs) pada overhead loop. sub eax,1/ jnzbukannya add eax,1/ cmp / jcc akan lebih efisien. 1 uop bukan 2 (setelah fusi makro dari sub / jcc atau cmp / jcc). Kode setelah kedua loop menulis EAX tanpa syarat, sehingga tidak menggunakan nilai akhir dari penghitung loop.

Hanya jika orang yang membuat komputer buruk dengan logika boolean. Seharusnya tidak begitu.

Setiap perbandingan ( >= <= > <) dapat dilakukan dalam kecepatan yang sama.

Apa setiap perbandingan adalah, hanya pengurangan (perbedaan) dan melihat apakah itu positif / negatif.
(Jika msbdiatur, jumlahnya negatif)

Bagaimana cara mengeceknya a >= b? Sub a-b >= 0Periksa apakah a-bpositif.
Bagaimana cara mengeceknya a <= b? Sub 0 <= b-aPeriksa apakah b-apositif.
Bagaimana cara mengeceknya a < b? Sub a-b < 0Periksa apakah a-bnegatif.
Bagaimana cara mengeceknya a > b? Sub 0 > b-aPeriksa apakah b-anegatif.

Sederhananya, komputer bisa melakukan ini di bawah tenda untuk operasi yang diberikan:

a >= b== msb(a-b)==0
a <= b== msb(b-a)==0
a > b== msb(b-a)==1
a < b==msb(a-b)==1

dan tentu saja komputer tidak perlu melakukan ==0atau ==1salah satunya.
untuk ==0itu bisa saja membalikkan msbdari rangkaian.

Bagaimanapun, mereka pasti tidak a >= bakan dihitung sebagai a>b || a==blol