Yra <greičiau nei <=?

Aš perskaičiau knygą, kurioje autorius sako, kad if( a < 901 ) greitesnis nei if( a <= 900 ) .

Nemėgsta šiame paprastame pavyzdyje, tačiau yra nedideli pokyčiai sudėtingo kilpos kodo veikime. Manau, kad tai turėtų daryti kažką su sukurtu mašinos kodu, jei tai net tiesa.

1431
27 авг. pateikė Vinícius Magalhães Horta 27 rug. 2012-08-27 05:10 '12 at 5:10 am 2012-08-27 05:10
šaltinis
@ 14 atsakymų

Ne, dauguma architektūrų nebus greičiau. Nenurodėte, bet x86 atveju visi integriniai palyginimai paprastai atliekami dviem instrukcijomis:

  • test arba cmp kuris įdiegia EFLAGS
  • Ir „ Jcc (perėjimas) , priklausomai nuo palyginimo tipo (ir kodo išdėstymo):
    • jne Peršokti, jei ne lygus → ZF = 0
    • jz - Peršokti, jei nulis (lygus) → ZF = 1
    • jg - Pereiti, jei daugiau → ZF = 0 and SF = OF
    • (ir tt)

Pavyzdys (redaguotas, kad būtų $ gcc -m32 -S -masm=intel test.c ) Sudaryta su $ gcc -m32 -S -masm=intel test.c

  mov eax, DWORD PTR [esp+24] ; a cmp eax, DWORD PTR [esp+28] ; b jge .L2 ; jump if a is >= b ; Do something 1 .L2: 

ir

  mov eax, DWORD PTR [esp+24] ; a cmp eax, DWORD PTR [esp+28] ; b jg .L5 ; jump if a is > b ; Do something 2 .L5: 

Taigi vienintelis skirtumas tarp jų yra „ jg prieš „ jge . Šie du veiksmai užims tą patį laiką.


Norėčiau atkreipti dėmesį į pastabą, kad niekas nenurodo, kad skirtingos pereinamojo laikotarpio instrukcijos užima tiek pat laiko. Tai šiek tiek sunku atsakyti, bet tai, ką galiu duoti, yra: „ Intel“ instrukcijų Jcc jie visi sugrupuoti pagal vieną bendrąjį nurodymą, „ Jcc (eiti, jei įvykdyta sąlyga). Tą pačią grupę sudaro optimizavimo informacinis vadovas , C priedas. Vėlavimas ir našumas.

Vėlavimas - laikrodžio ciklų, kurių reikia branduoliui užbaigti, skaičius, kad būtų užbaigti visi μops, kurie sudaro nurodymą.

Bandwidth . - Laiko ciklų skaičius, kurio reikia laukti, kol probleminiai prievadai vėl galės priimti tą patį nurodymą. Daugeliui instrukcijų instrukcijų perdavimas gali būti žymiai mažesnis už jo atidėjimą.

Jcc reikšmės:

Redaguoti: slankusis taškas

Tai pasakytina ir apie x87-slankiojo kablelio: (gana daug to paties kodo, kaip ir anksčiau, bet double vietoj int .)

1608
27 авг. Jonathon Reinhart atsakymas 2012-08-27 05:13 '12 at 5:13 2012-08-27 05:13
šaltinis

Istoriškai (kalbame apie 1980-ųjų ir dešimtojo dešimtmečio pradžią) buvo keletas architektūrų, kuriose tai buvo tiesa. Pagrindinė problema yra ta, kad sveikasis skaičius lyginamas su sveikais skaičiais. Tai sukelia šiuos atvejus.

 Comparison Subtraction ---------- ----------- A < B --> A - B < 0 A = B --> A - B = 0 A > B --> A - B > 0 

