Apakah multiplikasi dan pembagian menggunakan operator shift di C sebenarnya lebih cepat?

288

Penggandaan dan pembagian dapat dicapai menggunakan operator bit, misalnya

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

dan seterusnya.

Apakah benar-benar lebih cepat menggunakan say (i<<3)+(i<<1)untuk dikalikan dengan 10 daripada menggunakan i*10secara langsung? Apakah ada input yang tidak dapat dikalikan atau dibagi dengan cara ini?

eku
sumber
8
Sebenarnya, pembagian murah dengan konstanta selain kekuatan dua adalah mungkin, tetapi subjek rumit yang Anda tidak melakukan keadilan dengan "/ Divisi ... / dibagi" dalam pertanyaan Anda. Lihat misalnya hackersdelight.org/divcMore.pdf (atau dapatkan buku "Kegembiraan hacker" jika Anda bisa).
Pascal Cuoq
46
Kedengarannya seperti sesuatu yang bisa dengan mudah diuji.
juanchopanza
25
Seperti biasa - itu tergantung. Sekali waktu saya mencoba ini di assembler pada Intel 8088 (IBM PC / XT) di mana perkalian mengambil bazillion jam. Bergeser dan menambahkan dieksekusi jauh lebih cepat, jadi sepertinya ide yang bagus. Namun, ketika mengalikan unit bus bebas untuk mengisi antrian instruksi dan instruksi selanjutnya dapat segera dimulai. Setelah serangkaian perubahan dan menambahkan antrian instruksi akan kosong dan CPU harus menunggu instruksi berikutnya diambil dari memori (satu byte setiap kali!). Ukur, ukur, ukur!
Bo Persson
19
Juga, berhati-hatilah bahwa penggeseran kanan hanya didefinisikan dengan baik untuk bilangan bulat yang tidak ditandatangani . Jika Anda memiliki bilangan bulat yang ditandatangani, tidak ditentukan apakah 0 atau bit tertinggi diisi dari kiri. (Dan jangan lupa waktu yang diperlukan orang lain (bahkan diri Anda sendiri) untuk membaca kode setahun kemudian!)
Kerrek SB
29
Sebenarnya, kompiler pengoptimal yang baik akan menerapkan penggandaan dan pembagian dengan pergeseran ketika mereka lebih cepat.
Peter G.

Jawaban:

487

Jawaban singkat: Tidak mungkin.

Jawaban panjang: Kompiler Anda memiliki pengoptimal di dalamnya yang tahu cara melipatgandakan secepat arsitektur prosesor target Anda mampu. Taruhan terbaik Anda adalah memberi tahu kompiler niat Anda dengan jelas (yaitu i * 2 daripada i << 1) dan biarkan ia memutuskan apa urutan kode perakitan / mesin tercepat. Bahkan dimungkinkan bahwa prosesor itu sendiri telah mengimplementasikan instruksi penggandaan sebagai urutan pergeseran & menambahkan dalam kode mikro.

Intinya - jangan menghabiskan banyak waktu untuk mengkhawatirkan hal ini. Jika Anda bermaksud bergeser, bergeserlah. Jika Anda bermaksud melipatgandakan, gandakan. Lakukan apa yang paling jelas secara semantik - rekan kerja Anda akan berterima kasih nanti. Atau, lebih mungkin, mengutuk Anda nanti jika Anda melakukannya sebaliknya.

Drew Hall
sumber
31
Yap, seperti yang dikatakan keuntungan yang mungkin untuk hampir setiap aplikasi akan benar-benar melebihi ketidakjelasan yang diperkenalkan. Jangan khawatir tentang optimasi semacam ini sebelum waktunya. Bangun apa yang secara semi-jelas jelas, identifikasi kemacetan, dan optimalkan dari sana ...
Dave
4
Setuju, mengoptimalkan keterbacaan dan pemeliharaan mungkin akan memberi Anda lebih banyak waktu untuk menghabiskan hal-hal yang sebenarnya mengoptimalkan yang dikatakan oleh profiler adalah jalur kode panas.
doug65536
5
Komentar ini membuatnya terdengar seperti Anda menyerah pada kinerja potensial dari memberi tahu kompiler bagaimana melakukan tugasnya. Ini bukan masalahnya. Anda benar-benar mendapatkan kode yang lebih baik dari gcc -O3pada x86 dengan return i*10dari dari versi shift . Sebagai seseorang yang sering melihat keluaran kompiler (lihat banyak jawaban asm / optimisasi saya), saya tidak terkejut. Ada saat-saat itu dapat membantu untuk memegang kompiler dengan satu cara dalam melakukan sesuatu , tetapi ini bukan salah satunya. gcc pandai integer matematika, karena itu penting.
Peter Cordes
Baru saja mengunduh sketsa arduino yang telah millis() >> 2; Apakah terlalu banyak meminta hanya membagi?
Paul Wieland
1
Saya menguji i / 32vs i >> 5dan i / 4vs i >> 2pada gcc untuk cortex-a9 (yang tidak memiliki divisi perangkat keras) dengan optimasi -O3 dan perakitan yang dihasilkan persis sama. Saya tidak suka menggunakan divisi dulu tapi itu menggambarkan niat saya dan hasilnya sama.
robsn
91

