Kodėl šis „C ++“ kodas yra greitesnis nei mano rašytinis „Collatz“ hipotezės testavimas?

Šiuos du sprendimus parašiau „ Project Euler Q14“ statyboje ir „C ++“. Jie atitinka tą pačią brutalia jėgos metodą, kad būtų galima išbandyti Collatz hipotezę . Surinkimo tirpalas buvo surinktas naudojant

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

C ++ buvo sudarytas su

 g++ p14.cpp -o p14 

Sukurkite, 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; } 

Aš žinau apie kompiliatoriaus optimizavimą, kad būtų pagerintas greitis ir kad tai yra, bet nematau daug būdų optimizuoti savo kūrimo sprendimą (o ne matematiniu būdu).

C ++ kodas turi modulį kiekvienam nariui ir padalijimą kiekvienam lygiaverčiam skaičiui nariui, kur surinkimas yra tik vienas padalinys už vienodą numerį.

Tačiau pastatas trunka vidutiniškai 1 sekundę ilgiau nei C ++ sprendimas. Kodėl taip? Aš klausiu smalsumo.

Redaguoti: užsakymo laikas

Mano sistema: 64 bitų Linux su 1,4 GHz „Intel Celeron 2955U“ („Haswell“ mikroarchitektūra).

689
01 нояб. dovana sūnus 01 nov. 2016-11-01 09:12 '16 at 9:12 2016-11-01 09:12
@ 11 atsakymų

Jei manote, kad 64 bitų DIV komanda yra geras būdas jį padalyti į dvi dalis, nenuostabu, kad asm kompiliatoriaus išvestis viršijo jūsų rankinį kodą net su -O0 (greitai sukompiliuoti, be papildomo optimizavimo ir saugojimo / perkrovimo į atmintį po / prieš kiekvienam C operatoriui, kad derintojas galėtų keisti kintamuosius).

Kaip rašyti efektyvų asm., Žr. „ Agner Fog Optimizing Assembly“ vadovą . Jame taip pat yra instrukcijų lapai ir mikroarchyvinis vadovas, skirtas konkretiems procesoriams. Taip pat žr.

Taip pat žiūrėkite bendresnį klausimą apie kompiliatoriaus užkirtimą rankiniu parašu: Ar įmontuota surinkimo kalba yra lėtesnė nei vietinis C + + kodas? . TL: DR: taip, jei tai neteisinga (pvz., Šis klausimas).

Paprastai jūs puikiai sutinkate su kompilatoriumi, ypač jei bandote parašyti C ++, kuris gali būti efektyviai surenkamas . Taip pat žiūrėkite, kaip sukurti greičiau nei surašytos kalbos? . Vienas iš atsakymų yra susijęs su šiais tvarkingais skaidres , rodančiais, kaip įvairūs C kompiliatoriai optimizuoja kai kurias tikrai paprastas funkcijas, naudodami triukus.


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

„Intel Haswell“, div r64 - 36 valandos, su 32–96 ciklų atidėjimu ir vieno iš 21–74 ciklų našumu. (Be to, 2 kartus sukonfigūruokite RBX ir nulinį RDX, bet vykdymas iš eilės gali jas pradėti anksčiau). Aukšto lygio nurodymai, pvz., DIV, yra mikroduomenys, kurie taip pat gali sukelti naujų žinių. Tokiu atveju vėlavimas yra svarbiausias veiksnys, nes jis priklauso tikslinės priklausomybės grandinei.

shr rax, 1 atlieka tą patį nepasirašytą skaidinį: 1 uop, su 1c vėlavimu ir gali dirbti 2 kartus per parą.

Palyginimui, 32 bitų padalijimas yra greitesnis, bet vis dar baisus nuo pamainų. idiv r32 - 9 valandos, 22–29 s ir vienas - 8–11c pralaidumas Haswell.


