Redna ekspanzija

Redna ekspanzija ili staza, u računarstvu, je priručnik ili kompilator optimizacije koji zamenjuje funkciju poziva sajta sa telom pod nazivom funkcije. Staza za proširenje je slična makrou ekspanzije, ali se javlja tokom kompilacije, bez menjanja izvornog koda (teksta), dok se makro proširenje javlja pre kompilacije, i rezultatima u različitom tekstu koji zatim obrađuje kompilator.

Staza je važna optimizacija, ali ima komplikovane efekte na performanse. Kao pravilo, neka staza će poboljšati brzinu za veoma male troškove prostora, ali višak staze će poremetiti brzinu, zbog linije koda, konzumiranja previše instrukcija keša, a takođe će koštati i značajnog dela prostora. Anketa skromne akademske literature o stazama iz 1980-ih i 1990-ih data je u Jones & Marlow 1999.

Pregled

Staza za proširenje je slična makrou ekspanzije kao prevodilac koji stavlja novu kopiju funkcije na svakom mestu gde se zove. Staza funkcije radi malo brže od normalnih funkcija kao funkcija-calling-režijski troškovi su smanjeni, međutim, plaćaju se kazne. Ako je funkcija pozvana 10 puta, biće 10 primeraka funkcije ubačeno u kodu. Stoga je staza najbolja za male, što se često nazivaju. U C++ član funkcije klase, ako je definisan u definiciji klase, onda se staza podrazumeva (nema potrebe da se koristi staza za ključnu reč); inače, ključna reč je potrebna. Prevodilac može ignorisati pokušaj programera da pozove funkciju, uglavnom ako je posebno velika.

Staza za proširenje se koristi kako bi se eliminisalo vreme preleta (višak vremena) kada se poziva funkcija. Obično se koristi za funkcije koje se izvršavaju često. Ona takođe ima prostor da se koristi za veoma male funkcije, i omogućava transformaciju za druge optimizacije.

Bez paralelnih funkcija, prevodilac odlučuje koja funkcija funkcioniše na stazi. Programer ima malo ili nimalo kontrole nad funkcijom staze. Davanje stepena kontrole programeru omogućava korišćenje specifičnih znanja primene u izboru koji funkcioniše na stazi.

Obično, kada se poziva funkcija, kontrola se prenosi na svoju definiciju u grani ili se poziva instrukcija. Sa stazom, kontrola pada kroz direktni kod za funkciju, bez grani ili poziva instrukcije.

Kompajleri obično sprovodi naredbu sa staze. Uslovi petlje i petlja tela treba da imaju sporu evaluaciju. Ova opcija je ispunjena kada je kod računanja uslova petlje i petlje tela pozvan. Razmatranja mogućnosti su još jedan razlog da se pozovu naredbe.

U kontekstu funkcionalnih programskih jezika, posle rednog proširenja obično sledi transformacija Lambda računa.

Programer može da pozove funkciju ručno pomoću kopiranja, kao jednokratna operacija u izvornom kodu. Međutim, druge metode kontrole (vidi dole) su bolje, jer ne precipitiraju bagove koji proističu kada je programer gledao, a (možda izmenio) kopiranu verziju originalne funkcije tela, dok je popravljao grešku u unutrašnjoj funkciji.

Uticaj na performanse

Direktan efekat ove optimizacije je poboljšanje vremena i korišćenja prostora (eliminacijom poziva),[lower-alpha 1] po ceni od pogoršanja korišćenja prostora (zbog dupliranja funkcije tela). Ekspanzija kod zbog dupliranja funkcije tela dominira, osim u jednostavnim slučajevima,[lower-alpha 2] i tako direktan uticaj redne ekspanzije je da se poboljša vreme na račun prostora.

Međutim, osnovna prednost redne ekspanzije je da omogući dalje optimizacije i poboljšane zakazivanja, zbog povećanja veličine tela funkcije, kao što je bolja optimizacija omogućena većim funkcijama. Krajnji uticaj redne ekspanzije na brzinu je komplikovan, zbog višestrukih efekata na performanse memorijskog sistema (prvenstveno uputstvo keša), gde dominiraju performanse na savremenim procesorima: u zavisnosti od konkretnog programa i keša, posebne funkcije mogu povećati ili smanjiti performanse.

