Predviđanje grana u Javi

1. Uvod

Predviđanje grana zanimljiv je koncept u računalnoj znanosti i može imati dubok utjecaj na izvedbu naših aplikacija. Još općenito se dobro ne razumije i većina programera tome posvećuje vrlo malo pažnje.

U ovom ćemo članku istražiti što je to točno, kako utječe na naš softver i što možemo učiniti s tim.

2. Što su cjevovodi s uputama?

Kada pišemo bilo koji računalni program, pišemo skup naredbi za koje očekujemo da će ih računalo izvršiti u nizu.

Rana računala pokrenula bi ih po jedan. To znači da se svaka naredba učitava u memoriju, izvršava u cijelosti, a tek kad se dovrši, učitat će se sljedeća.

Upute cjevovodi su poboljšanje u odnosu na ovo. Omogućuju procesoru da rad podijeli na komade, a zatim paralelno izvodi različite dijelove. To bi onda omogućilo procesoru da izvrši jednu naredbu dok učitava sljedeću, spremnu za rad.

Dulji cjevovodi unutar procesora ne samo da omogućuju pojednostavljivanje svakog dijela već omogućuju paralelno izvođenje više njegovih dijelova. To može poboljšati ukupne performanse sustava.

Na primjer, mogli bismo imati jednostavan program:

int a = 0; a + = 1; a + = 2; a + = 3;

Ovo se može obraditi cjevovodom koji sadrži segmente Dohvati, Dekodiraj, Izvrši, Pohrani kao:

Ovdje možemo vidjeti kako se cjelokupno izvršavanje četiri naredbe izvodi paralelno, čineći tako čitavu sekvencu bržom.

3. Koje su opasnosti?

Određene naredbe koje procesor treba izvršiti stvorit će probleme za cjevovod. To su bilo koje naredbe kod kojih izvršavanje jednog dijela cjevovoda ovisi o ranijim dijelovima, ali gdje ti raniji dijelovi možda još nisu izvršeni.

Grane su specifični oblik opasnosti. Oni uzrokuju da izvršenje ide u jednom od dva smjera i nije moguće znati u kojem smjeru dok se grana ne riješi. Ovo znači to svaki pokušaj učitavanja naredbi mimo grane nije siguran jer ne možemo znati odakle ih učitati.

Promijenimo naš jednostavni program za uvođenje grane:

int a = 0; a + = 1; ako je (a <10) {a + = 2; } a + = 3;

Rezultat je isti kao i prije, ali uveli smo ako izjava usred nje. Računalo će to vidjeti i neće moći učitavati naredbe nakon toga dok se to ne riješi. Kao takav, protok će izgledati otprilike ovako:

Odmah možemo vidjeti utjecaj koji to ima na izvršavanje našeg programa i koliko je koraka takta bilo potrebno za izvršavanje istog rezultata.

4. Što je predviđanje grana?

Predviđanje grana je poboljšanje gore navedenog, gdje će naše računalo pokušati predvidjeti kojim će putem grana ići, a zatim postupiti u skladu s tim.

U našem gornjem primjeru, procesor bi to mogao predvidjeti ako (a <10) vjerojatno će biti pravi, i tako će se ponašati kao da je uputa a + = 2 bio sljedeći koji je izvršen. To bi onda uzrokovalo da protok izgleda otprilike:

Odmah možemo vidjeti da je to poboljšalo izvedbu našeg programa - sada treba devet krpelja, a ne 11, pa je brže za 19%.

Ipak, ovo nije bez rizika. Ako pogrešno predviđanje grane pogriješi, tada će početi stavljati u red upute koje se ne bi trebale izvoditi. Ako se to dogodi, tada će ih računalo morati baciti i početi ispočetka.

Okrenimo naš uvjetni uvjet tako da je sada lažno:

int a = 0; a + = 1; ako je (a> 10) {a + = 2; } a + = 3;

Ovo bi moglo izvršiti nešto poput:

Ovo je sada sporije od ranijeg toka, iako radimo manje! Procesor je pogrešno predvidio da će grana procijeniti na pravi, počeo je stavljati u red čekanja a + = 2 upute, a zatim je morao odbaciti i započeti ispočetka kad je grana procijenila na lažno.

5. Stvarni utjecaj na kod

Sad kad znamo što je predviđanje grana i koje su koristi, kako to može utjecati na nas? Nakon svega, govorimo o gubitku nekoliko procesorskih ciklusa na brzim računalima, tako da sigurno to neće biti primjetno.

A ponekad je to istina. Ali ponekad to može iznenaditi promjenu u izvedbi naših aplikacija. Ovisi puno o tome što točno radimo. Točnije, ovisi o tome koliko radimo u kratkom vremenu.

5.1. Brojanje unosa na popisu

Pokušajmo brojati unose na popisu. Generirat ćemo popis brojeva, a zatim izbrojiti koliko ih je manje od određenog graničnog broja. To je vrlo slično gornjim primjerima, ali to radimo u petlji, umjesto kao samo jednu uputu:

Brojevi popisa = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); if (shuffle) {Collections.shuffle (numbers); } dugi rez = vrh / 2; dugo brojanje = 0; dugi početak = System.currentTimeMillis (); for (Long number: numbers) {if (number <cutoff) {++ count; }} long end = System.currentTimeMillis (); LOG.info ("Prebrojani {} / {} {} brojevi u {} ms", count, top, shuffle? "Promiješano": "sortirano", kraj - početak);

Imajte na umu da vremensku petlju mjerimo samo za brojanje jer je to ono što nas zanima. Dakle, koliko to traje?

Ako generiramo dovoljno male popise, tada se kôd izvodi tako brzo da se ne može vremenski odrediti - popis veličine 100 000 i dalje pokazuje vrijeme od 0 ms. Međutim, kada popis postane dovoljno velik da ga možemo tempirati, možemo vidjeti značajnu razliku na temelju toga jesmo li promijenili popis. Za popis od 10 000 000 brojeva:

  • Razvrstano - 44ms
  • Izmiješano - 221ms

To je, promiješanom popisu treba pet puta duže brojanje od razvrstanog popisa, iako su stvarni brojevi koji se broje jednaki.

Međutim, čin razvrstavanja popisa znatno je skuplji od pukog izvršavanja brojanja. Uvijek bismo trebali profilirati naš kôd i utvrditi da li je poboljšanje izvedbe korisno.

5.2. Red podružnica

Slijedom gore navedenog, čini se razumnim da redoslijed grana u ako / inače izjava bi trebala biti važna. Odnosno, mogli bismo očekivati ​​da će sljedeće imati bolju izvedbu nego da smo ponovno naručili grane:

if (mostLikely) {// Učinite nešto} else if (lessLikely) {// Učinite nešto} else if (najmanjeLikely) {// Učinite nešto}

Međutim, moderna računala mogu izbjeći ovaj problem pomoću predmemorije predviđanja grana. Doista, možemo i ovo testirati:

Brojevi popisa = LongStream.range (0, top) .boxed () .collect (Collectors.toList ()); if (shuffle) {Collections.shuffle (numbers); } long cutoff = (long) (top * cutoffPercentage); dugo nisko = 0; dugo visoko = 0; dugi početak = System.currentTimeMillis (); za (Dugi broj: brojevi) {if (broj <presijecanje) {++ nizak; } else {++ visoko; }} long end = System.currentTimeMillis (); LOG.info ("Prebrojani {} / {} brojevi u {} ms", mali, visoki, kraj - početak);

Ovaj se kod izvršava otprilike u isto vrijeme - ~ 35ms za razvrstane brojeve, ~ 200ms za promiješane brojeve - kada broji 10.000.000 brojeva, bez obzira na vrijednost granični postotak.

Ovo je zbog prediktor grana podjednako rukuje obje grane i pravilno pogađajući kojim ćemo putem krenuti prema njima.

5.3. Kombiniranje uvjeta

Što ako imamo izbor između jednog ili dva uvjeta? Možda bi bilo moguće prepisati našu logiku na drugačiji način koji ima isto ponašanje, ali bismo li to trebali učiniti?

Kao primjer, ako uspoređujemo dva broja s 0, alternativni pristup je pomnožiti ih i usporediti rezultat s 0. To je tada zamjena uvjeta množenjem. No isplati li se ovo?

Razmotrimo primjer:

long [] prvi = LongStream.range (0, TOP) .map (n -> Math.random () Math.random () <FRACTION? 0: n) .toArray (); dugo brojanje = 0; dugi početak = System.currentTimeMillis (); for (int i = 0; i <TOP; i ++) {if (prvo [i]! = 0 && drugo [i]! = 0) {++ count; }} long end = System.currentTimeMillis (); LOG.info ("Prebrojani {} / {} brojevi koji koriste zasebni način rada u {} ms", count, TOP, end - start);

Naše stanje unutar petlje može se zamijeniti, kao što je gore opisano. To zapravo utječe na vrijeme izvođenja:

  • Odvojeni uvjeti - 40ms
  • Višestruko i pojedinačno stanje - 22ms

Dakle, izvršavanje opcije koja koristi dva različita uvjeta zapravo traje dvostruko duže.

6. Zaključak

Vidjeli smo što je predviđanje grana i kako može imati utjecaja na naše programe. To nam može pružiti neke dodatne alate kako bismo osigurali da naši programi budu što učinkovitiji.

Međutim, kao što je uvijek slučaj, moramo se sjetiti profilirati naš kôd prije velikih promjena. Ponekad može biti slučaj da uvođenje promjena koje pomažu predviđanju grana koštaju više na druge načine.

Primjeri slučajeva iz ovog članka dostupni su na GitHubu.


$config[zx-auto] not found$config[zx-overlay] not found