Kaip matote iš gcc- -O0 asm išvesties („ Godbolt Explorer“ , ji naudoja tik pamainas . „ -O0 naiviai kaupia, kaip jūs manėte, netgi naudodami 64 bitų IDIV du kartus. (Optimizuojant, kompiliatoriai naudoja abu IDIV išėjimus, kai šaltinis atlieka padalijimą ir modulį su tais pačiais operandais, jei jie visai naudoja IDIV

Persijos įlankos bendradarbiavimo taryba nėra visiškai naivus; jis visada konvertuojamas per „GIMPLE“, o tai reiškia, kad kai kurių „optimizacijų“ negalima išjungti . Tai apima suskirstymo pagal konstantą ir perjungimų (galios 2) arba daugialypės atvirkštinės fiksuoto taško transformacijos (ne galios 2), kad būtų išvengta IDIV, atpažinimo (žr. „Div_by_13“ pirmiau pateiktoje „godbolt“ nuorodoje).

gcc -Os (dydžio optimizavimas), deja, naudoja IDIV atskyrimui be įgaliojimų 2, net ir tais atvejais, kai daugkartinis atvirkštinis kodas yra tik šiek tiek didesnis, bet daug lėčiau.


Kompiliatoriaus pagalba

(šios bylos santrauka: naudokite uint64_t n )

Visų pirma, įdomu tik pažvelgti į optimizuotą kompiliatoriaus produkciją. ( -O3 ). -O0 greitis iš esmės yra beprasmis.

Pažvelkite į savo „ASM“ išvestį („Godbolt“ arba žr. „ Kaip pašalinti„ triukšmą “) iš GCC / c> ). Kai kompiliatorius nepateikia optimalaus kodo: C / C + + šaltinio rašymas tokiu būdu, kuris padeda kompiliatoriui sukurti geriausią kodą, paprastai yra geriausias būdas . Jūs turėtumėte žinoti ace ir žinoti, kad jūs veiksmingai, bet netiesiogiai taikote šias žinias. Kompiliatoriai taip pat yra geras idėjų šaltinis: kartais užklijuoja kažką atvėsti, ir jūs galite rankiniu būdu paimti gcc tą patį dalyką: žr. Šį atsakymą ir tai, ką aš padariau su nepanaudotu kilpu toliau pateiktame @Veedrac kode.)

Šis požiūris yra nešiojamas, o po 20 metų kai kuris ateities kompiliatorius gali jį sukompiliuoti į būsimą įrangą (x86 ar ne), galbūt naudojant naują ISA plėtinį arba automatinį vektorizavimą. Nuo 15 metų ranka parašytas x86-64 asm paprastai nebūtų optimaliai pritaikytas Skylake. pavyzdžiui, tuo metu makro ir makrokomandų palyginimas nebuvo atliktas. Tai, kas dabar yra optimali vieno mikro architektūros asm rankinei architektūrai, gali būti netinkama kitiems dabartiniams ir būsimiems procesoriams. Pastabos dėl atsakymo @johnfound aptaria pagrindinius skirtumus tarp „AMD Bulldozer“ ir „Intel Haswell“, kurie labai veikia šį kodą. Tačiau teoriškai g++ -O3 -march=bdver3 ir g++ -O3 -march=skylake padarys teisingą dalyką. (Arba -march=native .) Arba -mtune=... tiesiog sukonfigūravote nenaudodami kitų CPU palaikomų instrukcijų.

Manau, kad kompiliatoriaus vadovas „asm“, kuris tinka dabartiniam procesoriui, kuriam rūpi, neturėtų būti problema būsimiems kompiliatoriams. Tikimės, kad jie yra geresni nei šiuolaikiniai kompiliatoriai, ieškodami būdų, kaip konvertuoti kodą ir rasti būdą, kuris veikia būsimiems procesoriams. Nepaisant to, ateityje x86 greičiausiai nebus baisus, jei kas nors geras dabartiniame x86, o būsimas kompiliatorius vengs bet kokių klaidų, susijusių su ASM, įgyvendindamas kažką panašaus duomenų perdavimo iš jūsų „C“ šaltinio, jei jis nieko nemato tai geriau

