Pertanyaan Mengapa kode C ++ ini lebih cepat daripada rakitan tulisan tangan saya untuk menguji dugaan Collatz?


Saya menulis dua solusi ini untuk Proyek Euler Q14, dalam perakitan dan dalam C ++. Mereka adalah pendekatan kekuatan kasar identik yang sama untuk menguji Dugaan Collatz. Solusi perakitan dirakit bersama

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 pengoptimalan kompiler untuk meningkatkan kecepatan dan segalanya, tetapi saya tidak melihat banyak cara untuk mengoptimalkan solusi perakitan saya lebih lanjut (berbicara secara terprogram bukan secara matematis).

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

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: Linux 64 bit pada 1,4 GHz Intel Celeron 2955U (Haswell microarchitecture).


737
2017-11-01 06:12


asal


Jawaban:


Jika Anda berpikir instruksi DIV 64-bit adalah cara yang baik untuk membagi dua, maka tidak mengherankan kompilator asm output mengalahkan kode yang ditulis tangan Anda, bahkan dengan -O0 (kompilasi cepat, tidak ada optimasi tambahan, dan simpan / kembali ke memori setelah / sebelum setiap pernyataan C sehingga debugger dapat memodifikasi variabel).

Lihat Panduan Majelis Mengoptimalkan Agner Fog untuk belajar bagaimana menulis asm efisien. Dia juga memiliki tabel instruksi dan panduan microarch untuk detail spesifik untuk CPU tertentu. Lihat juga  tag wiki untuk tautan lebih sempurna.

Lihat juga ini pertanyaan yang lebih umum tentang mengalahkan kompiler dengan asm tulisan tangan: Apakah bahasa assembly inline lebih lambat daripada native C ++ code?. TL: DR: ya jika kamu salah (seperti pertanyaan ini).

Biasanya Anda baik-baik saja membiarkan compiler melakukan hal itu, terutama jika Anda cobalah menulis C ++ yang dapat dikompilasi secara efisien. Juga lihat apakah perakitan lebih cepat dari bahasa yang dikompilasi?. Salah satu jawaban terhubung ini slide rapi menunjukkan bagaimana berbagai compiler C mengoptimalkan beberapa fungsi yang sangat sederhana dengan trik-trik keren.


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

Di Intel Haswell, div r64 adalah 36 Uops, dengan a 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 high-uop-count seperti DIV adalah microcoded, yang juga dapat menyebabkan kemacetan front-end. Dalam hal ini, latensi adalah faktor yang paling relevan karena itu adalah bagian dari rantai ketergantungan loop-carry.

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

Sebagai perbandingan, pembagian 32-bit lebih cepat, tetapi masih mengerikan vs shift. idiv r32 adalah 9 Uops, 22-29c latency, dan satu per 8-11c throughput pada Haswell.


Seperti yang Anda lihat dari melihat gcc's -O0 asm output (Penjelajah kompilator Godbolt), hanya menggunakan instruksi shift. dentang -O0 melakukan kompilasi secara naif seperti yang Anda duga, bahkan menggunakan IDIV 64-bit dua kali. (Saat mengoptimalkan, kompiler menggunakan kedua keluaran IDIV ketika sumber melakukan pembagian dan modulus dengan operan yang sama, jika mereka menggunakan IDIV sama sekali)

GCC tidak memiliki mode yang sepenuhnya naif; itu selalu berubah melalui GIMPLE, yang berarti beberapa "optimisasi" tidak dapat dinonaktifkan. Ini termasuk mengenali pembagian-oleh-konstan dan menggunakan pergeseran (kekuatan 2) atau invers multiplikatif titik tetap (non daya 2) untuk menghindari IDIV (lihat div_by_13 di link godbolt di atas).

gcc -Os (mengoptimalkan ukuran) tidak gunakan IDIV untuk non-power-of-2 division, sayangnya bahkan dalam kasus di mana kode pembalikan perkalian hanya sedikit lebih besar tetapi jauh lebih cepat.


Membantu compiler

(ringkasan untuk kasus ini: gunakan uint64_t n)

