Kode C ++ untuk menguji dugaan Collatz lebih cepat dari perakitan tulisan tangan - mengapa?

833

Saya menulis dua solusi ini untuk Project Euler Q14 , dalam perakitan dan dalam C ++. Mereka adalah pendekatan brute force yang sama identik untuk menguji dugaan Collatz . Solusi perakitan dirakit dengan

nasm -felf64 p14.asm && gcc p14.o -o p14

C ++ dikompilasi dengan

g++ p14.cpp -o p14

Majelis, p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp

#include <iostream>

using namespace std;

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n*3 + 1;

        ++count;
    }

    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }

    cout << maxi << endl;
}

Saya tahu tentang optimisasi kompiler untuk meningkatkan kecepatan dan segalanya, tetapi saya tidak melihat banyak cara untuk mengoptimalkan solusi perakitan saya lebih lanjut (berbicara secara terprogram bukan matematis).

Kode C ++ memiliki modulus setiap istilah dan pembagian setiap istilah genap, di mana perakitan hanya satu divisi per istilah genap.

Tetapi perakitan mengambil rata-rata 1 detik lebih lama dari solusi C ++. Kenapa ini? Saya bertanya terutama karena rasa ingin tahu.

Waktu eksekusi

Sistem saya: 64 bit Linux pada 1.4 GHz Intel Celeron 2955U (Haswell microarchitecture).

meniduri putra
sumber
232
Sudahkah Anda memeriksa kode rakitan yang dihasilkan GCC untuk program C ++ Anda?
ruakh
69
Kompilasi dengan -Suntuk mendapatkan perakitan yang dihasilkan oleh kompiler. Kompiler cukup pintar untuk menyadari bahwa modulus melakukan pembagian pada saat yang sama.
user3386109
267
Saya pikir pilihan Anda adalah 1. Teknik pengukuran Anda cacat, 2. Kompiler menulis perakitan yang lebih baik yang Anda, atau 3. Kompiler menggunakan sihir.
Galik
17
Hasilkan asm dengan kode C + nomor baris antar-anyaman dan bandingkan catatan.
legends2k
18
@jefferson Kompiler dapat menggunakan brute force yang lebih cepat. Misalnya mungkin dengan instruksi SSE.
user253751

Jawaban:

1896

Jika Anda berpikir instruksi DIV 64-bit adalah cara yang baik untuk membaginya dengan dua, maka tidak heran output kompiler mengalahkan kode tulisan tangan Anda, bahkan dengan -O0(kompilasi cepat, tanpa optimasi tambahan, dan simpan / muat ulang ke memori setelah / sebelum setiap pernyataan C sehingga debugger dapat memodifikasi variabel).

Lihat panduan Perakitan Mengoptimalkan Agner Fog untuk mempelajari cara menulis asm efisien. Dia juga memiliki tabel instruksi dan panduan microarch untuk detail spesifik untuk CPU tertentu. Lihat juga beri tag wiki untuk lebih banyak tautan perf.

Lihat juga pertanyaan yang lebih umum tentang mengalahkan compiler dengan asm yang ditulis tangan: Apakah bahasa assembly inline lebih lambat daripada kode C ++ asli? . TL: DR: ya jika Anda salah melakukannya (seperti pertanyaan ini).

Biasanya Anda baik-baik saja membiarkan kompiler melakukan tugasnya, terutama jika Anda mencoba menulis C ++ yang dapat dikompilasi secara efisien . Lihat juga apakah perakitan lebih cepat daripada bahasa yang dikompilasi? . Salah satu tautan jawaban ke slide rapi ini menunjukkan bagaimana berbagai kompiler C mengoptimalkan beberapa fungsi yang sangat sederhana dengan trik keren. Pembicaraan CppCon2017 Matt Godbolt akhir-akhir ini, “ Apa yang Telah Dilakukan Penyusun Saya untuk Saya? Membuka kunci Tutup Pengumpul ”dengan nada yang sama.


even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

Pada Intel Haswell, div r64adalah 36 uops, dengan latensi 32-96 siklus , dan throughput satu per 21-74 siklus. (Ditambah 2 uops untuk mengatur RBX dan nol RDX, tetapi eksekusi out-of-order dapat menjalankannya lebih awal). Instruksi penghitungan-tinggi seperti DIV di-mikrokodekan, yang juga dapat menyebabkan kemacetan front-end. Dalam hal ini, latensi adalah faktor yang paling relevan karena merupakan bagian dari rantai ketergantungan yang digerakkan oleh loop.

shr rax, 1melakukan pembagian unsigned yang sama: Ini 1 uop, dengan latensi 1c , dan dapat menjalankan 2 siklus per jam.

Sebagai perbandingan, pembagian 32-bit lebih cepat, tetapi masih mengerikan vs bergeser. idiv r32adalah 9 uops, 22-29c latency, dan satu per 8-11c throughput di Haswell.


Seperti yang Anda lihat dari melihat -O0output asm gcc ( Godbolt compiler explorer ), ia hanya menggunakan instruksi shift . dentang -O0memang mengkompilasi secara naif seperti yang Anda pikirkan, bahkan menggunakan IDIV 64-bit dua kali. (Ketika mengoptimalkan, kompiler memang menggunakan kedua output IDIV ketika sumber melakukan pembagian dan modulus dengan operan yang sama, jika mereka menggunakan IDIV sama sekali)

GCC tidak memiliki mode yang sepenuhnya naif; selalu berubah melalui GIMPLE, yang berarti beberapa "optimisasi" tidak dapat dinonaktifkan . Ini termasuk mengenali pembagian-demi-konstan dan menggunakan shift (kekuatan 2) atau invers multiplikasi titik tetap (bukan kekuatan 2) untuk menghindari IDIV (lihat div_by_13di tautan godbolt di atas).

gcc -Os(optimalkan untuk ukuran) memang menggunakan IDIV untuk divisi non-power-of-2, sayangnya bahkan dalam kasus-kasus di mana kode inversi multiplikasi hanya sedikit lebih besar tetapi jauh lebih cepat.


Membantu kompiler

(ringkasan untuk kasus ini: gunakan uint64_t n)

Pertama-tama, hanya menarik untuk melihat output kompiler yang dioptimalkan. ( -O3). -O0kecepatan pada dasarnya tidak ada artinya.

Lihatlah output asm Anda (pada Godbolt, atau lihat Bagaimana menghapus "noise" dari GCC / output rakitan? ). Ketika kompiler tidak membuat kode optimal di tempat pertama: Menulis sumber C / C ++ Anda dengan cara yang memandu kompiler membuat kode yang lebih baik biasanya merupakan pendekatan terbaik . Anda harus tahu ASM, dan tahu apa yang efisien, tetapi Anda menerapkan pengetahuan ini secara tidak langsung. Compiler juga merupakan sumber ide yang bagus: kadang-kadang dentang akan melakukan sesuatu yang keren, dan Anda dapat menahan gcc untuk melakukan hal yang sama: lihat jawaban ini dan apa yang saya lakukan dengan loop yang tidak terbuka dalam kode @ Veedrac di bawah.)

Pendekatan ini portabel, dan dalam 20 tahun beberapa kompiler masa depan dapat mengkompilasinya ke apa pun yang efisien pada perangkat keras masa depan (x86 atau tidak), mungkin menggunakan ekstensi ISA baru atau auto-vektorisasi. Tulisan tangan x86-64 asm dari 15 tahun yang lalu biasanya tidak akan optimal untuk Skylake. misal bandingkan & cabang-fusi makro tidak ada saat itu. Apa yang optimal sekarang untuk asm kerajinan tangan untuk satu mikroarsitektur mungkin tidak optimal untuk CPU lainnya saat ini dan di masa depan. Komentar pada jawaban @ johnfound membahas perbedaan besar antara AMD Bulldozer dan Intel Haswell, yang memiliki pengaruh besar pada kode ini. Namun secara teori, g++ -O3 -march=bdver3dan g++ -O3 -march=skylakeakan melakukan hal yang benar. (Atau -march=native.) Atau -mtune=...hanya menyetel, tanpa menggunakan instruksi yang mungkin tidak didukung oleh CPU lain.