Hanya titik konkret: bertahun-tahun yang lalu, saya membandingkan dua versi algoritma hashing saya:

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = 127 * h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

dan

unsigned
hash( char const* s )
{
    unsigned h = 0;
    while ( *s != '\0' ) {
        h = (h << 7) - h + (unsigned char)*s;
        ++ s;
    }
    return h;
}

Pada setiap mesin yang saya gunakan untuk benchmark, yang pertama setidaknya secepat yang kedua. Agak mengherankan, kadang-kadang lebih cepat (misalnya pada Sun Sparc). Ketika perangkat keras tidak mendukung perkalian cepat (dan sebagian besar tidak saat itu), kompiler akan mengubah perkalian menjadi kombinasi shift dan add / sub yang sesuai. Dan karena ia tahu tujuan akhir, kadang-kadang bisa melakukannya dengan instruksi yang lebih sedikit daripada ketika Anda secara eksplisit menulis shift dan add / subs.

Perhatikan bahwa ini kira-kira 15 tahun yang lalu. Mudah-mudahan, kompiler hanya menjadi lebih baik sejak itu, sehingga Anda dapat mengandalkan compiler untuk melakukan hal yang benar, mungkin lebih baik daripada yang Anda bisa. (Juga, alasan kodenya terlihat begitu adalah karena lebih dari 15 tahun yang lalu. Saya jelas-jelas menggunakan std::stringdan iterator hari ini.)

James Kanze
sumber
5
Anda mungkin tertarik pada posting blog berikut ini, di mana penulis mencatat bahwa kompiler pengoptimal modern tampaknya merekayasa balik pola umum yang mungkin digunakan pemrogram untuk berpikir mereka lebih efisien ke dalam bentuk matematika mereka sehingga benar-benar menghasilkan urutan instruksi yang paling efisien untuk mereka. . shape-of-code.coding-guidelines.com/2009/06/30/…
Pascal Cuoq
@PascalCuoq Tidak ada yang benar-benar baru tentang ini. Saya menemukan hal yang hampir sama untuk Sun CC hampir 20 tahun yang lalu.
James Kanze
67

Selain semua jawaban baik lainnya di sini, izinkan saya menunjukkan alasan lain untuk tidak menggunakan shift ketika Anda bermaksud membagi atau mengalikan. Saya belum pernah melihat seseorang memperkenalkan bug dengan melupakan prioritas relatif multiplikasi dan penambahan. Saya telah melihat bug yang diperkenalkan ketika programmer pemeliharaan lupa bahwa "mengalikan" melalui shift adalah perkalian secara logis tetapi tidak secara sintaksis dengan prioritas yang sama dengan perkalian. x * 2 + zdan x << 1 + zsangat berbeda!

Jika Anda bekerja pada angka maka gunakan operator aritmatika seperti + - * / %. Jika Anda bekerja pada array bit, gunakan operator yang suka memutar-mutar bit & ^ | >>. Jangan mencampurnya; ekspresi yang memiliki sedikit twiddling dan aritmatika adalah bug yang menunggu untuk terjadi.

Eric Lippert
sumber
5
Dihindari dengan tanda kurung sederhana?
Joel B
21
@ Joel: Tentu. Jika Anda ingat bahwa Anda membutuhkannya. Maksud saya adalah mudah untuk melupakan yang Anda lakukan. Orang yang memiliki kebiasaan mental membaca "x << 1" seolah-olah "x * 2" memiliki kebiasaan berpikir bahwa << adalah prioritas yang sama dengan perkalian, padahal bukan.
Eric Lippert
1
Yah, saya menemukan ekspresi "(hai << 8) + lo" lebih banyak mengungkapkan maksud daripada "hai * 256 + lo". Mungkin ini masalah selera, tetapi kadang-kadang lebih jelas untuk menulis sedikit-twiddling. Dalam banyak kasus saya sangat setuju dengan poin Anda.
Ivan Danilov
32
@Ivan: Dan "(hai << 8) | lo" bahkan lebih jelas. Mengatur bit bit array yang rendah bukanlah penambahan bilangan bulat . ini pengaturan bit , jadi tulis kode yang menetapkan bit.
Eric Lippert
1
Wow. Tidak memikirkannya seperti ini sebelumnya. Terima kasih.
Ivan Danilov
50

Ini tergantung pada prosesor dan kompiler. Beberapa kompiler sudah mengoptimalkan kode dengan cara ini, yang lain tidak. Jadi, Anda perlu memeriksa setiap kali kode Anda perlu dioptimalkan dengan cara ini.

Kecuali Anda sangat perlu mengoptimalkan, saya tidak akan mengacak kode sumber saya hanya untuk menyimpan instruksi perakitan atau siklus prosesor.

