Optimalizálás (számítástechnika)

Az optimalizálás  egy rendszer módosítása a hatékonyság javítása érdekében. A rendszer lehet egyetlen számítógépes program , digitális eszköz, számítógépek gyűjteménye vagy akár egy teljes hálózat.

Bár az optimalizálás célja az optimális rendszer elérése, az optimalizálási folyamat során nem mindig sikerül igazán optimális rendszert elérni. Az optimalizált rendszer általában csak egy feladathoz vagy felhasználói csoporthoz optimális: valahol fontosabb lehet a program befejezéséhez szükséges idő csökkentése, akár több memória fogyasztása árán is; Azokban az alkalmazásokban, ahol a memória fontosabb, lassabb , kisebb memóriaigényű algoritmusok választhatók.

Sőt, gyakran nincs univerzális megoldás (minden esetben jól működik), ezért a mérnökök kompromisszumos megoldásokat  alkalmaznak csak a legfontosabb paraméterek optimalizálására. Ráadásul a teljesen optimális, tovább nem javítható program eléréséhez szükséges erőfeszítés szinte mindig meghaladja az ebből elérhető hasznot, így az optimalizálás általában a teljes optimalitás elérése előtt befejeződik. Szerencsére a legtöbb esetben még ezzel is észrevehető javulás érhető el.

Az optimalizálást óvatosan kell elvégezni. Először Tony Hoare mondta, majd Donald Knuth gyakran megismételte a híres mondást: „Az idő előtti optimalizálás minden rossz gyökere.” Nagyon fontos, hogy legyen egy hangos algoritmus és egy működő prototípus.

Alapok

Egyes feladatok gyakran hatékonyabban is elvégezhetők. Például egy C program , amely 1-től N-ig összegzi az összes egész számot:

int i , összeg = 0 ; for ( i = 1 ; i <= N ; i ++ ) összeg += i ;

Feltételezve, hogy itt nincs túlcsordulás , ez a kód a következőképpen írható át a megfelelő matematikai képlettel :

int összeg = ( N * ( N + 1 )) / 2 ;

Az "optimalizálás" kifejezés általában azt jelenti, hogy a rendszer megőrzi ugyanazt a funkciót. A redundáns funkciók eltávolításával azonban gyakran jelentős teljesítményjavulás érhető el. Például, ha feltételezzük, hogy a programnak nem kell 100-nál több elemet támogatnia a bemeneten , akkor a lassabb dinamikus kiosztás helyett statikus allokációt is használhatunk .

Kompromisszumok

Az optimalizálás elsősorban az egyszeri vagy ismételt végrehajtási időre, a memóriahasználatra, a lemezterületre, a sávszélességre vagy más erőforrásokra összpontosít. Ez általában kompromisszumokat igényel – az egyik paramétert a többiek rovására optimalizálják. Például valami szoftver gyorsítótár méretének növelése javítja a futásidejű teljesítményt, de növeli a memóriafogyasztást is. Egyéb gyakori kompromisszumok közé tartozik a kód átláthatósága és kifejezőképessége, ami szinte mindig az optimalizálás deaktiválása árán történik. Az összetett speciális algoritmusok több hibakeresési erőfeszítést igényelnek, és növelik a hibák esélyét .

Különféle területek

Az operációkutatásban az optimalizálás egy olyan függvény bemeneti értékeinek meghatározásának problémája, amelyre vonatkozóan maximális vagy minimális értéke van. Néha korlátozások vonatkoznak ezekre az értékekre, egy ilyen feladatot korlátozott optimalizálásnak neveznek .

A programozásban az optimalizálás általában a kód és fordítási beállításainak módosítását jelenti egy adott architektúrához a hatékonyabb szoftver létrehozása érdekében.

A tipikus problémáknak annyi lehetősége van, hogy a programozók általában csak egy "elég jó" megoldást engedhetnek meg.

Szűk keresztmetszetek

