Ketika saya menguji perbedaan waktu antara pemindahan dan pengali dalam C, tidak ada perbedaan. Mengapa?

Saya telah diajarkan bahwa pergeseran dalam biner jauh lebih efisien daripada mengalikannya dengan 2 ^ k. Jadi saya ingin bereksperimen, dan saya menggunakan kode berikut untuk menguji ini:

#include <time.h>
#include <stdio.h>

int main() {
    clock_t launch = clock();
    int test = 0x01;
    int runs;

    //simple loop that oscillates between int 1 and int 2
    for (runs = 0; runs < 100000000; runs++) {


    // I first compiled + ran it a few times with this:
    test *= 2;

    // then I recompiled + ran it a few times with:
    test <<= 1;

    // set back to 1 each time
    test >>= 1;
    }

    clock_t done = clock();
    double diff = (done - launch);
    printf("%f\n",diff);
}

Untuk kedua versi, hasil cetakannya sekitar 440000, memberi atau menerima 10.000. Tidak ada (secara visual, setidaknya) perbedaan yang signifikan antara keluaran kedua versi. Jadi pertanyaan saya adalah, apakah ada yang salah dengan metodologi saya? Haruskah ada perbedaan visual? Apakah ini ada hubungannya dengan arsitektur komputer saya, kompiler, atau sesuatu yang lain?

Seperti yang dikatakan dalam jawaban lain, sebagian besar kompiler akan secara otomatis mengoptimalkan perkalian yang harus dilakukan dengan bitshifts.

Ini adalah aturan yang sangat umum ketika mengoptimalkan: Kebanyakan 'optimasi' sebenarnya akan menyesatkan kompilasi tentang apa yang sebenarnya Anda maksudkan, dan bahkan mungkin mengurangi kinerja.

Hanya optimalkan ketika Anda melihat masalah kinerja dan mengukur apa masalahnya. (dan kebanyakan kode yang kita tulis tidak sering dieksekusi, jadi kita tidak perlu repot)

Kelemahan besar untuk mengoptimalkan adalah bahwa kode 'yang dioptimalkan' seringkali jauh lebih mudah dibaca. Jadi dalam kasus Anda, selalu lakukan penggandaan saat Anda ingin menggandakan. Dan lakukan bit shifting saat Anda ingin memindahkan bit.

Kompiler mengenali konstanta dan mengonversi multiplikasi ke shift yang sesuai.

Apakah perpindahan lebih cepat daripada multiplikasi tergantung pada arsitektur CPU Anda. Kembali pada hari-hari Pentium dan sebelumnya, pergeseran sering kali lebih cepat daripada perkalian, tergantung pada jumlah 1 bit di multiplicand Anda. Misalnya, jika multiplicand Anda adalah 320, itu 101000000, dua bit.

a *= 320;               // Slower
a = (a<<7) + (a<<9);    // Faster

Tetapi jika Anda memiliki lebih dari dua bit ...

a *= 324;                        // About same speed
a = (a<<2) + (a<<7) + (a<<9);    // About same speed

a *= 340;                                 // Faster
a = (a<<2) + (a<<4) + (a<<7) + (a<<9);    // Slower

Pada mikrokontroler kecil seperti PIC18 dengan siklus tunggal, tetapi tidak ada barel shifter , perkalian lebih cepat jika Anda menggeser lebih dari 1 bit.

a  *= 2;   // Exactly the same speed
a <<= 1;   // Exactly the same speed

a  *= 4;   // Faster
a <<= 2;   // Slower

Perhatikan bahwa itulah kebalikan dari apa yang berlaku pada CPU Intel yang lebih lama.

Tapi itu masih tidak sesederhana itu. Jika saya ingat dengan benar, karena arsitektur Superscalar-nya, sebuah Pentium dapat memproses satu instruksi perkalian atau dua instruksi shift secara bersamaan (selama keduanya tidak saling bergantung). Ini berarti bahwa jika Anda ingin mengalikan dua variabel dengan kekuatan 2, maka menggeser mungkin lebih baik.

a  *= 4;   // 
b  *= 4;   // 

a <<= 2;   // Both lines execute in a single cycle
b <<= 2;   // 

