Пређи на садржај

Редна експанзија

С Википедије, слободне енциклопедије

Редна експанзија или стаза, у рачунарству, је приручник или компилатор оптимизације који замењује функцију позива сајта са телом под називом функције. Стаза за проширење је слична макроу експанзије, али се јавља током компилације, без мењања изворног кода (текста), док се макро проширење јавља пре компилације, и резултатима у различитом тексту који затим обрађује компилатор.

Стаза је важна оптимизација, али има компликоване ефекте на перформансе.[1] Као правило, нека стаза ће побољшати брзину за веома мале трошкове простора, али вишак стазе ће пореметити брзину, због линије кода, конзумирања превише инструкција кеша, а такође ће коштати и значајног дела простора. Анкета скромне академске литературе о стазама из 1980-их и 1990-их дата је у Jones & Marlow 1999.[2]

Преглед

[уреди | уреди извор]

Стаза за проширење је слична макроу експанзије као преводилац који ставља нову копију функције на сваком месту где се зове. Стаза функције ради мало брже од нормалних функција као функција-calling-режијски трошкови су смањени, међутим, плаћају се казне. Ако је функција позвана 10 пута, биће 10 примерака функције убачено у коду. Стога је стаза најбоља за мале, што се често називају. У C++ члан функције класе, ако је дефинисан у дефиницији класе, онда се стаза подразумева (нема потребе да се користи стаза за кључну реч); иначе, кључна реч је потребна. Преводилац може игнорисати покушај програмера да позове функцију, углавном ако је посебно велика.

Стаза за проширење се користи како би се елиминисало време прелета (вишак времена) када се позива функција. Обично се користи за функције које се извршавају често. Она такође има простор да се користи за веома мале функције, и омогућава трансформацију за друге оптимизације.

Без паралелних функција, преводилац одлучује која функција функционише на стази. Програмер има мало или нимало контроле над функцијом стазе. Давање степена контроле програмеру омогућава коришћење специфичних знања примене у избору који функционише на стази.

Обично, када се позива функција, контрола се преноси на своју дефиницију у грани или се позива инструкција. Са стазом, контрола пада кроз директни код за функцију, без грани или позива инструкције.

Компајлери обично спроводи наредбу са стазе. Услови петље и петља тела треба да имају спору евалуацију. Ова опција је испуњена када је код рачунања услова петље и петље тела позван. Разматрања могућности су још један разлог да се позову наредбе.

У контексту функционалних програмских језика, после редног проширења обично следи трансформација Ламбда рачуна.

Програмер може да позове функцију ручно помоћу копирања, као једнократна операција у изворном коду. Међутим, друге методе контроле (види доле) су боље, јер не преципитирају багове који проистичу када је програмер гледао, а (можда изменио) копирану верзију оригиналне функције тела, док је поправљао грешку у унутрашњој функцији.

Утицај на перформансе

[уреди | уреди извор]

Директан ефекат ове оптимизације је побољшање времена и коришћења простора (елиминацијом позива),[lower-alpha 1] по цени од погоршања коришћења простора (због дуплирања функције тела). Експанзија код због дуплирања функције тела доминира, осим у једноставним случајевима,[lower-alpha 2] и тако директан утицај редне експанзије је да се побољша време на рачун простора.

Међутим, основна предност редне експанзије је да омогући даље оптимизације и побољшане заказивања, због повећања величине тела функције, као што је боља оптимизација омогућена већим функцијама.[1] Крајњи утицај редне експанзије на брзину је компликован, због вишеструких ефеката на перформансе меморијског система (првенствено упутство кеша), где доминирају перформансе на савременим процесорима: у зависности од конкретног програма и кеша, посебне функције могу повећати или смањити перформансе.[1]

Утицај редне експанзије варира у зависности од програмског језика и програма, због различитих степена апстракције. У нижим нивоима императивних језика као што су С и Фортран то је типично 10-20% повећање брзине, са мањим утицајем на величину кода, док је у вишим апстрактним језицима знатно важније, због броја слојева које редна експанзија уклања, са екстремним примером Self-а, где је један преводилац видео факторе побољшања од 4 до 55 помоћу редне експанзије.[2]