Perasaan saya adalah bahwa membimbing kompiler ke asm itu bagus untuk CPU saat ini yang Anda pedulikan seharusnya tidak menjadi masalah bagi kompiler masa depan. Mereka diharapkan lebih baik daripada kompiler saat ini dalam menemukan cara untuk mengubah kode, dan dapat menemukan cara yang bekerja untuk CPU di masa depan. Apapun, x86 masa depan mungkin tidak akan mengerikan pada apa pun yang baik pada x86 saat ini, dan kompiler masa depan akan menghindari jebakan asm-spesifik saat mengimplementasikan sesuatu seperti pergerakan data dari sumber C Anda, jika tidak melihat sesuatu yang lebih baik.

ASM tulisan tangan adalah kotak hitam untuk pengoptimal, jadi propagasi konstan tidak berfungsi saat inlining menjadikan input konstanta waktu kompilasi. Optimalisasi lainnya juga terpengaruh. Baca https://gcc.gnu.org/wiki/DontUseInlineAsm sebelum menggunakan asm. (Dan hindari asline inline gaya MSVC: input / output harus melalui memori yang menambah overhead .)

Dalam hal ini : Anda nmemiliki tipe yang ditandatangani, dan gcc menggunakan urutan SAR / SHR / ADD yang memberikan pembulatan yang benar. (IDIV dan "putaran" pergeseran-aritmatika berbeda untuk input negatif, lihat SAR dan masukkan entri manual ref ). (IDK jika gcc mencoba dan gagal membuktikan bahwa itu ntidak boleh negatif, atau apa. Signed-overflow adalah perilaku yang tidak terdefinisi, jadi seharusnya bisa.)

Anda seharusnya sudah menggunakannya uint64_t n, jadi bisa saja SHR. Dan itu portabel untuk sistem di mana longhanya 32-bit (misalnya x86-64 Windows).


BTW, output asm yang dioptimalkan gcc terlihat cukup baik (menggunakan )unsigned long n : loop internal itu main()melakukan hal ini:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

Loop dalam tidak memiliki cabang, dan jalur kritis dari rantai ketergantungan loop-carry adalah:

  • 3 komponen LEA (3 siklus)
  • cmov (2 siklus di Haswell, 1c di Broadwell atau lebih baru).

Total: 5 siklus per iterasi, hambatan latensi . Eksekusi out-of-order menangani semua hal lain secara paralel dengan ini (dalam teori: Saya belum menguji dengan counter perf untuk melihat apakah itu benar-benar berjalan pada 5c / iter).

Input FLAGS dari cmov(diproduksi oleh TEST) lebih cepat untuk diproduksi daripada input RAX (dari LEA-> MOV), jadi itu bukan di jalur kritis.

Demikian pula, MOV-> SHR yang menghasilkan input RDI CMOV berada di luar jalur kritis, karena juga lebih cepat daripada LEA. MOV di IvyBridge dan yang lebih baru memiliki latensi nol (ditangani saat register-rename). (Masih membutuhkan uop, dan slot di pipeline, jadi tidak gratis, hanya nol latensi). MOV ekstra dalam rantai depa LEA adalah bagian dari hambatan pada CPU lain.

Cmp / jne juga bukan bagian dari jalur kritis: ini bukan loop-carry, karena dependensi kontrol ditangani dengan prediksi cabang + eksekusi spekulatif, tidak seperti dependensi data pada jalur kritis.


Mengalahkan kompiler

GCC melakukan pekerjaan yang cukup bagus di sini. Itu bisa menyimpan satu byte kode dengan menggunakan inc edxalih-alihadd edx, 1 , karena tidak ada yang peduli tentang P4 dan dependensi-salahnya untuk instruksi memodifikasi flag parsial.

Itu juga bisa menyimpan semua instruksi MOV, dan TEST: SHR mengeset CF = bitnya digeser, jadi kita bisa menggunakan cmovcalih-alih test/ cmovz.

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

Lihat jawaban @ johnfound untuk trik pintar lainnya: hapus CMP dengan bercabang pada hasil flag SHR serta menggunakannya untuk CMOV: nol hanya jika n adalah 1 (atau 0) untuk memulai. (Fakta asyik : SHR dengan hitungan! = 1 di Nehalem atau sebelumnya menyebabkan kemacetan jika Anda membaca hasil flag . Begitulah cara mereka membuatnya menjadi satu-uop. Namun, pengodean khusus shift-by-1 baik-baik saja.)

Menghindari MOV sama sekali tidak membantu latensi di Haswell ( Bisakah MOV x86 benar-benar "bebas"? Mengapa saya tidak bisa mereproduksi ini sama sekali? ). Itu membantu secara signifikan pada CPU seperti Intel pre-IvB, dan keluarga AMD Bulldozer, di mana MOV bukan nol-latensi. Instruksi MOV yang terbuang dari kompiler mempengaruhi jalan kritis Kompleks BD-LEA dan CMOV keduanya memiliki latensi yang lebih rendah (masing-masing 2c dan 1c), jadi ini adalah fraksi yang lebih besar dari latensi. Juga, bottleneck throughput menjadi masalah, karena hanya memiliki dua pipa ALU integer. Lihat jawaban @ johnfound , di mana ia mendapatkan hasil timing dari CPU AMD.

Bahkan di Haswell, versi ini dapat sedikit membantu dengan menghindari beberapa penundaan di mana uop yang tidak kritis mencuri port eksekusi dari port yang ada di jalur kritis, menunda eksekusi dengan 1 siklus. (Ini disebut konflik sumber daya). Ini juga menyimpan register, yang dapat membantu ketika melakukan beberapa nnilai secara paralel dalam satu loop yang disisipkan (lihat di bawah).

Latensi LEA tergantung pada mode pengalamatan , pada CPU Intel SnB-family. 3c untuk 3 komponen ( [base+idx+const], yang membutuhkan dua tambahan terpisah), tetapi hanya 1c dengan 2 atau lebih sedikit komponen (satu tambahan). Beberapa CPU (seperti Core2) bahkan melakukan 3 komponen LEA dalam satu siklus, tetapi SnB-family tidak. Lebih buruk lagi, keluarga Intel SnB menstandarisasi latensi sehingga tidak ada 2c uops , jika tidak, LEA 3 komponen hanya akan 2c seperti Bulldozer. (LEA 3 komponen lebih lambat pada AMD juga, hanya saja tidak sebanyak).

Jadi lea rcx, [rax + rax*2]/ inc rcxhanya latensi 2c, lebih cepat daripada lea rcx, [rax + rax*2 + 1], pada CPU Intel SnB-family seperti Haswell. Break-even di BD, dan lebih buruk di Core2. Memang membutuhkan biaya tambahan, yang biasanya tidak layak untuk menyimpan latensi 1c, tetapi latensi adalah hambatan utama di sini dan Haswell memiliki saluran pipa yang cukup luas untuk menangani throughput tambahan uop.

Baik gcc, icc, atau clang (on godbolt) menggunakan output CF SHR, selalu menggunakan AND atau TEST . Kompiler konyol. : P Mereka adalah mesin-mesin rumit yang hebat, tetapi manusia yang pandai seringkali dapat mengalahkan mereka dalam masalah skala kecil. (Diberikan ribuan hingga jutaan kali lebih lama untuk memikirkannya, tentu saja! Kompiler tidak menggunakan algoritma lengkap untuk mencari setiap cara yang mungkin untuk melakukan sesuatu, karena itu akan memakan waktu terlalu lama ketika mengoptimalkan banyak kode inline, yang adalah apa mereka melakukan yang terbaik. Mereka juga tidak memodelkan pipa dalam mikroarsitektur target, setidaknya tidak dalam detail yang sama seperti IACA atau alat analisis statis lainnya; mereka hanya menggunakan beberapa heuristik.)


Buka gulungan sederhana tidak akan membantu ; bottleneck loop ini pada latensi rantai ketergantungan loop-carry, bukan pada overhead loop / throughput. Ini berarti akan lebih baik jika menggunakan hyperthreading (atau jenis SMT lainnya), karena CPU memiliki banyak waktu untuk menyisipkan instruksi dari dua utas. Ini berarti memparalelkan loop ke dalam main, tapi itu tidak masalah karena setiap thread dapat memeriksa rentang nnilai dan menghasilkan sepasang integer sebagai hasilnya.

Interleaving dengan tangan dalam satu utas mungkin juga bisa dilakukan . Mungkin menghitung urutan untuk sepasang angka secara paralel, karena masing-masing hanya membutuhkan pasangan register, dan mereka semua dapat memperbarui yang sama max/ maxi. Ini menciptakan paralelisme tingkat instruksi yang lebih banyak .