Uticaj redne ekspanzije varira u zavisnosti od programskog jezika i programa, zbog različitih stepena apstrakcije. U nižim nivoima imperativnih jezika kao što su S i Fortran to je tipično 10-20% povećanje brzine, sa manjim uticajem na veličinu koda, dok je u višim apstraktnim jezicima znatno važnije, zbog broja slojeva koje redna ekspanzija uklanja, sa ekstremnim primerom Self-a, gde je jedan prevodilac video faktore poboljšanja od 4 do 55 pomoću redne ekspanzije.

Direktne koristi od eliminacije funkcije poziva su:

• To eliminiše uputstva potrebna za funkciju poziva, i u funkciji poziva i pozivanog: stavljanje argumenata na stek ili u registrima, funkcija samu sebe poziva, prolog funkcije, a zatim na povratku epilog funkcije, povratna izjava, a zatim se povratna vrednost vraća natrag, i uklanjaju se argumenti iz gomile i vraćaju registri (ako je potrebno).
• Zbog toga što nije potrebno da registri prođu argumente, smanjuje se prosipanje registra.
• To eliminiše da moraju da prođu reference, a zatim dereference njih, kada se koristi poziv pomoću reference (ili pozivi po adresi, ili pozivi deljenja).

Primarna korist redne ekspanzije, međutim, su dalje optimizacije koje to dozvoljavaju. Optimizacije koje prelaze granice funkcija mogu da se urade bez potrebe interproceduralne optimizacije (IPO): jednom kada je redna ekspanzija izvršena dodatne intraproceduralne optimizacije ("globalne optimizacije") postale su moguće na proširenoj funkciji tela. Na primer:

• Konstanta kao argument se često može propagirati svim instancama odgovarajućih parametara ili delova funkcija koje se mogu "isticati iz" petlje (preko koda kretanja invarijantne petlje).
• Raspodela registra može da se uradi preko većeg tela funkcije.

Ovo se može uraditi bez redne ekspanzije, ali zahteva znatno komplikovaniji kompajler i linker (u slučaju poziva i pozvanog, oni su u odvojenim jedinicama kompilacije).

Nasuprot tome, u nekim slučajevima specifikacija jezika može dozvoliti programu da učini dodatne pretpostavke o argumentima za postupke koji se više ne mogu učiniti nakon postupka redne ekspanzije, sprečava neke optimizacije. Pametniji kompajleri (kao što je Glazgov Haskelov kompilator) će pratiti, ali naivna redna ekspanzija gubi ovu informaciju.

Dalja korist redne ekspanzije za memoriju sistema:

• Eliminacija grane i čuvanje koda koji se izvršava u blizini zajedno u memoriji poboljšava performanse instrukcija keša poboljšanjem lokaliteta reference (prostorni lokalitet i redosled uputstava). Ovo je manje nego optimizacije koje konkretno ciljaju po redosledu, ali je značajno.

Direktni troškovi redne ekspanzije povećavaju veličinu koda, zbog dupliranja funkcije tela na svakoj lokaciji poziva. Međutim, to nije uvek tako, odnosno u slučaju veoma kratke funkcije, gde je funkcija tela manja od veličine poziva funkcije (na pozivaoca, uključujući i argument i povratne vrednosti rukovanja), kao što su trivijalne metode mutatora ili metode korisnika (geteri i seteri); ili za neku funkciju koja se koristi samo na jednom mestu, u kom slučaju se ne dupliraju. Tako redna ekspanzija može da se svede na minimum ili da se eliminiše ako se optimizira za veličinu koda, kao što je često slučaj u ugrađenom sistemu.

