Programoptimalizálás

A számítógép-programozásban a programoptimalizálás egy folyamat, aminek az a célja, hogy a programot valamilyen szempontból (sebesség, erőforrások, például memória használata) jobbá tegye. Általában sebesség, memóriahasználat és processzor kihasználtsága lehet a szempont. A különböző szempontok egymással szembemennek, nem lehet mindhárom szempontból az optimálisak közül a legjobbat választani.

Bővebben

Ugyan az optimalizáció szó eredete ugyanaz, mint az optimálisé, viszonylag ritkán cél az adott szempontból optimális algoritmus megvalósítása. Az optimalizált rendszer elég jó ahhoz, hogy a felhasználó számára jó legyen. Emellett azt is figyelembe kell venni, hogy az eredmény ne legyen törékeny, azaz további változásokkal ne romoljon gyorsan adott szempontból. Emiatt sem keresik meg az optimális megoldást.

A különböző szempontok egymással szembemennek, egy gyorsabb algoritmus több memóriát használ, egy kevés memóriát használó lassabb. Egyes gyakori célokra vannak gyors, illetve kevés memóriaigényű algoritmusok, így ezek használatával átváltható az idő és a memória egymásba. Az optimalizáció folyamatára jellemző, hogy a nagyobb javulások az elején várhatók.

Szintjei

Az optimalizálás különböző szinteken végezhető. Tipikusan a felsőbb szinteken nagyobb eredményeket lehet elérni kevesebb munkával. Azonban vannak olyan esetek is, amikor ez nem igaz, mivel az alsóbb szintek működésétől függ az egész működése. Az optimalizáció előrehaladottabb állapotára is ez a jellemző, mivel a felső szinten kezdik. Néhány meggondolás végigvihető a teljes projekten, de az optimalizációt később végzik. Hosszabb projekteken több optimalizációs ciklus is végigvonul. Az egyik egység optimalizálása során vele összefüggő egységek korlátaira is fény derülhet. Ezekhez nem nyúlnak, ha nem éri meg.

Habár szokás a korai optimalizációt minden rossz forrásának tekinteni, néha az optimalizáció a követelmények között szerepel. Például egy videójáték 60 Hz-es frissítéssel megfelelő, de 6 Hz-en már erősen szaggat. Előfordul, hogy annyira félnek a korai optimalizációtól, hogy a prototípus sokkal lassabb, mint amilyennek a végeredménynek kellene lennie, akár több, mint egy nagyságrenddel. Azonban a performancia javítását akadályozhatja a hardver architektúrája, mint például az Intel 432 (1981); vagy évekbe telik, amíg elfogadható sebességet érnek el, mint például a Java (1995) csak a HotSpot (1999) eljövetelével. Az ekkora performanciaváltások nagy kockázatot és bizonytalanságot okoznak.

Tervezési szint

A legmagasabb szinten az optimalizáció figyelembe veheti a különböző célokat, elérhető erőforrásokat, követelményeket, használatot. Az architektúra meghatározó a performancia szempontjából. Például, ha lassú a hálózat, akkor ezt figyelembe véve nagyobb adatcsomagokat küldözgethet a program.

Egy fordító tervezése során figyelembe kell venni a fordító és a lefordított program performanciáját is. Egy egymenetes fordító gyorsabb, de kevésbé gyors bináris programot produkál. Egy többmenetes, habár saját maga lassabb, jobban tudja optimalizálni a programot, így annak kimenetele gyorsabb lehet.

Ezen a szinten választanak platformot és nyelvet, ezek megváltoztatása később a program újraírását igényli. Előfordulhat azonban, hogy csak a program egy részét kell átírni, például egy Python projektben a sebességkritikus részeket C-re. Az architektúra későbbi megváltoztatása szintén hasonló méretű változtatást igényel.

Algoritmusok és adatszerkezetek

A teljes terv keretében az algoritmusok és adatszerkezetek megválasztása, és hatékony megvalósítása következik. A tervezés után ezeknek van a legnagyobb hatása a program további részeire. Általában az adatszerkezetek megváltoztatása a legnehezebb, mivel az adatszerkezetek és performanciájuk mindenütt jelen van a programban, habár hatásuk gyengíthető absztrakt adatszerkezetek használatával a függvénydefiníciókban, és a konkrét adatszerkezetek kevés helyre való korlátozásában.