Triknya adalah memutuskan apakah akan menunggu sampai semua nnilai telah tercapai 1sebelum mendapatkan pasangan lain dari nnilai awal , atau apakah akan keluar dan mendapatkan titik awal baru untuk hanya satu yang mencapai kondisi akhir, tanpa menyentuh register untuk urutan lainnya. Mungkin yang terbaik adalah menjaga setiap rantai bekerja pada data yang berguna, jika tidak Anda harus meningkatkan penghitungnya secara kondisional.


Anda mungkin bahkan dapat melakukan ini dengan hal-hal yang dibungkus-bandingkan SSE untuk meningkatkan penghitung untuk elemen vektor di mana nbelum tercapai 1. Dan untuk menyembunyikan latensi yang lebih lama dari implementasi kenaikan-kondisional SIMD, Anda harus menjaga lebih banyak vektor nnilai di udara. Mungkin hanya bernilai dengan vektor 256b (4x uint64_t).

Saya pikir strategi terbaik untuk membuat deteksi 1"lengket" adalah dengan menutupi vektor semua yang Anda tambahkan untuk menambah penghitung. Jadi setelah Anda melihat 1sebuah elemen, vektor-kenaikan akan memiliki nol, dan + = 0 adalah no-op.

Gagasan yang belum diuji untuk vektorisasi manual

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

Anda dapat dan harus menerapkan ini dengan intrinsik alih-alih asm yang ditulis tangan.


Peningkatan algoritma / implementasi:

Selain hanya menerapkan logika yang sama dengan asm yang lebih efisien, cari cara untuk menyederhanakan logika, atau menghindari pekerjaan yang berlebihan. mis. memoize untuk mendeteksi akhiran umum untuk urutan. Atau bahkan lebih baik, lihat 8 bit tambahan sekaligus (jawaban gnasher)

@ EOF menunjukkan bahwa tzcnt(atau bsf) dapat digunakan untuk melakukan beberapa n/=2iterasi dalam satu langkah. Itu mungkin lebih baik daripada vektorisasi SIMD; tidak ada instruksi SSE atau AVX yang dapat melakukannya. Ini masih kompatibel dengan melakukan beberapa skalar nsecara paralel di register integer yang berbeda.

Jadi lingkarannya mungkin terlihat seperti ini:

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

Ini mungkin melakukan iterasi yang jauh lebih sedikit, tetapi perubahan jumlah variabel lambat pada CPU Intel SnB-family tanpa BMI2. 3 uops, 2c latency. (Mereka memiliki ketergantungan input pada FLAGS karena hitungan = 0 berarti bendera tidak dimodifikasi. Mereka menangani ini sebagai ketergantungan data, dan mengambil beberapa uops karena uop hanya dapat memiliki 2 input (toh HSW / BDW tetap)). Ini adalah jenis yang dikeluhkan orang tentang desain crazy-CISC x86. Itu membuat CPU x86 lebih lambat dari yang seharusnya jika ISA dirancang dari awal hari ini, bahkan dengan cara yang hampir sama. (Yaitu ini adalah bagian dari "pajak x86" yang membutuhkan kecepatan / daya.) SHRX / SHLX / SARX (BMI2) adalah kemenangan besar (latensi 1 uop / 1c).

Ini juga menempatkan tzcnt (3c di Haswell dan yang lebih baru) di jalur kritis, sehingga secara signifikan memperpanjang latensi total rantai ketergantungan loop-carry. Itu menghilangkan kebutuhan untuk CMOV, atau untuk mempersiapkan holding register n>>1. @ Veedrac menjawab semua ini dengan menunda tzcnt / shift untuk beberapa iterasi, yang sangat efektif (lihat di bawah).

Kita dapat menggunakan BSF atau TZCNT dengan aman secara bergantian, karena ntidak pernah bisa nol pada saat itu. Kode mesin TZCNT mendekode sebagai BSF pada CPU yang tidak mendukung BMI1. (Awalan tanpa arti diabaikan, jadi REP BSF berjalan sebagai BSF).

TZCNT berkinerja jauh lebih baik daripada BSF pada CPU AMD yang mendukungnya, jadi itu bisa menjadi ide yang baik untuk digunakan REP BSF, bahkan jika Anda tidak peduli tentang pengaturan ZF jika inputnya nol daripada output. Beberapa kompiler melakukan ini saat Anda menggunakannya __builtin_ctzllbahkan dengan -mno-bmi.

Mereka melakukan hal yang sama pada CPU Intel, jadi simpan saja byte jika itu yang terpenting. TZCNT pada Intel (pra-Skylake) masih memiliki ketergantungan salah pada operan output yang seharusnya hanya ditulis, seperti BSF, untuk mendukung perilaku tidak berdokumen bahwa BSF dengan input = 0 membuat tujuannya tidak dimodifikasi. Jadi Anda perlu mengatasinya kecuali hanya mengoptimalkan untuk Skylake, jadi tidak ada untungnya dari byte REP tambahan. (Intel sering melampaui apa yang disyaratkan manual x86 ISA, untuk menghindari pemecahan kode yang digunakan secara luas yang bergantung pada sesuatu yang seharusnya tidak ada, atau yang tidak berlaku surut. Misalnya Windows 9x mengasumsikan tidak ada pengambilan prefetching spekulatif dari entri TLB , yang aman ketika kode ditulis, sebelum Intel memperbarui aturan manajemen TLB .)

Bagaimanapun, LZCNT / TZCNT di Haswell memiliki dep false yang sama dengan POPCNT: lihat T&J ini . Inilah sebabnya mengapa dalam asm output gcc untuk kode @ Veedrac, Anda melihatnya melanggar rantai dep dengan xor-zeroing pada register yang akan digunakan sebagai tujuan TZCNT ketika tidak menggunakan dst = src. Karena TZCNT / LZCNT / POPCNT tidak pernah meninggalkan tujuannya tidak terdefinisi atau tidak dimodifikasi, ketergantungan salah ini pada output pada CPU Intel adalah bug kinerja / pembatasan. Agaknya itu layak beberapa transistor / kekuatan untuk memiliki mereka berperilaku seperti uops lain yang pergi ke unit eksekusi yang sama. Satu-satunya kelebihan adalah interaksi dengan batasan uarch lain: mereka dapat micro-fuse operan memori dengan mode pengalamatan terindeks pada Haswell, tetapi pada Skylake di mana Intel menghapus dep false untuk LZCNT / TZCNT mereka "un-laminate" mode pengalamatan terindeks sementara POPCNT masih dapat melebur mikro setiap mode addr.


Perbaikan ide / kode dari jawaban lain:

@ hidefromkgb's jawaban memiliki pengamatan yang bagus bahwa Anda dijamin dapat melakukan satu shift tepat setelah 3n +1. Anda dapat menghitung ini bahkan lebih efisien daripada hanya meninggalkan cek di antara langkah-langkah. Implementasi asm dalam jawaban itu rusak, (tergantung pada OF, yang tidak didefinisikan setelah SHRD dengan hitungan> 1), dan lambat: ROR rdi,2lebih cepat dari SHRD rdi,rdi,2, dan menggunakan dua instruksi CMOV pada jalur kritis lebih lambat daripada TEST tambahan yang bisa berjalan secara paralel.

Saya menaruh Tidied / peningkatan C (yang memandu kompiler untuk menghasilkan asm yang lebih baik), dan menguji + bekerja lebih cepat asm (dalam komentar di bawah C) di Godbolt: lihat tautan di jawaban @ hidefromkgb . (Jawaban ini mencapai batas ar 30k dari URL Godbolt yang besar, tetapi tautan pendek dapat membusuk dan terlalu panjang untuk goo.gl.)

Juga meningkatkan hasil pencetakan untuk mengkonversi ke string dan membuat satu write()alih-alih menulis satu karakter sekaligus. Ini meminimalkan dampak pada waktu seluruh program dengan perf stat ./collatz(untuk merekam penghitung kinerja), dan saya menghilangkan beberapa asm non-kritis.


@ Kode Veedrac

Saya mendapat speedup minor dari menggeser ke kanan sebanyak yang kita tahu perlu lakukan, dan memeriksa untuk melanjutkan loop. Dari 7,5 untuk batas = 1e8 ke 7,275, pada Core2Duo (Merom), dengan faktor membuka gulungan 16.