Dabar, kai A < B , atimtis turėtų užimti daug bitų, kad būtų tinkamai atimama, kaip ir nešiojant ir skolindami pridedant ir atimant rankiniu būdu. Šis „pasiskolintas“ bitas paprastai vadinamas nešimo bitu ir gali būti patvirtintas filialo instrukcija. Antrasis bitas, vadinamas nuliniu bitu, bus nustatytas, jei atimtis lygi nuliui vienodai, o tai reiškia lygybę.

Paprastai buvo bent du sąlyginiai filialo nurodymai, vienas - šakotam į nešimo bitą ir vienas - nulinis.

Dabar, norėdami suprasti klausimo esmę, leiskite mums išplėsti ankstesnę lentelę, kad būtų įtraukti nulio ir nulio bitų rezultatai.

 Comparison Subtraction Carry Bit Zero Bit ---------- ----------- --------- -------- A < B --> A - B < 0 0 0 A = B --> A - B = 0 1 1 A > B --> A - B > 0 1 0 

Taigi filialo įgyvendinimas A < B gali būti vykdomas vienoje komandoje, nes nešiojamoji bitė yra aiški tik šiuo atveju, ty,

 ;; Implementation of "if (A < B) goto address;" cmp A, B ;; compare A to B bcz address ;; Branch if Carry is Zero to the new address 

Bet jei norime palyginti mažiau nei lygiaverčius, turime atlikti papildomą nulinės vėliavos patikrinimą, kad sugautume lygybės bylą.

 ;; Implementation of "if (A <= B) goto address;" cmp A, B ;; compare A to B bcz address ;; branch if A < B bzs address ;; also, Branch if the Zero bit is Set 

Taigi, kai kuriose mašinose, naudojant „mažesnį“ palyginimą, galima išsaugoti vieną mašinų instrukciją. Tai buvo svarbi procesoriaus ir atminties 1: 1 sub-megahercų procesoriaus greičio ir greičio santykio eroje, tačiau šiandien ji beveik neturi reikšmės.

575
27 авг. Atsakyti Lucas 27 rug. 2012-08-27 20:53 '12 8:53 pm 2012-08-27 20:53
šaltinis

Darant prielaidą, kad kalbame apie vidinius sveikųjų skaičių tipus, nėra jokio būdo, kaip greičiau nei kitas. Jie akivaizdžiai yra semantiškai identiški. Jie abu prašo kompiliatoriaus daryti tą patį. Tik siaubingai sugadintas kompiliatorius sugeneruotų neišsamus kodą vienam iš jų.

Jei buvo tam tikra platforma, kur < buvo greitesnis nei <= paprastiems sveiko skaičiaus tipams, kompiliatorius visada turėtų konvertuoti <= į < konstantoms. Bet kuris kompiliatorius, kuris būtų ne tik blogas kompiliatorius (šiai platformai).

85
27 авг. Atsakymas, kurį pateikė David Schwartz 27 rug. 2012-08-27 05:31 '12 at 5:31 am 2012-08-27 05:31
šaltinis

Matau, kad tai nėra. Kompiliatorius generuoja tą patį mašinos kodą kiekvienoje būsenoje, kurios vertė yra kitokia.

 if(a < 901) cmpl $900, -4(%rbp) jg .L2 if(a <=901) cmpl $901, -4(%rbp) jg .L3 

Mano pavyzdys yra GCC x86_64 Linux.

Kompiliatorių rašytojai yra gana protingi žmonės, ir jie galvoja apie šiuos dalykus ir daugelį kitų, dauguma iš mūsų jį laiko savaime suprantamu dalyku.

Pastebėjau, kad jei jis nėra pastovus, tada tas pats mašinos kodas generuojamas.

 int b; if(a < b) cmpl -4(%rbp), %eax jge .L2 if(a <=b) cmpl -4(%rbp), %eax jg .L3 
66
27 авг. atsakymą pateikė Adrian Cornish 27 rug. 2012-08-27 05:16 '12 at 5:16 am 2012-08-27 05:16
šaltinis