Az algoritmusok bonyolultsága általában legfeljebb lineáris O(n), néha loglineáris O(n log n) a bemenet méretétől függően tárban és időben. Az O(n²) algoritmusok általában nem fogadhatók el, mivel rosszul skálázódnak, 10-szer nagyobb bemenet 100-szoros költségnövekedést okoz. Ismételten hívott lineáris algoritmusokat is célszerű konstans vagy logaritmikus algoritmusokra cserélni, ha lehetséges.

Az aszimptotikus bonyolultság mellett a konstans tényező is számít, hiszen a kisebb bemenetek gyakoribbak. Gyakran egy hibrid algoritmus nyújtja a legjobb teljesítményt, cserébe bonyolultabb lesz a program.

A stratégia lehet az, hogy például egyszerű szövegkezelést használnak latin betűs szöveghez, mint például dévanagari íráshoz bonyolultabbat. Egy másik módszer a számítások elkerülése. A gyakori eseteket meg lehet jegyezni, így csak ki kell keresni a memóriából. Ezt úgy is hívják, hogy memoizáció, vagy úgy is, hogy cachelés. Gyakran több szintű cachelés is van, ami azonban memóriaigényes. Azonban ha változó adatokat cache-elnek, akkor a korrektség is elveszhet.

Forráskód szint

A kiválasztott algoritmus megvalósítása szintén tartalmaz néhány lehetőséget. Például a korai C fordítók a while(1) ciklusból lassabb kódot fordítottak, mint a for(;;) ciklusból, mivel a while(1) feltételes maradt, aminek mindig ellenőrizni kellett a feltételét, de a for(;;) feltétel nélküli ugrássá alakult. Újabban optimalizáló fordítókat használnak erre a célra. A legelső optimalizáló fordító a BLISS számára készült 1970-ben, és erről a The Design of an Optimizing Compiler írt 1975-ben. Az 1980-as évek végétől kezdtek hatékonyabbá válni. A lehetőségek függenek a forrásnyelvtől, a célnyelvtől és a fordítótól. Előre nehéz megjósolni vagy megérteni, hogy milyen változtatásokat végeznek. A visszatérési érték optimalizálása a és a ciklusfüggetlen kód kiemelése példa arra, hogy hogyan lehet csökkenteni a szükséges segédváltozók számát, és gyorsítani a kódot a találomra végzett optimalizálás helyett.

Build szint

A forrás- és a célnyelv közötti szinten direktívák és flagek használhatók a különféle opciók hangolására. Így például az előfeldolgozó képes lehet kivenni azt, amit valójában nem használ a kód, a szükségtelen képességeket letiltani, végezhet optimalizációt speciálisan egy processzortípus számára a hardver képességeinek figyelembe vételével, vagy az elágazás megjóslásával. A forrásalapú disztribúciós rendszerek, mint a BSD Ports és a Gentoo Portage hasznot húzhat ebből a szintből.

Fordítási szint

Egy optimalizáló fordító használata biztosíthatja, hogy a végrehajtható program legalább annyira van optimalizálva, mint amennyire azt a fordító előrejelezte.

Assembly szint

Az assembly nyelvű programozás biztosítja a legtömörebb és leghatékonyabb kódot, ha a programozó előnyére fordítja a teljes utasításkészletet. A beágyazott rendszereket célzó operációs rendszerek közül sok ezért assemblyben készült. A legtöbb programot azonban nem assemblyben írják. A legtöbb assembly kódot fordító készíti, amikor egy magas szintű nyelvet lefordít, és ezt kézzel optimalizálják. Ha a hatékonyság és a méret kevésbé fontos, akkor nagyobb részek is íródhatnak magas szintű nyelven.

A modern optimalizációs fordítók gondoskodnak az adott cél szerinti optimalizáláshoz, ezért kézzel nehezebb ennél jobb kódot készíteni, és csak kevés projektnek van szüksége erre a szintre.

