Kecepatan << >> perkalian dan pembagian

Anda dapat menggunakan <<untuk mengalikan dan >>untuk membagi angka dalam python ketika saya mengatur waktu saya menemukan menggunakan cara shift biner melakukannya 10x lebih cepat daripada membagi atau mengalikan cara biasa.

Mengapa menggunakan <<dan >>jauh lebih cepat daripada *dan /?

Apa proses di balik layar yang terjadi *dan /sangat lambat?

Mari kita lihat dua program C kecil yang melakukan sedikit pergeseran dan pembagian.

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int b = i << 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
        int i = atoi(argv[0]);
        int d = i / 4;
}

Ini kemudian masing-masing dikompilasi gcc -Suntuk melihat apa yang akan menjadi majelis yang sebenarnya.

Dengan versi pergeseran bit, dari panggilan ke atoiuntuk kembali:

    callq   _atoi
    movl    $0, %ecx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    shll    $2, %eax
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Sementara versi bagi:

    callq   _atoi
    movl    $0, %ecx
    movl    $4, %edx
    movl    %eax, -20(%rbp)
    movl    -20(%rbp), %eax
    movl    %edx, -28(%rbp)         ## 4-byte Spill
    cltd
    movl    -28(%rbp), %r8d         ## 4-byte Reload
    idivl   %r8d
    movl    %eax, -24(%rbp)
    movl    %ecx, %eax
    addq    $32, %rsp
    popq    %rbp
    ret

Hanya dengan melihat ini ada beberapa instruksi lebih banyak dalam versi membagi dibandingkan dengan pergeseran bit.

Kuncinya adalah apa yang mereka lakukan?

Dalam versi bit shift, instruksi kuncinya adalah shll $2, %eaxshift kiri yang logis - ada pembagiannya, dan yang lainnya hanya memindahkan nilai.

Dalam versi membagi, Anda dapat melihat idivl %r8d- tetapi tepat di atas itu adalah cltd(konversi panjang menjadi dua kali lipat) dan beberapa logika tambahan di sekitar tumpahan dan muat ulang. Pekerjaan tambahan ini, mengetahui bahwa kita berurusan dengan matematika daripada bit sering diperlukan untuk menghindari berbagai kesalahan yang dapat terjadi dengan hanya melakukan sedikit matematika.

Mari kita lakukan beberapa perkalian cepat:

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int b = i >> 2;
}

#include <stdlib.h>

int main(int argc, char* argv[]) {
    int i = atoi(argv[0]);
    int d = i * 4;
}

Daripada melewati semua ini, ada satu baris yang berbeda:

$ diff mult.s bit.s
24c24
> shll $ 2,% eax
---
<sarl $ 2,% eax

Di sini kompiler dapat mengidentifikasi bahwa matematika dapat dilakukan dengan pergeseran, namun alih-alih perubahan logis itu melakukan perubahan aritmatika. Perbedaan antara ini akan jelas jika kita menjalankan ini - sarlmempertahankan tanda. Sehingga -2 * 4 = -8sementara shllitu tidak.

Mari kita lihat ini dalam skrip perl cepat:

#!/usr/bin/perl

$foo = 4;
print $foo << 2, "\n";
print $foo * 4, "\n";

$foo = -4;
print $foo << 2, "\n";
print $foo * 4, "\n";

Keluaran:

16
16
18446744073709551600
-16

Um ... -4 << 2adalah 18446744073709551600yang tidak persis seperti yang Anda harapkan saat berhadapan dengan perkalian dan pembagian. Benar, tapi itu bukan perkalian bilangan bulat.

Dan dengan demikian waspada terhadap optimasi prematur. Biarkan kompiler mengoptimalkan untuk Anda - ia tahu apa yang sebenarnya Anda coba lakukan dan kemungkinan akan melakukan pekerjaan yang lebih baik, dengan lebih sedikit bug.

Jawaban yang ada tidak benar-benar membahas sisi perangkat keras, jadi inilah yang sedikit berbeda. Kebijaksanaan konvensional adalah bahwa multiplikasi dan pembagian jauh lebih lambat daripada pergeseran, tetapi kisah aktual saat ini lebih bernuansa.