kode + komentar di Godbolt . Jangan gunakan versi ini dengan dentang; ia melakukan sesuatu yang konyol dengan defer-loop. Menggunakan penghitung tmp kdan kemudian menambahkannya untuk countkemudian mengubah apa yang dilakukan dentang, tapi itu sedikit menyakitkan gcc.

Lihat diskusi dalam komentar: Kode Veedrac sangat baik pada CPU dengan BMI1 (yaitu bukan Celeron / Pentium)

Peter Cordes
sumber
4
Saya sudah mencoba pendekatan vektor beberapa waktu lalu, itu tidak membantu (karena Anda dapat melakukan jauh lebih baik dalam kode skalar dengan tzcntdan Anda terkunci ke urutan terpanjang di antara elemen-elemen vektor Anda dalam kasus vektor).
EOF
3
@ EOF: tidak, maksud saya keluar dari loop dalam ketika salah satu elemen vektor hits 1, bukan ketika mereka semua memiliki (mudah terdeteksi dengan PCMPEQ / PMOVMSK). Kemudian Anda menggunakan PINSRQ dan hal-hal untuk mengutak-atik satu elemen yang diakhiri (dan penghitungnya), dan melompat kembali ke loop. Itu bisa dengan mudah berubah menjadi kerugian, ketika Anda terlalu sering keluar dari lingkaran dalam, tetapi itu berarti Anda selalu mendapatkan 2 atau 4 elemen pekerjaan yang berguna dilakukan setiap iterasi dari loop dalam. Poin bagus tentang memoisasi.
Peter Cordes
4
@jefferson Best yang saya kelola adalah godbolt.org/g/1N70Ib . Saya berharap saya bisa melakukan sesuatu yang lebih pintar, tetapi sepertinya tidak.
Veedrac
87
Hal yang mengherankan saya tentang jawaban yang luar biasa seperti ini adalah pengetahuan yang ditunjukkan dengan detail seperti itu. Saya tidak akan pernah tahu bahasa atau sistem ke tingkat itu dan saya tidak akan tahu caranya. Bagus, tuan.
camden_kid
8
Jawaban legendaris !!
Sumit Jain
104

Mengklaim bahwa kompiler C ++ dapat menghasilkan kode yang lebih optimal daripada programmer bahasa assembly yang kompeten adalah kesalahan yang sangat buruk. Dan khususnya dalam hal ini. Manusia selalu dapat membuat kode lebih baik daripada yang dapat dilakukan oleh kompiler, dan situasi khusus ini adalah ilustrasi yang baik untuk klaim ini.

Perbedaan waktu yang Anda lihat adalah karena kode rakitan dalam pertanyaan sangat jauh dari optimal di loop batin.

(Kode di bawah ini adalah 32-bit, tetapi dapat dengan mudah dikonversi menjadi 64-bit)

Misalnya, fungsi urutan hanya dapat dioptimalkan ke 5 instruksi:

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

Seluruh kode terlihat seperti:

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

Untuk mengkompilasi kode ini, FreshLib diperlukan.

Dalam pengujian saya, (prosesor 1 GHz AMD A4-1200), kode di atas kira-kira empat kali lebih cepat dari kode C ++ dari pertanyaan (ketika dikompilasi dengan -O0: 430 ms vs 1900 ms), dan lebih dari dua kali lebih cepat (430 ms vs 830 ms) ketika kode C ++ dikompilasi dengan -O3.

Output dari kedua program adalah sama: max sequence = 525 on i = 837799.

Johnfound
sumber
6
Hah, itu pintar. SHR menetapkan ZF hanya jika EAX adalah 1 (atau 0). Saya melewatkan hal itu ketika mengoptimalkan -O3output gcc , tetapi saya melihat semua optimasi lain yang Anda lakukan pada loop dalam. (Tapi mengapa Anda menggunakan LEA untuk peningkatan penghitung alih-alih INC? Tidak apa-apa untuk mengibarkan bendera pada saat itu, dan menyebabkan perlambatan pada apa pun kecuali P4 (ketergantungan salah pada bendera lama untuk INC dan SHR). LEA bisa ' t berjalan pada banyak port, dan dapat menyebabkan konflik sumber daya menunda jalur kritis lebih sering.)
Peter Cordes
4
Oh, sebenarnya Bulldozer mungkin mengalami hambatan pada throughput dengan output compiler. Ini memiliki latensi CMOV lebih rendah dan LEA 3-komponen dari Haswell (yang saya pertimbangkan), jadi rantai dep-loop yang diangkut hanya 3 siklus dalam kode Anda. Juga tidak memiliki instruksi MOV nol-latensi untuk register integer, jadi instruksi MOV g ++ yang sia-sia sebenarnya meningkatkan latensi jalur kritis, dan merupakan masalah besar bagi Bulldozer. Jadi ya, optimasi tangan benar-benar mengalahkan kompiler secara signifikan untuk CPU yang tidak cukup modern untuk mengunyah instruksi yang tidak berguna.
Peter Cordes
95
" Mengklaim kompiler C ++ lebih baik adalah kesalahan yang sangat buruk. Dan terutama dalam kasus ini. Manusia selalu dapat membuat kode lebih baik bahwa dan masalah khusus ini adalah ilustrasi yang baik dari klaim ini. " Anda dapat membalikkannya dan akan sama validnya . " Mengklaim manusia yang lebih baik adalah kesalahan yang sangat buruk. Dan terutama dalam kasus ini. Manusia selalu dapat membuat kode buruk bahwa dan khusus ini pertanyaan adalah ilustrasi yang baik dari klaim ini. " Jadi saya tidak berpikir Anda memiliki titik di sini generalisasi seperti itu salah.
Luk32
5
@ Lukuk32 - Tetapi penulis pertanyaan tidak dapat argumen sama sekali, karena pengetahuannya tentang bahasa assembly hampir nol. Setiap argumen tentang manusia vs kompiler, secara implisit menganggap manusia dengan setidaknya beberapa tingkat pengetahuan ASM. Lebih lanjut: Teorema "Kode tertulis manusia akan selalu lebih baik atau sama dengan kode yang dihasilkan kompiler" sangat mudah untuk dibuktikan secara formal.
johnfound
30
@ Lukuk32: Seorang manusia yang terampil dapat (dan biasanya harus) mulai dengan output kompiler. Jadi, selama Anda membuat tolok ukur upaya Anda untuk memastikan mereka benar-benar lebih cepat (pada perangkat keras target yang Anda tuju), Anda tidak dapat melakukan yang lebih buruk daripada kompiler. Tapi ya, saya harus setuju itu sedikit pernyataan yang kuat. Compiler biasanya melakukan jauh lebih baik daripada coders asm pemula. Tetapi biasanya mungkin untuk menyimpan satu atau dua instruksi dibandingkan dengan apa yang dihasilkan oleh kompiler. (Namun, tidak selalu di jalur kritis, tergantung pada uarch). Mereka sangat berguna mesin kompleks, tetapi mereka tidak "pintar".
Peter Cordes
24

Untuk kinerja lebih lanjut: Perubahan sederhana mengamati bahwa setelah n = 3n + 1, n akan genap, sehingga Anda dapat membaginya dengan 2 segera. Dan n tidak akan menjadi 1, jadi Anda tidak perlu mengujinya. Jadi, Anda dapat menyimpan beberapa jika pernyataan dan menulis:

while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
    n = (3*n + 1) / 2;
    if (n % 2 == 0) {
        do n /= 2; while (n % 2 == 0);
        if (n == 1) break;
    }
}

Inilah kemenangan besar : Jika Anda melihat 8 bit terendah n, semua langkah sampai Anda dibagi 2 delapan kali sepenuhnya ditentukan oleh delapan bit tersebut. Misalnya, jika delapan bit terakhir adalah 0x01, itu dalam biner angka Anda ???? 0000 0001 maka langkah selanjutnya adalah:

3n+1 -> ???? 0000 0100
/ 2  -> ???? ?000 0010
/ 2  -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2  -> ???? ???0 0010
/ 2  -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2  -> ???? ???? ?010
/ 2  -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2  -> ???? ???? ???0
/ 2  -> ???? ???? ????

Jadi semua langkah ini dapat diprediksi, dan 256k +1 diganti dengan 81k +1. Hal serupa akan terjadi untuk semua kombinasi. Jadi, Anda dapat membuat lingkaran dengan pernyataan beralih besar:

k = n / 256;
m = n % 256;

switch (m) {
    case 0: n = 1 * k + 0; break;
    case 1: n = 81 * k + 1; break; 
    case 2: n = 81 * k + 1; break; 
    ...
    case 155: n = 729 * k + 425; break;
    ...
}

Jalankan loop sampai n ≤ 128, karena pada saat itu n bisa menjadi 1 dengan kurang dari delapan divisi dengan 2, dan melakukan delapan langkah atau lebih pada satu waktu akan membuat Anda kehilangan titik di mana Anda mencapai 1 untuk pertama kalinya. Kemudian lanjutkan loop "normal" - atau siapkan tabel yang memberi tahu Anda berapa banyak langkah lagi yang perlu mencapai 1.

PS. Saya sangat curiga saran Peter Cordes akan membuatnya lebih cepat. Tidak akan ada cabang kondisional sama sekali kecuali satu, dan yang akan diprediksi dengan benar kecuali ketika loop benar-benar berakhir. Jadi kodenya akan seperti itu

static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }

while (n > 128) {
    size_t lastBits = n % 256;
    n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}

Dalam praktiknya, Anda akan mengukur apakah memproses 9, 10, 11, 12 bit terakhir sekaligus akan lebih cepat. Untuk setiap bit, jumlah entri dalam tabel akan berlipat ganda, dan saya mengharapkan perlambatan ketika tabel tidak masuk ke cache L1 lagi.

PPS. Jika Anda membutuhkan jumlah operasi: Dalam setiap iterasi kami melakukan tepat delapan divisi dengan dua, dan sejumlah variabel (3n +1) operasi, jadi metode yang jelas untuk menghitung operasi akan menjadi array lain. Tapi kita sebenarnya bisa menghitung jumlah langkah (berdasarkan jumlah iterasi dari loop).

Kita dapat mendefinisikan kembali masalah sedikit: Ganti n dengan (3n + 1) / 2 jika ganjil, dan ganti n dengan n / 2 jika genap. Maka setiap iterasi akan melakukan tepat 8 langkah, tetapi Anda dapat mempertimbangkan kecurangan itu :-) Jadi asumsikan ada operasi r n <- 3n + 1 dan operasi s n <- n / 2. Hasilnya akan persis n '= n * 3 ^ r / 2 ^ s, karena n <- 3n + 1 berarti n <- 3n * (1 + 1 / 3n). Mengambil logaritma kami menemukan r = (s + log2 (n '/ n)) / log2 (3).

Jika kita melakukan loop sampai n ≤ 1.000.000 dan memiliki tabel yang sudah dihitung berapa banyak iterasi yang dibutuhkan dari titik awal n ≤ 1.000.000 kemudian menghitung r seperti di atas, dibulatkan ke bilangan bulat terdekat, akan memberikan hasil yang tepat kecuali s benar-benar besar.

gnasher729
sumber
2
Atau buat tabel pencarian data untuk dikalikan dan tambahkan konstanta, alih-alih sakelar. Mengindeks dua tabel 256-entri lebih cepat daripada tabel lompatan, dan kompiler mungkin tidak mencari transformasi itu.
Peter Cordes
1
Hmm, saya pikir sebentar pengamatan ini mungkin membuktikan dugaan Collatz, tapi tidak, tentu saja tidak. Untuk setiap kemungkinan trailing 8 bit, ada sejumlah langkah hingga semuanya hilang. Tetapi beberapa dari pola 8-bit yang tertinggal akan memperpanjang sisa bitstring lebih dari 8, jadi ini tidak dapat mengesampingkan pertumbuhan tanpa batas atau siklus berulang.
Peter Cordes
Untuk memperbarui count, Anda memerlukan array ketiga, bukan? adders[]tidak memberi tahu Anda berapa banyak shift kanan yang dilakukan.
Peter Cordes
Untuk tabel yang lebih besar, ada baiknya menggunakan jenis yang lebih sempit untuk meningkatkan kepadatan cache. Pada kebanyakan arsitektur, beban nol-perluasan dari a uint16_tsangat murah. Pada x86, hanya semurah nol-memanjang dari 32-bit unsigned intke uint64_t. (MOVZX dari memori pada Intel CPU hanya membutuhkan load-port uop, tetapi AMD AMD juga membutuhkan ALU.) Oh BTW, mengapa Anda menggunakan size_tuntuk lastBits? Ini adalah tipe 32-bit dengan -m32, dan bahkan -mx32(mode panjang dengan pointer 32-bit). Ini pasti tipe yang salah untuk n. Gunakan saja unsigned.
Peter Cordes
20