Pertama-tama, itu hanya menarik untuk melihat output kompilator yang dioptimalkan. (-O3). -O0 kecepatan pada dasarnya tidak berarti.

Lihatlah output asm Anda (pada Godbolt, atau lihat Bagaimana cara menghapus "noise" dari output perakitan GCC / clang?). Ketika compiler tidak membuat kode optimal di tempat pertama: Menuliskan sumber C / C ++ Anda dengan cara yang memandu compiler untuk 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 baik: kadang-kadang dentang akan melakukan sesuatu yang keren, dan Anda dapat memegang gcc tangan untuk melakukan hal yang sama: lihat jawaban ini dan apa yang saya lakukan dengan loop yang tidak dapat dikendalikan dalam kode @ Veedrac di bawah ini.)

Pendekatan ini portabel, dan dalam 20 tahun, beberapa compiler masa mendatang dapat mengkompilasinya ke apa pun yang efisien pada perangkat keras masa depan (x86 atau tidak), mungkin menggunakan ekstensi ISA baru atau vectorizing otomatis. Tulisan tangan x86-64 dari 15 tahun yang lalu biasanya tidak akan disetel secara optimal untuk Skylake. misalnya bandingkan & cabang-fusi makro tidak ada saat itu. Apa yang optimal sekarang untuk asm buatan tangan untuk satu mikroarsitektur mungkin tidak optimal untuk CPU lain saat ini dan masa depan.  Komentar atas jawaban @ johnfound diskusikan perbedaan utama antara AMD Bulldozer dan Intel Haswell, yang memiliki pengaruh besar pada kode ini. Namun dalam teori, g++ -O3 -march=bdver3 dan g++ -O3 -march=skylake akan melakukan hal yang benar. (Atau -march=native.) Atau -mtune=... untuk selaras, tanpa menggunakan instruksi yang mungkin tidak didukung oleh CPU lain.

Perasaan saya adalah bahwa membimbing compiler ke asm itu bagus untuk CPU saat ini yang Anda pedulikan seharusnya tidak menjadi masalah bagi compiler masa depan. Mereka semoga lebih baik daripada kompiler saat ini dalam menemukan cara untuk mengubah kode, dan dapat menemukan cara yang berfungsi untuk CPU masa depan. Apapun, x86 masa mendatang mungkin tidak akan mengerikan pada apa pun yang baik pada x86 saat ini, dan kompilator masa depan akan menghindari perangkap khusus apa pun selagi mengimplementasikan sesuatu seperti gerakan data dari sumber C Anda, jika tidak melihat sesuatu yang lebih baik.

Asm tulisan tangan adalah kotak hitam untuk pengoptimal, sehingga propagasi konstan tidak berfungsi ketika penyisipan membuat masukan menjadi konstanta waktu kompilasi. Optimasi lainnya juga terpengaruh. Baca baca https://gcc.gnu.org/wiki/DontUseInlineAsm sebelum menggunakan asm. (Dan hindari MSVC-style inline asm: input / output harus melalui memori yang menambah overhead.)

Pada kasus ini: Anda n memiliki tipe bertanda tangan, dan gcc menggunakan urutan SAR / SHR / ADD yang memberikan pembulatan yang benar. (IDIV dan aritmetika-shift "putaran" berbeda untuk input negatif, lihat SAR insn mengatur entri manual ref). (IDK jika gcc mencoba dan gagal membuktikannya n tidak bisa negatif, atau apa. Signed-overflow adalah perilaku yang tidak terdefinisi, jadi seharusnya bisa.)

Anda seharusnya menggunakan uint64_t n, jadi itu hanya bisa SHR. Dan itu portabel untuk sistem di mana long hanya 32-bit (misalnya x86-64 Windows).


BTW, gcc's dioptimalkan asm output terlihat bagus (menggunakan unsigned long n): loop bagian dalam itu masuk ke dalam 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

Lingkaran dalam adalah tanpa 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, kemacetan latensi. Out-of-order eksekusi mengurus segala sesuatu yang lain secara paralel dengan ini (dalam teori: Saya belum diuji dengan penghitung perf untuk melihat apakah itu benar-benar berjalan pada 5c / iter).

