Pakeitus 32 bitų kontūrą su 64 bitų reikšmėmis, atsiranda beprasmiški skirtumai

Aš ieškojau sparčiausių būdų popcount didelius duomenų popcount . Aš bėgo į labai keistą efektą: pakeitus linijos kintamąjį nuo unsigned į uint64_t , mano kompiuterio našumas sumažėjo 50%.

Lyginamoji analizė

 #include <iostream> #include <chrono> #include <x86intrin.h> int main(int argc, char* argv[]) { using namespace std; if (argc != 2) { cerr << "usage: array_size in MB" << endl; return -1; } uint64_t size = atol(argv[1])<<20; uint64_t* buffer = new uint64_t[size/8]; char* charbuffer = reinterpret_cast<char*>(buffer); for (unsigned i=0; i<size; ++i) charbuffer[i] = rand()%256; uint64_t count,duration; chrono::time_point<chrono::system_clock> startP,endP; { startP = chrono::system_clock::now(); count = 0; for( unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with unsigned for (unsigned i=0; i<size/8; i+=4) { count += _mm_popcnt_u64(buffer[i]); count += _mm_popcnt_u64(buffer[i+1]); count += _mm_popcnt_u64(buffer[i+2]); count += _mm_popcnt_u64(buffer[i+3]); } } endP = chrono::system_clock::now(); duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "unsigned\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } { startP = chrono::system_clock::now(); count=0; for( unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with uint64_t for (uint64_t i=0;i<size/8;i+=4) { count += _mm_popcnt_u64(buffer[i]); count += _mm_popcnt_u64(buffer[i+1]); count += _mm_popcnt_u64(buffer[i+2]); count += _mm_popcnt_u64(buffer[i+3]); } } endP = chrono::system_clock::now(); duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "uint64_t\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } free(charbuffer); } 

Kaip matote, mes sukuriame atsitiktinių duomenų buferį, kurio dydis yra x megabaitai, kur x skaitomas iš komandų eilutės. Tada mes popcount per buferį ir panaudosime išplėstinę x86 popcount versiją, kad įvykdytume „popcount“. Norėdami gauti tikslesnį rezultatą, mes darome 10 000 kartų. Mes matuojame laiko skaičiavimą. uint64_t vidinis ciklo kintamasis yra unsigned , o mažesni, vidinis ciklo kintamasis yra uint64_t . Maniau, kad tai nebuvo svarbu, bet buvo priešingai.

Rezultatai (visiškai nenormalu)

Aš ją sukompiliuosiu (versija g ++: Ubuntu 4.8.2-19ubuntu1):

 g++ -O3 -march=native -std=c++11 test.cpp -o test 

Čia pateikiami mano Haswell Core i7-4770K procesoriaus @ 3,50 GHz rezultatai, test 1 (taip, kad 1 atsitiktinis MB duomenų):

  • nepasirašyta 41959360000 0.401554 sek 26.113 GB / s
  • uint64_t 41959360000 0.759822 sek 13.8003 GB / s