Jens
sumber
3
Hanya untuk menambahkan perkiraan kasar: Pada prosesor 16-Bit (80C166) khas menambahkan dua int datang pada 1-2 siklus, perkalian pada 10 siklus dan pembagian pada 20 siklus. Ditambah beberapa operasi pemindahan jika Anda mengoptimalkan i * 10 ke dalam beberapa operasi (masing-masing memindah satu siklus +1). Kompiler yang paling umum (Keil / Tugasking) tidak dioptimalkan kecuali untuk perkalian / pembagian dengan kekuatan 2.
Jens
55
Dan secara umum, kompiler mengoptimalkan kode lebih baik daripada Anda.
user703016
Saya setuju bahwa ketika mengalikan "kuantitas", operator perkalian umumnya lebih baik, tetapi ketika membagi nilai yang ditandatangani oleh kekuatan 2, >>operator lebih cepat daripada /dan, jika nilai yang ditandatangani dapat negatif, seringkali semantik juga superior. Jika seseorang membutuhkan nilai yang x>>4akan menghasilkan, itu jauh lebih jelas daripada x < 0 ? -((-1-x)/16)-1 : x/16;, dan saya tidak bisa membayangkan bagaimana kompiler dapat mengoptimalkan ekspresi yang terakhir itu untuk sesuatu yang bagus.
supercat
38

Apakah lebih cepat menggunakan say (i << 3) + (i << 1) untuk dikalikan dengan 10 daripada menggunakan i * 10 secara langsung?

Mungkin atau mungkin tidak ada di mesin Anda - jika Anda peduli, ukurlah dalam penggunaan dunia nyata Anda.

Sebuah studi kasus - dari 486 ke inti i7

Benchmarking sangat sulit dilakukan secara bermakna, tetapi kita dapat melihat beberapa fakta. Dari http://www.penguin.cz/~literakl/intel/s.html#SAL dan http://www.penguin.cz/~literakl/intel/i.html#IMUL kita mendapatkan gagasan tentang siklus clock x86 dibutuhkan untuk perubahan aritmatika dan perkalian. Katakanlah kita berpegang pada "486" (yang terbaru terdaftar), register 32 bit dan segera, IMUL mengambil 13-42 siklus dan IDIV 44. Setiap SAL mengambil 2, dan menambahkan 1, sehingga bahkan dengan beberapa dari mereka yang bersama-sama bergeser tampak dangkal seperti seorang pemenang.

Hari-hari ini, dengan i7 inti:

(dari http://software.intel.com/en-us/forums/showthread.php?t=61481 )

Latensi adalah 1 siklus untuk penambahan bilangan bulat dan 3 siklus untuk perkalian bilangan bulat . Anda dapat menemukan latensi dan masukan dalam Lampiran C "Manual Referensi Optimasi Arsitektur Intel® 64 dan IA-32", yang terdapat di http://www.intel.com/products/processor/manuals/ .

(dari beberapa uraian Intel)

Menggunakan SSE, Core i7 dapat mengeluarkan instruksi menambahkan dan mengalikan secara simultan, menghasilkan tingkat puncak 8 operasi floating-point (FLOP) per siklus clock

Itu memberi Anda gambaran tentang seberapa jauh hal-hal telah terjadi. Trivia optimisasi - seperti bit shifting versus* - yang telah dianggap serius bahkan sampai tahun 90an sudah usang sekarang. Bit-shifting masih lebih cepat, tetapi untuk non-power-of-two mul / div pada saat Anda melakukan semua shift Anda dan menambahkan hasilnya lebih lambat lagi. Kemudian, lebih banyak instruksi berarti lebih banyak kesalahan cache, lebih banyak potensi masalah dalam pemipaan, lebih banyak menggunakan register sementara dapat berarti lebih banyak menyimpan dan memulihkan konten register dari stack ... dengan cepat menjadi terlalu rumit untuk mengukur semua dampak secara definitif tetapi mereka sebagian besar negatif.

fungsionalitas dalam kode sumber vs implementasi

Secara umum, pertanyaan Anda ditandai C dan C ++. Sebagai bahasa generasi ke-3, mereka dirancang khusus untuk menyembunyikan detail set instruksi CPU yang mendasarinya. Untuk memenuhi Standar bahasa mereka, mereka harus mendukung operasi multiplikasi dan perpindahan (dan banyak lainnya) bahkan jika perangkat keras yang mendasarinya tidak . Dalam kasus seperti itu, mereka harus mensintesis hasil yang diperlukan menggunakan banyak instruksi lain. Demikian pula, mereka harus memberikan dukungan perangkat lunak untuk operasi floating point jika CPU tidak memilikinya dan tidak ada FPU. CPU modern semua mendukung *dan<<, jadi ini mungkin tampak tidak masuk akal secara teoritis dan historis, tetapi yang penting adalah bahwa kebebasan untuk memilih implementasi berjalan dua arah: bahkan jika CPU memiliki instruksi yang mengimplementasikan operasi yang diminta dalam kode sumber dalam kasus umum, kompiler bebas untuk pilih sesuatu yang lebih disukai karena lebih baik untuk kasus spesifik yang dihadapi oleh kompiler.

Contoh (dengan bahasa majelis hipotetis)

source           literal approach         optimised approach
#define N 0
int x;           .word x                xor registerA, registerA
x *= N;          move x -> registerA
                 move x -> registerB
                 A = B * immediate(0)
                 store registerA -> x
  ...............do something more with x...............

Instruksi seperti eksklusif atau ( xor) tidak memiliki hubungan dengan kode sumber, tetapi xor-ing apa pun dengan sendirinya membersihkan semua bit, sehingga dapat digunakan untuk mengatur sesuatu menjadi 0. Kode sumber yang menyiratkan alamat memori mungkin tidak memerlukan penggunaan apa pun.

Jenis peretasan ini telah digunakan selama komputer ada. Pada hari-hari awal 3GL, untuk mengamankan serapan pengembang, output kompiler harus memuaskan pengembang bahasa pengoptimalisasi tangan hardcore yang ada. komunitas bahwa kode yang dihasilkan tidak lebih lambat, lebih banyak kata atau lebih buruk. Compiler dengan cepat mengadopsi banyak optimisasi hebat - mereka menjadi toko yang lebih tersentralisasi daripada yang bisa dilakukan oleh programmer bahasa assembly mana pun, meskipun selalu ada kemungkinan mereka kehilangan optimasi tertentu yang penting dalam kasus tertentu - manusia kadang-kadang dapat buang dan grope untuk sesuatu yang lebih baik sementara kompiler hanya melakukan apa yang diperintahkan sampai seseorang memberi makan pengalaman itu kembali ke mereka.

Jadi, bahkan jika pengalihan dan penambahan masih lebih cepat pada beberapa perangkat keras tertentu, maka penulis kompiler kemungkinan telah bekerja tepat ketika itu aman dan menguntungkan.

Maintabilitas

Jika perubahan perangkat keras Anda, Anda dapat mengkompilasi ulang dan itu akan melihat CPU target dan membuat pilihan terbaik lain, sedangkan Anda tidak akan pernah ingin mengunjungi kembali "optimisasi" Anda atau daftar mana lingkungan kompilasi yang harus menggunakan perkalian dan mana yang harus bergeser. Pikirkan semua "optimisasi" non-kekuatan-dua-bit-bergeser yang ditulis 10+ tahun yang lalu yang memperlambat kode mereka saat berjalan pada prosesor modern ...!

Untungnya, kompiler yang baik seperti GCC biasanya dapat mengganti serangkaian bithift dan aritmatika dengan perkalian langsung ketika optimasi apa pun diaktifkan (mis. ...main(...) { return (argc << 4) + (argc << 2) + argc; }-> imull $21, 8(%ebp), %eax) sehingga kompilasi ulang dapat membantu bahkan tanpa memperbaiki kode, tetapi itu tidak dijamin.

Kode bitshifting aneh yang menerapkan perkalian atau pembagian jauh lebih ekspresif dari apa yang Anda coba capai secara konseptual, sehingga pengembang lain akan bingung dengan hal itu, dan programmer yang bingung lebih mungkin memperkenalkan bug atau menghapus sesuatu yang penting dalam upaya mengembalikan kewarasan yang tampak. Jika Anda hanya melakukan hal-hal yang tidak jelas ketika mereka benar-benar bermanfaat, dan kemudian mendokumentasikannya dengan baik (tapi jangan mendokumentasikan hal-hal lain yang intuitif), semua orang akan lebih bahagia.

Solusi umum versus solusi parsial

Jika Anda memiliki pengetahuan tambahan, seperti bahwa Anda intbenar-benar hanya akan menyimpan nilai x, ydan z, maka Anda mungkin dapat mengerjakan beberapa instruksi yang bekerja untuk nilai-nilai itu dan memberi Anda hasil Anda lebih cepat daripada ketika kompiler tidak memiliki wawasan itu dan membutuhkan implementasi yang bekerja untuk semua intnilai. Misalnya, pertimbangkan pertanyaan Anda:

Perkalian dan pembagian dapat dicapai menggunakan operator bit ...

Anda menggambarkan perkalian, tetapi bagaimana dengan pembagian?

int x;
x >> 1;   // divide by 2?

Menurut C ++ Standard 5.8:

-3- Nilai E1 >> E2 adalah posisi bit E2 bergeser kanan E1. Jika E1 memiliki tipe yang tidak ditandatangani atau jika E1 memiliki tipe yang ditandatangani dan nilai yang tidak negatif, nilai hasilnya adalah bagian integral dari hasil bagi E1 dibagi dengan jumlah 2 yang diangkat ke daya E2. Jika E1 memiliki tipe yang ditandatangani dan nilai negatif, nilai yang dihasilkan ditentukan oleh implementasi.

Jadi, bit shift Anda memiliki hasil yang ditentukan ketika hasilnya xnegatif: itu mungkin tidak bekerja dengan cara yang sama pada mesin yang berbeda. Tapi, /kerjanya jauh lebih mudah ditebak. (Ini mungkin juga tidak sepenuhnya konsisten, karena mesin yang berbeda mungkin memiliki representasi berbeda dari bilangan negatif, dan karenanya rentang yang berbeda bahkan ketika ada jumlah bit yang sama yang membentuk representasi.)

Anda mungkin berkata, "Saya tidak peduli ... yang intmenyimpan usia karyawan, itu tidak mungkin negatif". Jika Anda memiliki wawasan khusus semacam itu, maka ya - >>optimisasi aman Anda mungkin dilewati oleh kompiler kecuali Anda melakukannya secara eksplisit dalam kode Anda. Tapi, itu berisiko dan jarang berguna karena Anda tidak akan memiliki wawasan seperti ini, dan programmer lain yang bekerja dengan kode yang sama tidak akan tahu bahwa Anda telah bertaruh dengan harapan yang tidak biasa dari data yang Anda miliki. akan menangani ... apa yang tampaknya benar-benar perubahan yang aman bagi mereka mungkin menjadi bumerang karena "optimasi" Anda.

Apakah ada input yang tidak dapat dikalikan atau dibagi dengan cara ini?

Ya ... seperti yang disebutkan di atas, angka negatif memiliki implementasi perilaku yang ditentukan ketika "dibagi" dengan sedikit-bergeser.

Tony Delroy
sumber
2
Jawaban yang sangat bagus Perbandingan Core i7 vs 486 mencerahkan!
Drew Hall
Pada semua arsitektur biasa, intVal>>1akan memiliki semantik yang sama yang berbeda dari mereka intVal/2dengan cara yang kadang berguna. Jika seseorang perlu menghitung dengan cara portabel nilai yang akan dihasilkan oleh arsitektur biasa intVal >> 1, ekspresi itu harus agak lebih rumit dan lebih sulit untuk dibaca, dan kemungkinan akan menghasilkan kode yang jauh lebih rendah daripada yang diproduksi untuk intVal >> 1.
supercat
35

Baru saja mencoba di komputer saya mengkompilasi ini:

int a = ...;
int b = a * 10;

Ketika membongkar itu menghasilkan output:

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

Versi ini lebih cepat daripada kode yang dioptimalkan dengan tangan dengan perubahan dan penambahan murni.

Anda benar-benar tidak pernah tahu apa yang akan dihasilkan oleh kompiler, jadi lebih baik hanya menulis perkalian normal dan biarkan dia mengoptimalkan cara yang diinginkannya, kecuali dalam kasus yang sangat tepat di mana Anda tahu kompiler tidak dapat mengoptimalkan.

pengguna703016
sumber
1
Anda akan mendapatkan suara besar untuk ini jika Anda melewatkan bagian tentang vektor. Jika kompiler dapat memperbaiki perkalian, ia juga dapat melihat bahwa vektor tidak berubah.
Bo Persson
Bagaimana kompiler mengetahui ukuran vektor tidak akan berubah tanpa membuat asumsi yang sangat berbahaya? Atau pernahkah Anda mendengar tentang konkurensi ...
Charles Goodwin
1
Ok, jadi Anda mengulangi vektor global tanpa kunci? Dan saya mengulang-ulang vektor lokal yang alamatnya belum diambil, dan hanya memanggil fungsi anggota konst. Setidaknya kompiler saya menyadari bahwa ukuran vektor tidak akan berubah. (dan segera seseorang mungkin akan menandai kami untuk mengobrol :-).
Bo Persson
1
@ BoPersson Akhirnya, setelah sekian lama, saya menghapus pernyataan saya tentang kompiler yang tidak dapat dioptimalkan vector<T>::size(). Kompiler saya cukup kuno! :)
user703016
21