Директне користи од елиминације функције позива су:

Примарна корист редне експанзије, међутим, су даље оптимизације које то дозвољавају. Оптимизације које прелазе границе функција могу да се ураде без потребе интерпроцедуралне оптимизације (ИПО): једном када је редна експанзија извршена додатне интрапроцедуралне оптимизације ("глобалне оптимизације") постале су могуће на проширеној функцији тела. На пример:

Ово се може урадити без редне експанзије, али захтева знатно компликованији компајлер и линкер (у случају позива и позваног, они су у одвојеним јединицама компилације).

Насупрот томе, у неким случајевима спецификација језика може дозволити програму да учини додатне претпоставке о аргументима за поступке који се више не могу учинити након поступка редне експанзије, спречава неке оптимизације. Паметнији компајлери (као што је Глазгов Хаскелов компилатор) ће пратити, али наивна редна експанзија губи ову информацију.

Даља корист редне експанзије за меморију система:

  • Елиминација гране и чување кода који се извршава у близини заједно у меморији побољшава перформансе инструкција кеша побољшањем локалитета референце (просторни локалитет и редослед упутстава). Ово је мање него оптимизације које конкретно циљају по редоследу, али је значајно.[1]

Директни трошкови редне експанзије повећавају величину кода, због дуплирања функције тела на свакој локацији позива. Међутим, то није увек тако, односно у случају веома кратке функције, где је функција тела мања од величине позива функције (на позиваоца, укључујући и аргумент и повратне вредности руковања), као што су тривијалне методе мутатора или методе корисника (гетери и сетери); или за неку функцију која се користи само на једном месту, у ком случају се не дуплирају. Тако редна експанзија може да се сведе на минимум или да се елиминише ако се оптимизира за величину кода, као што је често случај у уграђеном систему.

Редна експанзија такође намеће трошкове на перформансе, због ширења кода (због дуплирања) онеспособљавајући упутство за кеш перформансе.[3] Ово је најзначајније ако је, пре експанзије, посао сет програма (или врелих делова кода) у једном нивоу хијерархије меморије (нпр, L1 кеш), али након ширења више не одговара, што доводи до тога да често кеш недостаје на том нивоу. Због значајне разлике у перформансама на различитим нивоима хијерархије, ово онеспособљава перформансе значајно. На највишем нивоу то може довести до повећања грешака страница, катастрофалне деградације перформанси због шлајфовања или да програм буде неисправан или да не ради уопште. Ово последње је реткост у десктоп и сервер апликацијама, где је величина броја мала у односу на расположиву меморију, али може бити проблем за ограниченим ресурсима окружења, као што су уграђени системи. Један од начина да се ублажи овај проблем је да се раздвоје функције у мању редну експанзију (брза стаза), и већу нередну (спора стаза).[3]

Редна експанзија утиче лоше на перформансе и то је пре свега проблем за велике функције које се користе на многим местима, али је провала и тачка преко које редна експанзија смањује учинак и то је тешко да се утврди и зависи у целини од прецизног оптерећења, тако да може бити предмет ручне оптимизације или профила вођене оптимизације.[4] Ово је слично питање за други код проширења оптимизација као што је одмотавање петље, које такође смањују број инструкција процесуираних, али могу смањити перформансе због слабијег учинка кеша.

Тачан ефекат редне експанзије на кеш перформансе је компликован. За мале величине кеша (много мање него радни сет постављен пре експанзије), повећања по редоследу доминирају, а редна експанзија побољшава перформансе кеша. За кеш величине близу радног сета, где редна експанзија шири посао сета тако да се више не уклапа у кешу, ово доминира и кеш перформансе смањује. За кеш величине веће од радног скупа, редна експанзија има занемарљив утицај на кеш перформансе. Даље, промене у дизајну кеша, као што су оптерећења шпедиције, може повећати промашаје у кешу.[1]

Подршка компилатора

[уреди | уреди извор]