Masukan BENDERA dari cmov (diproduksi oleh TEST) lebih cepat untuk menghasilkan daripada input RAX (dari LEA-> MOV), jadi itu tidak di jalur kritis.

Demikian pula, MOV-> SHR yang menghasilkan input RDI CMOV adalah dari jalur kritis, karena itu juga lebih cepat daripada LEA. MOV pada IvyBridge dan kemudian memiliki latensi nol (ditangani pada waktu register-rename). (Masih membutuhkan uop, dan slot di dalam pipa, jadi itu tidak gratis, hanya nol latensi). Ekstra MOV dalam rantai dep LEA adalah bagian dari bottleneck pada CPU lain.

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


Mengalahkan kompilator

GCC melakukan pekerjaan yang cukup bagus di sini. Itu bisa menghemat satu kode byte dengan menggunakan inc edx dari pada add edx, 1, karena tidak ada yang peduli tentang P4 dan dependensi-salahnya untuk instruksi-instruksi penginstalan bendera parsial.

Itu juga bisa menyimpan semua instruksi MOV, dan TEST: SHR set CF = bit bergeser keluar, jadi kita bisa menggunakan cmovc dari pada 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 mencabangkan pada hasil bendera SHR serta menggunakannya untuk CMOV: nol hanya jika n adalah 1 (atau 0) untuk memulai. (Fakta menarik: SHR dengan hitungan! = 1 pada Nehalem atau sebelumnya menyebabkan kios jika Anda membaca hasil bendera. Begitulah cara mereka membuatnya single-up. Namun, pengkodean khusus shift-by-1 baik-baik saja.)

Menghindari MOV tidak membantu dengan latensi sama sekali di Haswell (Dapatkah MOV x86 benar-benar "gratis"? Mengapa saya tidak dapat mereproduksi ini sama sekali?). Itu membantu secara signifikan pada CPU seperti Intel pre-IvB, dan AMD Bulldozer-family, di mana MOV bukan nol-latensi. Perintah MOV terbuang kompilator memang mempengaruhi jalur kritis. BD's complex-LEA dan CMOV keduanya memiliki latensi yang lebih rendah (masing-masing 2c dan 1c), jadi itu adalah fraksi yang lebih besar dari latensi. Juga, bottleneck throughput menjadi masalah, karena hanya memiliki dua pipa ALU bilangan bulat. Lihat jawaban @ johnfound, di mana dia memiliki hasil waktu dari CPU AMD.

Bahkan pada Haswell, versi ini dapat membantu sedikit dengan menghindari beberapa penundaan sesekali di mana uop non-kritis mencuri port eksekusi dari satu di jalur kritis, menunda eksekusi dengan 1 siklus. (Ini disebut konflik sumber daya). Ini juga menyimpan daftar, yang dapat membantu ketika melakukan banyak hal n nilai secara paralel dalam loop interleaved (lihat di bawah).

Latensi LEA bergantung pada mode pengalamatan, pada CPU Intel SnB-family. 3c untuk 3 komponen ([base+idx+const], yang mengambil dua penambahan terpisah), tetapi hanya 1c dengan 2 atau lebih sedikit komponen (satu tambah). Beberapa CPU (seperti Core2) bahkan melakukan 3-komponen LEA dalam satu siklus, tetapi SnB-family tidak. Lebih buruk, Intel SnB-family membakukan latensi sehingga tidak ada 2c Uops, jika tidak, 3-komponen LEA hanya 2c seperti Bulldozer. (LEA 3-komponen lebih lambat pada AMD juga, hanya tidak sebanyak).

Begitu lea rcx, [rax + rax*2] / inc rcx hanya 2c latency, lebih cepat daripada lea rcx, [rax + rax*2 + 1], pada CPU Intel SnB-family seperti Haswell. Break-even pada BD, dan lebih buruk di Core2. Itu biaya ekstra UOP, yang biasanya tidak layak untuk menyimpan latency 1c, tetapi latency adalah hambatan utama di sini dan Haswell memiliki pipa yang cukup luas untuk menangani throughput uop ekstra.