Anda memiliki beberapa masalah dengan program pengujian Anda.

Pertama, Anda sebenarnya tidak menggunakan nilai test. Tidak ada cara, dalam standar C, bahwa nilai testpenting. Pengoptimal adalah ini sepenuhnya gratis untuk menghapusnya. Setelah dihapus, loop Anda sebenarnya kosong. Satu-satunya efek yang terlihat adalah mengatur runs = 100000000, tetapiruns juga tidak digunakan. Jadi pengoptimal dapat (dan harus!) Menghapus seluruh loop. Perbaikan mudah: juga mencetak nilai yang dihitung. Perhatikan bahwa pengoptimal yang cukup ditentukan masih dapat mengoptimalkan pengulangan (bergantung sepenuhnya pada konstanta yang diketahui pada waktu kompilasi).

Kedua, Anda melakukan dua operasi yang saling membatalkan. Pengoptimal diizinkan untuk memperhatikan hal ini dan membatalkannya . Sekali lagi meninggalkan loop kosong, dan dihapus. Yang ini benar-benar sulit untuk diperbaiki. Anda dapat beralih ke unsigned int(jadi overflow bukan perilaku yang tidak terdefinisi), tetapi tentu saja hanya menghasilkan 0. Dan hal-hal sederhana (seperti, katakanlah, test += 1) cukup mudah bagi pengoptimal untuk mencari tahu, dan itu terjadi.

Akhirnya, Anda berasumsi bahwa test *= 2sebenarnya akan dikompilasi ke multiply. Itu optimasi yang sangat sederhana; jika bitshift lebih cepat, pengoptimal akan menggunakannya sebagai gantinya. Untuk menyiasatinya, Anda harus menggunakan sesuatu seperti inline perakitan khusus implementasi.

Atau, saya kira, cukup periksa lembar data mikroprosesor Anda untuk melihat mana yang lebih cepat.

Ketika saya memeriksa hasil perakitan dari mengkompilasi program Anda dengan gcc -S -O3menggunakan versi 4.9, optimizer benar-benar melihat setiap variasi sederhana di atas, dan beberapa lainnya. Dalam semua kasus, itu menghapus loop (memberikan konstanta ke test), satu-satunya yang tersisa adalah panggilan untuk clock(), konversi / kurangi, dan printf.

Saya pikir akan lebih membantu bagi si penanya untuk memiliki jawaban yang lebih berbeda, karena saya melihat beberapa asumsi yang tidak diteliti dalam pertanyaan dan dalam beberapa jawaban atau komentar.

Runtime relatif yang dihasilkan dari pergeseran dan perkalian tidak ada hubungannya dengan C. Ketika saya mengatakan C, saya tidak bermaksud contoh dari implementasi spesifik, seperti itu atau itu versi GCC, tetapi bahasa. Saya tidak bermaksud mengambil iklan absurdum ini, tetapi menggunakan contoh ekstrem untuk ilustrasi: Anda dapat menerapkan kompiler C yang sepenuhnya memenuhi standar dan penggandaan membutuhkan waktu satu jam, sementara menggeser membutuhkan milidetik - atau sebaliknya. Saya tidak mengetahui adanya pembatasan kinerja seperti itu di C atau C ++.

Anda mungkin tidak peduli dengan teknis ini dalam berargumentasi. Niat Anda mungkin hanya untuk menguji kinerja relatif dari melakukan shift versus multiplikasi dan Anda memilih C, karena itu umumnya dianggap sebagai bahasa pemrograman tingkat rendah, sehingga orang dapat mengharapkan kode sumbernya untuk menerjemahkan ke dalam instruksi yang sesuai lebih langsung. Pertanyaan-pertanyaan semacam itu sangat umum dan saya pikir jawaban yang baik harus menunjukkan bahwa bahkan dalam C kode sumber Anda tidak diterjemahkan ke dalam instruksi secara langsung seperti yang Anda pikirkan dalam contoh yang diberikan. Saya telah memberi Anda beberapa hasil kompilasi di bawah ini.