Sok kódot arra terveznek, hogy különféle platformokon fusson. Emiatt nem lehet számítani az újabb processzorok hatékonyabb kódjára, vagy figyelembe venni a régi módellek speciális szükségleteit. Ha az egyik eszközre finomhangolják az assembly kódot, abból nem származik előny a többi platform számára.

Ahelyett, hogy assemblyben írnának, a programozók többnyire disassemblert használnak a kimenet elemzésére, és inkább a forráskódot módosítják, hogy jobb kód forduljon belőle.

Futtatható állomány

A helyben, futtatás előtt fordított kód felhasználhat futás idejű adatokat az optimalizációhoz azon az áron, hogy a fordítás lassabb lesz. Ez a technika az első szabályos kifejezések korára megy vissza, a Java HotSpot és a JavaScript V8 tette népszerűvé. Néha az adaptív optimalizáció futás idejű optimalizációt is végezhet, a statikus fordítókkal szemben dinamikusan változtat paramétereket az aktuális inputtal vagy más más tényezőkkel összefüggésben.

A profilvezérelt optimalizáció egy futásidejű profilokon alapuló technika, ami hasonlít a statikus átlagos eset analógjához az adaptív optimalizáció dinamikus technikájának esetén.

Az önmódosító kód dinamikusan megváltoztathatja önmagát a futás idejű környezethez alkalmazkodva. Ez gyakoribb volt az assemblyben írt kód esetén.

Egyes CPU-k futás időben végezhetnek optimalizációt, mint például a sorrend megváltoztatása, spekulatív végrehajtás, utasításfutószalagok, és elágazás-előrejelzés. Egyes fordítók segíthetik ezt is, például utasításütemezéssel.

Platformfüggőség

Az optimalizáció platformfüggő és platformfüggetlen módszerekre osztható. A platformfüggetlen módszerek bármely számítógépen javítják a program működését, a platformfüggők csak egyetlen platformot, processzortípust, sőt, a felhasználó egyetlen gépének speciális tulajdonságait használják ki. Ez utóbbiak más gépeken akár ronthatják is a program működését; emiatt az optimalizáció késői szakaszában több kódváltozatot kell fenntartani.

Platformfüggetlenek azok az általános módszerek, amelyek a legtöbb CPU-t hasonlóan érintik. Ilyenek a ciklus kigöngyölítése, a függvényhívások számának csökkentése, a memóriahatékony rutinok és a feltételek redukciója. Egy további példa a belső for ciklusról szóló döntés, hogy megmaradjon-e for ciklusnak, vagy hatékonyabb-e kigöngyölítve, esetleg while ciklusként. Ezek a módszerek általában az utasítások számát csökkentik, vagy a teljes memóriahasználatot.

A platformfüggő módszerek közé tartozik az utasítások ütemezése, az utasításszintű párhuzamosság, az adatszintű párhuzamosság és a cache optimalizációs technikák. Az utasítások leghatékonyabb ütemezése még az ugyanolyan architektúrájú processzorokon is egyedi.

Erő redukció

A számítási feladatok többféleképpen is megoldhatók, de különféle hatékonysággal. Egy hatékonyabb számításra való áttérést erő redukciónak is neveznek. Például a következő C kódszakasz 1-től N-ig összegzi az egészeket:

int i, sum = 0;
for (i = 1; i <= N; ++i) {
  sum += i;
}
printf("sum: %d\n", sum);

Ezt a szakasz helyettesíthető egy képlet felhasználásával, feltéve, hogy nincs túlcsordulás:

int sum = N * (1 + N) / 2;
printf("sum: %d\n", sum);

Az optimalizáció választhat az ismert algoritmusok közül, hogy elvégezze ugyanazt a számítást a célnak jobban megfelelve. Lásd algoritmushatékonyság. Gyakran azonban nagyobb javulás érhető elő a nem használt funkcionalitás eltávolításával.

Az optimalizáció nem mindig nyilvánvaló vagy intuitív. A fenti példában előfordulhat, hogy a sebesség csökken. Ennek az lehet az oka, hogy az összeadás gyorsabb, mint a ciklus adminisztrációja és a megfelelő szorzás elvégzése.