Baik gcc, icc, maupun clang (pada godbolt) menggunakan output CF SHR, selalu menggunakan AND atau TEST. Penyusun konyol. : P Mereka adalah bagian besar dari mesin yang rumit, tetapi manusia yang pandai sering dapat mengalahkan mereka dalam masalah berskala kecil. (Mengingat ribuan hingga jutaan kali lebih lama untuk memikirkannya, tentu saja! Compiler tidak menggunakan algoritme 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 di mikroarsitektur target, mereka hanya menggunakan beberapa heuristik.)


Pengulangan loop sederhana tidak akan membantu; kemacetan loop ini pada latency dari rantai ketergantungan loop-carry, bukan pada loop overhead / throughput. Ini berarti akan baik dengan hyperthreading (atau jenis SMT lainnya), karena CPU memiliki banyak waktu untuk interleave instruksi dari dua utas. Ini berarti paralelisasi loop dalam main, tapi itu bagus karena setiap utas hanya dapat memeriksa berbagai n nilai-nilai dan menghasilkan sepasang bilangan bulat sebagai hasilnya.

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

Caranya adalah memutuskan apakah akan menunggu sampai semua n nilai telah tercapai 1 sebelum memulai pasangan baru n nilai-nilai, atau apakah akan pecah 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 counter secara kondisional.


Anda bahkan bisa melakukan ini dengan SSE yang dikemas-bandingkan barang-barang ke conditionally increment counter untuk elemen vektor di mana n belum tercapai 1 namun. Dan kemudian untuk menyembunyikan latensi yang lebih panjang dari implementasi peningkatan bersyarat SIMD, Anda harus menyimpan lebih banyak vektor n nilai-nilai di udara. Mungkin hanya bernilai dengan 256b vektor (4x uint64_t).

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

Gagasan yang belum teruji 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

    # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure.  Probably worth it
    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, bukan asm tulisan tangan.


Peningkatan algoritme / implementasi:

Selain hanya menerapkan logika yang sama dengan asm yang lebih efisien, cari cara untuk menyederhanakan logika, atau hindari pekerjaan yang berlebihan. misalnya memoize untuk mendeteksi akhir umum ke urutan. Atau lebih baik lagi, lihat 8 bit trailing sekaligus (jawaban gnasher)

@EOF menunjukkan itu tzcnt (atau bsf) dapat digunakan untuk melakukan banyak hal n/=2 iterasi dalam satu langkah. Itu mungkin lebih baik daripada vectorizing SIMD, karena tidak ada SSE atau instruksi AVX yang bisa melakukannya. Ini masih kompatibel dengan melakukan skalar ganda ns paralel dalam register bilangan bulat yang berbeda.

Jadi perulangannya 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 pergeseran variabel-angka lambat pada CPU Intel SnB-family tanpa BMI2. 3 kali, 2c latensi. (Mereka memiliki ketergantungan input pada FLAGS karena count = 0 berarti flag tidak dimodifikasi. Mereka menangani ini sebagai ketergantungan data, dan mengambil beberapa Uops karena sebuah uop hanya dapat memiliki 2 input (pra-HSW / BDW juga)). Ini adalah jenis yang dikeluhkan orang tentang desain gila-CISC x86. Itu membuat CPU x86 lebih lambat dari yang seharusnya jika ISA dirancang dari nol hari ini, bahkan dengan cara yang hampir serupa. (yaitu ini adalah bagian dari "pajak x86" yang membutuhkan kecepatan / daya.) SHRX / SHLX / SARX (BMI2) adalah kemenangan besar (1 utop / 1c latensi).

Ini juga menempatkan tzcnt (3c pada Haswell dan kemudian) di jalur kritis, sehingga secara signifikan memperpanjang total latensi dari rantai ketergantungan loop-carry. Itu menghapus kebutuhan untuk CMOV, atau untuk mempersiapkan memegang register n>>1, meskipun. Jawaban @ Veedrac mengatasi semua ini dengan menunda tzcnt / shift untuk beberapa iterasi, yang sangat efektif (lihat di bawah).