Pergeseran pada umumnya jauh lebih cepat daripada mengalikan pada tingkat instruksi tetapi Anda mungkin membuang-buang waktu melakukan optimasi prematur. Kompiler dapat melakukan optimasi ini pada saat kompilasi. Melakukannya sendiri akan memengaruhi keterbacaan dan mungkin tidak berpengaruh pada kinerja. Mungkin hanya layak untuk melakukan hal-hal seperti ini jika Anda telah membuat profil dan menemukan ini sebagai hambatan.

Sebenarnya trik pembagian, yang dikenal sebagai 'divisi sihir' sebenarnya dapat menghasilkan hadiah besar. Sekali lagi Anda harus profil dulu untuk melihat apakah itu diperlukan. Tetapi jika Anda menggunakannya ada program yang berguna di sekitar untuk membantu Anda mengetahui instruksi apa yang diperlukan untuk semantik divisi yang sama. Berikut ini sebuah contoh: http://www.masm32.com/board/index.php?topic=12421.0

Contoh yang saya angkat dari utas OP di MASM32:

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

Akan menghasilkan:

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16
Mike Kwan
sumber
7
@Drew karena suatu alasan komentar Anda membuat saya tertawa dan menumpahkan kopi saya. Terima kasih.
asawyer
30
Tidak ada utas forum acak tentang menyukai matematika. Siapa pun yang suka matematika tahu betapa sulitnya untuk membuat utas forum "acak" yang sebenarnya.
Joel B
1
Mungkin hanya layak untuk melakukan hal-hal seperti ini jika Anda telah membuat profil dan menemukan ini sebagai hambatan dan menerapkan alternatif dan profil lagi dan mendapatkan setidaknya 10 kali keunggulan kinerja .
Lie Ryan
12

Instruksi shift dan integer multiply memiliki kinerja yang serupa pada kebanyakan CPU modern - instruksi integer integer relatif lambat pada tahun 1980-an tetapi secara umum ini tidak lagi benar. Instruksi pengganda bilangan bulat mungkin memiliki latensi yang lebih tinggi , sehingga mungkin masih ada kasus di mana pergeseran lebih disukai. Ditto untuk kasus-kasus di mana Anda dapat membuat unit eksekusi lebih sibuk (meskipun ini dapat memotong dua arah)