Kaip matote, tik pusė uint64_t versijos našumo yra viena iš unsigned versijų! Problema yra ta, kad sukuriamas kitas surinkimas, bet kodėl? Pirma, aš galvojau apie kompiliatoriaus klaidą, todėl bandžiau c> (Ubuntu C>

 c> 

Rezultatas: test 1

  • nepasirašytas 41959360000 0,398293 sek 26,3267 Gb / s
  • uint64_t 41959360000 0.680954 sek 15.3986 Gb / s

Taigi tai yra beveik tas pats rezultatas ir vis dar keistas. Bet dabar ji tampa super keista. Aš pakeisiu buferio, kuris buvo perskaitytas iš įvesties, dydį, kurio konstanta yra 1 , todėl pakeisiu:

 uint64_t size = atol(argv[1]) << 20; 

į

 uint64_t size = 1 << 20; 

Taigi kompiliatorius dabar žino buferio dydį kompiliavimo metu. Galbūt jis gali pridėti keletą optimizacijų! Čia yra g++ numeriai:

  • nepasirašyta 41959360000 0.509156 sek 20.5944 GB / s
  • uint64_t 41959360000 0.508673 sek 20.6139 GB / s

Dabar abi versijos yra vienodai greitai. Tačiau unsigned gavo dar lėčiau ! Jis nukrito nuo 26 iki 20 GB/s , taip pakeičiant ne pastovią vertę pastovia verte, bus sumažintas optimizavimas . Rimtai, aš nesuprantu, kas čia vyksta! Bet dabar, jei norite c> su nauja versija:

  • nepasirašytas 41959360000 0.677009 sek 15.4884 GB / s
  • uint64_t 41959360000 0.676909 sek 15.4906 GB / s

Palaukite, ką? Dabar abi versijos sumažėjo iki 15 bps. Taigi, netinkamos vertės keitimas pastovia verte netgi sukelia lėtą kodą C>

Aš paprašiau kolegos iš CPU

1250
01 авг. geksicido rinkinys 01 rug . 2014-08-01 13:33 '14 at 13:33 2014-08-01 13:33
@ 10 atsakymų

Kaltininkas: False Data priklausomybė (ir kompiliatorius net nežino apie tai)

Sandy / Ivy Bridge ir Haswell procesorių instrukcijose:

 popcnt src, dest 

atrodo, kad turi klaidingą priklausomybę nuo paskirties vietos. Nors instrukcija tik rašo, komanda laukia, kol dest bus paruoštas vykdyti.

Ši priklausomybė ne tik išlaiko 4 „ popcnt iš vienos kilpos iteracijos. Jis gali turėti kintamojo ciklo iteracijas, todėl procesoriui neįmanoma lygiagrečiai naudoti skirtingų ciklo iteracijų.

unsigned uint64_t ir kiti uint64_t tiesiogiai neturi įtakos problemai. Bet jie veikia registro paskirstytoją, kuris priskiria registrus kintamiesiems.

Jūsų atveju greitis yra tiesioginis rezultatas, kuris yra įstrigo priklausomybės grandinėje (false), priklausomai nuo to, ką registro paskirstytojas nusprendė daryti.

  • 13 GB / s turi grandinę: popcnt - add - popcnt - popcnt → kitas kartojimas
  • 15 GB / s turi grandinę: popcnt - add - popcnt - add → kitą iteraciją
  • 20 GB / s turi grandinę: popcnt - popcnt → kitą iteraciją
  • 26 GB / s turi grandinę: popcnt - popcnt → kitą iteraciją

Skirtumas tarp 20 GB / s ir 26 GB / s atrodo mažas netiesioginio adresavimo artefaktas. Bet kuriuo atveju procesorius pradeda pataikyti į kitas kliūtis, kai tik pasieksite šį greitį.


Norėdami tai išbandyti, naudoju inline kūrinį, kad apečiau kompiliatorių ir gautų tiksliai tą norimą pastatą. Aš taip pat suskirstiau count kintamąjį, kad sugriautumėte visas kitas priklausomybes, kurios galėtų išbandyti bandymus.

Pateikiami rezultatai:

„Sandy Bridge Xeon @ 3,5 GHz“ (visas testo kodas pateikiamas žemiau)

  • GCC 4.6.3: g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
  • Ubuntu 12

Įvairūs registrai: 18,6195 Gb / s

 .L4: movq (%rbx,%rax,8), %r8 movq 8(%rbx,%rax,8), %r9 movq 16(%rbx,%rax,8), %r10 movq 24(%rbx,%rax,8), %r11 addq $4, %rax popcnt %r8, %r8 add %r8, %rdx popcnt %r9, %r9 add %r9, %rcx popcnt %r10, %r10 add %r10, %rdi popcnt %r11, %r11 add %r11, %rsi cmpq $131072, %rax jne .L4 

Tas pats registras: 8.49272 GB / s

 .L9: movq (%rbx,%rdx,8), %r9 movq 8(%rbx,%rdx,8), %r10 movq 16(%rbx,%rdx,8), %r11 movq 24(%rbx,%rdx,8), %rbp addq $4, %rdx # This time reuse "rax" for all the popcnts. popcnt %r9, %rax add %rax, %rcx popcnt %r10, %rax add %rax, %rsi popcnt %r11, %rax add %rax, %r8 popcnt %rbp, %rax add %rax, %rdi cmpq $131072, %rdx jne .L9 

Tas pats registras su skaldyta grandine: 17,8869 Gb / s

 .L14: movq (%rbx,%rdx,8), %r9 movq 8(%rbx,%rdx,8), %r10 movq 16(%rbx,%rdx,8), %r11 movq 24(%rbx,%rdx,8), %rbp addq $4, %rdx # Reuse "rax" for all the popcnts. xor %rax, %rax # Break the cross-iteration dependency by zeroing "rax". popcnt %r9, %rax add %rax, %rcx popcnt %r10, %rax add %rax, %rsi popcnt %r11, %rax add %rax, %r8 popcnt %rbp, %rax add %rax, %rdi cmpq $131072, %rdx jne .L14 

Taigi, kas atsitiko su kompilatoriumi?

Atrodo, kad nei GCC, nei „Visual Studio“ nežino, kad „ popcnt turi tokią klaidingą priklausomybę. Tačiau šios klaidingos priklausomybės nėra retos. Tai tik klausimas, ar kompiliatorius apie tai žino.

popcnt “ nėra visiškai naudojamas instrukcija. Todėl nenuostabu, kad didelis kompiliatorius galėtų praleisti kažką panašaus. Taip pat nėra jokių dokumentų, kuriose minėta ši problema. Jei „Intel“ to neatskleidžia, nė vienas iš jų nežino, kol kažkas atsitiks su ja.

( Atnaujinimas: Pradedant nuo 4.9.2 versijos , GCC žino apie šią klaidingą priklausomybę ir generuoja kodą, kad kompensuotų šį optimizavimą. Dideli kompiliatoriai iš kitų tiekėjų, įskaitant „C>

Kodėl procesorius turi tokią klaidingą priklausomybę?

Mes galime tik atspėti, bet, greičiausiai, „Intel“ turi tokį patį apdorojimą, kad gautų kelias instrukcijas su dviem operandais. Bendrosios instrukcijos, pvz., add , atlieka du operandus, kurie abu yra įėjimai. Taigi, „Intel“ tikriausiai pradėjo tos pačios kategorijos „ popcnt , kad supaprastintų procesoriaus dizainą.

Atrodo, kad AMD procesoriai neturi tokios klaidingos priklausomybės.


Visą bandymo kodą rasite toliau pateikiamoje nuorodoje:

 #include <iostream> #include <chrono> #include <x86intrin.h> int main(int argc, char* argv[]) { using namespace std; uint64_t size=1<<20; uint64_t* buffer = new uint64_t[size/8]; char* charbuffer=reinterpret_cast<char*>(buffer); for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256; uint64_t count,duration; chrono::time_point<chrono::system_clock> startP,endP; { uint64_t c0 = 0; uint64_t c1 = 0; uint64_t c2 = 0; uint64_t c3 = 0; startP = chrono::system_clock::now(); for( unsigned k = 0; k < 10000; k++){ for (uint64_t i=0;i<size/8;i+=4) { uint64_t r0 = buffer[i + 0]; uint64_t r1 = buffer[i + 1]; uint64_t r2 = buffer[i + 2]; uint64_t r3 = buffer[i + 3]; __asm__( "popcnt %4, %4 \n\t" "add %4, %0 \n\t" "popcnt %5, %5 \n\t" "add %5, %1 \n\t" "popcnt %6, %6 \n\t" "add %6, %2 \n\t" "popcnt %7, %7 \n\t" "add %7, %3 \n\t" : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3) : "r" (r0), "r" (r1), "r" (r2), "r" (r3) ); } } count = c0 + c1 + c2 + c3; endP = chrono::system_clock::now(); duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } { uint64_t c0 = 0; uint64_t c1 = 0; uint64_t c2 = 0; uint64_t c3 = 0; startP = chrono::system_clock::now(); for( unsigned k = 0; k < 10000; k++){ for (uint64_t i=0;i<size/8;i+=4) { uint64_t r0 = buffer[i + 0]; uint64_t r1 = buffer[i + 1]; uint64_t r2 = buffer[i + 2]; uint64_t r3 = buffer[i + 3]; __asm__( "popcnt %4, %%rax \n\t" "add %%rax, %0 \n\t" "popcnt %5, %%rax \n\t" "add %%rax, %1 \n\t" "popcnt %6, %%rax \n\t" "add %%rax, %2 \n\t" "popcnt %7, %%rax \n\t" "add %%rax, %3 \n\t" : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3) : "r" (r0), "r" (r1), "r" (r2), "r" (r3) : "rax" ); } } count = c0 + c1 + c2 + c3; endP = chrono::system_clock::now(); duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "Chain 4 \t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } { uint64_t c0 = 0; uint64_t c1 = 0; uint64_t c2 = 0; uint64_t c3 = 0; startP = chrono::system_clock::now(); for( unsigned k = 0; k < 10000; k++){ for (uint64_t i=0;i<size/8;i+=4) { uint64_t r0 = buffer[i + 0]; uint64_t r1 = buffer[i + 1]; uint64_t r2 = buffer[i + 2]; uint64_t r3 = buffer[i + 3]; __asm__( "xor %%rax, %%rax \n\t" // <--- Break the chain. "popcnt %4, %%rax \n\t" "add %%rax, %0 \n\t" "popcnt %5, %%rax \n\t" "add %%rax, %1 \n\t" "popcnt %6, %%rax \n\t" "add %%rax, %2 \n\t" "popcnt %7, %%rax \n\t" "add %%rax, %3 \n\t" : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3) : "r" (r0), "r" (r1), "r" (r2), "r" (r3) : "rax" ); } } count = c0 + c1 + c2 + c3; endP = chrono::system_clock::now(); duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "Broken Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } free(charbuffer); } 

Ne mažiau įdomių gairių galima rasti čia: http://pastebin.com/kbzgL8si
Šis kriterijus pakeičia priklausomybės grandinėje esančių „ popcnt “ skaičių (klaidingą).

 False Chain 0: 41959360000 0.57748 sec 18.1578 GB/s False Chain 1: 41959360000 0.585398 sec 17.9122 GB/s False Chain 2: 41959360000 0.645483 sec 16.2448 GB/s False Chain 3: 41959360000 0.929718 sec 11.2784 GB/s False Chain 4: 41959360000 1.23572 sec 8.48557 GB/s 
1404
02 авг. atsakymas pateikiamas Mysticial 02 rug . 2014-08-02 01:41 '14 ne 1:41 am 2014-08-02 01:41

Aš kodavau lygiavertę eksperimentavimo programą ir galiu patvirtinti šį keistą elgesį. size_t daugiau, gcc mano, kad 64 bitų sveikasis skaičius (kuris tikriausiai turėtų būti size_t ...) turėtų būti geresnis, nes naudojant uint_fast32_t gcc naudoja 64 bitų uint.

Aš šiek tiek dirbau su pastatu:
Tiesiog paimkite 32 bitų versiją, pakeiskite visas 32 bitų instrukcijas / registrus 64 bitų versijoje „popcount“ programos vidinėje linijoje. Stebėjimas: kodas yra toks pat greitas kaip 32 bitų versija!

Akivaizdu, kad tai yra nulaužimas, nes kintamojo dydis iš tikrųjų nėra 64 bitų, nes kitos programos dalys vis dar naudoja 32 bitų versiją, tačiau tol, kol vidinė „popcount“ kilpa dominuoja našumu, tai yra geras pradžia.

Tada nukopijuoju vidinės linijos kodą iš 32 bitų programos versijos, nulaužiau jį iki 64 bitų, atkūrus registrus, kad jį pakeistumėte 64 bitų versijos vidine kilpa. Šis kodas taip pat veikia taip pat greitai, kaip 32 bitų versija.

Aš padariau išvadą, kad tai yra prastas kompiliatoriaus komandų planavimas, o ne tikrasis 32 bitų instrukcijų greitis / vėlavimas.

(Atsargiai: aš įsilaužiau į susirinkimą, galėčiau kažką sulaužyti be pastebėjimo.

border=0
49
02 авг. atsakymą pateikė EOF 02 rug. 2014-08-02 01:55 '14 at 1:55 2014-08-02 01:55

Tai nėra atsakymas, tačiau sunku skaityti, jei pateikiu rezultatus komentaruose.

Šiuos rezultatus gaunu naudojant „ Mac Pro“ („ Westmere 6-Cores Xeon 3.33 GHz“). Aš c> jį su c> ( c> gauti tą patį rezultatą).

su uint64_t size=atol(argv[1])<<20;

 unsigned 41950110000 0.811198 sec 12.9263 GB/s uint64_t 41950110000 0.622884 sec 16.8342 GB/s 

uint64_t size=1<<20;

 unsigned 41950110000 0.623406 sec 16.8201 GB/s uint64_t 41950110000 0.623685 sec 16.8126 GB/s 

Aš taip pat bandžiau:

  • Atšaukite bandymo užsakymą, rezultatas bus tas pats, kad pašalintumėte talpyklos veiksnį.
  • Paleiskite for (uint64_t i=size/8;i>0;i-=4) atvirkštine tvarka: for (uint64_t i=size/8;i>0;i-=4) . Tai duoda tą patį rezultatą ir įrodo, kad kompiliatorius pakankamai protingas, kad ne kiekvienu iteracijos būdu padalintų dydį 8 (kaip tikėtasi).

Štai mano laukinis spėjimas:

Greičio koeficientas susideda iš trijų dalių:

  • kodo talpykla: uint64_t versija turi didesnį kodo dydį, tačiau tai neturi įtakos mano „Xeon“ procesoriui. Tai lėtina 64 bitų versiją.

  • Naudotos instrukcijos. Atkreipkite dėmesį ne tik į ciklų skaičių, bet ir į buferį su 32 bitų ir 64 bitų indeksu dviem versijomis. Paspaudus 64 bitų nuokrypį rodyklę, reikalingas specialus 64 bitų registras ir adresavimas, o jūs galite naudoti tiesioginį 32 bitų poslinkį. Tai gali padaryti 32 bitų versiją greičiau.

  • Instrukcijos išduodamos tik 64 bitų kompiuteryje (t.y., iš anksto pateikiant). Tai leidžia 64 bitų greičiau.

Šie trys veiksniai kartu sutampa su tariamai prieštaringais rezultatais.

24
01 авг. Atsakymas duodamas „ Ne maskable Interrupt 01 rug. 2014-08-01 14:04 '14, 14:04 2014-08-01 14:04

Aš negaliu pateikti autoritetingo atsakymo, bet pateikiu galimą priežastį. Ši nuoroda aiškiai parodo, kad jūsų ciklo kūno instrukcijose yra santykis tarp vėlavimo ir dažnių juostos pločio 3: 1. Taip pat parodomas keleto siuntimo poveikis. Kadangi šiuolaikiniuose x86 procesoriuose yra (duoti ar priimti) trys visai vienetai, paprastai galite siųsti tris komandas per ciklą.

Taigi, tarp didžiausio dujotiekio ir daugelio dažnių juostos pločio ir šių mechanizmų atsisakymo turime šešis veiklos rodiklius. Visai gerai žinoma, kad x86 instrukcijų rinkinio sudėtingumas yra gana paprastas keistai pertraukai. Šis dokumentas yra puikus pavyzdys:

Pentium 4 pasirodymas 64 bitų teisingiems poslinkiams yra labai blogas. 64 bitų kairysis poslinkis ir visi 32 bitų poslinkiai turi priimtiną našumą. Atrodo, kad duomenų kelias iš 32 didžiausių 32 bitų ALU apačioje yra prastai sukurtas.

Aš asmeniškai susidūriau su keistu atveju, kai karštoji linija dirbo daug lėčiau keturių branduolių lusto (AMD, jei prisimenu) branduolyje. Tiesą sakant, žemėlapyje pasiekėme geresnius rezultatus - sumažinkite skaičiavimus išjungdami šį branduolį.

Čia manau, kad konkursas visoms dalims: kad „ popcnt skaitiklis, kilpos skaitiklis ir adreso skaičiavimas gali veikti tik visu greičiu, naudojant 32 bitų skaitiklį, bet 64 bitų skaitiklis sukelia konkurenciją ir kioskų konvejerį. Kadangi iš viso yra apie 12 ciklų, potencialiai 4 ciklai su keliais dispečeriais, kiekvienam ciklui atlikti, vienas stovas gali pagrįstai paveikti vykdymo laiką 2 kartus.

Pakeičiamas dėl statinio kintamojo naudojimo, kuris, manau, tik sukelia nereikšmingą nurodymų pertvarkymą, yra dar vienas raktas į tai, kad 32 bitų kodas yra tam tikru konkurencijos nutraukimo momentu.

Žinau, kad tai nėra išsami analizė, tačiau tai yra patikimas paaiškinimas.

10
01 авг. atsakymas duotas Gene 01 rug. 2014-08-01 23:12 '14, 23:12 2014-08-01 23:12

Bandžiau tai atlikti naudojant „ Visual Studio 2013 Express“ , naudodamas rodyklę vietoj indekso, kuris šiek tiek pagreitino procesą. Įtariu, kad tai yra todėl, kad adresavimas yra perkeltas + registruoti, o ne kompensuoti + registruoti + (registruoti <3). C + + kodas.

  uint64_t* bfrend = buffer+(size/8); uint64_t* bfrptr; // ... { startP = chrono::system_clock::now(); count = 0; for (unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with uint64_t for (bfrptr = buffer; bfrptr < bfrend;){ count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); count += __popcnt64(*bfrptr++); } } endP = chrono::system_clock::now(); duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count(); cout << "uint64_t\t" << count << '\t' << (duration/1.0E9) << " sec \t" << (10000.0*size)/(duration) << " GB/s" << endl; } 

statymo kodas: r10 = bfrptr, r15 = bfrend, rsi = skaičius, rdi = buferis, r13 = k:

 $LL5@main: mov r10, rdi cmp rdi, r15 jae SHORT $LN4@main npad 4 $LL2@main: mov rax, QWORD PTR [r10+24] mov rcx, QWORD PTR [r10+16] mov r8, QWORD PTR [r10+8] mov r9, QWORD PTR [r10] popcnt rdx, rax popcnt rax, rcx add rdx, rax popcnt rax, r8 add r10, 32 add rdx, rax popcnt rax, r9 add rsi, rax add rsi, rdx cmp r10, r15 jb SHORT $LL2@main $LN4@main: dec r13 jne SHORT $LL5@main 
10
02 авг. atsakymas pateikiamas rcgldr 02 rug . 2014-08-02 06:48 '14 at 6:48 2014-08-02 06:48

Ar bandėte perduoti -funroll-loops -fprefetch-loop-arrays į GCC?

Su šiais papildomais optimizavimais gaunu šiuos rezultatus:

 [1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1 model name : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz [1829] /tmp/so_25078285 $ g++ --version|head -n1 g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3 [1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3 [1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11 test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays [1829] /tmp/so_25078285 $ ./test_o3 1 unsigned 41959360000 0.595 sec 17.6231 GB/s uint64_t 41959360000 0.898626 sec 11.6687 GB/s [1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1 unsigned 41959360000 0.618222 sec 16.9612 GB/s uint64_t 41959360000 0.407304 sec 25.7443 GB/s 
9
04 авг. atsakymas duotas Dangelov 04 rug . 2014-08-04 18:37 '14 at 18:37 2014-08-04 18:37

Ar bandėte išeiti iš kontūro? Šiuo metu turite duomenų priklausomybę, kuri iš tikrųjų nereikalinga.

Pabandykite:

  uint64_t subset_counts[4] = {}; for( unsigned k = 0; k < 10000; k++){ // Tight unrolled loop with unsigned unsigned i=0; while (i < size/8) { subset_counts[0] += _mm_popcnt_u64(buffer[i]); subset_counts[1] += _mm_popcnt_u64(buffer[i+1]); subset_counts[2] += _mm_popcnt_u64(buffer[i+2]); subset_counts[3] += _mm_popcnt_u64(buffer[i+3]); i += 4; } } count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3]; 

Jūs taip pat turite keistą anti-aliasingą, kad nesu įsitikinęs, ar jis atitinka griežtas slapyvardžių taisykles.

7
01 авг. Ben Voigt atsakymas rugpjūčio 01 d 2014-08-01 21:33 '14, 21:33 2014-08-01 21:33

Tl; DR: vietoj to naudokite __builtin vidines __builtin .

Gebėjau gcc 4.8.4 (ir net 4.7.3 gcc.godbolt.org) sukurti optimalų kodą šiam naudojimui __builtin_popcountll , kuris naudoja tą patį kūrimo nurodymą, bet neturi šios klaidingos priklausomybės klaidos.

Aš nesu 100% tikras mano lyginamojo indekso kodas, tačiau objdump atrodo objdump mano nuomonėmis. Aš naudoju keletą kitų gudrybių ( ++i vs i++ ), kad galėčiau sudaryti kompiliavimo ciklą be movl instrukcijų (keistai elgtis, turiu pasakyti).

Rezultatai:

 Count: 20318230000 Elapsed: 0.411156 seconds Speed: 25.503118 GB/s 

Palyginamojo kodo kodas:

 #include <stdint.h> #include <stddef.h> #include <time.h> #include <stdio.h> #include <stdlib.h> uint64_t builtin_popcnt(const uint64_t* buf, size_t len){ uint64_t cnt = 0; for(size_t i = 0; i < len; ++i){ cnt += __builtin_popcountll(buf[i]); } return cnt; } int main(int argc, char** argv){ if(argc != 2){ printf("Usage: %s <buffer size in MB>\n", argv[0]); return -1; } uint64_t size = atol(argv[1]) << 20; uint64_t* buffer = (uint64_t*)malloc((size/8)*sizeof(*buffer)); // Spoil copy-on-write memory allocation on *nix for (size_t i = 0; i < (size / 8); i++) { buffer[i] = random(); } uint64_t count = 0; clock_t tic = clock(); for(size_t i = 0; i < 10000; ++i){ count += builtin_popcnt(buffer, size/8); } clock_t toc = clock(); printf("Count: %lu\tElapsed: %f seconds\tSpeed: %f GB/s\n", count, (double)(toc - tic) / CLOCKS_PER_SEC, ((10000.0*size)/(((double)(toc - tic)*1e+9) / CLOCKS_PER_SEC))); return 0; } 

Rinkimo parinktys:

 gcc --std=gnu99 -mpopcnt -O3 -funroll-loops -march=native bench.c -o bench 

GCC versija:

 gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4 

Linux branduolio versija:

 3.19.0-58-generic 

Procesoriaus informacija:

 processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 70 model name : Intel(R) Core(TM) i7-4870HQ CPU @ 2.50 GHz stepping : 1 microcode : 0xf cpu MHz : 2494.226 cache size : 6144 KB physical id : 0 siblings : 1 core id : 0 cpu cores : 1 apicid : 0 initial apicid : 0 fpu : yes fpu_exception : yes cpuid level : 13 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx rdtscp lm constant_tsc nopl xtopology nonstop_tsc eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm arat pln pts dtherm fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid xsaveopt bugs : bogomips : 4988.45 clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtual power management: 
5
04 мая '16 в 14:14 2016-05-04 14:14 atsakymas pateikiamas assp1r1n3 04 gegužės 16 d. 14:14 2016-05-04 14:14

Na, noriu trumpai atsakyti į vieną iš VP klausimų, kurie, atrodo, nėra nagrinėjami esamuose klausimuose. Atsargumo žodis: nepadariau jokių bandymų, kodų generavimo ar išardymo, tik norėjau pasidalinti idėja, kurią kiti galėtų paaiškinti.

Kodėl static keitimas veikia?

Laikoma linija: uint64_t size = atol(argv[1])<<20;

Trumpas atsakymas

Norėčiau pažvelgti į surinktą rinkinį, kad galėčiau pasiekti size ir sužinoti, ar yra papildomų veiksmų nukreipti žymeklį, susijusį su nestatine versija.

Длинный ответ

Поскольку существует только одна копия переменной, независимо от того, была ли она объявлена static или нет, а размер не изменился, я предполагаю, что различие заключается в расположении памяти, используемой для хранения переменной вместе с тем, где она используется в коде. дальше.

Хорошо, чтобы начать с очевидного, помните, что всем локальным переменным (вместе с параметрами) функции предоставляется место в стеке для использования в качестве хранилища. Теперь очевидно, что стек стека для main() никогда не очищается и генерируется только один раз. Хорошо, а как насчет того, чтобы сделать его static ? Что ж, в этом случае компилятор знает, что нужно зарезервировать пространство в глобальном пространстве данных процесса, поэтому его местоположение не может быть очищено удалением стекового фрейма. Но, тем не менее, у нас есть только одно местоположение, так в чем же разница? Я подозреваю, что это связано с тем, как ссылки на ячейки памяти в стеке упоминаются.