Mérlegelés

Az optimalizáció bizonyos esetekben kiforrottabb algoritmusok használatát jelenti. Ez lehetővé teszi, hogy egyes speciális eseteket jobban kihasználjanak, illetve trükköket vessenek be. Mindezek azonban rontják az olvashatóságot, így esélyesen több lesz bennük a hiba és nehezebben karbantarthatók, mint a nem optimalizált, elvben azonos működésű kód. Emiatt a következő verzió inkább a nem optimalizált változatot fogja felhasználni.

Mivel a különböző szempontok egymással szembemennek, csak egyet lehet kiválasztani. Az optimalizált program csak ebből a szempontból lesz jobb, a többiből rosszabb. Ide tartozik a fordítási, a futási idő, a memóriahasználat, a lemezhasználat, a sávszélesség és a felhasznált teljesítmény. Például a cache méretének növelése növeli a memóriahasználatot, és gyorsítja a programot. További példa a tömörség és az olvashatóság szembenállása.

Vannak esetek, amikor arról kell dönteni, hogy bizonyos műveleteket annak árán lehet gyorsítani, hogy azzal más műveletek lassulnak. Így lehet például választani egy adatszerkezet különböző megvalósításai között. Nagyban is előfordulhat hasonló. Néha a döntés nem technikai természetű, hanem egy vetélytárs hasonló termékét akarják legyőzni bizonyos tesztműveletekben. Emiatt a program működése romlik más műveletekben, például a normális használat lelassul. Az ilyen változtatásokat pesszimizációnak is nevezik.

Palacknyak

Az optimalizáció kereshet palacknyakakat a rendszerben. Ezek a részek korlátozzák a program végrehajtásának sebességét. Ez gyakran egy erőforrást használó kritikus rész, habár lehet hálózati sávszélességi korlát vagy az I/O műveletek lassúsága.

A számítástudományban az erőforrások használata a hatványtörvényt követi, és alkalmazható a Pareto-elv, hogy az erőforrások 80%-át a program 20%-a használja. Azonban jobban alkalmazható becslés a 90/10-es szabály, hogy a program futásidejének 90%-át a kód 10%-án tölti.

Egyes algoritmusok jobban működnek kis, mások nagyobb bemenetre, melyek akár előkészítést is igényelnek. Ezért az optimalizációt végzőnek gondolnia kell arra, hogy adaptív vagy hibrid algoritmust vezessen be. Profilozóval be lehet határolni, hogy mikor melyik a jobb.

Bizonyos esetekben több memória igénybevételével a program felgyorsítható. Például egy szűrő algoritmus soronként olvas egy fájlt, és a kimenetet azonnal kiírja. Ez csak egy sornak megfelelő memóriát vesz igénybe, viszont tipikusan lassú, mivel sokszor kell olvasnia a lemezt. Kisebb, a memóriában elférő fájlok esetén felgyorsítható azzal, hogy egyszerre olvassa be a fájlt, de ez több memóriába kerül. Nagyobb fájlok blokkokra oszthatók. A cachelés hasonlóan hatékony lehet, ha egy eredményt egyszer kell kiszámítani és többször van rá szükség.

Makrók

Az optimalizáció használhat makrókat és sablon metaprogramozást is.

Egyes programozási nyelveken, mint C és C++, a makrókat szövegszerkesztéssel, tokencserékkel fejtik ki. Sok esetben az efféle makrókkal szemben az inline függvények jelentenek típusbiztos problémát. Az inline függvény törzse fordítás időben optimalizálható a makrókhoz hasonlóan, például a konstansok kiszámításával és behelyettesítésével (lásd konstansok helyettesítése).

Funkcionális nyelvekben, mint például Lispben a parser parsolási időben fejti ki, amikor az absztrakt szintaxisfát/parsolási fát parsolja. Ennek használatát biztonságosnak tekintik. Ez egy módja annak, hogy csak parsolási időben végezzék a feladatukat, és utána ne hívódjanak meg. Sokszor a funkcionális nyelvű programok is értelmezőben futnak, ami néha csak ezt az egyetlen módszert hagyja meg. A Lisp volt az első nyelv, ami ilyen makrókat használt, ezért ezt a fajta makrót Lisp-szerű makróknak nevezik. C++-ban sablon metaprogramozással hasonló eredmény érhető el.