Divisi integer masih relatif lambat, jadi menggunakan shift alih-alih pembagian dengan kekuatan 2 masih menang, dan sebagian besar kompiler akan menerapkan ini sebagai optimisasi. Namun perhatikan bahwa agar pengoptimalan ini valid, dividen perlu tidak ditandatangani atau harus diketahui positif. Untuk dividen negatif, shift dan pembagiannya tidak setara!

#include <stdio.h>

int main(void)
{
    int i;

    for (i = 5; i >= -5; --i)
    {
        printf("%d / 2 = %d, %d >> 1 = %d\n", i, i / 2, i, i >> 1);
    }
    return 0;
}

Keluaran:

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

Jadi jika Anda ingin membantu kompiler maka pastikan variabel atau ekspresi dalam dividen secara eksplisit tidak ditandatangani.

Paul R
sumber
4
Pengganda bilangan bulat di-mikrokode misalnya pada PPU PlayStation 3, dan menghentikan seluruh pipa. Dianjurkan untuk menghindari pengganda bilangan bulat pada beberapa platform masih :)
Maister
2
Banyak divisi yang tidak ditandatangani - dengan asumsi kompiler tahu caranya - diimplementasikan menggunakan perkalian yang tidak ditandatangani. Satu atau dua kali lipat @ beberapa siklus clock masing-masing dapat melakukan pekerjaan yang sama seperti pembagian @ 40 siklus masing-masing dan lebih.
Olof Forshell
1
@Olof: benar, tetapi hanya berlaku untuk pembagian oleh konstanta waktu kompilasi tentu saja
Paul R
4

Ini sepenuhnya tergantung pada perangkat target, bahasa, tujuan, dll.

Pixel berderak dalam driver kartu video? Sangat mungkin, ya!

Aplikasi bisnis .NET untuk departemen Anda? Sama sekali tidak ada alasan untuk melihatnya.

Untuk game berkinerja tinggi untuk perangkat seluler, mungkin perlu dilakukan pengamatan, tetapi hanya setelah optimasi yang lebih mudah dilakukan.

Brady Moritz
sumber
2

Jangan lakukan kecuali Anda benar-benar perlu dan maksud kode Anda memerlukan pengalihan daripada perkalian / pembagian.

Dalam hari-hari biasa - Anda berpotensi dapat menghemat beberapa siklus mesin (atau longgar, karena kompiler lebih tahu apa yang harus dioptimalkan), tetapi biayanya tidak sepadan - Anda menghabiskan waktu pada detail kecil daripada pekerjaan yang sebenarnya, mempertahankan kode menjadi lebih sulit dan rekan kerja Anda akan mengutuk Anda.

Anda mungkin perlu melakukannya untuk perhitungan beban tinggi, di mana setiap siklus yang disimpan berarti menit runtime. Tetapi, Anda harus mengoptimalkan satu tempat pada satu waktu dan melakukan tes kinerja setiap kali untuk melihat apakah Anda benar-benar membuatnya lebih cepat atau mematahkan logika kompiler.

Kromster
sumber
1

Sejauh yang saya tahu di beberapa mesin, perkalian bisa membutuhkan hingga 16 hingga 32 siklus mesin. Jadi Ya , tergantung pada jenis alat berat, operator bitshift lebih cepat daripada perkalian / pembagian.

Namun mesin tertentu memang memiliki prosesor matematika mereka, yang berisi instruksi khusus untuk perkalian / pembagian.

iammilind
sumber
7
Orang-orang yang menulis kompiler untuk mesin-mesin itu juga kemungkinan membaca Peretas yang Menyenangkan dan mengoptimalkannya.
Bo Persson
1

Saya setuju dengan jawaban yang ditandai oleh Drew Hall. Jawabannya bisa menggunakan beberapa catatan tambahan.

Untuk sebagian besar pengembang perangkat lunak, prosesor dan kompiler tidak lagi relevan dengan pertanyaan. Sebagian besar dari kita jauh melampaui 8.088 dan MS-DOS. Mungkin hanya relevan bagi mereka yang masih mengembangkan untuk prosesor tertanam ...

Di perusahaan perangkat lunak saya, Matematika (tambahkan / sub / mul / div) harus digunakan untuk semua matematika. Sedangkan Shift harus digunakan ketika mengkonversi antara tipe data misalnya. ushort ke byte sebagai n >> 8 dan bukan n / 256.

Deegee
sumber
Saya setuju dengan Anda juga. Saya mengikuti pedoman yang sama secara tidak sadar, meskipun saya belum pernah memiliki persyaratan formal untuk melakukannya.
Drew Hall
0

Dalam kasus bilangan bulat yang ditandatangani dan shift kanan vs divisi, itu bisa membuat perbedaan. Untuk bilangan negatif, giliran putaran putaran ke arah infinity negatif sedangkan putaran pembagian ke nol. Tentu saja kompiler akan mengubah pembagian menjadi sesuatu yang lebih murah, tetapi biasanya akan mengubahnya menjadi sesuatu yang memiliki perilaku pembulatan yang sama dengan pembagian, karena ia tidak dapat membuktikan bahwa variabel tidak akan negatif atau hanya tidak peduli. Jadi, jika Anda dapat membuktikan bahwa angka tidak akan negatif atau jika Anda tidak peduli ke arah mana angka itu akan membulatkannya, Anda dapat melakukan optimasi dengan cara yang lebih mungkin untuk membuat perbedaan.