Kintamojo taško kodo palyginimas <= iš tiesų gali būti lėtesnis (vienas nurodymas vienu metu) net ir šiuolaikinėje architektūroje. Čia yra pirmoji funkcija:

 int compare_strict(double a, double b) { return a < b; } 

„PowerPC“ pirmiausia atliekamas kintamo taško palyginimas (kuris atnaujina „ cr , būklės registrą), o po to paverčia būklės registrą į GPR, perkelia „palyginkite mažiau“ bitą ir tada grįžta. Jis priima keturias instrukcijas.

Dabar apsvarstykite šią funkciją:

 int compare_loose(double a, double b) { return a <= b; } 

Tam reikalingas tas pats darbas, kaip aukščiau, compare_strict ankstesniu compare_strict , bet dabar yra du įdomūs bitai: „buvo mažiau“ ir „buvo lygūs“. Tam reikia papildomos komandos („ cror - bitų arba OR būklės registras), kad šie du bitai būtų sujungti į vieną. Todėl compare_loose reikalauja penkių nurodymų, o compare_strict keturių.

Galbūt manote, kad kompiliatorius gali optimizuoti antrąją funkciją taip:

 int compare_loose(double a, double b) { return ! (a > b); } 

Tačiau tai neteisingai apdoroja NaN. NaN1 <= NaN2 ir NaN1 > NaN2 turėtų būti vertinami kaip klaidingi.

50
27 авг. atsakymas duotas ridiculous_fish rugpjūčio 27 d. 2012-08-27 21:32 '12 at 9:32 pm 2012-08-27 21:32
šaltinis

Galbūt šios nenurodytos knygos autorius skaito, a > 0 yra greitesnis nei a >= 1 , ir mano, kad tai tikrai universalus.

Tačiau taip yra dėl to, kad dalyvauja 0 (kadangi CMP , priklausomai nuo architektūros, gali būti pakeista, pavyzdžiui, OR ), o ne dėl < .

34
27 авг. atsakymas pateikiamas glglgl 27 rug . 2012-08-27 16:05 '12 at 4:05 pm 2012-08-27 16:05
šaltinis

Bent jau, jei taip buvo, kompiliatorius gali triviškai optimizuoti <= b į! (a> b), todėl net jei palyginimas iš tikrųjų buvo lėčiau, su visais, išskyrus pačių naivų kompiliatorius, nepastebėtumėte skirtumo.

30
27 авг. atsakymą pateikė Eliot Ball 27 rug. 2012-08-27 12:23 '12 12:23 val. 2012-08-27 12:23
šaltinis

Jie turi tą patį greitį. Gali būti, kad tam tikroje konkrečioje architektūroje, kurią jis teisingai pasakė, bet x86 šeimoje, bent jau žinau, kad jie yra tie patys. Dėl to CPU vykdys pagrindą (a - b) ir tada patikrins vėliavos registracijos vėliavą. Du šio registro bitai vadinami ZF (nulio vėliava) ir SF (ženklo vėliava), ir tai atliekama vienu ciklu, nes tai bus daroma naudojant vieną kaukę.

15
27 авг. atsakymas suteiktas Masoud 27 rug. 2012-08-27 11:25 '12, 11:25 am 2012-08-27 11:25
šaltinis

Tai labai priklausys nuo bazinės architektūros, su kuria yra sudaryta C. Kai kurie procesoriai ir architektūros gali turėti aiškius nurodymus vienodiems ar mažesniems ir lygiems, kurie vykdomi skirtingais ciklų skaičiais.

Tai būtų gana neįprasta, nors kompiliatorius gali jį apeiti, todėl nereikšmingas.

13
27 авг. atsakymas duotas Telginui 27 rugpjūčio mėn . 2012-08-27 05:15 '12 at 5:15 am 2012-08-27 05:15
šaltinis

Tl; DR atsakymas

Daugumai architektūros, kompiliatoriaus ir kalbos derinių tai nebus greičiau.