Rankinis raštas yra juoda dėžutė optimizatoriui, todėl pastovus paskirstymas neveikia, kai įdėjimas daro įvestį kompiliavimo laiko konstantu. Taip pat paveikti kiti pokyčiai. Prieš naudodami asm, skaitykite https://gcc.gnu.org/wiki/DontUseInlineAsm . (Ir venkite MSVC stiliaus įmontuoto asm: I / O turėtų eiti per atmintį, kuri prideda pridėtines vertes .)

Šiuo atveju : jūsų n turi pasirašytą tipą, o gcc naudoja SAR / SHR / ADD seką, kuri suteikia tinkamą apvalinimą. (IDIV ir aritmetinis poslinkis „apvalus“, skirtingai neigiamoms įvestims, žr. SAR insn set ref rankinį įrašą ). (IDK, jei gcc bandė ir nepavyko įrodyti, kad n negali būti neigiamas ar kažkas. Pasirašytas perpildymas yra neapibrėžtas elgesys, todėl jis turėjo būti galimas.)

Jūs uint64_t n naudoti uint64_t n , todėl jis gali būti tik SHR. Todėl jis perkeliamas į sistemas, kuriose long tik 32 bitų (pvz., „X86-64“ Windows).


„BTW“, gcc optimizuotas asm išvestis atrodo gana gera (naudojant unsigned long n ) : vidinė kilpa, įterpta į main() , yra tokia:

  # 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 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 

Vidinė kilpa yra šakojasi, o kritinės grandinės kelias yra priklausomi nuo ciklo:

  • 3 komponentų LEA (3 ciklai)
  • cmov (2 ciklai Haswell, 1c - Broadwell ar vėlesni).

Iš viso: 5 ciklai per iteraciją, laukimo trukmė . Neišsipildžiusi, viskas bus paraleluota kartu (tai teoriškai: aš neišbandžiau, naudojant perfometrus, kad pamatytumėte, ar jis tikrai veikia 5c / iter).

„FLAGS cmov (sukurta pagal TEST) yra greitesnė už RAX išvestį (iš LEA-> MOV), todėl ji nėra kritiniame kelyje.

Panašiai MOV-> SHR, kuris generuoja CMOV RDI įvestį, atjungiamas nuo kritinio kelio, nes jis taip pat yra greitesnis nei LEA. MOV ant IvyBridge ir vėliau turi nulinį vėlavimą (apdorojamas, kai registras pervadinamas). (Jis vis dar užima uop ir lizdą dujotiekyje, todėl jis nėra laisvas, tik nulinis latentinis laikotarpis). Papildomas MOV LEA detektoriaus grandinėje yra kitų procesorių kliūtis.

cmp / etc taip pat nėra kritinio kelio dalis: jis nėra perkeliamas į kilpą, nes valdymo priklausomybės yra apdorojamos filialo prognozėmis + spekuliaciniu vykdymu, kitaip nei duomenų priklausomybės nuo kritinio kelio.


Kovos sudarytojas

GCC čia gerai sekė. Jis galėjo išsaugoti vieną baito kodą, naudodamas inc edx o ne add edx, 1 , nes niekas nerūpi apie P4 ir jo klaidingas priklausomybes dėl instrukcijų dėl dalinės vėliavos modifikavimo.

Jis taip pat gali išsaugoti visas MOV instrukcijas ir TEST: SHR nustato CF = bitą, todėl mes galime naudoti cmovc vietoj 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 = n%2 cmovc rax, rcx # n= (n ? 3*n+1 : n/2; inc edx # ++count; cmp rax, 1 jne .L9 #}while(n!=1) 

