Kodėl (a * b! = 0) greičiau nei (a! = 0 = 0) Java?

Rašau Java kodą, kur tam tikru momentu programos srautas nustatomas pagal tai, ar du kintamieji int "a" ir "b" yra nuliniai (pastaba: a ir b niekada nėra neigiami ir niekada neturėtų būti sveikasis skaičius) perpildymo numeriai).

Aš galiu ją įvertinti

 if (a != 0  b != 0) {  } 

Arba

 if (a*b != 0) {  } 

Kadangi tikiuosi, kad dalis kodo paleidžiama milijonus kartų, man įdomu, kuris iš jų bus greitesnis. Aš padariau eksperimentą, lyginant juos su didžiuliu atsitiktinai sugeneruotu masyvu, ir aš taip pat norėjau sužinoti, kaip masyvo retumas (duomenų dalis = 0) turės įtakos rezultatams:

 long time; final int len = 50000000; int arbitrary = 0; int[][] nums = new int[2][len]; for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) { for(int i = 0 ; i < 2 ; i++) { for(int j = 0 ; j < len ; j++) { double random = Math.random(); if(random < fraction) nums[i][j] = 0; else nums[i][j] = (int) (random*15 + 1); } } time = System.currentTimeMillis(); for(int i = 0 ; i < len ; i++) { if(  ) arbitrary++; } System.out.println(System.currentTimeMillis() - time); } 

Ir rezultatai rodo, kad jei tikitės „a“ arba „b“ būti 0 daugiau nei ~ 3% laiko, a*b != 0 bus greitesnis nei a!=0 b!=0 :

2019

21 февр. nustatė Maljamas vasario 21 d 2016-02-21 04:51 '16 at 4:51 2016-02-21 04:51
@ 5 atsakymai

Aš ignoruoju klausimą, kad jūsų lyginamoji analizė gali būti klaidinga, o rezultatas - nominaliąja verte.

Ar tai kompiliatorius, ar tai yra aparatūros lygmeniu?

Tai yra paskutinis manau:

  if (a != 0  b != 0) 

bus sukompiliuota dviem atminties ir dviem sąlyginėms šakoms

  if (a * b != 0) 

bus sukompiliuota dviem atminties, dauginimo ir vieno sąlyginio filialo apkrovoms.

Tikėtina, kad dauginimas bus greitesnis nei antrasis sąlyginis filialas, jei pramonės lygio prognozė bus neveiksminga. Kadangi santykiai didėja, šakos prognozavimas tampa mažiau veiksmingas.

Priežastis, kodėl sąlyginiai filialai yra lėtesni, yra tai, kad jie sukelia komandinį vamzdyną. Skaičiuojant filialus reikia vengti stendo, prognozuoti, kaip pramonė ketina eiti ir spekuliatyviai pasirinkti kitą nurodymą, paremtą tuo. Jei prognozė nepavyksta, vėluojama, kai instrukcija įkeliama kitai krypčiai.

(Pastaba: aukščiau pateiktas paaiškinimas yra supaprastintas. Norėdami gauti tikslesnį paaiškinimą, reikia pažvelgti į literatūrą, kurią pateikia CPU gamintojas surinkimo kalbų koduotojams ir kompiliatorių rašytojams. Vikipedijos puslapis apie pramonės prognozes yra geras pagrindas.)


Tačiau yra vienas dalykas, kurį jums reikia atidžiai stebėti. Ar yra kokių nors vertybių, kai a * b != 0 suteikia neteisingą atsakymą? Apsvarstykite atvejus, kai produkto skaičiavimas lemia sveikų skaičių perpildymą.


UPDATE

Jūsų grafika paprastai patvirtina mano žodžius.

  • Esant sąlyginiam atšakui a * b != 0 yra „šakos prognozavimo“ efektas, ir tai rodoma grafikuose.

  • Jei x ašyje projektuojate kreives virš 0,9, atrodo, kad: 1) jie susitiks maždaug 1,0 ir 2), susitikimo vieta bus maždaug tokia pati kaip X = 0.0.


UPDATE 2

Nesuprantu, kodėl kreivės skiriasi tuo atveju, kai a + b != 0 ir a | b != 0 a | b != 0 . Kažkas protingas gali būti šakų prognozavimo logika. Arba tai gali reikšti kažką kitą.

(Atkreipkite dėmesį, kad tokie dalykai gali būti būdingi konkrečiam mikroschemos modelio numeriui arba netgi versijai. Jūsų bandymų rezultatai kitose sistemose gali skirtis.)

Tačiau abi jos turi pranašumą visoms neigiamoms a ir b reikšmėms.

197
21 февр. Atsakymą pateikė Stephen C 21 vasaris. 2016-02-21 05:09 '16 at 5:09 2016-02-21 05:09