Kami dapat dengan aman digunakan BSF atau TZCNT secara bergantian, karena n tidak pernah bisa nol pada saat itu. TZCNT's mesin-kode decode sebagai BSF pada CPU yang tidak mendukung BMI1. (Prefix tidak bermakna diabaikan, jadi REP BSF berjalan sebagai BSF).

TZCNT berkinerja jauh lebih baik daripada BSF pada CPU AMD yang mendukungnya, jadi ini bisa menjadi ide yang bagus untuk digunakan REP BSF, bahkan jika Anda tidak peduli tentang pengaturan ZF jika inputnya adalah nol daripada output. Beberapa kompiler melakukan ini ketika Anda menggunakan __builtin_ctzll bahkan 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-palsu pada operan output yang seharusnya hanya-menulis, seperti BSF, untuk mendukung perilaku tidak terdokumentasi bahwa BSF dengan input = 0 meninggalkan tujuannya tidak dimodifikasi. Jadi Anda perlu mengusahakannya kecuali mengoptimalkan hanya Skylake, jadi tidak ada yang didapat dari byte REP tambahan. (Intel sering berjalan di atas dan melampaui apa yang diperlukan oleh manual ISA x86, untuk menghindari pemutusan kode yang digunakan secara luas yang bergantung pada sesuatu yang seharusnya tidak dilakukan, atau yang secara retroaktif tidak diizinkan. Mis. Windows 9x mengasumsikan tidak ada pemadaman spekulatif terhadap entri TLB, yang aman saat kode ditulis, sebelum Intel memperbarui aturan manajemen TLB.)

Pokoknya, LZCNT / TZCNT di Haswell memiliki depalsu yang sama dengan POPCNT: lihat Q & A ini. Inilah sebabnya mengapa dalam output asm gcc untuk kode @ Veedrac, Anda melihatnya memecah rantai dep dengan xor-zeroing pada register ini akan digunakan sebagai tujuan TZCNT, ketika tidak menggunakan dst = src. Karena TZCNT / LZCNT / POPCNT tidak pernah meninggalkan tujuan mereka tidak terdefinisi atau tidak dimodifikasi, ketergantungan palsu pada output pada CPU Intel ini murni merupakan bug / pembatasan kinerja. Agaknya itu bernilai beberapa transistor / kekuatan untuk memiliki mereka berperilaku seperti Uops lain yang pergi ke unit eksekusi yang sama. Satu-satunya perangkat lunak yang terlihat adalah interaksi dengan batasan mikroarsitektur lainnya: mereka dapat menggabungkan mikro-operand memori dengan mode pengalamatan terindeks di Haswell, tetapi di Skylake, di mana Intel menghapus dependensi palsu untuk LZCNT / TZCNT, mode pengodean yang diindeks "tidak laminasi" sementara POPCNT masih bisa menggabungkan mikro mode addr apa pun.


Perbaikan ide / kode dari jawaban lain:

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

Saya merapikan / meningkatkan C (yang memandu compiler untuk menghasilkan asm lebih baik), dan menguji + bekerja lebih cepat asm (dalam komentar di bawah C) pada Godbolt: lihat tautan di Jawaban @ hidefromkgb. (Jawaban ini mencapai batas char 30k dari URL Godbolt yang besar, tapi tautan pendek bisa membusuk dan terlalu lama untuk goo.gl pula.)

Juga meningkatkan output-cetak untuk mengkonversi ke string dan membuatnya write() alih-alih menulis satu arang sekaligus. Ini meminimalkan dampak pada waktu seluruh program dengan perf stat ./collatz (untuk mencatat penghitung kinerja), dan saya mengaburkan beberapa asm non-kritis.


Kode @ Veedrac

Saya mendapat kecepatan yang sangat kecil dari pengalihan yang benar sebanyak yang kami lakukan tahu perlu dilakukan, dan memeriksa untuk melanjutkan pengulangan. Dari 7.5s untuk limit = 1e8 turun ke 7.275s, di Core2Duo (Merom), dengan faktor unroll 16.