Az optimalizáláshoz meg kell találni egy szűk keresztmetszetet ( angolul  bottleneck - bottleneck): a kód kritikus részét, amely a szükséges erőforrás fő fogyasztója. A kód körülbelül 20%-ának javítása néha az eredmények 80%-ának megváltoztatásával jár, a Pareto-elv szerint . Az erőforrások (memória, fogantyúk stb.) kiszivárgása a programvégrehajtás sebességének csökkenéséhez is vezethet. Az ilyen szivárgások keresésére speciális hibakereső eszközöket, a szűk keresztmetszetek kimutatására pedig profilokat használnak .

Egy rendszer építészeti kialakítása különösen erősen befolyásolja annak teljesítményét. Az algoritmusválasztás minden más tervezési elemnél jobban befolyásolja a hatékonyságot . Az összetettebb algoritmusok és adatstruktúrák nagyszámú elemet jól kezelnek, míg az egyszerű algoritmusok kis adatmennyiséghez jók – az összetettebb algoritmus inicializálásának többletköltsége meghaladhatja a használat előnyeit.

Minél több memóriát használ egy program, annál gyorsabban fut. Például egy szűrőprogram általában beolvassa az egyes sorokat, szűri és közvetlenül adja ki azt a sort. Ezért csak egy sor tárolására használ memóriát, de teljesítménye általában nagyon gyenge. A teljesítmény nagymértékben javítható a teljes fájl elolvasásával, majd a szűrt eredmény írásával, azonban ez a módszer több memóriát használ. Az eredmények gyorsítótárazása is hatékony, de több memóriát igényel a használatához.

A programok CPU-idő szempontjából történő optimalizálásának legegyszerűbb technikái

A processzoridő-optimalizálás különösen fontos azoknál a számítási programoknál, amelyekben a matematikai számítások nagy szerepet játszanak. Íme néhány optimalizálási technika, amelyet a programozó használhat a program forráskódjának írásakor.

Adatobjektum inicializálása

Sok programban az adatobjektumok egy részét inicializálni kell , azaz kezdeti értékeket kell hozzárendelni. Az ilyen hozzárendelés vagy a program elején, vagy például a ciklus végén kerül végrehajtásra. Az objektum megfelelő inicializálása értékes CPU-időt takarít meg. Így például, ha tömbök inicializálásáról van szó, a hurok használata valószínűleg kevésbé hatékony, mint a tömb közvetlen hozzárendelésének deklarálása.

Aritmetikai műveletek programozása

Abban az esetben, ha a program idejének jelentős részét aritmetikai számítások töltik le, az aritmetikai (és logikai) kifejezések helyes programozásában jelentős tartalékok rejtőznek a program sebességének növelésére. Fontos, hogy a különböző aritmetikai műveletek sebessége jelentősen eltérjen. A legtöbb architektúrán a leggyorsabb műveletek az összeadás és a kivonás. A szorzás lassabb, ezt követi az osztás. Például a kifejezés értékének kiszámítása , ahol  egy konstans, lebegőpontos argumentumokhoz gyorsabban hajtódik végre a formában , ahol  a programfordítási szakaszban kiszámított konstans (valójában a lassú osztás művelet helyett a gyors szorzási művelet). Egész argumentum esetén gyorsabb a kifejezés kiszámítása a formában (a szorzási műveletet az összeadási művelet helyettesíti) vagy a balra eltolás művelettel (ami nem minden processzoron biztosít erősítést). Az ilyen optimalizációkat működési erőcsökkentésnek nevezzük . Az x86 család processzoraiban az egész argumentumok konstanssal való szorzata hatékonyan elvégezhető az assembler utasítások használatával , és az utasítások használata helyett : LEASHLADDMUL/IMUL

; Forrás operandus az EAX regiszterben ADD EAX , EAX ; szorzás 2-vel LEA EAX , [ EAX + 2 * EAX ] ; szorzás 3-mal SHL EAX , 2 ; szorzás 4-gyel LEA EAX , [ 4 * EAX ] ; egy másik módja a 4-gyel való szorzás megvalósításának LEA EAX , [ EAX + 4 * EAX ] ; szorzás 5-tel LEA EAX , [ EAX + 2 * EAX ] ; szorozni 6 -tal ADD EAX , EAX ; stb.