Компилатори користе различите механизме да одлуче који позив функције треба да се редно прошири; то могу бити ручни наговештаји програмера за одређене функције, заједно са општом контролом преко опције командне линије. Редно проширење се врши аутоматски од стране многих компилатора на многим језицима, на основу пресуде да ли је редно проширење корисно, док у другим случајевима се може ручно навести преко компајлера директивама, обично користећи директиву компилатора или кључне речи под називом inline. Обично то само наговештава да се жели редно проширење, пре него захтевање, са снагом наговештаја која варира од језика и компилатора.

Типично, програмери компилатора могу задржати питања горњих перформанси, и укључити хеуристике у своје копилаторе да одлуче која функција треба редно да се прошири како би се побољшали перформансе, пре него повећање грешака, у већини случајева.

Имплементација

[уреди | уреди извор]

Када је компилатор одлучио да прошири одређену функцију, обављање саме операције проширења је обично једноставно. У зависности од тога да ли се компајлер проширује функцијама широм кода на различитим језицима, компилатор може да уради редно проширење било на високом нивоу средње репрезентације (као апстрактне синтаксе дрвета) или средње репрезентације ниског нивоа. У сваком случају, компилатор једноставно израчунава аргументе, складишти их у варијабли које одговарају аргументима функције, а затим убацује тело функције на позив сајта.

Линкери, као и компилатори, такође могу да ураде функцију редног проширења. Када линкер редно прошири функције, може онда и да редно прошири функције чији извор није на располагању, као што је функција библиотеке (погледајте линк времена оптимизације). Систем извршавања може редно проширити функцију. Рантајм редног проширења може користити динамичке информације профилисања да доносе боље одлуке о томе које функције треба да се редно прошире, као у Java Hotspot компилатору.

Овде је једноставан пример редног проширења које се врши "ручно" на изворном нивоу у С програмском језику: 

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

Пре редног проширења:

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

После редног проширења:

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;
}

Имајте на уму да је ово само један пример. У стварној С апликацији, било би пожељно да користите функцију редног проширења, као што су параметеризованог макроа или паралелних функција да трансформишу код на овај начин. Следећи одељак наводи начине за оптимизацију овог кода.

Редно проширење макро експанзије

[уреди | уреди извор]

Асемблер макроа треба да обезбеди алтернативни приступ редног проширења где секвенца инструкција нормално може да генерише макро експанзије из једне макро изјаве извора (са нула или више параметара). Један од параметара може бити опција за алтернативно генерисање једнократног потпрограма који садржи секвенцу и обрађује га уместо позива функције. Пример: 

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

Компарација са макроима

[уреди | уреди извор]

Традиционално, на језицима као што су С, редна експанзија је постигнута на изворном нивоу користећи параметаризоване макрое. Коришћење правих паралелних функција, као што су доступни у С99, нуде неколико предности у односу на овај приступ:

  • У С, макро призивања не обавља проверу типа, или чак провере да ли су аргументи добро формирани, док функција позива обично ради.
  • У С, макро не може користити кључну реч са истим значењем у функцији (да би функција за коју тражимо проширење могла да се обави, а не макро). Другим речима, макро не може да врати ништа што није резултат последњег израза који га је позвао унутра.
  • Пошто С макрои користе текстуалну замену, то може довести до нежељених споредних ефеката и неефикасности због поновне процене аргумената и редоследа операција.
  • Грешке компилатора у оквиру макроа се често могу тешко разумети, јер се односе на проширење кода, а не код програмера који је куцао. Тако, дебаговање информације за линије кода је обично више од помоћи него макро проширење кода.
  • Многе конструкције се непријатно или немогуће изражавају помоћу макроа, или користе битно другачију синтаксу. Редно проширене функције користе исту синтаксу као обичне функције, и може се редно проширити и непроширене по вољи са лакоћом.

Многи компајлери такође могу проширити редне неке рекурзивне функције; рекурзивни макрои су обично илегални.

Бјарне Стравструп, дизајнер C++, воли да истакне да треба избегавати макрое кад год је то могуће, и залаже се за широку употребу функција редног проширења.

Предности

[уреди | уреди извор]