Sebagai contoh, memang benar bahwa perkalian adalah operasi yang lebih kompleks untuk diimplementasikan dalam perangkat keras, tetapi tidak selalu selalu lebih lambat . Ternyata, addjuga jauh lebih kompleks untuk diimplementasikan daripada xor(atau secara umum operasi bitwise), tetapi add(dan sub) biasanya mendapatkan cukup transistor yang didedikasikan untuk operasi mereka yang akhirnya sama cepatnya dengan operator bitwise. Jadi Anda tidak bisa hanya melihat kompleksitas implementasi perangkat keras sebagai panduan untuk kecepatan.

Jadi mari kita lihat secara detail pada operator shifting versus operator "penuh" seperti multiplikasi dan shifting.

Bergeser

Pada hampir semua perangkat keras, perpindahan dengan jumlah konstan (yaitu, jumlah yang dapat ditentukan oleh kompiler pada waktu kompilasi) adalah cepat . Secara khusus, biasanya akan terjadi dengan latensi satu siklus, dan dengan throughput 1 per siklus atau lebih baik. Pada beberapa perangkat keras (misalnya, beberapa chip Intel dan ARM), pergeseran tertentu dengan konstanta bahkan mungkin "bebas" karena dapat dibangun ke dalam instruksi lain ( leapada Intel, kemampuan pengalihan khusus dari sumber pertama dalam ARM).

Bergeser dengan jumlah variabel lebih merupakan area abu-abu. Pada perangkat keras lama, ini kadang-kadang sangat lambat, dan kecepatan berubah dari generasi ke generasi. Sebagai contoh, pada rilis awal P4 Intel, perpindahan dengan jumlah variabel terkenal lambat - membutuhkan waktu yang sebanding dengan jumlah pergeseran! Pada platform itu, menggunakan multiplikasi untuk menggantikan shift bisa menguntungkan (yaitu, dunia telah terbalik). Pada chip Intel sebelumnya, serta generasi berikutnya, bergeser dengan jumlah variabel tidak begitu menyakitkan.

Pada chip Intel saat ini, beralih dengan jumlah variabel tidak terlalu cepat, tetapi juga tidak buruk. Arsitektur x86 adalah sembelih ketika datang ke perubahan variabel, karena mereka mendefinisikan operasi dengan cara yang tidak biasa: menggeser jumlah 0 tidak mengubah flag kondisi, tetapi semua shift lainnya melakukannya. Ini menghambat penggantian nama yang efisien dari register bendera karena tidak dapat ditentukan sampai shift mengeksekusi apakah instruksi selanjutnya harus membaca kode kondisi yang ditulis oleh shift, atau beberapa instruksi sebelumnya. Lebih jauh, shift hanya menulis ke bagian register bendera, yang dapat menyebabkan kios bendera parsial.

Hasilnya adalah bahwa pada arsitektur Intel baru-baru ini, pergeseran dengan jumlah variabel membutuhkan tiga "operasi mikro" sementara sebagian besar operasi sederhana lainnya (tambahkan, operasi bitwise, bahkan penggandaan) hanya mengambil 1. Pergeseran tersebut dapat dijalankan paling banyak sekali setiap 2 siklus .

Perkalian

Tren perangkat keras desktop dan laptop modern adalah membuat operasi perkalian menjadi cepat. Pada chip Intel dan AMD baru-baru ini, pada kenyataannya, satu perkalian dapat dikeluarkan setiap siklus (kami menyebut throughput timbal balik ini ). Namun latensi dari penggandaan adalah 3 siklus. Jadi itu berarti Anda mendapatkan hasil dari setiap siklus perkalian 3 yang diberikan setelah Anda memulainya, tetapi Anda bisa memulai perkalian baru setiap siklus. Nilai mana (1 siklus atau 3 siklus) yang lebih penting tergantung pada struktur algoritma Anda. Jika multiplikasi adalah bagian dari rantai ketergantungan kritis, latensi itu penting. Jika tidak, throughput timbal balik atau faktor lainnya mungkin lebih penting.