Di sinilah komentar yang mempertanyakan kegunaan pengganti kesetaraan ini dalam perangkat lunak dunia nyata masuk. Anda dapat melihat beberapa di komentar untuk pertanyaan Anda, seperti yang dari Eric Lippert. Ini sejalan dengan reaksi yang biasanya Anda dapatkan dari insinyur yang lebih berpengalaman dalam menanggapi optimasi tersebut. Jika Anda menggunakan pergeseran biner dalam kode produksi sebagai alat selimut untuk mengalikan dan membagi, orang kemungkinan besar akan merasa ngeri pada kode Anda dan memiliki beberapa tingkat reaksi emosional ("Saya telah mendengar klaim tidak masuk akal yang dibuat tentang JavaScript demi Tuhan.") Untuk itu mungkin tidak masuk akal bagi programmer pemula, kecuali mereka lebih memahami alasan untuk reaksi tersebut.

Alasan-alasan tersebut terutama merupakan kombinasi dari penurunan keterbacaan dan kesia-siaan dari optimasi tersebut, karena Anda mungkin sudah mengetahui dengan membandingkan kinerja relatif mereka. Namun, saya tidak berpikir bahwa orang akan memiliki reaksi yang kuat jika penggantian shift untuk multiplikasi adalah satu-satunya contoh optimasi tersebut. Pertanyaan seperti milik Anda sering kali muncul dalam berbagai bentuk dan dalam berbagai konteks. Saya pikir apa yang benar-benar bereaksi oleh insinyur senior dengan sangat kuat, setidaknya saya miliki pada saat itu, adalah bahwa ada potensi bahaya yang jauh lebih luas ketika orang-orang menggunakan optimisasi mikro semacam itu secara bebas di seluruh basis kode. Jika Anda bekerja di perusahaan seperti Microsoft pada basis kode besar, Anda akan menghabiskan banyak waktu membaca kode sumber insinyur lain, atau berusaha menemukan kode tertentu di dalamnya. Bahkan mungkin kode Anda sendiri yang akan Anda coba masuk akal dalam beberapa tahun ke depan, terutama pada beberapa waktu yang paling tidak tepat, seperti ketika Anda harus memperbaiki pemadaman produksi setelah panggilan yang Anda terima pada pager tugas pada hari Jumat malam, akan keluar untuk bersenang-senang dengan teman-teman ... Jika Anda menghabiskan banyak waktu untuk membaca kode, Anda akan menghargai itu karena dapat dibaca sebagai mungkin. Bayangkan membaca novel favorit Anda, tetapi penerbit telah memutuskan untuk merilis edisi baru di mana mereka menggunakan abbrv. semua ovr th plc bcs thnk itu svs spc. Itu mirip dengan reaksi insinyur lain mungkin harus kode Anda, jika Anda menaburkannya dengan optimasi seperti itu. Seperti yang telah ditunjukkan oleh jawaban lain, lebih baik jelaskan apa yang Anda maksudkan,

Bahkan dalam lingkungan itu, Anda mungkin menemukan diri Anda memecahkan pertanyaan wawancara di mana Anda diharapkan mengetahui hal ini atau kesetaraan lainnya. Mengetahui mereka tidak buruk dan seorang insinyur yang baik akan menyadari efek aritmatika dari pergeseran biner. Perhatikan bahwa saya tidak mengatakan bahwa ini membuat insinyur yang baik, tetapi insinyur yang baik akan tahu, menurut pendapat saya. Secara khusus, Anda mungkin masih menemukan beberapa manajer, biasanya menjelang akhir wawancara Anda, yang akan menyeringai lebar pada Anda dalam mengantisipasi kegembiraan untuk mengungkapkan "trik" rekayasa pintar ini kepada Anda dalam pertanyaan koding dan membuktikan bahwa dia , juga, dulu atau merupakan salah satu insinyur yang cerdas dan bukan "hanya" seorang manajer. Dalam situasi itu, cobalah untuk terlihat terkesan dan berterima kasih padanya untuk wawancara yang mencerahkan.

Mengapa Anda tidak melihat perbedaan kecepatan dalam C? Jawaban yang paling mungkin adalah keduanya menghasilkan kode perakitan yang sama:

int shift(int i) { return i << 2; }
int multiply(int i) { return i * 2; }

Dapat dikompilasi menjadi keduanya

shift(int):
    lea eax, [0+rdi*4]
    ret