Visas atsakymas

Kiti atsakymai buvo sutelkti į x86 architektūrą, ir aš nežinau ARM architektūros (kaip atrodo jūsų montuotojo pavyzdys) pakankamai gerai, kad galėtumėte komentuoti specialiai sukurtą kodą, tačiau tai yra labai architektūriniu požiūriu specifinio optimizavimo pavyzdys. kaip optimizavimas .

Taigi, manau, kad toks mikrooptimalizavimas yra kulto apkrovos programavimo pavyzdys , o ne geriausia programinės įrangos kūrimo praktika.

Tikriausiai yra keletas architektūrų, kuriose tai yra optimizavimas, bet aš žinau bent vieną architektūrą, kurioje gali būti tiesa. Garbingoje Transputer architektūroje mašinos kodo instrukcijos buvo vienodos ir didesnės nei lygios, todėl visi palyginimai turėjo būti sukurti iš šių primityvių.

Net ir tada beveik visais atvejais kompiliatorius galėjo supaprastinti vertinimo instrukcijas, kad praktiškai jokio palyginimo nebūtų jokio pranašumo prieš kitus. Blogiausiu atveju gali tekti pridėti atvirkštinę instrukciją (REV), norint pakeisti operandų steką į viršų du elementus. Tai buvo vieno baito instrukcija, kuriai reikėjo užbaigti vieną ciklą, todėl buvo mažiausios galimos išlaidos.

Nesvarbu, ar tai yra optimalus optimizavimas ar optimizavimas, priklauso nuo konkrečios naudojamos architektūros, todėl paprastai yra bloga idėja priprasti prie architektūros specifinių mikroprocesorių, kitaip galite instinktyviai naudoti vieną, kai tai netinkama. ir saugo jūsų skaitomą knygą.

11
31 авг. Mark Booth atsakymas rugpjūčio 31 d 2012-08-31 21:33 '12, 21:33 2012-08-31 21:33
šaltinis

Jūs negalėsite pastebėti skirtumo, net jei jis yra. Be to, praktiškai jums reikės papildomų a + 1 arba a - 1 , kad sąlyga būtų vertinga, jei nenorite naudoti tam tikrų magiškų konstantų, o tai yra labai bloga praktika.

6
27 авг. atsakymas duotas shinkou rugpjūčio 27 d 2012-08-27 05:17 '12 at 5:17 am 2012-08-27 05:17
šaltinis

Galima sakyti, kad eilutė yra teisinga daugelyje skriptų kalbų, nes papildomas simbolis leidžia šiek tiek lėčiau apdoroti kodą. Tačiau, kaip nurodė pagrindinis atsakymas, jis neturėtų turėti įtakos C ++, o viskas, kas padaryta su skriptų kalba, tikriausiai nėra susijusi su optimizavimu.

3
29 авг. atsakymą pateikė Ecksters 29 rug . 2012-08-29 05:47 '12 at 5:47 am 2012-08-29 05:47
šaltinis

Kai parašiau šį atsakymą, aš svarstiau tik pavadinimo klausimą apie <vs. <= kaip visuma, o ne konkretus konstanta a < 901 palyginti su a <= 900 pavyzdys. Daugelis kompiliatorių visuomet sumažina konstantų vertę konvertuodami tarp < ir <= , pavyzdžiui, nes tiesioginis x86 operandas turi trumpesnį 1 baitą už -128 .. 127.

ARM ir ypač AArch64 atveju galimybė koduoti kaip tiesioginę priklauso nuo galimybės siaurą lauką paversti bet kuria žodžio padėtimi. Taigi, cmp w0, #0x00f000 bus užkoduota ir cmp w0, #0x00effff gali būti ne. Taigi palyginimo taisyklė su kompiliavimo laiko konstantu ne visada taikoma AArch64.


<vs. <= apskritai, įskaitant kintamuosius runtime