Kunci utama yang dapat diambil adalah bahwa pada chip laptop modern (atau lebih baik), perkalian adalah operasi yang cepat, dan cenderung lebih cepat daripada urutan instruksi 3 atau 4 yang akan dikeluarkan oleh kompiler untuk "mendapatkan pembulatan" yang tepat untuk shift yang dikurangi dengan kekuatan. Untuk perubahan variabel, pada Intel, perkalian juga umumnya lebih disukai karena masalah yang disebutkan di atas.

Pada platform faktor bentuk yang lebih kecil, perkalian mungkin masih lebih lambat, karena membangun pengganda 32-bit penuh dan cepat atau terutama 64-bit membutuhkan banyak transistor dan daya. Jika seseorang dapat mengisi dengan rincian kinerja multiply pada chip ponsel baru-baru ini, itu akan sangat dihargai.

Membagi

Divide adalah operasi yang lebih kompleks, perangkat keras, daripada perkalian dan juga jauh lebih jarang terjadi dalam kode aktual - yang berarti bahwa lebih sedikit sumber daya yang kemungkinan dialokasikan untuk itu. Tren chip modern masih mengarah ke pembagi yang lebih cepat, tetapi bahkan chip modern modern memerlukan 10-40 siklus untuk melakukan pembagian, dan mereka hanya sebagian disalurkan melalui pipa. Secara umum, 64-bit membagi bahkan lebih lambat dari 32-bit membagi. Tidak seperti kebanyakan operasi lain, divisi dapat mengambil sejumlah siklus variabel tergantung pada argumen.

Hindari membagi dan ganti dengan shift (atau biarkan kompiler melakukannya, tetapi Anda mungkin perlu memeriksa perakitan) jika Anda bisa!

BINARY_LSHIFT dan BINARY_RSHIFT adalah proses yang lebih sederhana secara algoritmik daripada BINARY_MULTIPLY dan BINARY_FLOOR_DIVIDE dan mungkin memerlukan lebih sedikit siklus clock. Itu adalah jika Anda memiliki nomor biner dan perlu bithift oleh N, yang harus Anda lakukan adalah menggeser digit di atas banyak ruang dan menggantinya dengan nol. Penggandaan biner pada umumnya lebih rumit , meskipun teknik seperti pengganda Dadda membuatnya cukup cepat.

Memang, adalah mungkin bagi kompiler pengoptimal untuk mengenali kasus ketika Anda mengalikan / membagi dengan kekuatan dua dan menggantinya dengan pergeseran kiri / kanan yang sesuai. Dengan melihat kode byte python yang dibongkar ternyata tidak melakukan ini:

>>> dis.dis(lambda x: x*4)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (4)
              6 BINARY_MULTIPLY     
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x<<2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_LSHIFT       
              7 RETURN_VALUE        


>>> dis.dis(lambda x: x//2)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (2)
              6 BINARY_FLOOR_DIVIDE 
              7 RETURN_VALUE        

>>> dis.dis(lambda x: x>>1)
  1           0 LOAD_FAST                0 (x)
              3 LOAD_CONST               1 (1)
              6 BINARY_RSHIFT       
              7 RETURN_VALUE        

Namun, pada prosesor saya, saya menemukan multiplikasi dan shift kiri / kanan memiliki timing yang sama, dan pembagian lantai (dengan kekuatan dua) sekitar 25% lebih lambat:

>>> import timeit

>>> timeit.repeat("z=a + 4", setup="a = 37")
[0.03717184066772461, 0.03291916847229004, 0.03287005424499512]

>>> timeit.repeat("z=a - 4", setup="a = 37")
[0.03534698486328125, 0.03207516670227051, 0.03196907043457031]

>>> timeit.repeat("z=a * 4", setup="a = 37")
[0.04594111442565918, 0.0408930778503418, 0.045324087142944336]

>>> timeit.repeat("z=a // 4", setup="a = 37")
[0.05412912368774414, 0.05091404914855957, 0.04910898208618164]

>>> timeit.repeat("z=a << 2", setup="a = 37")
[0.04751706123352051, 0.04259490966796875, 0.041903018951416016]

>>> timeit.repeat("z=a >> 2", setup="a = 37")
[0.04719185829162598, 0.04201006889343262, 0.042105913162231445]