Žr. @Johnfound atsakymą į kitą protingą triuką: pašalinkite CMP, padalinkite jį į SHR vėliavos rezultatą ir naudokite jį CMOV: nulis tik tada, jei n buvo 1 (arba 0). (Patenkinamas faktas: SHR su skaičiumi! = 1 Nehalem'e ar anksčiau sukelia suskirstymą, jei perskaitėte vėliavos rezultatus . Štai kaip jie padarė vienakūrį. Po-1 specialus kodavimas yra gerai.)

Išvengimas MOV nepadeda vėluoti „Haswell“ ( ar „MOV x86“ tikrai gali būti „laisvas“? Kodėl aš negaliu jų visiškai atkurti? ). Tai labai padeda procesoriams, tokiems kaip „Intel pre-IvB“ ir „AMD Bulldozer“ šeima, kur MOV neturi nulinio latentinio laiko. Kompiliatoriaus išeikvotos komandos MOV tikrai veikia kritinį kelią. BD kompleksas-LEA ir CMOV yra tiek mažesnis latentinis laikas (atitinkamai 2c, tiek 1c), todėl tai yra didelė delsos dalis. Be to, dažnių juostos pločio problemos tampa problema, nes joje yra tik du ALU kanalai. Žr. @Johnfound atsakymą, kur jis gauna rezultatus iš AMD procesoriaus.

Net ir Haswelle, ši versija gali šiek tiek padėti, vengiant kai kurių atsitiktinių vėlavimų, kai nepriimtinas wop pavogia vykdymo prievadą iš vieno kritinio kelio, atidedant 1 ciklo vykdymą. (Tai vadinama išteklių konfliktu). Jis taip pat saugo registrą, kuris gali padėti atlikti keletą n reikšmių lygiagrečiai kintančioje kilpoje (žr. Žemiau).

LEA latencija priklauso nuo adresavimo režimo , „Intel SnB“ procesorių šeimose. 3c 3 komponentams ( [base+idx+const] , kurie priima du atskirus priedus), bet tik 1c su 2 ar mažiau komponentų (vienas pridedamas). Kai kurie procesoriai (pvz., Core2) netgi atlieka 3 komponentų LEA vieną ciklą, tačiau „SnB“ šeima to nedaro. Blogiau, „ Intel SnB“ šeima standartizuoja latenciją, todėl nėra 2c uops , kitaip 3 komponentų LEA bus tik 2c, kaip ir buldozeris. (3 komponentų LEA dėl AMD taip pat yra lėtesnė, tiesiog ne taip).

Taigi, „ lea rcx, [rax + rax*2] / inc rcx yra tik 2c-latency, greičiau nei „ lea rcx, [rax + rax*2 + 1] „Intel SnB“ šeimos procesoriuose, pvz., „Haswell“. „BD“ spraga ir dar blogiau „Core2“. Tai kainuoja papildomą uop, kuri paprastai nėra verta taupyti 1c latentinį laiką, tačiau latencija yra pagrindinė kliūtis čia, o Haswell turi gana platų papildomo pralaidumo tvarkymo vamzdyną.

Nei gcc, icc, nei c> . Kvaili kompiliatoriai: P Tai puikūs sudėtingų technologijų kūriniai, tačiau protingas žmogus dažnai gali juos nugalėti dėl nedidelių problemų. (Žinoma, apie tūkstančius kartų ilgiau galvoti apie tai! Kompiliatoriai nenaudoja išsamių algoritmų, kad surastų visus galimus būdus, kaip padaryti kažką, nes daug laiko įdėti įterpto kodo optimizavimui. Jie taip pat nekonstruoja dujotiekio tikslinėje mikroarchitektūroje, o tiesiog naudokite kai kurias heuristikas.)


Paprastas kontūro valymas nepadės ; Šis ciklas yra su ciklu susijusi priklausomybės grandinė, o ne ciklo srautas / našumas. Tai reiškia, kad ji bus gera su hiperflow (arba bet kokios kitos rūšies SMT), nes procesorius turi daug laiko, kad pakeistų instrukcijas iš dviejų siūlų. Tai reikštų kilpų lygiagretinimą main , bet tai gerai, nes kiekvienas gija gali tiesiog patikrinti n reikšmių diapazoną ir sukurti keletą sveikų skaičių.

Perkėlimas rankiniu būdu per vieną giją taip pat gali būti gyvybingas . Galbūt skaičiuojate lygiagrečiai eilių poroms seką, nes kiekvienas iš jų užima tik porą registrų ir visi gali atnaujinti tą patį max / maxi . Tai sukuria didesnį lygiagretumo lygį .

Apgaulė nusprendžia, ar palaukti, kol visos n reikšmės pasieks 1 , prieš gaunant kitą n pradinių verčių porą, ar suskaidant ir gaunant naują pradinį tašką tik galutinei sąlygai, neliesdami skirtingos sekos registrų. Tikriausiai geriausia laikyti kiekvieną grandinę naudingais duomenimis, kitaip turėsite sąlyginai padidinti skaitiklį.


Galbūt netgi galite tai padaryti su pakuotės SSE paketu, kad būtų galima sąlyginai padidinti vektoriaus elementų skaitiklį, kur n dar nepasiekė 1 . Ir tada, norėdami paslėpti dar didesnį vėlavimą įgyvendinti SIMD sąlyginį prieaugį, reikės išlaikyti daugiau n reikšmių vektorių ore. Jis gali būti vertas tik su 256b vektoriu (4x uint64_t ).

Manau, kad geriausia strategija, kaip aptikti 1 lipnus, yra užmaskuoti visus tuos vektorius, kuriuos pridedate, kad padidintumėte skaitiklį. Taigi, po to, kai pamatysite 1 elementą, prieaugio vektorius turės nulį ir + = 0 - ne-op.

Neribota idėja rankiniam vektorizavimui

 # 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. 

Jūs galite ir turėtumėte tai padaryti su savimi, o ne rankiniu būdu.


Patobulintas algoritmas / įgyvendinimas:

Be to, kad būtų įgyvendinta ta pati logika su efektyvesne asm, ieškokite būdų, kaip supaprastinti logiką arba išvengti nereikalingo darbo. pavyzdžiui, prisiminkite, kad nustatytumėte bendras sekų pabaigas. Arba dar geriau, pažiūrėkite į 8 galinius bitus (gnasher atsakymas)

@EOF nurodo, kad tzcnt (arba bsf ) gali būti panaudota daugeliui n/=2 pakartojimų vienu žingsniu atlikti. Tai tikriausiai geriau nei SIMD vektorizavimas, nes jokia SSE ar AVX instrukcija negali tai padaryti. Tačiau jis vis dar yra suderinamas su kelių skalarų n vykdymu įvairiuose sveikų skaičių registruose.

Taigi kilpa gali atrodyti taip:

 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); 

