Software engineering deep level optimization - INLINE tehnika optimizacije - II deo

Nedavno sam krenuo sa pisanjem seta blog postova na temu deep level optimizacije te da nastavim sa istim. Kao što sam naveo u prvom blog postu, postoji više tehnika deep level optimizacije software-a, kako bi se što bolje iskoristio potencijal mikroprocesora i računarskog sistema generalno. Kompajleri, ključne reči kompajlera (koje nisu deo standarda programskog jezika već deo kompajlerskih komandi), setovi instrukcija, prevashodno ekstenzije van standardnog seta Intel instrukcija, su ključ za deep level optimizaciju. U ovom tekstu navodim prvu tehniku optimizacije koja se zove "inline" a svodi se na redukovanje korišćenja stack-a kao i optimizacije broja instrukcija koje treba izvršiti, te se jedan deo posla prepušta kompajleru.

Tehnika optimizacije zvana INLINE

Sam naziv tehnike deep level optimizacije je logičan, u trenutku kada shvatite koncept optimizovanja software-a ovom tehnikom. Ključ inline optimizacije je zaobilaženje stack-a i samim tim redukovanje broja instrukcija koje je potrebno izvršiti u situaciji kada se stack koristi. Prvo što treba jasno staviti na znanje jeste da inline, nema apsolutno nikakve veze sa definisanjem standarda programskog jezika. Ključna reč inline je komanda koja se odnosi na kompajler i šta treba raditi sa istom programskom metodom ukoliko je definisana sa ključnom reči inline. Znači inline nema veze sa programskim jezikom, već sa kompajlerskom komandom koja zadaje komandu kopajleru da tokom build-a metodu ne poziva sa instrukcijom call već da je nalepi u okviru tela pozivne metode, što ću ovom prilikom i pokazati. Samim tim što će kompajler nalepiti telo metode u okviru tela pozivne metode, elimišemo call instrukciju ali ne samo istu već i određeni set instrukcija koje moraju da čuvaju stanje mikroprocesorkih registara na stack, pre poziva metode kako bi vratili isti u prethodno stanje, kada metoda završi sa izvršavanjem. Ovde su stvari jasne, standardan poziv metode u okviru programskog koda, za koju nije rečeno kompajleru da je nalepi sa inline, koristi stack radi čuvanja stanja procesorskih registara koje nakon izvršenja metode mora da vrati u registre, te samim tim i imamo overhead koji može da predstavlja veliki overhead na performanse izvršavanja programskog koda koji po zahtevima mora biti brz i ništa više. Te je inline tehnika optimizacije koja zaobilazi korišćenje stack-a prilikom poziva metode ali samim tim i redukuje broj instrukcija koje procesor mora da izvrši. Ovo ćemo prikazati na prostom primeru C++ programskog koda, Visual C++ kompajler, 32 bitni mod izvršavanja.

INLINE primer programskog koda

U tekstu koji sledi dat je primer inline optimizacije, primer prikazuje koncept i šta inline optimizacija zapravo znači, te je uzet jednostavan primer, programski C++ kod je prikazan na donjoj slici.

Tehnika optimizacije zvana inline

Prvo ćemo proći primer bez kompajlerske ključne reči inline, kako bih prikazao koncept ove optimizacije. Primer C++ koda je prost, sadrži main entry point ili ti main metodu i test metodu čiji je zadatak da izvrši sabiranje pet long brojeva. Ova metoda ima standard ABI (application binary interface) call, ili ti _stdcall, ovu ključnu reč sam namerno napisao iako se smatra default calling konvencijom pozivanja metoda. U zavisnosti od calling konvencije i moda izvršavanja: 32 bita ili 64 bita, zavisi i način poziva, te ovde korisitmo defaultni _stdcall (pored ostalih calling konvencija definisane ABI-ijem, te imamo i fastcall koji se drastično razlikuje od standardnog poziva u okviru 32 bitnog moda izvršavanja).

Standardna calling konvencija smešta ulazne vrednosti metoda na stack, što ću prikazati u primeru dole u tekstu, dok recimo postoje i calling konvencije koje ulazne vrednosti smeštaju direktno u mikroprocesorske registre. Za ovaj primer radi jednostavnosti, uzeta je standardna calling konvencija, ali i sama poenta ovog bloga je pokazati šta inline znači, te šta i optimizuje i na koji način ubrzava izvršavanje programskog koda, te se držimo _stdcall koji je i defaultni.

Prvo ćemo proći primer C++ programskog koda bez inline ključne reči i pogledati kako kompajler generiše asemblerski kod, mod build-a je 32 bitni, debug.

Asemblerski kod bez inline optimizacije

Analiziraćemo deo koji je naznačen crveni strelicama. C++ programski kod je jednstavan, main metoda poziva test metodu kojoj su zadate celobrojne ulazne vrednosti koje treba da sabere i vrati rezulata. Kod izvršavanja test metode nalazi se na drugoj memorijskoj adresi od koda izvršavanja main metode, koja kao što vidimo poziva test metodu, instrukcija call. Pre poziva metode test instrukcijom call (opcode E8 što se jasno vidi iz priloženog asemblerskog koda), _stdcall calling konvecija kako to nalaže ABI standard propisan za istu, smešta sve celobrojne vrednosti na stack, te imamo tačno pet push instrukcija koje smeštaju ulazne vrednosti metode test na stack: push 5, push 4, push 3, push 2, push 1. Nakon toga sledi izvršavanje test metode što se izvršava korišćenjem instrukcije call. Ključna stvar je upravo poziv metode test. Pre poziva metode, procesor je izvršavao određene instrukcije i smeštao vrednosti rezultata što na stack što u okviru registara itd. Ono što se mora uraditi jeste da se kompletno trenutno stanje registara sačuva na stack kako bi se isto stanje vratilo nakon izvršavanja metode test. Ako se to ne uradi, jednostavno imamo problem i nećemo imati tačne rezultate u daljoj obrati kao i nedefinisano ponašanje programa. Znači pre poziva call instrukcije, potrebno je kompletno sačuvati trenutno stanje mikroprocesora na stack. Stanje se čuva izvršavanjem dodatnih setova instrukcija i tu upravo leži problem! Jer čuvanje stanja je overhead koje znatno može da uspori totalno vreme izvršavanja programa i da naruši performanse. Iz tog razloga se koristi tehnika inline koja instrukciju call u potpunosti eliminiše i telo metode test lepi (inline) na main metodu, što ćemo u daljem tekstu videti kako.