Harold
sumber
atau berikan nomornya keunsigned
Lie Ryan
4
Apakah Anda yakin bahwa perilaku pemindahan terstandarisasi? Saya mendapat kesan bahwa pergeseran kanan pada int negatif ditentukan oleh implementasi.
Kerrek SB
1
Meskipun Anda mungkin harus menyebutkan bahwa kode yang bergantung pada perilaku tertentu untuk angka negatif penggeseran kanan harus mendokumentasikan persyaratan itu, keuntungan untuk pengalihan kanan sangat besar dalam kasus di mana ia secara alami menghasilkan nilai yang tepat dan operator divisi akan menghasilkan kode untuk dibuang waktu menghitung nilai yang tidak diinginkan yang mana kode pengguna kemudian harus membuang waktu tambahan menyesuaikan untuk menghasilkan apa yang akan diberikan pergeseran di tempat pertama. Sebenarnya, jika saya memiliki pemabuk saya, kompiler akan memiliki opsi untuk mengomel dalam upaya untuk melakukan divisi yang ditandatangani, karena ...
supercat
1
... kode yang mengetahui operan positif dapat meningkatkan optimisasi jika dilemparkan ke unsigned sebelum pembagian (mungkin casting kembali untuk ditandatangani sesudahnya), dan kode yang tahu operan mungkin negatif umumnya harus berurusan dengan kasus itu secara eksplisit bagaimanapun (dalam hal ini seseorang mungkin menganggap mereka positif).
supercat
0

Tes Python melakukan perkalian yang sama 100 juta kali terhadap angka acak yang sama.

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

Jadi dalam melakukan pergeseran daripada perkalian / pembagian dengan kekuatan dua di python, ada sedikit peningkatan (~ 10% untuk divisi; ~ 1% untuk perkalian). Jika ini adalah non-kekuatan dua, ada kemungkinan perlambatan yang cukup besar.

Sekali lagi #s ini akan berubah tergantung pada prosesor Anda, kompiler Anda (atau penerjemah - lakukan dengan python untuk kesederhanaan).

Seperti orang lain, jangan optimalkan secara prematur. Tulis kode yang sangat mudah dibaca, profil jika tidak cukup cepat, dan kemudian coba optimalkan bagian yang lambat. Ingat, kompiler Anda jauh lebih baik dalam optimasi daripada Anda.

dr jimbob
sumber
0

Ada optimisasi yang tidak dapat dilakukan oleh kompiler karena mereka hanya bekerja untuk set input yang berkurang.

Di bawah ini ada kode sampel c ++ yang dapat melakukan pembagian yang lebih cepat dengan melakukan 64bits "Penggandaan oleh timbal balik". Baik pembilang dan penyebut harus di bawah ambang tertentu. Perhatikan bahwa itu harus dikompilasi untuk menggunakan instruksi 64 bit agar benar-benar lebih cepat daripada pembagian normal.

#include <stdio.h>
#include <chrono>

static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;

static unsigned long long s_f;
static unsigned long long s_fr;

static void fastDivInitialize(const unsigned d)
{
    s_f = s_p / d;
    s_fr = s_f * (s_p - (s_f * d));
}

static unsigned fastDiv(const unsigned n)
{
    return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}

static bool fastDivCheck(const unsigned n, const unsigned d)
{
    // 32 to 64 cycles latency on modern cpus
    const unsigned expected = n / d;

    // At least 10 cycles latency on modern cpus
    const unsigned result = fastDiv(n);

    if (result != expected)
    {
        printf("Failed for: %u/%u != %u\n", n, d, expected);
        return false;
    }

    return true;
}

int main()
{
    unsigned result = 0;

    // Make sure to verify it works for your expected set of inputs
    const unsigned MAX_N = 65535;
    const unsigned MAX_D = 40000;

    const double ONE_SECOND_COUNT = 1000000000.0;

    auto t0 = std::chrono::steady_clock::now();
    unsigned count = 0;
    printf("Verifying...\n");
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            count += !fastDivCheck(n, d);
        }
    }
    auto t1 = std::chrono::steady_clock::now();
    printf("Errors: %u / %u (%.4fs)\n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        fastDivInitialize(d);
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += fastDiv(n);
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Fast division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    t0 = t1;
    count = 0;
    for (unsigned d = 1; d <= MAX_D; ++d)
    {
        for (unsigned n = 0; n <= MAX_N; ++n)
        {
            result += n / d;
        }
    }
    t1 = std::chrono::steady_clock::now();
    printf("Normal division time: %.4fs\n", (t1 - t0).count() / ONE_SECOND_COUNT);

    getchar();
    return result;
}
pengguna2044859
sumber
0

Saya pikir dalam satu kasus bahwa Anda ingin mengalikan atau membagi dengan kekuatan dua, Anda tidak bisa salah dengan menggunakan operator bitshift, bahkan jika kompiler mengubahnya menjadi MUL / DIV, karena beberapa prosesor mikrokode (sungguh, sebuah makro) mereka tetap, jadi untuk kasus-kasus Anda akan mencapai peningkatan, terutama jika pergeseran lebih dari 1. Atau lebih eksplisit, jika CPU tidak memiliki operator bitshift, itu akan tetap menjadi MUL / DIV, tetapi jika CPU memiliki operator bitshift, Anda menghindari cabang mikrokode dan ini sedikit instruksi.