Redna ekspanzija takođe nameće troškove na performanse, zbog širenja koda (zbog dupliranja) onesposobljavajući uputstvo za keš performanse. Ovo je najznačajnije ako je, pre ekspanzije, posao set programa (ili vrelih delova koda) u jednom nivou hijerarhije memorije (npr, L1 keš), ali nakon širenja više ne odgovara, što dovodi do toga da često keš nedostaje na tom nivou. Zbog značajne razlike u performansama na različitim nivoima hijerarhije, ovo onesposobljava performanse značajno. Na najvišem nivou to može dovesti do povećanja grešaka stranica, katastrofalne degradacije performansi zbog šlajfovanja ili da program bude neispravan ili da ne radi uopšte. Ovo poslednje je retkost u desktop i server aplikacijama, gde je veličina broja mala u odnosu na raspoloživu memoriju, ali može biti problem za ograničenim resursima okruženja, kao što su ugrađeni sistemi. Jedan od načina da se ublaži ovaj problem je da se razdvoje funkcije u manju rednu ekspanziju (brza staza), i veću nerednu (spora staza).

Redna ekspanzija utiče loše na performanse i to je pre svega problem za velike funkcije koje se koriste na mnogim mestima, ali je provala i tačka preko koje redna ekspanzija smanjuje učinak i to je teško da se utvrdi i zavisi u celini od preciznog opterećenja, tako da može biti predmet ručne optimizacije ili profila vođene optimizacije. Ovo je slično pitanje za drugi kod proširenja optimizacija kao što je odmotavanje petlje, koje takođe smanjuju broj instrukcija procesuiranih, ali mogu smanjiti performanse zbog slabijeg učinka keša.

Tačan efekat redne ekspanzije na keš performanse je komplikovan. Za male veličine keša (mnogo manje nego radni set postavljen pre ekspanzije), povećanja po redosledu dominiraju, a redna ekspanzija poboljšava performanse keša. Za keš veličine blizu radnog seta, gde redna ekspanzija širi posao seta tako da se više ne uklapa u kešu, ovo dominira i keš performanse smanjuje. Za keš veličine veće od radnog skupa, redna ekspanzija ima zanemarljiv uticaj na keš performanse. Dalje, promene u dizajnu keša, kao što su opterećenja špedicije, može povećati promašaje u kešu.

Podrška kompilatora

Kompilatori koriste različite mehanizme da odluče koji poziv funkcije treba da se redno proširi; to mogu biti ručni nagoveštaji programera za određene funkcije, zajedno sa opštom kontrolom preko opcije komandne linije. Redno proširenje se vrši automatski od strane mnogih kompilatora na mnogim jezicima, na osnovu presude da li je redno proširenje korisno, dok u drugim slučajevima se može ručno navesti preko kompajlera direktivama, obično koristeći direktivu kompilatora ili ključne reči pod nazivom inline. Obično to samo nagoveštava da se želi redno proširenje, pre nego zahtevanje, sa snagom nagoveštaja koja varira od jezika i kompilatora.

Tipično, programeri kompilatora mogu zadržati pitanja gornjih performansi, i uključiti heuristike u svoje kopilatore da odluče koja funkcija treba redno da se proširi kako bi se poboljšali performanse, pre nego povećanje grešaka, u većini slučajeva.

Implementacija

Kada je kompilator odlučio da proširi određenu funkciju, obavljanje same operacije proširenja je obično jednostavno. U zavisnosti od toga da li se kompajler proširuje funkcijama širom koda na različitim jezicima, kompilator može da uradi redno proširenje bilo na visokom nivou srednje reprezentacije (kao apstraktne sintakse drveta) ili srednje reprezentacije niskog nivoa. U svakom slučaju, kompilator jednostavno izračunava argumente, skladišti ih u varijabli koje odgovaraju argumentima funkcije, a zatim ubacuje telo funkcije na poziv sajta.

Linkeri, kao i kompilatori, takođe mogu da urade funkciju rednog proširenja. Kada linker redno proširi funkcije, može onda i da redno proširi funkcije čiji izvor nije na raspolaganju, kao što je funkcija biblioteke (pogledajte link vremena optimizacije). Sistem izvršavanja može redno proširiti funkciju. Rantajm rednog proširenja može koristiti dinamičke informacije profilisanja da donose bolje odluke o tome koje funkcije treba da se redno prošire, kao u Java Hotspot kompilatoru.

Ovde je jednostavan primer rednog proširenja koje se vrši "ručno" na izvornom nivou u S programskom jeziku:

int pred(int x) {
    if (x == 0)
       return 0;
    else
       return x - 1;
}

Pre rednog proširenja:

 int f(int y) {
     return pred(y) + pred(0) + pred(y+1);
 }