Pada GCC tanpa optimasi, yaitu menggunakan flag "-O0", Anda mungkin mendapatkan ini:

shift(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    sal eax, 2
    pop rbp
    ret
multiply(int):
    push    rbp
    mov rbp, rsp
    mov DWORD PTR [rbp-4], edi
    mov eax, DWORD PTR [rbp-4]
    add eax, eax
    pop rbp
    ret

Seperti yang Anda lihat, meneruskan "-O0" ke GCC tidak berarti bahwa tidak akan terlalu pintar tentang jenis kode apa yang dihasilkannya. Secara khusus, perhatikan bahwa bahkan dalam kasus ini kompiler menghindari penggunaan instruksi penggandaan. Anda dapat mengulangi percobaan yang sama dengan menggeser dengan angka lain dan bahkan mengalikan dengan angka yang bukan kekuatan dua. Kemungkinannya adalah bahwa pada platform Anda, Anda akan melihat kombinasi shift dan penambahan, tetapi tidak ada multiplikasi. Sepertinya sedikit kebetulan bagi kompiler untuk menghindari penggunaan perkalian dalam semua kasus jika perkalian dan pergeseran benar-benar memiliki biaya yang sama, bukan? Tetapi saya tidak bermaksud memberikan anggapan untuk bukti, jadi mari kita beralih.

Anda dapat menjalankan kembali pengujian dengan kode di atas dan melihat apakah Anda melihat perbedaan kecepatan sekarang. Meskipun demikian, Anda tidak menguji shift versus multiply, seperti yang dapat Anda lihat dengan tidak adanya multiplikasi, tetapi kode yang dihasilkan dengan serangkaian flag oleh GCC untuk operasi C shift dan dikalikan dalam contoh tertentu . Jadi, dalam tes lain Anda dapat mengedit kode perakitan dengan tangan dan alih-alih menggunakan instruksi "imul" dalam kode untuk metode "multiply".

Jika Anda ingin mengalahkan beberapa kecerdasan dari kompiler, Anda bisa mendefinisikan metode shift dan multiply yang lebih umum dan akan berakhir dengan sesuatu seperti ini:

int shift(int i, int j) { return i << j; }
int multiply(int i, int j) { return i * j; }

Yang dapat menghasilkan kode perakitan berikut:

shift(int, int):
    mov eax, edi
    mov ecx, esi
    sal eax, cl
    ret
multiply(int, int):
    mov eax, edi
    imul    eax, esi
    ret

Di sini kita akhirnya memiliki, bahkan pada tingkat optimisasi tertinggi dari GCC 4.9, ekspresi dalam instruksi perakitan yang mungkin Anda harapkan ketika Anda awalnya memulai tes Anda. Saya pikir itu sendiri dapat menjadi pelajaran penting dalam optimasi kinerja. Kita dapat melihat perbedaan yang dibuat untuk mengganti variabel untuk konstanta konkret dalam kode kita, dalam hal kecerdasan yang dapat diterapkan oleh kompiler. Optimalisasi mikro seperti penggantian shift-multiply adalah beberapa optimasi tingkat sangat rendah yang biasanya mudah dilakukan oleh kompiler. Optimalisasi lain yang jauh lebih berdampak pada kinerja memerlukan pemahaman maksud kodeyang sering tidak dapat diakses oleh kompiler atau hanya dapat ditebak oleh beberapa heuristik. Di situlah Anda sebagai insinyur perangkat lunak datang dan tentu saja biasanya tidak melibatkan penggantian perkalian dengan shift. Ini melibatkan faktor-faktor seperti menghindari panggilan berlebihan ke layanan yang menghasilkan I / O dan dapat memblokir suatu proses. Jika Anda pergi ke hard disk Anda atau, semoga saja, ke basis data jauh untuk beberapa data tambahan yang bisa Anda peroleh dari apa yang sudah Anda miliki dalam memori, waktu yang Anda habiskan lebih lama daripada pelaksanaan sejuta instruksi. Sekarang, saya pikir kami telah menyimpang agak jauh dari pertanyaan awal Anda, tetapi saya pikir menunjukkan hal ini kepada penanya, terutama jika kita mengira seseorang yang baru mulai memahami terjemahan dan pelaksanaan kode,

Jadi, mana yang lebih cepat? Saya pikir ini adalah pendekatan yang baik yang Anda pilih untuk benar-benar menguji perbedaan kinerja. Secara umum, mudah untuk dikejutkan oleh kinerja runtime dari beberapa perubahan kode. Ada banyak teknik yang digunakan prosesor modern dan interaksi antara perangkat lunak juga bisa rumit. Bahkan jika Anda harus mendapatkan hasil kinerja yang menguntungkan untuk perubahan tertentu dalam satu situasi, saya pikir berbahaya untuk menyimpulkan bahwa jenis perubahan ini akan selalu menghasilkan manfaat kinerja. Saya pikir itu berbahaya untuk menjalankan tes seperti itu sekali, katakan, "Oke, sekarang saya tahu mana yang lebih cepat!" dan kemudian tanpa pandang bulu menerapkan optimasi yang sama ke kode produksi tanpa mengulangi pengukuran Anda.

Lalu bagaimana jika shift lebih cepat dari pada multiplikasi? Tentu saja ada indikasi mengapa itu benar. GCC, seperti yang Anda lihat di atas, tampaknya berpikir (bahkan tanpa optimasi) bahwa menghindari perkalian langsung yang mendukung instruksi lain adalah ide yang bagus. The Intel 64 dan IA-32 manual Arsitektur Optimasi Reference akan memberikan gambaran tentang biaya relatif instruksi CPU. Sumber lain, yang lebih fokus pada latensi dan throughput pengajaran, adalah http://www.agner.org/optimize/instruction_tables.pdf. Perhatikan bahwa mereka bukan prediktor runtime absolut yang baik, tetapi kinerja instruksi relatif satu sama lain. Dalam loop yang ketat, saat tes Anda disimulasikan, metrik "throughput" harus paling relevan. Ini adalah jumlah siklus yang biasanya diikat oleh unit eksekusi ketika menjalankan instruksi yang diberikan.

Jadi bagaimana jika shift TIDAK lebih cepat dari perkalian? Seperti yang saya katakan di atas, arsitektur modern bisa sangat kompleks dan hal-hal seperti prediksi cabang, caching, pipelining, dan unit eksekusi paralel dapat mempersulit untuk memprediksi kinerja relatif dari dua bagian kode yang setara secara logis pada suatu waktu. Saya benar-benar ingin menekankan hal ini, karena di sinilah saya tidak senang dengan sebagian besar jawaban untuk pertanyaan-pertanyaan seperti ini dan dengan sekumpulan orang langsung mengatakan bahwa tidak benar (lagi) bahwa bergeser lebih cepat daripada perkalian.

Tidak, sejauh yang saya tahu kami tidak menemukan saus rekayasa rahasia pada tahun 1970-an atau kapan pun untuk tiba-tiba membatalkan selisih biaya unit penggandaan dan sedikit shifter. Perkalian umum, dalam hal gerbang logis, dan tentu saja dalam hal operasi logis, masih lebih kompleks daripada pergeseran dengan shifter barel di banyak skenario, di banyak arsitektur. Bagaimana ini diterjemahkan ke dalam runtime keseluruhan pada komputer desktop mungkin agak buram. Saya tidak tahu pasti bagaimana mereka diimplementasikan dalam prosesor tertentu, tetapi di sini adalah penjelasan dari suatu perkalian: Apakah perkalian bilangan bulat benar-benar kecepatan yang sama seperti penambahan pada CPU modern

Sementara di sini ada penjelasan tentang Barrel Shifter . Dokumen-dokumen yang saya rujuk pada paragraf sebelumnya memberikan pandangan lain tentang biaya operasi relatif, dengan proksi instruksi CPU. Para insinyur di Intel tampaknya sering mendapatkan pertanyaan serupa: siklus clock forum pengembang zona intel untuk multiplikasi bilangan bulat dan penambahan prosesor core 2 duo

Ya, dalam sebagian besar skenario kehidupan nyata, dan hampir pasti dalam JavaScript, upaya untuk mengeksploitasi kesetaraan ini demi kinerja mungkin merupakan usaha yang sia-sia. Namun, bahkan jika kami memaksakan penggunaan instruksi perkalian dan kemudian tidak melihat perbedaan dalam run-time, itu lebih disebabkan oleh sifat metrik biaya yang kami gunakan, tepatnya, dan bukan karena tidak ada perbedaan biaya. Runtime end-to-end adalah satu metrik dan jika itu satu-satunya yang kami pedulikan, semuanya baik-baik saja. Tetapi itu tidak berarti bahwa semua perbedaan biaya antara multiplikasi dan pergeseran hilang begitu saja. Dan saya pikir tentu bukan ide yang baik untuk menyampaikan ide itu kepada penanya, baik secara implisit atau tidak, yang jelas-jelas baru mulai mendapatkan ide tentang faktor-faktor yang terlibat dalam run-time dan biaya kode modern. Rekayasa selalu tentang pertukaran. Pertanyaan dan penjelasan tentang apa pengorbanan prosesor modern telah dibuat untuk menunjukkan waktu eksekusi yang kita sebagai pengguna akhirnya melihat dapat menghasilkan jawaban yang lebih berbeda. Dan saya pikir jawaban yang lebih terdiferensiasi daripada "ini tidak benar lagi" dijamin jika kita ingin melihat lebih sedikit insinyur memeriksa kode yang dioptimalkan secara mikro menghapus keterbacaan, karena dibutuhkan pemahaman yang lebih umum tentang sifat "optimisasi" tersebut untuk lihat beragamnya inkarnasi yang beragam daripada sekadar menyebut beberapa contoh spesifik sebagai ketinggalan zaman.

Apa yang Anda lihat adalah efek pengoptimal.

Pekerjaan optimisers adalah untuk membuat kode yang dikompilasi yang dihasilkan menjadi lebih kecil, atau lebih cepat (tetapi jarang keduanya sekaligus ... tetapi seperti banyak hal ... ITU TERGANTUNG pada apa kode itu).

Dalam PRINCIPLE, panggilan apa pun ke perpustakaan multiplikasi, atau, sering, bahkan penggunaan pengganda perangkat keras akan lebih lambat daripada hanya melakukan perubahan bitwise.

Jadi ... jika compiler naif menghasilkan panggilan ke perpustakaan untuk operasi * 2, maka tentu saja itu akan berjalan lebih lambat daripada pergeseran bitwise *.

Namun optimis ada untuk mendeteksi pola dan mencari cara untuk membuat kode lebih kecil / lebih cepat / apa pun. Dan apa yang Anda lihat adalah kompiler yang mendeteksi bahwa * 2 sama dengan shift.

Sama seperti yang menarik, saya hanya hari ini melihat assembler yang dihasilkan untuk beberapa operasi seperti * 5 ... tidak benar-benar melihat itu tetapi hal-hal lain, dan sepanjang jalan saya perhatikan bahwa kompiler telah mengubah * 5 menjadi:

• bergeser
• bergeser
• tambahkan nomor asli

Jadi pengoptimal kompiler saya cukup pintar (setidaknya untuk konstanta kecil tertentu) untuk menghasilkan pergeseran inline dan menambahkan bukannya panggilan ke perpustakaan multiply tujuan umum.

Seni pengoptimal kompiler adalah subjek yang terpisah, diisi dengan sihir, dan benar-benar dipahami oleh sekitar 6 orang di seluruh planet ini :)

