Laskennassa funktion upottaminen (eng. Inlining ) on optimointimenetelmä , jossa funktiokutsu korvataan suoraan sen rungolla. Funktioiden sisällyttäminen on pohjimmiltaan samanlainen kuin makrokorvaus , mutta toisin kuin se ei muuta lähdekoodia ja tapahtuu käännöshetkellä, kun taas makrot muuttavat lähdekoodia ennen kääntämistä.
Toimintojen sisällyttäminen on tärkeä optimointi, mutta tehokkuusvaikutus voi vaihdella [1] . Tyypillisesti jotkin rivitykset parantavat suorituskykyä hyvin pienellä tilalla, mutta liikakäyttö voi hidastaa ohjelmaa, koska tekstin sisäinen koodi kuluttaa liikaa käskyvälimuistia ja vie myös huomattavan määrän tilaa. Jones & Marlow'n vuonna 1999 julkaisema kirja [2] tarjoaa yleiskatsauksen 1980- ja 1990-lukujen akateemiseen kirjallisuuteen funktion inlinoinnista.
Funktioiden sisällyttäminen on samanlainen kuin makrolaajennus – pohjimmiltaan kääntäjä asettaa uuden kopion funktiosta jokaiseen paikkaan, jossa sitä kutsutaan. Sisäisiä toimintoja sisältävä koodi toimii hieman normaalia koodia nopeammin, koska funktioiden kutsumisen lisävaiheet ovat poissa, mutta se lisää myös muistin kulutusta. Jos funktio on sisäänrakennettu 10 kertaa, koodiin lisätään 10 kopiota funktiosta. Siksi upottaminen sopii parhaiten pieniin usein käytettyihin toimintoihin. C++ : ssa oletusarvoisesti luokkamäärityksessä määritellyt menetelmät on rivitetty (ei tarvitse käyttää rivin avainsanoja ); muuten avainsana on pakollinen. Kääntäjä voi jättää huomioimatta ohjelmoijan yrityksen julistaa funktio inline - tämä pätee pääasiassa erittäin suuriin funktioihin.
Funktioinline-toimintoa käytetään säästämään CPU-aikaa, joka kuluu toimintokutsuihin. Yleensä käytetään usein suoritettaviin toimintoihin. Tekniikka säästää myös muistia hyvin pienille toiminnoille, lisäksi se mahdollistaa muiden optimointien soveltamisen .
Ilman inline-ohjeita kääntäjä usein päättää, mitkä funktiot rivittää. Ohjelmoijalla on vain vähän hallintaa siihen, mitkä toiminnot tulevat sisään. Jos ohjelmoija päättää toiminnon sisällyttämisestä itse, hän voi käyttää tietoa tietyn sovelluksen toiminnasta parempaan optimointiin.
Kun funktiota kutsutaan, ohjaus siirretään sen runkoon haarakäskyllä ( haara) tai kutsukäskyllä (kutsu). Sisäänrakentaminen mahdollistaa näiden ohjeiden poistamisen - tässä tapauksessa ohjaus siirtyy suoraan toimintokoodiin.
Yleensä kääntäjät käyttävät rivitystä toteuttaakseen joitain . Esimerkiksi syklien rungot ja ehdot on laskettava suoraan suorituksen aikana . Tämä saavutetaan upottamalla koodi olosuhteiden ja silmukoiden rungon arvioimiseksi, joissa niitä kutsutaan. Lausunto lisää myös suorituskykyä.
Kun tarkastellaan funktionaalisten ohjelmointikielten kontekstissa , funktion rivitystä seuraa yleensä beta - redusointimuunnos .
Ohjelmoija voi upottaa funktion manuaalisesti kopioimalla sen koodin ja liittämällä sen kutsusivustoille . Muut inline-ohjausmenetelmät (katso alla) ovat kuitenkin parempia, koska ne eivät aiheuta virheitä, joita esiintyy, jos ohjelmoija ei päivitä yhtä sen kaksoiskappaleista korjatessaan virhettä rivifunktiossa.
Tämän optimoinnin tärkein vaikutus on parantaa suorituskykyä (johtuen puhelukustannusten eliminoinnista) ja lisätä muistin kulutusta [a] (johtuen toimintorungon päällekkäisyydestä ). Koodin monistamisesta johtuva muistinkulutus hallitsee, paitsi yksinkertaisissa tapauksissa [b] . Siivouksen pääasiallinen vaikutus on siis koodin nopeuttaminen tilan kustannuksella.
Sisällyttämisen tärkein etu on kuitenkin mahdollisuus lisäoptimointiin ja parempaan suunnitteluun suurentamalla funktiorungon kokoa, koska suurempia toimintoja voidaan optimoida paremmin [3] . Vaikutusta suorituskykyyn on melko vaikea arvioida täysin, koska muistijärjestelmään (ensisijaisesti käskyvälimuistiin ) kohdistuu suuri määrä vaikutuksia, joilla on merkittävä vaikutus nykyaikaisten prosessorien suorituskykyyn. Tiettyjen toimintojen upottaminen tietyn ohjelman ja välimuistin mukaan voi joko lisätä tai vähentää suorituskykyä [1] .
Sisäänrakentamisen vaikutus riippuu myös ohjelmointikielestä, johtuen erilaisesta abstraktiotasosta. Alemman tason pakollisilla kielillä, kuten C ja Fortran, voidaan saavuttaa 10-20 % nopeuden lisäys ilman vain vähän vaikutusta koodin kokoon. Abstraktimmilla kielillä vaikutus voi olla paljon suurempi johtuen upotuksen poistamien tasojen määrästä. Esimerkkinä voidaan mainita Self -kieli , jossa upotuksen ansiosta oli mahdollista saavuttaa kiihtyvyyskertoimet 4:stä 55:een [4] .
Toimintokutsun poistamisen välitön hyöty on seuraava:
Sisällön pääasiallinen hyöty on kuitenkin sen tarjoamissa mahdollisuuksissa lisäoptimointiin. Koodioptimoinnit useista toiminnoista voidaan suorittaa ilman, että tarvitaan inter-procedural-optimointia (IPO): laajennettuun funktiorunkoon sisällyttämisen jälkeen ylimääräiset "prosessinsisäiset" ("globaalit") optimoinnit ovat mahdollisia. Esimerkiksi:
Tällaiset optimoinnit voidaan tehdä ilman rivitystä, mutta ne vaativat paljon monimutkaisempia kääntäjiä ja linkkejä (jos kutsu ja toteutus ovat erillisissä käännösyksiköissä).
Joissakin tapauksissa kielimääritykset sallivat kuitenkin ohjelmien tehdä lisäoletuksia proseduuriargumenteista. Sisällyttämisen jälkeen nämä tiedot voivat kadota, jolloin jotkin optimoinnit ovat mahdottomia. Älykkäämmät kääntäjät (kuten Glasgow'n Haskell-kääntäjä ) seuraavat tätä, mutta yksinkertainen inline-toteutus ei ota tätä huomioon.
Sisäänrakennetun muistijärjestelmän osalta voidaan erottaa seuraavat edut:
Sisällyttämisen suora hinta on koodikoon kasvu, joka johtuu funktion rungon päällekkäisyydestä kussakin puhelupaikassa. Näitä kustannuksia ei esiinny vain erittäin pienissä funktioissa, joissa funktion runko on pienempi kuin kutsun hinta (kutsuminen, argumenttien käsittely ja palautusarvot), kuten triviaali accessori (getterit ja asettajat); tai toiminnoille, joita käytetään vain kerran. Siksi optimoitaessa kokoa (tarvitaan usein sulautetuissa järjestelmissä ) tämä optimointitekniikka voidaan minimoida tai sitä ei käytetä.
Sisällys heikentää myös suorituskykyä laajentamalla (kopioimalla) koodia, mikä heikentää käskyvälimuistin suorituskykyä. [8] Hidastuminen on havaittavin, jos ennen laajennusta ohjelman työmäärä (ns. kuuma koodin osa) sijoitetaan yhdelle muistihierarkian tasolle (esimerkiksi tason 1 välimuistiin ) ja laajennuksen jälkeen se ei enää mahdu sinne, mikä johtaa toistuviin välimuistin puutteisiin tällä tasolla. Välimuistihierarkian eri tasojen suorituskyvyn merkittävien erojen vuoksi tämä hidastaa koodia. Hierarkian korkeimmalla tasolla tämä voi johtaa sivuvirheiden määrän kasvuun , katastrofaaliseen suorituskyvyn heikkenemiseen pusertamisen vuoksi ja jopa ohjelman täydelliseen epäonnistumiseen. Jälkimmäinen on harvinainen tyypillisissä työpöytä- ja palvelinsovelluksissa, joissa koodin koko on pieni verrattuna käytettävissä olevaan muistiin, mutta se voi olla ongelma resurssirajoitteisissa ympäristöissä (esim. sulautetut järjestelmät). Yksi ratkaisu on jakaa funktiokoodi lyhyeksi kuumaksi ( nopea ) poluksi upotuksilla ja pitkäksi kylmäksi (hidas) poluksi ilman upotuksia. [kahdeksan]
Sisäänrakentamisen tärkein suorituskykyvaikutus kohdistuu ensisijaisesti suuriin toimintoihin, joita käytetään monissa paikoissa. Kannattavuuspisteen määrittäminen, jonka ylittyessä rivitys vähentää suorituskykyä, on kuitenkin monimutkaista ja riippuu todellisesta työmäärästä. Reunatapauksissa tämä voi olla manuaalista optimointia tai optimointia profiloinnin avulla . [9] Samanlainen ongelma esiintyy muissa hajautusoptimoinneissa, kuten silmukan purkamisessa : vaikka käskyjen määrä vähenee, suorituskyky voi heikentyä hitaamman välimuistin vuoksi.
On vaikea arvioida tarkasti upottamisen vaikutusta välimuistin suorituskykyyn. Pienillä välimuistikooilla (paljon pienempi kuin työkoko ennen laajennusta) sekvenssin lisääminen hallitsee, joten rivitys parantaa välimuistin suorituskykyä. Jos välimuistin koko on lähellä työkokoa , välimuistin suorituskyky heikkenee, koska lisäyksen jälkeen laajennettu koodi ei mahdu välimuistiin. Jos välimuisti on suurempi kuin työtila , upotuksella on vain vähän vaikutusta välimuistin suorituskykyyn. Myös jotkin välimuistin suunnittelun parannukset (kuten kuorman edelleenlähetys) voivat lieventää välimuistin menetysten lisääntymistä. [kymmenen]
Kääntäjät käyttävät useita menetelmiä päättääkseen, mitkä funktiot sisällytetään; Näiden joukossa sekä ohjelmoijien nimenomaiset ohjeet tiettyjä toimintoja varten että yleiset ohjeet komentorivin valinnoista ovat tärkeitä. Monissa kääntäjissä monilla kielillä automaattinen rivitys perustuu arvioon siitä, onko se hyödyllistä; muissa tapauksissa se voidaan asettaa manuaalisesti kääntäjän käskyjen avulla tai käyttämällä inline. Tämä avainsana osoittaa vain, että funktio on upotettava - tämän ilmaisun merkitys vaihtelee kielen ja kääntäjän mukaan.
Kääntäjän kehittäjät ottavat edellä mainitut asiat huomioon ja ottavat kääntäjiinsä käyttöön erilaisia heuristiikkaa , jotka valitsevat sisäänrakennettavat toiminnot, jotta useimmissa tapauksissa se parantaa suorituskykyä sen sijaan, että se heikentää sitä.
Kääntäjän suorittama rivityksen toteuttaminen on yleensä melko yksinkertaista. Riippuen siitä, suoritetaanko tämä toiminto koodissa eri kielillä, kääntäjä voi suorittaa rivityksen joko korkean tason välimuodossa (kuten abstraktissa syntaksipuussa ) tai matalan tason välimuodossa. Kummassakin tapauksessa kääntäjä yksinkertaisesti arvioi argumentit , tallentaa ne muuttujiin, jotka vastaavat funktion argumentteja, ja lisää sitten funktion rungon kutsupaikkaan.
Linkkeri voi myös upottaa toimintoja, joiden lähdekoodia ei ole saatavilla, kuten kirjastofunktiot (katso linkkiajan optimointi ). Suoritusaika voi myös sisällyttää toimintoja ajon aikana . Ympäristöt, kuten Java Hotspot , käyttävät dynaamisia profilointitietoja päättääkseen, mitkä ominaisuudet rakennetaan [11] .
Tässä on yksinkertainen esimerkki "manuaalisesta" upottamisesta lähdetasolla C :ssä :
int pred ( int x ) { jos ( x == 0 ) paluu 0 ; muu paluu x - 1 ; }Ennen upottamista:
int func ( int y ) { paluu pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }Upotuksen jälkeen:
int func ( int y ) { int tmp ; jos ( y = = 0 ) tmp = 0 ; muuten tmp = y - 1 ; /* (yksi) */ if ( 0 == 0 ) tmp += 0 ; muuten tmp + = 0-1 ; _ /* (2) */ jos ( y + 1 == 0 ) tmp += 0 ; muuten tmp += ( y + 1 ) - 1 ; /* (3) */ paluu tmp ; }Huomaa, että tämä on vain esimerkki. Oikeassa C-sovelluksessa olisi parempi käyttää sisäistä toiminnallisuutta, kuten parametroitua makroa tai rivifunktiota jotta kääntäjä muuntaa koodin tällä tavalla. Seuraavassa osiossa luetellaan tapoja optimoida tämä koodi.
Kokoonpanokielimakrot tarjoavat vaihtoehtoisen lähestymistavan upottamiseen, jossa käskysarja luodaan "laajentamalla" jotain alkuperäistä makrolauseketta (nolla tai useammalla parametrilla). Yksi parametreistä voi määrittää, että käskysarjan sijaan generoidaan erillinen kertaluonteinen aliohjelma , joka sisältää halutun sekvenssin ja jota kutsutaan sisäänrakennetun koodin sijaan. Esimerkki:
MOVE FROM=taulukko1,TO=jono2,INLINE=EIUseita erilaisia upotuksen heuristioita on tutkittu. Tyypillisesti inline-algoritmille annetaan tietty tilabudjetti (ohjelman koon sallittu lisäys). Algoritmi pyrkii rakentamaan arvokkaimmat haasteet ylittämättä tätä budjettia. Tässä mielessä monet upotusalgoritmit mallintavat tyypillisesti reppuongelman ratkaisua . [12] Päättääkseen, mitkä kutsupaikat ovat arvokkaimpia, sisäänrakennetun algoritmin on arvioitava niiden hyöty eli odotettu suoritusajan lyheneminen. Yleensä hyödyn arvioimiseen käytetään profilointidataa eri koodipolkujen suoritustiheydestä. [13]
Profilointidatan lisäksi nykyaikaiset dynaamiset kääntäjät käyttävät useita kehittyneempiä heuristioita, kuten: [6]
Inlineing itsessään on jo optimointia, koska se eliminoi puhelun ylimääräiset kustannukset, mutta sen tärkein etu on, että se on yhteistoiminnallinen optimointi . Tämä tarkoittaa, että sen jälkeen, kun funktion runko on sisällytetty kutsupaikkaan (usein argumenteilla, jotka voivat olla kiinteitä vakioita ), kääntäjällä on mahdollisuus suorittaa aiemmin mahdottomia muunnoksia. Saattaa esimerkiksi käydä ilmi, että haaralauseen ehto on aina tosi (tai aina epätosi) kyseiselle puhelusivustolle. Tämä puolestaan johtaa kuolleen koodin poistamiseen, invariantin koodin poimimiseen silmukasta tai induktiivisen muuttujan poistamiseen .
Yllä olevassa C-esimerkissä on runsaasti tilaa lisäoptimoinnille. Kääntäjä voi tehdä seuraavaa:
Tämän seurauksena toiminto näyttää tältä:
int func ( int y ) { jos ( y == 0 ) paluu 0 ; jos ( y == -1 ) paluu -2 ; paluu 2 * y - 1 ; }Täysi rivitys ei aina ole mahdollista rekursion vuoksi : rekursiivinen puhelun rivitys ei koskaan valmistu. Tähän ongelmaan on olemassa useita ratkaisuja, kuten upottaminen tiettyyn rajaan asti tai puhelukaavion analysointi ja syklien katkaiseminen tietyissä solmuissa (eli upotussyklin katkaiseminen joissakin paikoissa) [14] . Samanlainen ongelma ilmenee makrolaajennuksessa - rekursiivinen laajennus ei lopu koskaan. Yleensä tämä ratkaistaan yksinkertaisella kiellolla käyttää rekursiivisia makroja (kuten C ja C ++).
Perinteisesti C :n kaltaisilla kielillä rivitys tehtiin lähdetasolla käyttämällä parametroituja makroja. C99 :ssä saatavilla olevalla kyvyllä käyttää todellista funktion inliningiä on useita etuja:
Monet kääntäjät voivat myös sisällyttää joitain rekursiivisia funktioita [15] ja rekursiiviset makrot ovat yleensä kiellettyjä.
C++:n luoja Björn Stroustrup haluaa korostaa, että makroja tulee välttää aina kun mahdollista, ja suosittelee useammin sisäisten funktioiden käyttöä.
Monet kääntäjät toimivat aggressiivisesti rivissä aina, kun siitä on hyötyä. Vaikka tämä voi kasvattaa suoritettavan -tiedoston kokoa , tämä aggressiivinen strategia yleensä kannattaa, koska tietokonejärjestelmän muisti kasvaa nopeammin kuin prosessorin nopeus. Sisäänrakentaminen on kriittinen optimointi toiminnallisille ja olio- ohjelmointikielille: ne käyttävät yleensä pieniä funktioita, ja inlining antaa niille tarpeeksi kontekstia, jotta klassinen optimointi olisi tehokasta.
Monet kielet, mukaan lukien Java ja toiminnalliset kielet , eivät tarjoa kielirakenteita funktioiden sisällyttämiseen, mutta niiden kääntäjät tai tulkit toimivat automaattisesti aggressiivisesti. [6] Muut kielet tarjoavat syntaksin eksplisiittisille ohjeille, yleensä kääntäjäohjeiden (pragma) muodossa .
Ada - ohjelmointikielessä on ohje sisäänrakennetuille funktioille.
Common Lispissä voit määrittää funktioita tekstin sisäisiksi määrityksiksi inline: [16]
( declaim ( inline dispatch )) ( defun dispatch ( x ) ( funcall ( get ( auto x ) 'lähetys ) x ))GHC Haskell -kääntäjä yrittää automaattisesti sisällyttää riittävän pieniä funktioita, mutta on myös mahdollista käyttää direktiivejä osoittamaan tarvetta sisällyttää direktiiviin: [17]
key_function :: Int -> String -> ( Bool , Double ) {-# INLINE key_function #-}C- ja C++-kielillä on avainsana inline. Se toimii samanaikaisesti kääntäjädirektiivinä, joka osoittaa, että rivitys on "toivottu" mutta ei "pakollinen" ja muuttaa myös toiminnon näkyvyyttä ja linkkerin käyttäytymistä. Muutos näkyvyyteen on tarpeen, jotta funktio voidaan rivittää käyttämällä standardia C-työkalupakkia: jossa yksittäisten tiedostojen (tai käännösyksiköiden ) kokoaminen edeltää linkittämistä. Siksi, jotta linkkeri sisäisiin funktioihin, ne on ilmoitettava otsikossa (jotta ne ovat näkyvissä) ja merkitä inline(jotta vältetään moniselitteisyys useista määritelmistä).