Saya menulis beberapa kode sekarang yang membutuhkan banyak operasi penggandaan / separuh karena bekerja pada pohon biner padat, dan ada satu operasi lagi yang saya curigai mungkin lebih optimal daripada penambahan - kiri (kekuatan dua kali lipat ) bergeser dengan tambahan. Ini dapat diganti dengan shift kiri dan xor jika shift lebih lebar dari jumlah bit yang ingin Anda tambahkan, contoh mudahnya adalah (i << 1) ^ 1, yang menambahkan satu ke nilai dua kali lipat. Ini tentu saja tidak berlaku untuk pergeseran kanan (kekuatan dua membagi) karena hanya pergeseran (endian kecil) kiri mengisi kesenjangan dengan nol.

Dalam kode saya, ini mengalikan / membagi dengan dua dan kekuatan dua operasi sangat intensif digunakan dan karena formula sudah cukup singkat, setiap instruksi yang dapat dihilangkan dapat menjadi keuntungan yang substansial. Jika prosesor tidak mendukung operator bitshift ini, tidak ada keuntungan yang akan terjadi tetapi juga tidak akan ada kerugian.

Juga, dalam algoritma yang saya tulis, mereka secara visual mewakili gerakan yang terjadi sehingga dalam arti mereka sebenarnya lebih jelas. Sisi kiri pohon biner lebih besar, dan kanan lebih kecil. Selain itu, dalam kode saya, angka ganjil dan genap memiliki arti khusus, dan semua anak kiri di pohon itu ganjil dan semua anak kanan, dan akarnya, genap. Dalam beberapa kasus, yang belum saya temui, tetapi mungkin, oh, sebenarnya, saya bahkan tidak memikirkan hal ini, x & 1 mungkin merupakan operasi yang lebih optimal dibandingkan dengan x% 2. x & 1 pada bilangan genap akan menghasilkan nol, tetapi akan menghasilkan 1 untuk bilangan ganjil.

Melangkah lebih jauh dari sekadar identifikasi ganjil / genap, jika saya mendapatkan nol untuk x & 3, saya tahu bahwa 4 adalah faktor nomor kami, dan sama untuk x% 7 untuk 8, dan seterusnya. Saya tahu bahwa kasus-kasus ini mungkin memiliki utilitas terbatas tetapi senang mengetahui bahwa Anda dapat menghindari operasi modulus dan menggunakan operasi logika bitwise sebagai gantinya, karena operasi bitwise hampir selalu yang tercepat, dan paling tidak mungkin ambigu dengan kompiler.

Saya cukup banyak menciptakan bidang pohon biner padat jadi saya berharap bahwa orang tidak dapat memahami nilai komentar ini, karena sangat jarang orang ingin hanya melakukan factorisations hanya pada kekuatan dua, atau hanya memperbanyak / membagi kekuatan dua.

Louki Sumirniy
sumber
0

Apakah itu sebenarnya lebih cepat tergantung pada perangkat keras dan kompiler yang sebenarnya digunakan.

Albert van der Horst
sumber
0

Jika Anda membandingkan output untuk x + x, x * 2 dan x << 1 sintaks pada kompiler gcc, maka Anda akan mendapatkan hasil yang sama dalam perakitan x86: https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

Jadi, Anda dapat menganggap gcc sebagai cukup pintar untuk menentukan solusi terbaiknya sendiri terlepas dari apa yang Anda ketikkan.

Buridan
sumber
0

Saya juga ingin melihat apakah saya bisa mengalahkan House. ini adalah bitwise yang lebih umum untuk sembarang angka dengan sembarang nomor perkalian. macro yang saya buat sekitar 25% lebih banyak dua kali lebih lambat dari perkalian * normal. seperti yang dikatakan oleh orang lain jika itu dekat dengan kelipatan 2 atau terdiri dari beberapa kelipatan 2 Anda mungkin menang. seperti X * 23 terdiri dari (X << 4) + (X << 2) + (X << 1) + X akan lebih lambat maka X * 65 terdiri dari (X << 6) + X.

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

#define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0))
#define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0))
int main()
{
    int randomnumber=23;
    int randomnumber2=23;
    int checknum=23;
    clock_t start, diff;
    srand(time(0));
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    int msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYMINUS Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2);
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("MULTIPLYINTBYSHIFT Time %d milliseconds", msec);
    start = clock();
    for(int i=0;i<1000000;i++)
    {
        randomnumber = rand() % 10000;
        randomnumber2 = rand() % 10000;
        checknum= randomnumber*randomnumber2;
        if (checknum!=randomnumber*randomnumber2)
        {
            printf("s %i and %i and %i",checknum,randomnumber,randomnumber2);
        }
    }
    diff = clock() - start;
    msec = diff * 1000 / CLOCKS_PER_SEC;
    printf("normal * Time %d milliseconds", msec);
    return 0;
}
AlexanderLife
sumber