Coba atur waktu dengan:

for (runs = 0; runs < 100000000; runs++) {
      ;
}

Compiler harus mengakui bahwa nilai testtidak berubah setelah setiap iterasi dari loop, dan nilai akhir dari testtidak digunakan, dan menghilangkan loop sepenuhnya.

Perkalian adalah kombinasi dari pergeseran dan penambahan.

Dalam kasus yang Anda sebutkan, saya tidak percaya itu penting apakah kompiler mengoptimalkannya atau tidak - "dikalikan xdua" dapat diimplementasikan sebagai:

• Geser bit dari xsatu tempat ke kiri.
• Tambahkan xke x.

Ini adalah masing-masing operasi atom dasar; satu tidak lebih cepat dari yang lain.

Ubah ke "kalikan xempat", (atau apa saja 2^k, k>1) dan ini sedikit berbeda:

• Geser bit dari xdua tempat ke kiri.
• Tambahkan xke xdan panggil y, tambahkan yke y.

Pada arsitektur dasar, itu sederhana untuk melihat bahwa pergeseran lebih efisien - mengambil satu vs dua operasi, karena kita tidak dapat menambahkan yuntuk ysampai kita tahu apa yyang.

Coba yang terakhir (atau apa saja 2^k, k>1), dengan opsi yang sesuai untuk mencegah Anda mengoptimalkannya menjadi hal yang sama dalam implementasi. Anda harus menemukan shift lebih cepat, mengambil O(1)dibandingkan dengan penambahan berulang di O(k).