Posle rednog proširenja:

int f(int y) {
    int temp;
    if (y   == 0) temp  = 0; else temp  = y       - 1; /* (1) */
    if (0   == 0) temp += 0; else temp += 0       - 1; /* (2) */
    if (y+1 == 0) temp += 0; else temp += (y + 1) - 1; /* (3) */
    return temp;
}

Imajte na umu da je ovo samo jedan primer. U stvarnoj S aplikaciji, bilo bi poželjno da koristite funkciju rednog proširenja, kao što su parameterizovanog makroa ili paralelnih funkcija da transformišu kod na ovaj način. Sledeći odeljak navodi načine za optimizaciju ovog koda.

Redno proširenje makro ekspanzije

Asembler makroa treba da obezbedi alternativni pristup rednog proširenja gde sekvenca instrukcija normalno može da generiše makro ekspanzije iz jedne makro izjave izvora (sa nula ili više parametara). Jedan od parametara može biti opcija za alternativno generisanje jednokratnog potprograma koji sadrži sekvencu i obrađuje ga umesto poziva funkcije. Primer:

MOVE FROM=array1,TO=array2,INLINE=NO

Komparacija sa makroima

Tradicionalno, na jezicima kao što su S, redna ekspanzija je postignuta na izvornom nivou koristeći parametarizovane makroe. Korišćenje pravih paralelnih funkcija, kao što su dostupni u S99, nude nekoliko prednosti u odnosu na ovaj pristup:

• U S, makro prizivanja ne obavlja proveru tipa, ili čak provere da li su argumenti dobro formirani, dok funkcija poziva obično radi.
• U S, makro ne može koristiti ključnu reč sa istim značenjem u funkciji (da bi funkcija za koju tražimo proširenje mogla da se obavi, a ne makro). Drugim rečima, makro ne može da vrati ništa što nije rezultat poslednjeg izraza koji ga je pozvao unutra.
• Pošto S makroi koriste tekstualnu zamenu, to može dovesti do neželjenih sporednih efekata i neefikasnosti zbog ponovne procene argumenata i redosleda operacija.
• Greške kompilatora u okviru makroa se često mogu teško razumeti, jer se odnose na proširenje koda, a ne kod programera koji je kucao. Tako, debagovanje informacije za linije koda je obično više od pomoći nego makro proširenje koda.
• Mnoge konstrukcije se neprijatno ili nemoguće izražavaju pomoću makroa, ili koriste bitno drugačiju sintaksu. Redno proširene funkcije koriste istu sintaksu kao obične funkcije, i može se redno proširiti i neproširene po volji sa lakoćom.

Mnogi kompajleri takođe mogu proširiti redne neke rekurzivne funkcije; rekurzivni makroi su obično ilegalni.

Bjarne Stravstrup, dizajner C++, voli da istakne da treba izbegavati makroe kad god je to moguće, i zalaže se za široku upotrebu funkcija rednog proširenja.

Prednosti

Redna ekspanzija je sama optimizacija, jer iznad glave eliminiše pozive, ali je mnogo važnija kao omogućavajuća transformacija. To je, kada prevodilac proširuje funkciju tela u kontekstu svog poziva sajta često sa argumentima koji mogu biti fiksne konstante - može biti u stanju da uradi različite transformacije koje nisu bile moguće pre. Na primer, uslovna grana se može ispostaviti da je uvek istina ili uvek lažna na ovom sajtu poziva. Ovo zauzvrat može omogućiti eliminaciju mrtvog koda, kod kretanja invarijantne petlje, ili indukciona eliminacija promenljive. 

U S primeru u prethodnom odeljku, mogućnosti za optimizaciju obiluju. Prevodilac može da prati ovaj redosled koraka:

•  temp += 0 izjave u redovima obeleženim (2) i (3) ne rade ništa. Prevodilac može da ih ukloni.
• Uslov 0 == 0 je uvek istina, tako da prevodilac može da zameni liniju obeleženu (2) kao posledicu, temp += 0 (ne radi ništa).
• Prevodilac može prepraviti stanje y+1 == 0 u y == -1.
• Prevodilac može smanjiti izraz (y + 1) - 1 u y.
• Izrazi y i y+1 ne mogu oba biti jednaka nuli. Ovo omogućava prevodiocu da eliminiše jedan test.
• U izjavama poput if (y == 0) return y vrednosty je poznata u telu i može se redno proširiti.