Pada catatan yang agak tidak terkait: peretasan kinerja lebih banyak!

  • [«dugaan» pertama telah akhirnya dibongkar oleh @ShreevatsaR; dihapus]

  • Saat melintasi urutan, kami hanya bisa mendapatkan 3 kemungkinan kasus di 2-lingkungan dari elemen saat ini N(diperlihatkan pertama):

    1. [bahkan aneh]
    2. [ganjil genap]
    3. [datar] [datar]

    Melompati 2 elemen ini berarti menghitung (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1dan N >> 2, masing-masing.

    Mari kita buktikan bahwa untuk kedua kasus (1) dan (2) dimungkinkan untuk menggunakan rumus pertama (N >> 1) + N + 1,.

    Kasus (1) jelas. Kasus (2) menyiratkan (N & 1) == 1, jadi jika kita mengasumsikan (tanpa kehilangan generalitas) bahwa N adalah 2-bit panjang dan bitnya badari yang paling signifikan hingga yang paling signifikan, maka a = 1, dan berikut ini berlaku:

    (N << 1) + N + 1:     (N >> 1) + N + 1:
    
            b10                    b1
             b1                     b
           +  1                   + 1
           ----                   ---
           bBb0                   bBb

    mana B = !b. Pergeseran kanan hasil pertama memberi kita apa yang kita inginkan.

    QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.

    Sebagai terbukti, kita dapat melintasi urutan 2 elemen sekaligus, menggunakan operasi ternary tunggal. Pengurangan 2 × waktu lagi.

Algoritma yang dihasilkan terlihat seperti ini:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

Di sini kami membandingkan n > 2karena prosesnya mungkin berhenti pada 2 bukannya 1 jika total panjang urutannya ganjil.

[EDIT:]

Mari terjemahkan ini ke dalam kumpulan!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

Gunakan perintah ini untuk mengkompilasi:

nasm -f elf64 file.asm
ld -o file file.o

Lihat C dan versi asm yang diperbaiki / diperbaiki bug oleh Peter Cordes di Godbolt . (catatan editor: Maaf karena meletakkan barang-barang saya di jawaban Anda, tetapi jawaban saya mencapai batas char 30k dari tautan + teks Godbolt!)

hidefromkgb
sumber
2
Tidak ada yang integral Qseperti itu 12 = 3Q + 1. Poin pertama Anda tidak benar, metinks.
Veedrac
1
@Veedrac: Telah bermain-main dengan ini: Ini dapat diimplementasikan dengan asm yang lebih baik daripada implementasi dalam jawaban ini, menggunakan ROR / TEST dan hanya satu CMOV. Kode asm ini infinite-loop pada CPU saya, karena tampaknya bergantung pada OF, yang tidak terdefinisi setelah SHRD atau ROR dengan jumlah> 1. Ini juga berusaha keras untuk mencoba menghindari mov reg, imm32, tampaknya untuk menghemat byte, tetapi kemudian menggunakan byte, tetapi kemudian menggunakan Versi 64-bit mendaftar di mana-mana, bahkan untuk xor rax, rax, jadi ia memiliki banyak awalan REX yang tidak perlu. Kami jelas hanya membutuhkan REX pada regs yang memegang nloop internal untuk menghindari overflow.
Peter Cordes
1
Waktu hasil (dari Core2Duo E6600: Merom 2.4GHz. Complex-LEA = 1c latency, CMOV = 2c) . Implementasi single-step asm single-loop terbaik (dari Johnfound): 111ms per run dari loop utama ini. Keluaran kompiler dari versi C saya yang kurang jelas ini (dengan beberapa tmp vars): clang3.8 -O3 -march=core2: 96ms. gcc5.2: 108ms. Dari versi perbaikan dari loop batin asm dentang saya: 92ms (seharusnya melihat peningkatan yang lebih besar pada keluarga SnB, di mana LEA kompleks adalah 3c bukan 1c). Dari versi + kerja saya yang ditingkatkan dari loop asm ini (menggunakan ROR + TEST, bukan SHRD): 87ms. Diukur dengan 5 repetisi sebelum dicetak
Peter Cordes
2
Berikut adalah 66 set-setter pertama (A006877 di OEIS); Saya telah menandai yang genap dalam huruf tebal: 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331 1503, 15030 1723519, 2298025, 3064033, 3542887, 3732423, 5649499, 6649279, 8400511, 11200681, 14934241, 15733191, 31466382, 36791535, 63728127, 127456254, 169941673, 226588897, 268549803, 537099606, 670617279, 1341234558
ShreevatsaR
1
@hidefromkgb Hebat! Dan saya menghargai poin Anda yang lain dengan lebih baik sekarang: 4k + 2 → 2k + 1 → 6k + 4 = (4k + 2) + (2k + 1) + 1, dan 2k + 1 → 6k + 4 → 3k + 2 = ( 2k + 1) + (k) + 1. Pengamatan yang bagus!
ShreevatsaR
6

Program C ++ diterjemahkan ke program perakitan selama pembuatan kode mesin dari kode sumber. Akan benar-benar salah untuk mengatakan bahwa perakitan lebih lambat daripada C ++. Selain itu, kode biner yang dihasilkan berbeda dari kompiler ke kompiler. Jadi kompiler C ++ yang cerdas dapat menghasilkan kode biner yang lebih optimal dan efisien daripada kode assembler yang bodoh.

Namun saya percaya metodologi pembuatan profil Anda memiliki kelemahan tertentu. Berikut ini adalah panduan umum untuk pembuatan profil:

  1. Pastikan sistem Anda dalam keadaan normal / idle. Hentikan semua proses yang berjalan (aplikasi) yang Anda mulai atau yang menggunakan CPU secara intensif (atau polling melalui jaringan).
  2. Ukuran data Anda harus lebih besar.
  3. Tes Anda harus dijalankan untuk sesuatu yang lebih dari 5-10 detik.
  4. Jangan hanya mengandalkan satu sampel. Lakukan pengujian Anda sebanyak N kali. Kumpulkan hasil dan hitung rata-rata atau median hasil.
Mangu Singh Rajpurohit
sumber
Ya saya belum melakukan profiling formal tetapi saya telah menjalankan keduanya beberapa kali dan saya mampu mengatakan 2 detik dari 3 detik. Pokoknya terima kasih sudah menjawab. Saya sudah mengambil banyak info di sini
anak nakal
9
Ini mungkin bukan hanya kesalahan pengukuran, kode asm yang ditulis tangan menggunakan instruksi DIV 64-bit alih-alih shift kanan. Lihat jawaban saya. Tapi ya, mengukur dengan benar juga penting.
Peter Cordes
7
Poin-poin poin adalah format yang lebih tepat daripada blok kode. Harap berhenti menempatkan teks Anda ke dalam blok kode, karena itu bukan kode dan tidak mendapat manfaat dari font monospace.
Peter Cordes
16
Saya tidak benar-benar melihat bagaimana ini menjawab pertanyaan. Ini bukan pertanyaan yang tidak jelas tentang apakah kode assembly atau kode C ++ mungkin lebih cepat --- ini adalah pertanyaan yang sangat spesifik tentang kode aktual , yang dia bantu berikan dalam pertanyaan itu sendiri. Jawaban Anda bahkan tidak menyebutkan kode apa pun, atau melakukan jenis perbandingan apa pun. Tentu, tips Anda tentang bagaimana tolok ukur pada dasarnya benar, tetapi tidak cukup untuk membuat jawaban yang sebenarnya.
Cody Grey
6

Untuk masalah Collatz, Anda bisa mendapatkan peningkatan kinerja yang signifikan dengan melakukan caching "tails". Ini adalah pertukaran waktu / memori. Lihat: memoisasi ( https://en.wikipedia.org/wiki/Memoization ). Anda juga dapat melihat solusi pemrograman dinamis untuk pertukaran waktu / memori lainnya.

Contoh implementasi python:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))
Emanuel Landeholm
sumber
1
Jawaban gnasher menunjukkan bahwa Anda dapat melakukan lebih dari sekadar menembolok ekor: bit tinggi tidak memengaruhi apa yang terjadi selanjutnya, dan menambahkan / mul hanya merambatkan carry ke kiri, jadi bit tinggi tidak memengaruhi apa yang terjadi pada bit rendah. yaitu Anda dapat menggunakan pencarian LUT untuk mendapatkan 8 (atau jumlah apa pun) bit sekaligus, dengan mengalikan dan menambahkan konstanta untuk diterapkan ke sisa bit. Memo- tail ekor tentu saja membantu dalam banyak masalah seperti ini, dan untuk masalah ini ketika Anda belum memikirkan pendekatan yang lebih baik, atau belum membuktikannya benar.
Peter Cordes
2
Jika saya memahami ide Gnasher di atas dengan benar, saya pikir memoisasi ekor adalah optimasi ortogonal. Jadi Anda bisa melakukan keduanya. Akan menarik untuk menyelidiki berapa banyak yang bisa Anda dapatkan dari menambahkan memoisasi ke algoritma gnasher.
Emanuel Landeholm
2
Kita mungkin dapat membuat memoisasi lebih murah dengan hanya menyimpan bagian hasil yang padat. Tetapkan batas atas pada N, dan di atasnya, jangan periksa memori. Di bawahnya, gunakan hash (N) -> N sebagai fungsi hash, jadi key = position dalam array, dan tidak perlu disimpan. Entri 0cara belum hadir. Kita dapat lebih mengoptimalkan dengan hanya menyimpan N ganjil dalam tabel, jadi fungsi hash adalah n>>1, membuang 1. Tulis kode langkah untuk selalu diakhiri dengan n>>tzcnt(n)atau sesuatu untuk memastikan itu ganjil.
Peter Cordes
1
Itu berdasarkan pada ide saya (yang belum diuji) bahwa nilai-nilai N yang sangat besar di tengah-tengah sekuens cenderung kurang umum untuk beberapa sekuens, jadi kami tidak ketinggalan terlalu banyak dari tidak mem-memoise-nya. Juga bahwa N berukuran cukup akan menjadi bagian dari banyak sekuens panjang, bahkan yang dimulai dengan N. sangat besar (Ini mungkin angan-angan; jika itu salah maka hanya melakukan caching kisaran padat berturut-turut N dapat kalah vs hash tabel yang dapat menyimpan kunci sewenang-wenang.) Apakah Anda sudah melakukan semacam pengujian tingkat hit untuk melihat apakah mulai dekat N cenderung memiliki kesamaan dalam nilai urutan mereka?
Peter Cordes
2
Anda bisa menyimpan hasil pra-perhitungan untuk semua n <N, untuk beberapa N. besar. Jadi Anda tidak perlu overhead tabel hash. Data dalam tabel itu akan digunakan pada akhirnya untuk setiap nilai awal. Jika Anda hanya ingin mengonfirmasi bahwa urutan Collatz selalu berakhir dengan (1, 4, 2, 1, 4, 2, ...): Ini dapat dibuktikan setara dengan membuktikan bahwa untuk n> 1, urutan tersebut pada akhirnya akan kurang dari aslinya n. Dan untuk itu, caching tail tidak akan membantu.
gnasher729
5

Dari komentar:

Tapi, kode ini tidak pernah berhenti (karena integer overflow)!?! Yves Daoust

Untuk banyak angka itu tidak akan meluap.

Jika itu akan meluap - untuk salah satu dari benih awal yang tidak beruntung itu, jumlah overflown kemungkinan besar akan menyatu ke arah 1 tanpa luapan lainnya.

Masih ini menimbulkan pertanyaan menarik, apakah ada beberapa nomor benih overflow-siklik?

Setiap seri konvergensi akhir sederhana dimulai dengan kekuatan dua nilai (cukup jelas?).

2 ^ 64 akan melimpah ke nol, yang merupakan undefined loop berdasarkan algoritma (berakhir hanya dengan 1), tetapi solusi yang paling optimal dalam jawaban akan selesai karena shr raxmenghasilkan ZF = 1.