Jelas, di mana multiplicand bukan kekuatan dua, kombinasi shift dan penambahan (satu di mana jumlah masing-masing adalah nol) diperlukan.

Penggandaan nilai-nilai yang ditandatangani atau tidak oleh kekuatan dua sama dengan menggeser ke kiri, dan sebagian besar penyusun akan melakukan substitusi. Pembagian nilai yang tidak ditandatangani, atau nilai yang ditandatangani yang dapat dibuktikan oleh kompiler tidak pernah negatif , sama dengan pergeseran kanan, dan sebagian besar kompiler akan melakukan penggantian itu (meskipun beberapa tidak cukup canggih untuk membuktikan ketika nilai yang ditandatangani tidak boleh negatif) .

Perlu dicatat, bahwa pembagian nilai-nilai yang ditandatangani berpotensi negatif tidak setara dengan pergeseran kanan. Ekspresi suka (x+8)>>4tidak setara dengan (x+8)/16. Yang pertama, dalam 99% kompiler, akan memetakan nilai dari -24 hingga -9 hingga -1, -8 hingga +7 hingga 0, dan +8 hingga +23 hingga 1 [angka pembulatan hampir simetris sekitar nol]. Yang terakhir akan memetakan -39 ke -24 ke -1, -23 hingga +7 hingga 0, dan +8 hingga +23 ke +1 [sangat asimetris, dan kemungkinan bukan apa yang dimaksudkan]. Perhatikan bahwa bahkan ketika nilai tidak diharapkan menjadi negatif, penggunaan >>4kode kemungkinan akan menghasilkan lebih cepat daripada /16kecuali kompilator dapat membuktikan nilai tidak bisa negatif.