Редна експанзија је сама оптимизација, јер изнад главе елиминише позиве, али је много важнија као омогућавајућа трансформација. То је, када преводилац проширује функцију тела у контексту свог позива сајта често са аргументима који могу бити фиксне константе - може бити у стању да уради различите трансформације које нису биле могуће пре. На пример, условна грана се може испоставити да је увек истина или увек лажна на овом сајту позива. Ово заузврат може омогућити елиминацију мртвог кода, код кретања инваријантне петље, или индукциона елиминација променљиве. 

У С примеру у претходном одељку, могућности за оптимизацију обилују. Преводилац може да прати овај редослед корака:

  •  temp += 0 изјаве у редовима обележеним (2) и (3) не раде ништа. Преводилац може да их уклони.
  • Услов 0 == 0 је увек истина, тако да преводилац може да замени линију обележену (2) као последицу, temp += 0 (не ради ништа).
  • Преводилац може преправити стање y+1 == 0 у y == -1.
  • Преводилац може смањити израз (y + 1) - 1 у y.
  • Изрази y и y+1 не могу оба бити једнака нули. Ово омогућава преводиоцу да елиминише један тест.
  • У изјавама попут if (y == 0) return y вредностy је позната у телу и може се редно проширити.

Нова функција изгледа овако: 

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

Ограничења

[уреди | уреди извор]

Комплетна редна експанзија није увек могућа, због рекурзије: рекурзивно редно проширење позива се неће прекинути. Постоје различита решења, као што је проширење на ограничени износ, или анализирање позива графика и разбијање петље на одређеним чворовима (тј. не шири неку предност у рекурзивној петљи).[2]  Идентичан проблем се јавља у макро експанзији, као рекурзивна експанзија која не престаје, а обично се решава забрањивањем рекурзивног макроа (као у C и C++).

Методе селекције

[уреди | уреди извор]

Многи компајлери агресивно редно проширују функције где год да је корисно да се то учини. Иако то може довести до већих извршења, агресивна редна експанзија је ипак све више и више пожељна као капацитет меморије која је бржа од брзине процесора. Редна експанзија је критична оптимизација у функционалним језицима и објектно оријентисаним програмским језицима , који се ослањају на њега да обезбеди довољно контекста за своје типично мале функције да чине класичне оптимизације ефикасним.

Језичка подршка

[уреди | уреди извор]

Многи језици, укључујући и Јаву и функционалне језике, не обезбеђују језичке конструкције за функције редне експанзије, али њихови компајлери или преводиоци често обављају агресивну редну експанзију. Остали језици обезбеђују конструкције за експлицитне наговештаје, углавном као директиве компајлера (прагме).

У Ада програмском језику, постоји прагма за функције редне ескпанзије.

Функције у Common Lisp могу се дефинисати као редне експанзије помоћу inline декларације као:[5]

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

Хаскелов компилатор ГХЦ покушава да редно прошири функције или вредности које су довољно мале, али редна експанзија може бити експлицитно наведена коришћењем језика прагме:[6]

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

C и C++

[уреди | уреди извор]

C и C++ имају  inline кључну реч, која функционише и као компајлер директиве - прецизирајући да се жели редна експанзија, али није обавезна - и мења понашање видљивости и повезује. Промена видљивости је неопходна да би функција могла да се редно прошири преко стандардне С алатке, где компилација индивидуалних фајлова (пре него, преводилачких јединица) је затим повезана да би линкер могао да редно прошири функције, које морају бити наведене у заглављу (да буде видљиво) и означено inline (да би се избегла двосмисленост са више дефиниција).

Види још

[уреди | уреди извор]

Референце

[уреди | уреди извор]
  1. ^ а б в г д Chen et al. 1993.
  2. ^ а б в Jones & Marlow 1999.
  3. ^ а б Benjamin Poulain (August 8, 2013).
  4. ^ See for example the Adaptive Optimization System Архивирано на сајту Wayback Machine (9. август 2011) in the Jikes RVM for Java.
  5. ^ Declaration INLINE, NOTINLINE at the Common Lisp HyperSpec
  6. ^ 7.13.5.1.

Литература

[уреди | уреди извор]

Спољашње везе

[уреди | уреди извор]
Преузето из „https://sr.wikipedia.org/w/index.php?title=Редна_експанзија&oldid=27673128”