Nova funkcija izgleda ovako:

int f(int y) {
    if (y == 0)
        return 0;
    if (y == -1)
        return -2;
    return 2*y - 1;
}

Ograničenja

Kompletna redna ekspanzija nije uvek moguća, zbog rekurzije: rekurzivno redno proširenje poziva se neće prekinuti. Postoje različita rešenja, kao što je proširenje na ograničeni iznos, ili analiziranje poziva grafika i razbijanje petlje na određenim čvorovima (tj. ne širi neku prednost u rekurzivnoj petlji).  Identičan problem se javlja u makro ekspanziji, kao rekurzivna ekspanzija koja ne prestaje, a obično se rešava zabranjivanjem rekurzivnog makroa (kao u C i C++).

Metode selekcije

Mnogi kompajleri agresivno redno proširuju funkcije gde god da je korisno da se to učini. Iako to može dovesti do većih izvršenja, agresivna redna ekspanzija je ipak sve više i više poželjna kao kapacitet memorije koja je brža od brzine procesora. Redna ekspanzija je kritična optimizacija u funkcionalnim jezicima i objektno orijentisanim programskim jezicima , koji se oslanjaju na njega da obezbedi dovoljno konteksta za svoje tipično male funkcije da čine klasične optimizacije efikasnim.

Jezička podrška

Mnogi jezici, uključujući i Javu i funkcionalne jezike, ne obezbeđuju jezičke konstrukcije za funkcije redne ekspanzije, ali njihovi kompajleri ili prevodioci često obavljaju agresivnu rednu ekspanziju. Ostali jezici obezbeđuju konstrukcije za eksplicitne nagoveštaje, uglavnom kao direktive kompajlera (pragme).

U Ada programskom jeziku, postoji pragma za funkcije redne eskpanzije.

Funkcije u Common Lisp mogu se definisati kao redne ekspanzije pomoću inline deklaracije kao:

 (declaim (inline dispatch))
 (defun dispatch (x)
   (funcall
     (get (car x) 'dispatch) x))

Haskelov kompilator GHC pokušava da redno proširi funkcije ili vrednosti koje su dovoljno male, ali redna ekspanzija može biti eksplicitno navedena korišćenjem jezika pragme:

key_function :: Int -> String -> (Bool, Double)
{-# INLINE key_function #-}

C i C++

C i C++ imaju  inline ključnu reč, koja funkcioniše i kao kompajler direktive - precizirajući da se želi redna ekspanzija, ali nije obavezna - i menja ponašanje vidljivosti i povezuje. Promena vidljivosti je neophodna da bi funkcija mogla da se redno proširi preko standardne S alatke, gde kompilacija individualnih fajlova (pre nego, prevodilačkih jedinica) je zatim povezana da bi linker mogao da redno proširi funkcije, koje moraju biti navedene u zaglavlju (da bude vidljivo) i označeno inline (da bi se izbegla dvosmislenost sa više definicija).

Vidi još

• Makro (računarstvo)
• Parcijalna evaluacija
• Repna rekurzija

Literatura

• Chen, W. Y.; Chang, P. P.; Conte, T. M.; Hwu, W. W. (1993). „The effect of code expanding optimizations on instruction cache design” (PDF). IEEE Transactions on Computers. 42 (9): 1045—1057. doi:10.1109/12.241594. 

Spoljašnje veze

• "Eliminating Virtual Function Calls in C++ Programs" od Geralda Egnera i Ursa Helcla
• "Reducing Indirect Function Call Overhead In C++ Programs" od Breda Kaldera i Dirka Gramvalda
• ALTO - A Link-Time Optimizer for the DEC Alpha
• "Advanced techniques" od Džona R. Levina
• "Inlining Semantics for Subroutines which are Recursive Arhivirano na sajtu Wayback Machine (13. oktobar 2004)" od Henrija G. Bejkera
• "Whole Program Optimization with Visual C++ .NET" od Brendona Breja