Bisakah kita menghasilkan 2 ^ 64? Jika angka awal adalah 0x5555555555555555, itu angka ganjil, angka selanjutnya adalah 3n + 1, yaitu 0xFFFFFFFFFFFFFFFF + 1= 0. Secara teoritis dalam keadaan algoritma yang tidak ditentukan, tetapi jawaban yang dioptimalkan dari johnfound akan pulih dengan keluar pada ZF = 1. The cmp rax,1Peter Cordes akan berakhir dalam loop tak terbatas (QED varian 1, "murahan" melalui 0nomor yang tidak ditentukan ).

Bagaimana dengan bilangan yang lebih kompleks, yang akan menciptakan siklus tanpa 0? Terus terang, saya tidak yakin, teori Matematika saya terlalu kabur untuk mendapatkan ide yang serius, bagaimana menghadapinya secara serius. Tetapi secara intuitif saya akan mengatakan seri akan konvergen ke 1 untuk setiap angka: 0 <angka, karena rumus 3n + 1 perlahan akan mengubah setiap faktor prima non-2 dari angka asli (atau menengah) menjadi beberapa kekuatan 2, cepat atau lambat . Jadi kita tidak perlu khawatir tentang infinite loop untuk seri asli, hanya overflow yang bisa menghambat kita.

Jadi saya hanya memasukkan beberapa angka ke lembar dan melihat angka terpotong 8 bit.

Ada tiga nilai meluap ke 0: 227, 170dan 85( 85akan langsung ke 0, dua lainnya maju menuju 85).

Tetapi tidak ada nilai untuk membuat benih luapan siklis.

Lucunya saya melakukan cek, yang merupakan angka pertama yang menderita pemotongan 8 bit, dan sudah 27terpengaruh! Itu mencapai nilai 9232dalam seri non-terpotong yang tepat (nilai terpotong pertama adalah 322dalam langkah 12), dan nilai maksimum yang dicapai untuk salah satu dari 2-255 nomor input dengan cara non-terpotong adalah 13120(untuk 255dirinya sendiri), jumlah maksimum langkah untuk konvergen 1adalah sekitar 128(+ -2, tidak yakin apakah "1" akan dihitung, dll ...).

Cukup menarik (bagi saya) jumlahnya 9232maksimum untuk banyak nomor sumber lain, apa istimewanya? : -O 9232= 0x2410... hmmm .. tidak tahu.

Sayangnya saya tidak bisa mendapatkan pemahaman mendalam dari seri ini, mengapa konvergen dan apa implikasi dari pemotongan mereka ke k bit, tetapi dengan cmp number,1kondisi terminating tentu saja mungkin untuk menempatkan algoritma ke dalam loop tak terbatas dengan nilai input tertentu yang berakhir 0setelah pemotongan.

Tetapi nilai yang 27meluap untuk kasus 8 bit adalah semacam peringatan, ini terlihat seperti jika Anda menghitung jumlah langkah untuk mencapai nilai 1, Anda akan mendapatkan hasil yang salah untuk sebagian besar angka dari total k-bit set integer. Untuk bilangan bulat 8 bit angka 146 dari 256 telah mempengaruhi seri oleh pemotongan (beberapa dari mereka mungkin masih mencapai jumlah langkah yang benar secara tidak sengaja mungkin, aku terlalu malas untuk memeriksa).

Ped7g
sumber
"jumlah overflown sangat mungkin akan menyatu ke arah 1 tanpa overflow lain": kode tidak pernah berhenti (Itu dugaan karena saya tidak bisa menunggu sampai akhir zaman untuk memastikan ...)
Yves Daoust
@YvesDaoust oh, tapi ya? ... misalnya 27seri dengan pemotongan 8b terlihat seperti ini: 82 41 124 62 31 94 47 142 71 214 107 66 (terpotong) 33 100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 (sisanya berfungsi tanpa pemotongan). Saya tidak mengerti, maaf. Itu tidak akan pernah berhenti jika nilai terpotong akan sama dengan beberapa yang sebelumnya dicapai dalam seri yang sedang berlangsung saat ini, dan saya tidak dapat menemukan nilai seperti itu vs pemotongan k-bit (tapi saya juga tidak bisa mengetahui teori Matematika di belakang, mengapa ini tahan selama pemotongan 8/16/32/64 bit, hanya secara intuitif saya pikir itu berfungsi).
Ped7g
1
Saya seharusnya memeriksa deskripsi masalah asli lebih cepat: "Meskipun belum terbukti (Masalah Collatz), diperkirakan bahwa semua angka mulai selesai pada 1." ... ok, tidak heran saya tidak dapat memahaminya dengan pengetahuan Matematika kabur saya yang terbatas ...: D Dan dari percobaan lembar saya, saya dapat meyakinkan Anda bahwa ia bertemu untuk setiap 2- 255nomor, baik tanpa pemotongan (untuk 1), atau dengan pemotongan 8 bit (untuk yang diharapkan 1atau 0untuk tiga angka).
Ped7g
Hem, ketika saya mengatakan bahwa itu tidak pernah berhenti, maksud saya ... bahwa itu tidak berhenti. Kode yang diberikan berjalan selamanya jika Anda mau.
Yves Daoust
1
Terpilih untuk analisis tentang apa yang terjadi pada overflow. Loop berbasis CMP dapat menggunakan cmp rax,1 / jna(yaitu do{}while(n>1)) untuk mengakhiri pada nol. Saya berpikir untuk membuat versi terinstal dari loop yang merekam max yang nterlihat, untuk memberikan gambaran seberapa dekat kita dengan overflow.
Peter Cordes
5

Anda tidak memposting kode yang dihasilkan oleh kompiler, jadi ada beberapa dugaan di sini, tetapi bahkan tanpa melihatnya, dapat dikatakan bahwa ini:

test rax, 1
jpe even

... memiliki peluang 50% untuk salah menduga cabang, dan itu akan menjadi mahal.

Kompiler hampir pasti melakukan kedua perhitungan (yang biayanya lebih besar karena div / mod latensi yang cukup lama, jadi tambah-ganda adalah "bebas") dan diikuti dengan CMOV. Yang, tentu saja, memiliki peluang nol persen untuk salah duga.

Damon
sumber
1
Ada beberapa pola percabangan; mis. angka ganjil selalu diikuti oleh angka genap. Tapi kadang-kadang 3n + 1 meninggalkan banyak bit nol yang tertinggal, dan saat itulah ini akan salah duga. Saya mulai menulis tentang pembagian dalam jawaban saya, dan tidak membahas bendera merah besar lainnya dalam kode OP. (Perhatikan juga bahwa menggunakan kondisi paritas benar-benar aneh, dibandingkan dengan hanya JZ atau CMOVZ. Ini juga lebih buruk untuk CPU, karena CPU Intel dapat makro-sekering TEST / JZ, tetapi tidak TEST / JPE. Agner Fog mengatakan AMD dapat memadukan TEST / CMP dengan JCC apa pun, jadi dalam hal ini hanya lebih buruk bagi pembaca manusia)
Peter Cordes
5

Bahkan tanpa melihat perakitan, alasan paling jelas adalah bahwa /= 2mungkin dioptimalkan karena >>=1dan banyak prosesor memiliki operasi shift yang sangat cepat. Tetapi bahkan jika prosesor tidak memiliki operasi shift, divisi integer lebih cepat daripada divisi floating point.

Sunting: jarak tempuh Anda mungkin berbeda pada pernyataan "pembagian bilangan bulat lebih cepat daripada pembagian floating point" di atas. Komentar di bawah ini mengungkapkan bahwa prosesor modern telah memprioritaskan mengoptimalkan divisi fp daripada divisi integer. Jadi, jika seseorang mencari alasan yang paling mungkin untuk percepatan yang ditanyakan oleh pertanyaan ini, maka kompilator mengoptimalkan /=2sebagai >>=1tempat pertama yang terbaik untuk dilihat.


Pada catatan yang tidak terkait , jika naneh, ekspresi n*3+1akan selalu genap. Jadi tidak perlu memeriksa. Anda dapat mengubah cabang itu menjadi

{
   n = (n*3+1) >> 1;
   count += 2;
}