Daugumoje mašinų montavimo kalba palyginimas <= turi tokias pačias išlaidas kaip ir palyginimas < . Tai taikoma neatsižvelgiant į tai, ar jūs jį padalijote, prisijungiate, kad sukurtumėte sveiką skaičių 0/1, arba naudokite jį kaip pasirinkimo laisvės pasirinkimo operacijos predikatą (pvz., CMOV x86). Kiti atsakymai buvo susiję tik su šia klausimo dalimi.

Tačiau šis klausimas susijęs su C + + operatoriais, optimizatoriaus įvesties duomenimis. Paprastai jie abu yra vienodai veiksmingi; knygos patarimai skamba visiškai fiktyviai, nes kompiliatoriai visada gali konvertuoti jų atliktą palyginimą asm. Tačiau yra bent viena išimtis, kai naudojant <= gali atsitiktinai sukurti kažką, ko kompiliatorius negali optimizuoti.

Kaip ciklo sąlyga, yra atvejų, kai <= kokybiškai skiriasi nuo < , kai jis neleidžia kompiliatoriui įrodyti, kad ciklas nėra begalinis. Tai gali padaryti didelį skirtumą išjungiant automatinį vektorizavimą.

Nepatvirtintas perpildymas aiškiai apibrėžiamas kaip 2 bazinis apėjimas, o ne pasirašytas perpildymas (UB). Pasirašyti kilpos skaitikliai paprastai yra apsaugoti nuo to, nes kompiliatoriai, optimizuojantys UB co ++i <= size perpildymo perpildymą, nepasireiškia: ++i <= size visada baigsis klaidingu. ( Ką kiekvienas C programuotojas turėtų žinoti apie nenustatytą elgesį )

 void foo(unsigned size) { unsigned upper_bound = size - 1; // or any calculation that could produce UINT_MAX for(unsigned i=0 ; i <= upper_bound ; i++) ... 

Kompiliatorius galima optimizuoti tik taip, kad būtų išsaugotas (apibrėžtas ir teisiškai pastebimas) C ++ šaltinio elgesys visoms galimoms įvesties vertėms , išskyrus tas, kurios lemia neapibrėžtą elgesį.

(Paprasta problema atsirastų ir „ i <= size , bet maniau, kad viršutinės ribos apskaičiavimas buvo realesnis pavyzdys, kaip atsitiktinai įvesti begalinę kilpą, kuri jus domina, bet kurią kompiliatorius turi atsižvelgti.)

Tokiu atveju size=0 rezultatų upper_bound=UINT_MAX , o i <= UINT_MAX visada teisinga. Taigi ši kilpa yra begalė size=0 , ir kompiliatorius turi į tai atsižvelgti, net jei jūs, kaip programuotojas, tikriausiai niekada neketinate perkelti dydžio = 0. Jei kompiliatorius gali įterpti šią funkciją į skambinimo funkciją, kur jis gali įrodyti, kad dydis = 0 yra neįmanoma, jis yra puikus, jis gali optimizuoti tokiu pat būdu kaip ir i < size .

Asm, if(!size) skip the loop; do{...}while(--size); ne do{...}while(--size); tai yra vienas iš veiksmingų būdų optimizuoti for( i<size ) kilpą, jei faktinė„ i vertė nereikalinga kilpos viduje ( kodėl ciklai visuomet rengiami„ do ..., o “stiliaus (uodegos))?

Tačiau tai daro {}, nors ji negali būti begalinė: jei įvedate size==0 , gauname 2 ^ n iteracijas. ( Iteracija virš visų nepasirašytų sveikų skaičių „ C“ kontūre leidžia jums išreikšti ciklą per visus nepasirašytus sveikus skaičius, įskaitant nulį, bet be nešimo vėliavos, tai nėra paprasta, kaip ir asm.)

Atsižvelgiant į galimybę keisti kilpos skaitiklį, šiuolaikiniai kompiliatoriai dažnai paprasčiausiai „atsisako“ ir beveik ne taip agresyviai optimizuoja.

Pavyzdys: sveikųjų skaičių suma nuo 1 iki n

Naudojant nepasirašytą i <= n laimi idiomo atpažinimą, kuris optimizuoja sum(1.. n) ciklus su uždarąja forma pagal „Gauss“ formulę n * (n+1)/2 .

 unsigned sum_1_to_n_finite(unsigned n) { unsigned total = 0; for (unsigned i = 0 ; i < n+1 ; ++i) total += i; return total; } 

} nepasirašyta sum_1_to_n_finite (nepasirašyta n) {% 0A ++++ nepasirašyta iš viso = 0;% 0A ++++ (nepasirašyta I = 0+; I <n% 2B1 +; ++ i) {% 0A ++++ iš viso + = i % 0A ++++}% 0A ++++ grąža; Itora Godbolt

  # c> 

Bet naivi versija, mes tiesiog gauti nuobodu kilpa c>

 unsigned sum_1_to_n_naive(unsigned n) { unsigned total = 0; for (unsigned i = 0 ; i<=n ; ++i) total += i; return total; } 
 # c> 

Persijos įlankos bendradarbiavimo taryba bet kuriuo atveju nenaudoja uždarosios formos, todėl ciklo būklės pasirinkimas iš tikrųjų nepažeidžiamas ; jis automatiškai vektorizuojamas pridėjus sveikojo skaičiaus SIMD, tuo pačiu metu atliekant 4M reikšmes XMM registro elementuose.

 # "naive" inner loop .L3: add eax, 1 # do { paddd xmm0, xmm1 # vect_total_4.6, vect_vec_iv_.5 paddd xmm1, xmm2 # vect_vec_iv_.5, tmp114 cmp edx, eax # bnd.1, ivtmp.14 # bound and induction-variable tmp, I think. ja .L3 #, # }while( n > i ) "finite" inner loop # before the loop: # xmm0 = 0 = totals # xmm1 = {0,1,2,3} = i # xmm2 = set1_epi32(4) .L13: # do { add eax, 1 # i++ paddd xmm0, xmm1 # total[0..3] += i[0..3] paddd xmm1, xmm2 # i[0..3] += 4 cmp eax, edx jne .L13 # }while( i != upper_limit ); then horizontal sum xmm0 and peeled cleanup for the last n%3 iterations, or something. 

Ji taip pat turi paprastą skaliarinę kilpą, kuri, mano manymu, naudojama labai mažam n ir (arba) begalinės kilpos atveju.

Beje, abu šie ciklai eikvoja savo nurodymus (ir „Sandybridge“ procesorių šeimą) ciklo kaina. sub eax,1 / jnz vietoj add eax,1 / cmp / jcc bus efektyvesnis. 1 mop vietoj 2 (po makrokomandos sub / jcc arba cmp / jcc). Kodas po abiejų kilpų besąlygiškai rašo EAX, taigi jis nenaudoja galutinės kilpos skaitiklio vertės.

1
20 янв. Peterio Cordeso atsakymas dėl sausio 20 d 2019-01-20 14:30 „19, 14:30, 2019-01-20 14:30
šaltinis

Tiesą sakant, jie bus lygiai tokie patys, nes surinkimo lygiu jie paima vieną eilutę. Pavyzdžiui:

  • jl ax,dx (praleidžia, jei AX yra mažesnis nei DX)
  • jle ax,dx (šuoliai, jei AX yra mažesnis arba lygus DX)

Ne, ne, ne greičiau. Но если вы хотите получить техническую технику, я думаю, если бы вы проверили ее на текущем уровне электрона, это было бы немного быстрее, но не где-нибудь рядом со скоростью, которую вы заметили бы.

-7
ответ дан Kevin Usher 31 авг. '12 в 17:59 2012-08-31 17:59
šaltinis

Другие вопросы по меткам или Задайте вопрос