kode + komentar pada Godbolt. Jangan gunakan versi ini dengan dentang; itu melakukan sesuatu yang konyol dengan penundaan-loop. Menggunakan penghitung tmp k dan kemudian menambahkannya count kemudian mengubah apa yang dilakukan clang, tapi itu sedikit sakit gcc.

Lihat diskusi dalam komentar: kode Veedrac adalah luar biasa pada CPU dengan BMI1 (yaitu bukan Celeron / Pentium)


1747
2017-11-01 07:04



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

Perbedaan waktu yang Anda lihat adalah karena kode assembly dalam pertanyaan sangat jauh dari optimal dalam loop bagian dalam.

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

Sebagai contoh, fungsi urutan dapat dioptimalkan hanya untuk 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 daripada kode C ++ dari pertanyaan (saat 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: urutan max = 525 pada i = 837799.


93
2017-11-01 08:29



Untuk kinerja lebih: Perubahan sederhana adalah mengamati bahwa setelah n = 3n + 1, n akan genap, sehingga Anda dapat membagi dengan 2 segera. Dan n tidak akan menjadi 1, jadi Anda tidak perlu mengujinya. Jadi Anda dapat menyimpan beberapa pernyataan jika 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;
    }
}

Ini a besar win: Jika Anda melihat 8 bit terendah n, semua langkah hingga Anda dibagi dengan 2 delapan kali sepenuhnya ditentukan oleh delapan bit tersebut. Sebagai contoh, jika delapan bit terakhir adalah 0x01, yaitu dalam biner nomor Anda adalah ???? 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. Sesuatu yang serupa akan terjadi untuk semua kombinasi. Jadi Anda dapat membuat lingkaran dengan pernyataan sakelar 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 titik itu n bisa menjadi 1 dengan kurang dari delapan divisi oleh 2, dan melakukan delapan atau lebih langkah 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 Anda capai 1.

PS. Saya sangat curiga bahwa saran Peter Cordes akan membuatnya lebih cepat. Tidak akan ada cabang bersyarat sama sekali kecuali satu, dan yang satu 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 pemrosesan 9, 10, 11, 12 bit terakhir pada suatu waktu akan lebih cepat. Untuk setiap bit, jumlah entri dalam tabel akan berlipat ganda, dan saya mengekspektasi perlambatan ketika tabel tidak sesuai dengan cache L1 lagi.

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

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

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


19
2017-11-02 10:04



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

  • [«Penentuan» pertama akhirnya dibantah oleh @ShreevatsaR; dihapus]

  • Ketika melintasi urutan, kita hanya bisa mendapatkan 3 kemungkinan kasus di 2-tetangga dari elemen saat ini N (ditampilkan pertama):

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

    Untuk melompat melewati 2 elemen ini berarti menghitung (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1 dan 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) sudah jelas. Kasus (2) menyiratkan (N & 1) == 1, jadi jika kita berasumsi (tanpa kehilangan keumuman) bahwa N adalah 2-bit panjang dan bit-bitnya ba dari yang paling-ke-paling-signifikan, lalu a = 1, dan yang berikut ini berlaku:

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

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

    Q.E.D .: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.

    Sebagaimana terbukti, kita dapat melintasi urutan 2 elemen pada satu waktu, menggunakan operasi terner tunggal. Pengurangan waktu 2 × lainnya.

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 kita bandingkan n > 2 karena proses dapat berhenti pada 2 bukannya 1 jika total panjang urutannya ganjil.

[EDIT:]

Mari kita terjemahkan ini menjadi perakitan!

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-perintah ini untuk dikompilasi:

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

Lihat C dan versi perbaikan / perbaikan bug oleh Peter Cordes pada Godbolt. (Catatan editor: Maaf karena memasukkan barang-barang saya ke dalam jawaban Anda, tetapi jawaban saya mencapai batas 30k char dari tautan Godbolt + teks!)