Jadi seluruh pernyataan itu akan menjadi

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}
Dmitry Rubanovich
sumber
4
Divisi integer sebenarnya tidak lebih cepat dari divisi FP pada CPU x86 modern. Saya pikir ini karena Intel / AMD menghabiskan lebih banyak transistor pada pembagi FP mereka, karena ini adalah operasi yang lebih penting. (Pembagian integer dengan konstanta dapat dioptimalkan ke multiply oleh invers modular). Periksa Agn Fog's insn tables, dan bandingkan DIVSD (float presisi ganda) dengan DIV r32(integer 32-bit unsigned) atau DIV r64(integer unsigned 64-bit yang jauh lebih lambat). Khusus untuk throughput, pembagian FP jauh lebih cepat (single uop, bukan micro-coded, dan sebagian pipelined), tetapi latensi lebih baik juga.
Peter Cordes
1
misalnya pada OP Haswell CPU: DIVSD adalah 1 uop, 10-20 siklus latensi, satu per 8-14c throughput. div r64adalah 36 uops, 32-96c latency, dan satu per 21-74c throughput. Skylake memiliki throughput divisi FP yang lebih cepat (pipelined pada satu per 4c dengan latensi yang tidak jauh lebih baik), tetapi tidak lebih cepat integer div. Hal serupa pada keluarga AMD Bulldozer: DIVSD adalah 1M-op, latensi 9-27c, satu per throughput 4,5-11c. div r64adalah 16M-ops, 16-75c latency, satu per 16-75c throughput.
Peter Cordes
1
Bukankah pembagian FP pada dasarnya sama dengan eksponen integer-kurangi, integer-bagi mantissa, deteksi denormals? Dan 3 langkah itu bisa dilakukan secara paralel.
MSalters
2
@ MSalters: yeah, itu kedengarannya benar, tetapi dengan langkah normalisasi pada akhir atau bit pergeseran antara eksponen dan mantra. doublememiliki mantissa 53-bit, tetapi masih secara signifikan lebih lambat daripada div r32di Haswell. Jadi itu pasti hanya masalah seberapa banyak hardware Intel / AMD melemparkan masalah, karena mereka tidak menggunakan transistor yang sama untuk pembagi integer dan fp. Integer adalah skalar (tidak ada pembagian integer-SIMD), dan satu vektor menangani 128b vektor (bukan 256b seperti vektor ALU lainnya). Yang penting adalah bahwa integer div adalah banyak uops, berdampak besar pada kode di sekitarnya.
Peter Cordes
Kesalahan, bukan menggeser bit antara mantissa dan eksponen, tetapi menormalkan mantissa dengan shift, dan menambahkan jumlah shift ke eksponen.
Peter Cordes
4

Sebagai jawaban umum, tidak secara khusus diarahkan pada tugas ini: Dalam banyak kasus, Anda dapat secara signifikan mempercepat program apa pun dengan melakukan perbaikan di tingkat tinggi. Seperti menghitung data satu kali, bukan berkali-kali, menghindari pekerjaan yang tidak perlu sepenuhnya, menggunakan cache dengan cara terbaik, dan sebagainya. Hal-hal ini jauh lebih mudah dilakukan dalam bahasa tingkat tinggi.

Menulis kode assembler, adalah mungkin untuk memperbaiki apa yang dilakukan oleh kompiler yang mengoptimalkan, tetapi ini adalah kerja keras. Dan begitu selesai, kode Anda jauh lebih sulit untuk dimodifikasi, sehingga jauh lebih sulit untuk menambahkan peningkatan algoritmik. Terkadang prosesor memiliki fungsionalitas yang tidak dapat Anda gunakan dari bahasa tingkat tinggi, perakitan inline sering berguna dalam kasus ini dan masih memungkinkan Anda menggunakan bahasa tingkat tinggi.

Dalam masalah Euler, sebagian besar waktu Anda berhasil dengan membangun sesuatu, menemukan mengapa itu lambat, membangun sesuatu yang lebih baik, menemukan mengapa itu lambat, dan seterusnya dan seterusnya. Itu sangat, sangat sulit menggunakan assembler. Algoritma yang lebih baik pada setengah kecepatan yang mungkin biasanya akan mengalahkan algoritma yang lebih buruk pada kecepatan penuh, dan mendapatkan kecepatan penuh dalam assembler bukanlah hal sepele.

gnasher729
sumber
2
Sepenuhnya setuju dengan ini. gcc -O3membuat kode yang berada dalam jarak 20% dari optimal pada Haswell, untuk algoritma yang tepat itu. (Mendapatkan speedup itu adalah fokus utama jawaban saya hanya karena itulah pertanyaan yang diajukan, dan memiliki jawaban yang menarik, bukan karena itu pendekatan yang tepat.) Speedup yang jauh lebih besar diperoleh dari transformasi yang tidak mungkin dicari oleh kompiler. , seperti menunda shift kanan, atau melakukan 2 langkah sekaligus. Speedup yang jauh lebih besar dari yang bisa didapat dari memoization / lookup-tables. Tes masih melelahkan, tapi bukan kekuatan kasar murni.
Peter Cordes
2
Namun, memiliki implementasi sederhana yang jelas benar sangat berguna untuk menguji implementasi lainnya. Apa yang akan saya lakukan mungkin hanya melihat output asm untuk melihat apakah gcc melakukannya tanpa cabang seperti yang saya harapkan (kebanyakan karena penasaran), dan kemudian beralih ke peningkatan algoritmik.
Peter Cordes
-2

Jawaban sederhana:

  • melakukan MOV RBX, 3 dan MUL RBX mahal; cukup ADD RBX, RBX dua kali

  • TAMBAH 1 mungkin lebih cepat daripada INC di sini

  • MOV 2 dan DIV sangat mahal; bergeser ke kanan

  • Kode 64-bit biasanya terasa lebih lambat dari kode 32-bit dan masalah perataan lebih rumit; dengan program kecil seperti ini Anda harus mengemasnya sehingga Anda melakukan komputasi paralel untuk memiliki peluang lebih cepat dari kode 32-bit

Jika Anda membuat daftar rakitan untuk program C ++ Anda, Anda dapat melihat perbedaannya dari rakitan Anda.

Tyler Durden
sumber
4
1): menambahkan 3 kali akan menjadi bodoh dibandingkan dengan LEA. Juga mul rbxpada CPU Haswell OP adalah 2 uops dengan latensi 3c (dan 1 throughput clock). imul rcx, rbx, 3hanya 1 uop, dengan latensi 3c yang sama. Dua instruksi ADD adalah 2 uops dengan latensi 2c.
Peter Cordes
5
2) ADD 1 mungkin lebih cepat dari INC di sini . Tidak, OP tidak menggunakan Pentium4 . Poin Anda 3) adalah satu-satunya bagian yang benar dari jawaban ini.
Peter Cordes
5
4) terdengar seperti omong kosong total. Kode 64-bit bisa lebih lambat dengan struktur data pointer-berat, karena pointer lebih besar berarti jejak cache lebih besar. Tetapi kode ini hanya berfungsi pada register, dan masalah penyelarasan kode sama dalam mode 32 dan 64 bit. (Begitu juga masalah penyelarasan data, tidak tahu apa yang Anda bicarakan dengan penyelarasan menjadi masalah yang lebih besar untuk x86-64). Lagi pula, kode itu bahkan tidak menyentuh memori di dalam loop.
Peter Cordes
Komentator tidak tahu apa yang sedang dibicarakan. Lakukan MOV + MUL pada CPU 64-bit akan kira-kira tiga kali lebih lambat daripada menambahkan register ke dirinya sendiri dua kali. Pernyataannya yang lain juga sama salahnya.
Tyler Durden
6
Yah MOV + MUL jelas bodoh, tapi MOV + ADD + ADD masih konyol (sebenarnya melakukan ADD RBX, RBXdua kali akan dikalikan dengan 4, bukan 3). Sejauh ini cara terbaik adalah lea rax, [rbx + rbx*2]. Atau, dengan biaya menjadikannya LEA 3-komponen, lakukan juga +1 dengan lea rax, [rbx + rbx*2 + 1] (latensi 3c pada HSW bukannya 1, seperti yang saya jelaskan dalam jawaban saya) Maksud saya adalah bahwa penggandaan 64-bit tidak terlalu mahal untuk CPU Intel baru-baru ini, karena mereka memiliki unit pengganda bilangan bulat yang sangat cepat (bahkan dibandingkan dengan AMD, di mana hal yang sama MUL r64adalah latensi 6c, dengan satu throughput 4c: bahkan tidak sepenuhnya disalurkan melalui pipa.
Peter Cordes