Mindkét esetben a munka inkább fordítási időben lesz elvégezve. A C stílusú makrók és a Lisp-szerű makrók, valamint C++ sablon metaprogramozás között az, hogy a C típusú makrók kifejtése szövegszerkesztés, a kijelölt számítások nem végződnek el, és az optimalizálás a fordítóra marad. Továbbá a C makrók nem támogatják sem az iterációt, sem a rekurziót, így nem alkotnak Turing-teljes nyelvet. Ezzel szemben a többi megengedi bármilyen típusú számítás elvégzését.

A többi optimalizálással szemben nem lehet a projekt befejezése előtt előrejelezni, hogy melyiknek lesz a legnagyobb hatása.

Automata és kézi optimalizálás

Az optimalizálás automatizálható vagy végezhetik programozók is. A legnagyobb javulást a globális optimalizációtól lehet várni, helyi javítások csak korlátozott eredményt hoznak; és rendszerint egy másik algoritmus bevezetéséről van szó.

Egészében véve kézi optimalizálást végeznek, mivel ez túl bonyolult ahhoz, hogy automatizálják. Ekkor a programozóknak vagy a rendszergazdának explicit meg kell változtatniuk a kódot, hogy a teljes rendszer jobban működhessen. Habár hatékonyabb, a kézi optimalizáció költségesebb, mint az automatizált. Mivel sok paraméter hat a program működésére, az optimalizációs tér nagy. Metaheurisztikákat és gépi tanulást használnak ennek egyszerűsítésére.

Néha a programozók azt hiszik, hogy tudják, hol vannak a palacknyakak, de az intuíció gyakran téves eredményt ad. A kevéssé fontos részek optimalizálása kevés eredményt hoz. Profilozók és performanciaelemzők segítenek megtalálni ezeket az erőforrás-igényes részeket.

Ha találtak egy palacknyakat, akkor újragondolják az itt használt algoritmust. Az a gyakoribb eset, hogy a helyzetre szabott algoritmus jobb, mint az általános. Például egy hosszú lista rendezésére a quicksort algoritmust használják, ami az egyik leggyorsabb. De ha tudunk valamit a listáról, akkor ezt az információt felhasználhatjuk ahhoz, hogy hatékonyabban rendezhessük.

Miután a programozó kiválasztotta a megfelelő algoritmust, megkezdődhet a kódoptimalizáció. A ciklusok kigöngyölíthetők, hogy csökkenjen az adminisztráció, bár ezzel lassulhat is a kód, mivel túlnőheti a cache-t. Az adattípusok mérete minimalizálható; ahol lehetséges, egész aritmetika használható lebegőpontos helyett, és így tovább.

Egyes palacknyakakat nem lehet az algoritmus megváltoztatásával kezelni, mivel azok a nyelv korlátai miatt keletkeztek. Emiatt meg kell gondolni, hogy nem lenne-e célszerűbb egyes részeket egy másik nyelven újraalkotni. Például egy Python program a sebességkritikus részeket C-ben; egy C program Assemblyben tartalmazhatja; továbbá egy D program használhat egyes helyeken inline assemblert. Ez azért működhet, mivel a program futásidejének 90%-át a kód 10%-án tölti. Ha ezeket a részeket sikerül meghatározni, és kijavítani, akkor a program is javul.

A kézi optimalizálás mellékhatása, hogy rontja a kód olvashatóságát. Ezért minden optimalizációs lépést gondosan dokumentálni kell, és meg kell határozni hatását a későbbi fejlesztésre. Ugyan a következő verzió készülhet a nem optimalizált verzió alapján, de akkor az újabb optimalizálás bonyolultabb lesz, illetve ugyanazokat a változtatásokat kell újra és újra elvégezni.