Beberapa info lagi saya baru saja check out.

Pada x86_64, opcode MUL memiliki latensi 10 siklus dan throughput 1/2 siklus. MOV, ADD dan SHL memiliki latensi 1 siklus, dengan throughput 2.5, 2.5, dan 1.7 cycle.

Penggandaan oleh 15 akan membutuhkan 3 SHL dan 3 ADD ops minimum dan mungkin beberapa MOVs.

https://gmplib.org/~tege/x86-timing.pdf

Metodologi Anda cacat. Peningkatan loop dan kondisi Anda memeriksa sendiri mengambil banyak waktu.

• Coba jalankan loop kosong dan ukur waktunya (sebut saja base).
• Sekarang tambahkan 1 operasi shift dan ukur waktunya (sebut saja s1).
• Selanjutnya tambahkan 10 operasi shift dan ukur waktunya (sebut saja s2)

Jika semuanya berjalan dengan benar base-s2harus 10 kali lebih banyak dari base-s1. Kalau tidak, sesuatu yang lain ikut bermain di sini.

Sekarang saya benar-benar mencoba ini sendiri dan menemukan, Jika loop menyebabkan masalah mengapa tidak menghapusnya sama sekali. Jadi saya pergi ke depan dan melakukan ini:

int main(){

    int test = 2;
    clock_t launch = clock();

    test << 6;
    test << 6;
    test << 6;
    test << 6;
    //.... 1 million times
    test << 6;

    clock_t done = clock();
    printf("Time taken : %d\n", done - launch);
    return 0;
}

Dan di sana Anda mendapatkan hasilnya

1 juta operasi shift dalam waktu kurang dari 1 milidetik? .

Saya melakukan hal yang sama untuk perkalian dengan 64 dan mendapat hasil yang sama. Jadi mungkin kompiler mengabaikan operasi sepenuhnya karena yang lain menyebutkan nilai tes tidak pernah berubah.