Tai gali lemti gerokai mažesnį iteracijų skaičių, bet „Intel SnB“ šeimos procesoriai be BMI2 yra lėtinami permainų su kintamu skaičiumi. 3 uops, 2c latency. (Jie turi įvesties priklausomybę nuo FLAGS, nes skaičius = 0 reiškia, kad vėliavos nėra modifikuotos. Jie traktuoja kaip duomenų priklausomybę ir priima keletą uops, nes uop gali turėti tik 2 įėjimus (iki HSW / BDW) . Tai yra tie, kuriuos nurodo žmonės, skundę dėl CISC x86 crazy dizaino. Tai daro x86 procesorius lėtesnius, nei būtų buvę, jei ISA būtų sukurta nuo nulio šiandien, netgi iš esmės taip pat. (t. y. tai yra „x86 mokesčio“ dalis, kuri kainuoja greitį / galią.) SHRX / SHLX / SARX (BMI2) - didelis laimėjimas (1 minutė / 1 s).

Ji taip pat įkelia tzcnt (3c į Haswell ir vėlesnį) į kritinį kelią, todėl ji žymiai pailgina su kilpa susijusią priklausomybės grandinės vėlavimą. Tačiau tai pašalina CMOV poreikį arba registrų registrą n>>1 . „@Veedrac“ atsakymas įveikė visa tai, atidėdamas tzcnt / shift keletą iteracijų, kurios yra labai veiksmingos (žr. Žemiau).

Mes galime saugiai naudoti BSF ar TZCNT , nes n niekada negali būti nulis. Mechaninis TZCNT kodas dekoduojamas kaip BSF procesoriams, kurie nepalaiko BMI1. (Infinite prefiksai ignoruojami, todėl BSF REP veikia kaip BSF).

TZCNT veikia daug geriau nei BSF su AMD procesoriais, kurie jį palaiko, todėl gerai naudoti REP BSF , net jei jums nereikia nustatyti ZF, jei įvesties signalas yra nulis, o ne išėjimas. Kai kurie kompiliatoriai tai daro, kai naudojate __builtin_ctzll net su -mno-bmi .

Jie daro tą patį „Intel“ procesoriuose, taigi tiesiog išsaugokite baitus, jei tai yra svarbu. „Intel“ TZCNT (pre-Skylake) vis dar turi melagingą priklausomybę nuo tariamai rašomojo išvesties operando, taip pat į BSF, kad palaikytų nepatvirtintą elgesį, kuriame BSF su įvesties = 0 palieka tikslą nepakeistą. Поэтому вам нужно обойти это, если не оптимизировать только для Skylake, так что ничего не получить от дополнительного байт REP. (Intel часто выходит за рамки того, что требует руководство по ISA x86, чтобы не нарушать широко используемый код, который зависит от чего-то, чего он не должен, или это ретроактивно запрещено. Например: Windows 9x не предполагает спекулятивной предварительной выборки записей TLB , что было безопасно, когда код был написан, до того, как Intel обновит правила управления TLB .)

В любом случае, LZCNT/TZCNT на Haswell имеют то же самое ложное значение, что и POPCNT: см. этот Q A . Вот почему в gcc asm output для кода @Veedrac вы видите разрыв цепочки dep с xor-zeroing в регистре, который он собирается использовать в качестве адресата TZCNT, когда он не использует dst = src. Поскольку TZCNT/LZCNT/POPCNT никогда не покидают свой пункт назначения undefined или немодифицированы, эта ложная зависимость от выхода на процессорах Intel является исключительно ошибкой/ограничением производительности. Предположительно, это стоит каких-то транзисторов/мощности, чтобы заставить их вести себя как другие uops, идущие к одному и тому же исполнительному блоку. Единственный программно-видимый потенциал - во взаимодействии с другим микроархитектурным ограничением: они могут скомпилировать операнд памяти с индексированным режимом адресации на Haswell, но на Skylake, где Intel удалили ложную зависимость для LZCNT/TZCNT, они "не ламинируют" индексированные режимы адресации, в то время как POPCNT все еще может замаскировать любой режим addr.


Усовершенствования идей/кода из других @:

@hidefromkgb answer имеет хорошее наблюдение, что вы гарантированно сможете сделать одну правую смену после 3n + 1. Вы можете вычислить это еще более эффективно, чем просто оставить проверки между шагами. Однако реализация asm в этом ответе прерывается (зависит от OF, который undefined после SHRD со счетом > 1) и медленный: ROR rdi,2 быстрее, чем SHRD rdi,rdi,2 , и используя две инструкции CMOV на критический путь медленнее, чем дополнительный TEST, который может работать параллельно.

Я поместил tidied/улучшенный C (который помогает компилятору создать лучший asm) и протестировал + работать быстрее asm (в комментариях ниже C) вверх на Godbolt: см. ссылку в @hidefromkgb answer . (Этот ответ попал в предел 30 тыс. char из больших URL-адресов Godbolt, но shortlinks может гнить и слишком долго для goo.gl.)

Также улучшена печать вывода, чтобы преобразовать в строку и сделать один write() вместо того, чтобы писать один char за раз. Это минимизирует влияние на выбор времени всей программы с помощью perf stat ./collatz (для записи счетчиков производительности), и я де-запутывал некоторые некритические asm.


Код @Veedrac