Az ilyen optimalizálás mikroarchitektúrás jellegű, és általában a programozó számára átláthatóan végzi el őket az optimalizáló fordító .

Viszonylag sok időt töltenek szubrutinok hívásával (paraméterek átadása a veremben , regiszterek és visszatérési címek mentése, másoláskonstruktorok meghívása). Ha az alprogram kevés műveletet tartalmaz, akkor beépíthető ( angolul inline ) - minden utasítása minden új hívási webhelyre másolódik (a soron belüli helyettesítésekre számos korlátozás vonatkozik: például az alprogram nem lehet rekurzív ). Ez kiküszöböli az alprogram meghívásának többletköltségét, de megnöveli a végrehajtható fájl méretét. Önmagában a futtatható fájl méretének növekedése nem jelentős, azonban bizonyos esetekben a végrehajtható kód túlléphet az utasítás- gyorsítótáron , ami a programvégrehajtás sebességének jelentős csökkenéséhez vezet. Ezért a modern optimalizáló fordítók általában rendelkeznek optimalizálási beállításokkal a kód méretéhez és a végrehajtási sebességhez.  

A teljesítmény az operandusok típusától is függ. Például a Turbo Pascal nyelvben az integer aritmetika megvalósítása miatt az összeadási művelet bizonyul a leglassabbnak az és típusú operandusok esetében Byte: ShortIntannak ellenére, hogy a változók egy bájtot foglalnak el, az aritmetikai műveletek két bájtos, ill. az ilyen típusú műveletek végrehajtása során a regiszterek felső bájtja nullázódik, és az operandus a memóriából a regiszter alsó bájtjába másolódik. Ez további időköltségekhez vezet.

Az aritmetikai kifejezések programozásakor olyan jelölési formát kell választani, hogy a "lassú" műveletek száma minimális legyen. Nézzünk egy ilyen példát. Legyen szükséges egy 4. fokú polinom kiszámítása:

Feltéve, hogy a fokszám kiszámítása az alap meghatározott számú szorzásával történik, könnyen megállapítható, hogy ez a kifejezés 10 szorzást ("lassú" műveletek) és 4 összeadást ("gyors" műveletek) tartalmaz. Ugyanez a kifejezés a következőképpen írható:

Ezt a jelölési formát Horner sémájának nevezik . Ennek a kifejezésnek 4 szorzása és 4 összeadása van. A műveletek teljes száma közel felére csökkent, és ennek megfelelően csökken a polinom számítási ideje is. Az ilyen optimalizálás algoritmikus, és általában nem hajtja végre automatikusan a fordító.

Ciklusok

A különböző típusú ciklusok végrehajtási ideje is eltérő. Egy számlálós ciklus és egy utófeltételes hurok végrehajtási ideje minden más azonossága mellett az előfeltételes ciklus egy kicsit tovább (kb. 20-30%-kal) hajtódik végre.

Beágyazott hurkok használatakor ne feledje, hogy az ilyen konstrukciók feldolgozására fordított CPU-idő függhet a beágyazott hurkok sorrendjétől. Például egy beágyazott ciklus egy Turbo Pascal számlálóval :

j := 1 - től 100000 - ig tegye k := 1 -től 1000 -ig tegye a := 1 -ig ; j := 1 - től 1000 -ig do k := 1 -től 100 000 - ig tegye a := 1 -ig ;

A bal oldali oszlopban lévő ciklus körülbelül 10%-kal tovább tart, mint a jobb oldali oszlopban.

Első ránézésre mind az első, mind a második esetben a hozzárendelés operátor 100 000 000 alkalommal kerül végrehajtásra, és a ráfordított időnek mindkét esetben azonosnak kell lennie. De nem az. Ez azzal magyarázható, hogy a hurok inicializálása (a fejléc processzora általi feldolgozása a számláló kezdeti és végső értékének, valamint a számláló növekedési lépésének meghatározása érdekében) időt vesz igénybe. Az első esetben a külső hurkot 1 alkalommal, a belsőt pedig 100 000-szer inicializálják, azaz összesen 100 001 inicializálást hajtanak végre. A második esetben csak 1001 ilyen inicializálás van.