A fordítóprogramok rendszerint tartalmaznak optimalizálókat. Ezek számos esetben az adott gépre tudják szabni a programot. Többnyire csak a fordítóprogramba épített optimalizálót használják. A programtranszformátorok elfogadják egy-egy probléma leírását, és nyelvspecifikus eszközökkel javítanak a kódon.

Egyes magas szintű nyelvek (Eiffel, Esterel) köztes nyelv használatával optimalizálják a programot.

Az elosztott programozás a teljes rendszer optimalizálását célozza a feladatkiosztás optimalizálásával. A jobban terhelt processzorokról feladatokat helyeznek át kevésbé terhelt processzorokra.

Mikor optimalizáljunk

Az optimalizáció rendszerint rontja az olvashatóságot és olyan kódot ad hozzá, aminek egyetlen célja, hogy a program valamilyen szempontból jobb legyen. Ez megnehezíti a karbantartást és a hibakeresést. Emiatt gyakran a fejlesztési szakasz végén végzik. Donald Knuth szerint a fejlesztési idő 97%-ában nem lenne szabad a kis hatásfokú javításokkal törődni. Nem kell feladni a lehetőségeket a 3%-kal kapcsolatban sem. Évekkel később Tony Hoare-nak tulajdonította azt a kijelentését, hogy a korai optimalizáció minden rossz forrása és Hoare is azt állította, hogy ezt ő mondta.

A mérnöki tudományokban bármikor könnyen elérhető 12%-os javulás, amit sosem szabad szem elől téveszteni. Hasonló nézőpontot kellene a szoftverfejlesztésben is megvalósítani.

A korai optimalizáció azt a helyzetet írja le, amikor már a tervezés során figyelembe veszik az optimalizációt. Ez egy kevésbé tiszta tervet eredményez, ami miatt kevésbé lehet észrevenni, ha egy kódrészlet hibás; mivel az optimalizáció miatt a kód bonyolultabb, és a programozó figyelmét elvonja az optimalizáció.

Amdahl törvényét figyelembe kell venni, amikor eldöntik, hogy egy kódszakaszt optimalizáljanak-e: az optimalizáció hatása attól függ, hogy mennyi időt tölt ott a vezérlés. Ezt azonban performanciaelemzés nélkül nem lehet eldönteni. Egy jobb megközelítés, ha profilozás után döntenek. Gyakran könnyebb optimalizálni egy elegáns és egyszerű tervet, és a profilozás gyakran olyan váratlan problémákat fed fel, amire nem gondoltak volna, ha korai optimalizációt használnak.

Gyakorlatban azonban már a tervnek számolnia kell a performanciával, azonban a programozóknak ezt kiegyensúlyozottan kell kezelniük.

A modern operációs rendszerek és fordítók hatékonysága nem mindig hagy teret az alkalmazás optimalizálására; az elérhető eredmények nem mutatkoznak. Például a cache-elés nem segít, ha az operációs rendszer mindent cache-el. A hardver fejlődése miatt is elavulhatnak bizonyos optimalizálási módszerek. Mindazonáltal idő hiányában és további hibalehetőségek miatt gyakran nem veszik ki, illetve cserélik le a semmi eredményt nem hozó, nehezen érthető kódot.

Rászánt idő

Az optimalizálásra szánt idő szintén kényes kérdés lehet.

Az optimalizálással előállított kód nem tartalmaz újabb képességeket, de bevezethet újabb hibákat, ronthatja a kód olvashatóságát és karbantarthatóságát. A kézi optimalizációnak ára van, így fontos tudni, hogy a befektetés megtérül-e.

Az automatizált optimalizálót is optimalizálni kell, meg kell találni a megfelelő beállításokat. Az így készült kód fordítása rendszerint tovább tart, de ez csak a nagyobb programoknál probléma.

A végrehajtási sebesség javításában kulcsszerep jut a tárgykóddal együtt végrehajtódó futásidejű fordítókomponensnek, ha a fordítás futás közben történik.

Források

• Jon Bentley: Writing Efficient Programs, ISBN 0-13-970251-2.
• Donald Knuth: The Art of Computer Programming

Fordítás

Ez a szócikk részben vagy egészben a Program optimization című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.