Manau, kad jūsų etalonas turi tam tikrų trūkumų ir gali būti naudingas norint sužinoti apie tikrąsias programas. Čia yra mano mintys:

  • (a*b)!=0 padarys neteisingą vertę, kai perpildyta vertė, ir (a+b)!=0 taip pat darys neteisingą teigiamų ir neigiamų vertybių, kurios prideda iki nulio, skaičių, todėl jūs negalite naudoti nė vieno šių išraiškų bendrai, net jei jie dirba čia.

  • (a|b)!=0 ir (a+b)!=0 yra tikrinami, jei bet kokia reikšmė yra nulinė, ir (a*b)!=0 ir a != 0 b != 0 yra tikrinami, jei abi reikšmės yra lygus nuliui. Dviejų tipų sąlygos neatitiks vieno procento duomenų.

  • VM optimizuos išraišką pirmaisiais išorinio ciklo ciklais ( fraction ), kai fraction yra 0, kai šakos beveik niekada nevykdomos. Optimizatorius gali atlikti skirtingus dalykus, jei pradėsite 0,5 fraction .

  • Jei VM čia negali pašalinti kai kurių masyvo ribų patikrinimų, išraiška yra tik keturi filialai tik dėl ribinių patikrinimų ir tai yra sudėtingas veiksnys bandant išsiaiškinti, kas vyksta žemai. Jūs galite gauti skirtingus rezultatus, jei padalysite dvimatį matricą į dvi plokščias matricas, pakeisdami nums[0][i] ir nums[1][i] į nums0[i] ir nums1[i] .

  • Procesoriaus šakos prognozės bando aptikti trumpus duomenis visuose filialuose, kurie yra priimtini ar nepriimti. Jūsų atsitiktinai sugeneruoti kontroliniai duomenys yra blogiausias dalykas, kuriuo galima prognozuoti pramonę, kurią galite pabandyti susidoroti. Jei jūsų tikrieji duomenys turi nuspėjamą modelį arba jis turi ilgas visų nulio ir visų nulinių reikšmių eigos, šakos gali kainuoti daug mažiau.

  • Konkretus kodas, kuris įvykdomas įvykdžius sąlygą, gali turėti įtakos pačios būklės veikimui, nes jis veikia tokius dalykus, kaip ciklas gali būti pašalintas, kokie procesoriaus registrai yra prieinami ir ar gautos sumos turi būti pakartotinai naudojamos po būklės įvertinimo. Paprastas standarto skaitiklio padidinimas nėra idealus vietovės ženklas tikram kodui.

  • System.currentTimeMillis() yra daugelyje sistemų ne daugiau kaip +/- 10 ms. System.nanoTime() paprastai yra tikslesnis.

Kaip matote, yra daug neapibrėžtumų, ir visada sunku pasakyti kažką konkretaus su tokiais mikroprocesoriais, nes vienoje virtualioje mašinoje ar procesoriuje greitesnis triukas gali būti lėtesnis kitoje. Jei jūsų virtualioji mašina yra „HotSpot“, turėkite omenyje, kad yra dar dvi veislės, o kliento virtualioji mašina turi skirtingą (silpnesnį) optimizavimą, palyginti su serverio virtualia mašina.

Jei galite išanalizuoti virtualios mašinos sukurtą mašinos kodą , tai atlikite ir nebandykite atspėti, ką jis daro!

59
21 февр. Atsakymą pateikė Boann , vasario 21 d. 2016-02-21 18:50 '16 at 18:50 2016-02-21 18:50

Atsakymai čia yra geri, nors turiu idėją, kuri gali pagerinti situaciją.

Kadangi du filialai ir su jais susijęs šakos prognozavimas yra tikėtinas kaltininkas, mes galime sumažinti šakos suskirstymą į vieną šaką nekeičiant logikos.

 bool aNotZero = (nums[0][i] != 0); bool bNotZero = (nums[1][i] != 0); if (aNotZero  bNotZero) {  } 

Jis taip pat gali dirbti

 int a = nums[0][i]; int b = nums[1][i]; if (a != 0  b != 0) {  } 

Taip yra todėl, kad pagal trumpojo jungimo taisykles, jei pirmoji loginė vertė yra klaidinga, antroji neturėtų būti vertinama. Ji turi atlikti papildomą filialą, kad būtų išvengta vertinti nums[1][i] jei nums[0][i] buvo klaidingas. Dabar jūs negalite rūpintis, jei nums[1][i] gauna sąmatą, bet kompiliatorius negali būti tikras, kad tai nepadės iš diapazono ar nulinės ref. Sumažinus blokų skaičių į paprastus „bools“, kompiliatorius gali būti pakankamai protingas, kad suprastų, kad antros loginės vertės įvertinimas be reikalo neturės neigiamų šalutinių poveikių.

21
22 февр. Atsakymą pateikė „ Pagefault “ vasario 22 d. 2016-02-22 05:43 '16 at 5:43 am 2016-02-22 05:43

Kai priimame dauginimą, net jei vienas skaičius yra 0, tada produktas yra 0. Rašant

  (a*b != 0) 

Ji įvertina produkto rezultatą, taip pašalindama pirmuosius kelis iteracijos įvykius, pradedant nuo 0. Todėl palyginimas yra mažesnis nei esant sąlygoms

  (a != 0  b != 0) 

Kai kiekvienas elementas yra lyginamas su 0 ir vertinamas. Todėl reikia mažiau laiko. Bet manau, kad antroji sąlyga gali suteikti jums tikslesnį sprendimą.

11
21 февр. atsakymas pateikiamas Sanket Gupte 21 vasaris. 2016-02-21 05:30 '16, 5:30, 2016-02-21 05:30

Jūs naudojate atsitiktinės atrankos įvestį, todėl filialai yra nenuspėjami. Praktikoje filialai dažnai yra (~ 90%) nuspėjami, todėl realiame kode šakinis kodas greičiausiai bus greitesnis.

Tai pasakė. Nematau, kaip a*b != 0 gali būti greitesnis nei (a|b) != 0 . Bendras dauginimas paprastai yra brangesnis nei bitų OR. Tačiau tokie dalykai kartais keistai. Pavyzdžiui, pavyzdys „7 pavyzdys: aparatūros sunkumai“ iš procesoriaus talpyklos efektų galerijos .

6
24 февр. Atsakymas pateikiamas StackedCrooked 24 vas. 2016-02-24 04:55 '16 at 4:55 2016-02-24 04:55