Az elő- és utófeltételes beágyazott hurkok hasonlóan viselkednek. Arra a következtetésre juthatunk, hogy a beágyazott ciklusok programozása során lehetőség szerint a legkisebb ismétlésszámú ciklust tegyük a legkülsővé, a legtöbb ismétlésszámot a legbelsővé.

Ha a hurkok memóriaeléréseket tartalmaznak (általában tömbök feldolgozásakor), a gyorsítótár leghatékonyabb felhasználása és az adatok memóriából történő hardveres előhívása érdekében ( angol  Hardware Prefetch ) a memóriacímek megkerülésének sorrendjét a lehető legszekvenciálisabbnak kell lennie. Az ilyen optimalizálás klasszikus példája a beágyazott hurkok átrendezése mátrixszorzáskor .

Változó kódrészletek

Az invariáns kódrészletek optimalizálása szorosan összefügg az optimális ciklusprogramozás problémájával. A cikluson belül lehetnek olyan kifejezések, amelyek töredékei semmilyen módon nem függenek a ciklus vezérlőváltozójától. Ezeket invariáns kódrészleteknek nevezzük . A modern fordítók gyakran észlelik az ilyen töredékek jelenlétét, és automatikusan optimalizálják azokat. Ez nem mindig lehetséges, és néha egy program teljesítménye teljes mértékben attól függ, hogyan van programozva a hurok. Példaként vegyük a következő programrészletet ( Turbo Pascal nyelv ):

for i := 1 - n do kezdődik ... for k := 1 - p do for m := 1 - q do kezdődik a [ k , m ] := Sqrt ( x * k * m - i ) + Abs ( u * i - x * m + k ) ; b [ k , m ] := Sin ( x * k * i ) + Abs ( u * i * m + k ) ; vége ; ... am := 0 ; bm := 0 ; k := 1 - p do for m := 1 - q do kezdődik am : = am + a [ k , m ] / c [ k ] ; bm := bm + b [ k , m ] / c [ k ] ; vége ; vége ;

Itt az invariáns kódrészletek az összegzés Sin(x * k * i)az első ciklusban a változó felett, més a tömb elemmel való osztás művelete c[k]a második ciklusban m. A szinusz és a tömbelem értékei nem változnak a ciklusban a változó felett m, ezért az első esetben kiszámíthatja a szinusz értékét, és hozzárendelheti egy segédváltozóhoz, amelyet a kifejezésben használni fog. a hurkon belül. A második esetben az osztást a ciklus vége után hajthatja végre m. Így az időigényes aritmetikai műveletek száma jelentősen csökkenthető.

Lásd még

Irodalom

  • Bentley, John Louis . Hatékony programok írása. ISBN 0-13-970251-2
  • Donald Knuth . The Art of Computer Programming = The Art of Computer Programming. - 3. kiadás - M .: Williams , 2006. - V. 1: Alapvető algoritmusok. — 720 s. - ISBN 0-201-89683-4 .
  • Donald Knuth . The Art of Computer Programming = The Art of Computer Programming. - 3. kiadás - M. : Williams , 2007. - V. 2: Megszerzett algoritmusok. — 832 p. — ISBN 0-201-89684-2 .
  • Donald Knuth . The Art of Computer Programming = The Art of Computer Programming. - 2. kiadás — M .: Williams , 2007. — V. 3: Rendezés és keresés. — 824 p. - ISBN 0-201-89685-0 .
  • S. A. NEMNYUGIN Workshop // Turbo Pascal. - 2. kiadás - Szentpétervár. : Péter, 2007. - 268 p. - ISBN 5-94723-702-4 .
  • Chris Kaspersky . Programoptimalizálási technika. Hatékony memóriahasználat. - Szentpétervár. : BHV-Pétervár, 2003. - 464 p. — ISBN 5-94157-232-8 .

Linkek