_stdcall calling konvencija

Asemblerski kod prikazan na gornjoj slici upravo prikazuje ono o čemu smo pisali, call instrukcija prvo mora sačuvati stanje, zatim sledi izvršavanje tela metoda (prikazano zelenim strelicama) a zatim stanje mikroprocesora vratiti u pređašnje (crvene strelice), pre nego što smo imali poziv metode test sa instrukcijom call. Zelene strelice isključivo prikazuju asemblerski kod vezan za telo test metode i kao što vidimo svodi se na svega par instrukcija, jedna mov koja sa stack-a smešta vrednost koju treba da sabira u 32bitni akumulator registar mikroprocesora EAX, a zatim sa steka skida sve ostale kako bi dobio željeni rezulata. Nakon što procesor izvrši sabiranje, sledi vraćanje prethodnog stanja mikroprocesora kako bi znao da nastavi izvršavanje main metode sa tačnim vrednostima. Ret instukcija je povratak iz metode test u metodu main. Sada da donesemo zaključak, kao što vidimo _stdcall calling konvencija ima veliki overhead pozivom instrukcije call, jer mora da čuva stanje procesora i posle da vraća isto kako bi program nastavio korektno da se izvršava, čuvanja stanja procesora na stack je overhead u smislu brzine jer uvodi izvršavanje nekolicine push i pop instrukcija. Push i pop instrukcije za čuvanje i vraćanje stanja procesora kao što već znamo znatno ugrožavaju brzinu, te je poenta kod inline optimizacije da se call zaobiđe u celosti a samim tim i čuvanje stanja. Jednostavno inline to zaobilazi, i prosto lepi telo metode na metodu koja zove funkciju što ćemo videti u nastavku.

Inline optimizacija

Inline kompajlerska ključna reč eliminiše call instrukciju a samim tim i redukuje broj push i pop instrukcija koje _stdcall calling konvencija nalaže - stanje procesora se ne čuva na stack, već se telo pozivne metode lepi u okviru tela metode, ako se telo metode lepi u telo metode, to znači da call nije ni potreban - samim tim redukuje se (smanjuje se) broj instrukcija, te ih ima manje za izvršavanje, ako imamo manji broj instrukcija za izvršavanje samim tim imamo i veću brzinu računanja, te software radi brže.

inline optimizacija

Kao što vidimo iz gore priloženog asemblerskog koda, inline build je zaobišao korišćenje instrukcije call, te je telo metode test nalepio u okviru metode main, samim tim imamo manje instrukcija za izvršavanje, jer nema potrebe čuvati stanje procesora na stack a zatim vraćati isti. Pri inline optimizaciji kompajler radi dodatnu optimizaciju, kao što možemo videti, kompajler koristi instrukciju mov da inicijalizuje 1 na akumulatorski 32bitni registar EAX, a zatim sabira tokom kompajliranja ostale vrednosti: 2+3+4+5 = 14, kao što se vidi. Zatim EAX instrukcijom add sabira sa 14 kako bi dobio rezultat 15 koji ponovo smešta u EAX jer je isti registar akumulator. Kako što vidimo nemamo poziv call instrukcije, te samim tim i nemamo čuvanja stanja procesora na stack i njegovo vraćanje nakon izvršavanja test metode, te dobijamo na brzini. Obzirom da je cela poenta metode test da sabere nekoliko brojeva, jasno se vidi iz datog primera da inline ključna reč, komanduje kompajleru da što je moguće više redukuje i optimizuje broj instrukcija izvršavanja te samim tim i ubrza celokupno izvršenje programa. U jednom od narednih blog postova, prikazaću merenje ovog pograma, te će se videti da inline meri mnogo manje clock perioda procesora tokom izvršavanja nego primer bez inline, da, za merenje se koristi broj clock perioda ;-)

Kako MS Visual Studio prikazuje inline optimizaciju

Obzirom da se radi o optimizaciji broja instrukcija i zaobilaženje korišćenja instrukcije call, MS Visual Studio u slučaju inline optimizacije datu metodu neće prikazati u okviru stack-a, što je prikazano dole na slici.

Poređenje bez inline i sa inline

Kao što se vidi na gornjoj slici, poređenje, bez inline izvršavanje test metode je prikazano u okviru Call Stack - MS Visual Studio. Sa inline optimizacijom, call instrukcija se zaobilazi i redukuje broj instrukcija, te nema ni korišćenja stack-a, jer je telo test metode inline sa main metodom (telo test metode je nalepljeno na main metodu) te Call Stack isključivo prikazuje main metodu. Isto tako nećete moći postaviti break point na metodu test u slučaju inline optimizacije, jer je ista metoda nalepljena na main metodu.

Autor:

Vladimir Savić

zilsel-invent