17
2017-11-01 19:35



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

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

  1. Pastikan sistem Anda dalam keadaan normal / tidak aktif. Hentikan semua proses yang berjalan (aplikasi) yang Anda mulai atau yang menggunakan CPU secara intensif (atau polling melalui jaringan).
  2. Ukuran datasize Anda harus lebih besar.
  3. Tes Anda harus berjalan untuk sesuatu yang lebih dari 5-10 detik.
  4. Jangan bergantung hanya pada satu sampel. Lakukan tes Anda N kali. Kumpulkan hasil dan hitung mean atau median hasilnya.

5
2017-11-01 06:26



Dari komentar:

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

Untuk banyak angka itu akan tidak meluap.

Jika akan meluap - untuk salah satu benih awal yang tidak beruntung, jumlah yang meluap akan sangat mungkin menyatu ke arah 1 tanpa luapan lainnya.

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

Setiap seri konvergen final sederhana dimulai dengan kekuatan dua nilai (cukup jelas?).

2 ^ 64 akan meluap ke nol, yang merupakan pengulangan tak terbatas berdasarkan algoritma (hanya berakhir dengan 1), tetapi solusi paling optimal dalam jawaban akan selesai karena shr rax menghasilkan ZF = 1.

Bisakah kita menghasilkan 2 ^ 64? Jika nomor awalnya 0x5555555555555555, itu angka ganjil, angka selanjutnya adalah 3n + 1, yang mana 0xFFFFFFFFFFFFFFFF + 1 = 0. Secara teoritis dalam keadaan tidak pasti algoritma, tetapi jawaban yang dioptimalkan dari johnfound akan pulih dengan keluar pada ZF = 1. Itu cmp rax,1 Peter Cordes akan berakhir dengan putaran tak terbatas (QED varian 1, "cheapo" melalui undefined 0 jumlah).

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 dengan serius. Tapi secara intuitif saya akan mengatakan seri ini akan menyatu menjadi 1 untuk setiap nomor: 0 <number, 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 pengulangan tak terbatas untuk seri asli, hanya luapan yang dapat menghambat kita.

Jadi saya hanya memasukkan beberapa angka ke dalam lembaran dan melihat angka 8 bit yang terpotong.

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

Tapi tidak ada nilai yang menciptakan biji pelimpah siklus.

Lucunya saya melakukan pemeriksaan, yang merupakan angka pertama yang menderita pemotongan 8 bit, dan sudah 27 terpengaruh! Itu mencapai nilai 9232 dalam seri non-terpotong yang tepat (nilai dipotong pertama adalah 322 di langkah ke-12), dan nilai maksimum yang dicapai untuk salah satu dari 2-255 nomor input dengan cara non-terpotong adalah 13120 (Untuk 255 sendiri), jumlah langkah maksimum untuk disatukan 1 adalah tentang 128 (+ -2, tidak yakin jika "1" adalah untuk menghitung, dll ...).

Cukup menarik (bagi saya) nomor tersebut 9232 maksimum untuk banyak nomor sumber lain, apa yang istimewa tentang itu? :-HAI 9232 = 0x2410 ... hmmm .. tidak tahu.

Sayangnya saya tidak dapat memahami seri ini secara mendalam, mengapa ia menyatu dan apa implikasi dari memangkasnya ke k bit, tetapi dengan cmp number,1 kondisi terminating tentu saja mungkin untuk menempatkan algoritma ke dalam infinite loop dengan nilai input tertentu berakhir sebagai 0 setelah pemotongan.

Tapi nilainya 27 melimpah untuk 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 bilangan k-bit bilangan bulat. Untuk 8 bit bilangan bulat, 146 nomor dari 256 telah mempengaruhi seri dengan pemotongan (beberapa dari mereka mungkin masih memukul jumlah langkah yang benar secara tidak sengaja mungkin, saya terlalu malas untuk memeriksa).


4
2017-11-01 17:18



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 50% kemungkinan salah mengartikan cabang, dan itu akan menjadi mahal.

Compiler hampir pasti melakukan kedua perhitungan (yang biaya jauh lebih banyak karena div / mod adalah latensi yang cukup panjang, sehingga perkalian-tambah adalah "gratis") dan menindaklanjuti dengan CMOV. Yang, tentu saja, memiliki nol persen kemungkinan salah didiktekan.


4
2017-11-01 19:50