Suomipelit – Optimointi

1. Yleistä #

Tarkoituksenani on tässä artikkelissa käydä läpi erilaisia optimointitekniikkoja yleisellä tasolla. Artikkelista olen pyrkinyt tekemään suhteellisen kattavan, jopa jossain suhteessa yleissivistävänkin. Kuten mitä tahansa artikkelia lukiessa, kannattaa suhtautua artikkelin koko sisältöön pienellä varauksella. Artikkeli on vain minun näkemykseni optimoinnista ja siihen liittyvistä vaaroista.

Optimoinnilla tarkoitetaan asioiden suorittamisen tehokkaammiksi muuttamista, tai mahdollisimman tehokkaan tavan löytämistä. Ohjelmoinnin alueella tällä tarkoitetaan yleisesti suorituskyvyn parantamista. Huomioitavaa on, että termiä voidaan käyttää myös muihin tarkoitusperiin (reitin optimointi, lineaarinen optimointi...). Tässä artikkelissa puhun kuitenkin pelkästään ohjelmakoodin suorituskyvyn optimoinnista.

2. Mitä optimoida? #

Ensimmäinen ja myös tärkein asia optimoinnissa on se, mihin optimointi kannattaa kohdistaa. Jos aikaa olisi loputtomasti, olisi varmaan järkevää optimoida jollain tasolla kaikki tuotettu ohjelmakoodi. Näin ei kuitenkaan ikinä tule tapahtumaan. Aina on jotain muuta tärkeämpää tehtävää, johon ajan voi laittaa: uudet ominaisuudet, bugejen korjaus, tuotteen viimeistely ja hiominen, tärkeämpien kohtien optimointi paremmin...

Optimointi kannattaa kohdistaa ohjelman aikakriittisiin kohtiin, koska suurin osa ohjelman suoritusajasta kuluu näissä kohdissa. Aikakriittisten kohtien löytäminen koodista vaatii pientä harjoittelua. Pääsääntönä voi pitää sitä, että mitä useammin koodirivi suoritetaan, sitä aikakriittisempi se on. Näinollen optimointia ei siis kannata kohdistaa esimerkiksi kerran ajettaviin koodiriveihin menun käynnistyksessä, vaan paljon mielummin vaikka koodiriveihin, jotka hoitavat yksittäisen pikselin ruudulle piirtämisen (joita suoritetaan miljardeja kertoja pelin aikana).

Aikakriittisten kohtien löytämiseen voi käyttää myös useiden ohjelmointiympäristöjen mukana tulevia profiler-apuohjelmia, jotka raportoivat yksittäisten funktioiden ja koodirivien viemät suoritusajat. Kun ohjelmaa suoritetaan, profileri laskee koodirivien suoritukseen kuluneet ajat ja kirjaa ne ylös. Suorituksen jälkeen ohjelmoija voi tutkailla profilerin tuottamaa tulostetta ja saada tietoa ohjelman aikakriittisistä osista. Näin optimoinnin kohdistaminen oikeisiin kohtiin helpottuu huomattavasti.

Yksi pahimmista virheistä optimoinnissa on ylioptimointi. Tällä termillä tarkoitan sitä, että ohjelmoija on liian innokas optimoimaan ohjelmakoodin kohtia joiden optimoinnista seuraa vain marginaalinen hyöty. Yleensä nämä optimointikohteet ovat ohjelman arkkitehtuurissa korkeammalla tasolla. Korkeamman tason koodin optimointi helposti rappauttaa ohjelman rakenteen ja tekee ohjelmasta vaikeasti ymmärrettävän. Ohjelman ylläpidettävyys ja muokattavuus kärsii. Varoittavia esimerkkejä tämän tason optimoinneista ovat esimerkiksi: rajapintojen ohittaminen ja karsiminen (suora käskytys on nopeampaa), julkiset atribuutit (pieni nopeuslisä), korkean tason luokasta ulospäin näkyvät rakenneoptimoinnit (vaikeuttavat luokan käytettävyyttä).

Optimointi kannattaa aina kohdistaa mahdollisimman alhaiselle tasolle ohjelmassa. Optimointi on onnistunut, jos luokan ulkopuolinen käyttäjä ei näe eroa optimoidussa ja optimoimattomassa luokassa.

3. Milloin optimoida? #

Lähes yhtä tärkeää kuin tietää mitä optimoida on tietää milloin optimoida. Olen usein kuullut sanonnan "kun sen kerran tekee kunnolla, ei siihen tarvitse enää palata". Valitettavasti tämä sanonta ei suoraan toimi optimoinnista puhuttaessa. Parempi sanonta olisikin "rakenna ensin kestävä perusta, perustan päälle talo, kalusta se ja viimekseksi koristele se, jos on tarvetta".

Uutta ohjelmakomponenttia kehittäessä on tärkeää saada aluksi ohjelmakomponentin rakenne valmiiksi. Tämän jälkeen on tärkeää, että komponentti toimii oikein. Näiden vaiheiden loppuun saamiseksi ohjelmoija tuottaa useita rivejä koodia ja käy tuottamaansa koodia useaan kertaan läpi ja korjailee tekemiään virheitä (bugeja). Vihdoin ohjelmakomponentti toimii "oikein" ja sitä voidaan testata toisien komponenttien kanssa yhdessä. Tässä vaiheessa löydetään vielä liuta uusia virheitä ja nämä korjataan.

Kehitysvaiheessa olevan ohjelmakomponentin koodin muutospaineet ovat suuret. Jos ohjelmakomponentti optimoidaan heti alussa, hankaloituu sen kehitys. Optimoitua koodia on huomattavasti hitaampaa tuottaa, hitaampaa muokata ja hitaampaa ymmärtää kuin optimoimatonta. Optimoidun koodin muuttaminen johtaa helposti optimointejen purkamiseen ja uusien optimointejen lisäämiseen. Tästä seuraa helposti virheitä ja näiden virheiden löytämiseen menee taas lisää aikaa.

Komponentti kannattaa optimoida kun se on valmis ja kunnolla testattu. Jos komponenttiin kohdistuvat muutospaineet ovat tämänkin jälkeen suuret, kannattaa optimointi kohdistaa komponenttiin vain siinä tapauksessa, jos siinä on osia, jotka ovat erittäin aikakriittisiä.

4. Optimointikohde: Tietorakenteet #

Tärkein optimointikohde on ohjelman tietorakenteet. Tietorakenneoptimoinneilla saavutetaan kaikista optimoinneista suurin hyöty pienimmällä vaivalla. Usein tietorakenneoptimoinnit eivät hankaloita koodin ymmärrettävyyttä lainkaan (olettaen, että lukija osaa käytetyt tietorakenteet). Valitettavasti näyttää siltä, että suurin ja ylivoimaisesti yleisin optimointivirhe on unohtaa tietorakenneoptimoinnit kokonaan ja keskittää voimavarat pelkästään algoritmien optimointeihin.

Yleisimpiä tietorakenteita ovat: taulukko, lista, jono, puu, pino, keko, hajautustaulu, hakemisto (indeksi)... Useimmista näistä on lukuisia variaatioita (esim. järjestetty taulukko, kahteen suuntaan linkitetty lista). Jokainen tietorakenne sopii tiettyyn tapaukseen muita rakenteita paremmin. Tärkeää on, että tietää tietorakenteiden heikkoudet ja vahvuudet, jotta osaa valita käyttötarkoitukseensa optimaalisimman tietorakenteen.

Tietorakenteita arvioidessa on tärkeää tietää kuinka aikaavievä mikäkin tietorakenteen operaatioista on. Yleisimpiä operaatioita ovat seuraavat:

[DEFTABLE]
[D]Alkion hakeminen[/D]
[E]- Ensimmäisen / viimeisen alkion hakeminen
- Suurimman / pienimmän alkion hakeminen
- Halutun alkion hakeminen (alkion tunnisteella)
- Alkion hakeminen halutusta indeksistä
- Alkioiden hakeminen tietyllä hakuehdolla[/E]
[D]Alkion lisääminen[/D]
[E]- Alkion lisääminen alkuun / loppuun
- Alkion lisääminen haluttuun paikkaan
- Alkion lisääminen sille kuuluvaan paikkaan (puut ja järjestetyt rakenteet)[/E]
[D]Alkion poistaminen[/D]
[E]- Ensimmäisen / viimeisen alkion poistaminen
- Suurimman / pienimmän alkion poistaminen
- Halutun alkion poistaminen (alkion tunnisteella)
- Alkion poistaminen halutusta indeksistä
- Alkioiden poistaminen tietyllä hakuehdolla[/E]
[/DEFTABLE]

Operaatiot jakautuvat siis kolmeen kategoriaan: haku, lisäys ja poisto. Näiden operaatioiden merkitys vaihtelee hieman tietorakenteittain. Esimerkiksi puurakenteissa, keossa ja järjestetyissä listoissa/taulukoissa alkio lisätään aina sille kuuluvaan paikkaan (avainarvon mukaan), kun taas järjestämättömissä listoissa/taulukoissa vaihtoehtoja on useampia (alkuun, loppuun, haluttuun paikkaan).

Kun tiedät mitä operaatioita tarvitset tietorakenteeltasi ja kuinka paljon kutakin käytät, voit analysoida ongelmaasi sopivia tietorakenteita ja valita niistä sopivimman.

Esimerkiksi tavallisella taulukolla alkion hakeminen indeksillä on erittäin nopeaa, mutta toisaalta taas alkion lisääminen ja poistaminen taulukon keskeltä on erittäin raskasta. Taulukkoa kannattaa siis käyttää silloin, kun indeksoituja hakuja tulee suhteessa paljon verrattuna lisäyksiin ja poistoihin.

Tietorakenteista löytyy huomattava määrä kirjallisuutta. Suosittelen jokaiselle ohjelmoijalle tutustumista tietorakenteisiin, vaikka optimointi ei itsessään edes kiinnostaisi.

5. Optimointikohde: Algoritmit #

Kun ohjelman tietorakenteet on optimoitu viimeisen päälle ja vielä tarvitaan lisää tehoja, on siirryttävä algoritmien optimointiin. Algoritmien optimoinnilla tarkoitan tässä alemman tason optimointeja, jotka eivät muuta tietorakenteita.

Tärkein asia algoritmioptimoinnissa on varmistaa, että käytössä on oikea algoritmi, joka sopii parhaiten haluttuun ongelmaan ja sopii käytetyille tietorakenteille. Esimerkiksi lajittelualgoritmeja on lukuisia erilaisia ja algoritmit vaihtelevat huomattavasti suorituskyvyltään. Parhaiden yleiskäyttöisten lajittelualgoritmien aikavaativuus on n * log(n), kun n on alkioiden määrä.

Tässä lyhyt oppimäärä aikavaativuusluokituksista. Aikavaativuudet on järjestetty nopeimmasta hitaimpaan:

1
Kiinteä aikavaativuus. Tähän aikavaativuusluokitukseen kuuluvat kaikki operaatiot jotka suoritetaan vain kerran (riippumatta alkioiden määrästä).

operaatio()

for (int a=100; a>0; a/=2) operaatio();

for (int a=0; a<100; a++) operaatio();

for (int a=0; a<100; a++)
   for (int b=100; b>0; b/=2) operaatio();

for (int a=0; a<100; a++)
   for (int b=0; b<100; b++) operaatio();

for (int a=0; a<100; a++)
   for (int b=0; b<100; b++)
      for (int c=0; c<100; c++) operaatio();

6. Operaation optimointi #

Vihdoinkin päästään aiheen ytimeen, eli siihen "oikeaan" optimointiin. Kun tietorakenteiden ja algoritmien valinta on helppoa yleisen oppikirjatietouden avulla, alemman tason operaatioiden optimointia voidaan kutsua jo omaksi taiteen lajikseen. Tämän tason optimoinneissa tärkeää on tietää miten laitteisto toimii, ja luoda ohjelmakoodia, joka hyödyntää mahdollisimman täydellisesti laitteiston antamat resurssit, välttäen laitteiston lukuisia pullonkauloja.


6.1 Mikä maksaa nykyisillä PC arkkitehtuureilla

Ennen kun aloitetaan optimointi on tärkeää tietää laitteiston rajoitteet, pullonkaulat ja operaatioiden aikavaativuudet.

Nykyiset PC:t ovat erittäin monimutkaisia laitteita. Prosessorin lisäksi koneesta löytyy huomattava määrä muitakin aikakriittisiä komponentteja: muistit, muistiväylä, muistiohjain, näytönohjain, AGP/PCI väylä. Nämä kaikki komponentit yhdessä vaikuttavat lopullisen ohjelmakoodin suoritusnopeuteen. Pullonkaulaksi sanotaan sitä komponenttia johon kohdistuu suurin rasitus, ja tämän komponentin takia muut komponentit joutuvat odottamaan. Esimerkiksi hitaan muistiväylän takia prosessori ei saa tarpeeksi tietoa käsiteltäväkseen ja joutuu odottelemaan tiedon saapumista. Hyvin optimoitu ohjelmakoodi rasittaa laitteistoa tasaisesti. Näin pullonkauloja ei pääse syntymään.


6.2 Käskyjen optimointi

Aloitetaan helpoimmasta, eli käskyjen optimoinneista. Vanhemmilla ja yksinkertaisimmilla arkkitehtuureilla prosessori oli usein ainut laitteiston pullonkaula. Tälläisen laitteen suorituskyvyn optimointi tapahtuu yksinkertaisesti optimoimalla käskyjä. Mitä vähemmän käskyjä ja mitä halvempia käskyjä suoritetaan, sitä nopemmin ohjelman suoritus etenee.

Analysoin peruskäskyjen suoritusaikoja koneellani, ja sain seuraavanlaisen tuloksen:

Yhteenlasku (+), vähennyslasku (-), shiftaukset (<< ja >>), bittioperaatiot (&, |...), vertailu (if): 1 aikayksikkö
Kertolasku (*): 2 aikayksikköä
Funktiokutsu yhdellä parametrilla ja paluuarvolla: 4 aikayksikköä
Int/float konversio (int(), float()): 8 aikayksikköä
Jakolasku (/), modulo (%): 20 aikayksikköä
Neliöjuuri (sqrt): 30 aikayksikköä (huomioi: liukuluvuilla suoritettu)
Sini (sin), kosini (cos): 80 aikayksikköä (huomioi: liukuluvuilla suoritettu)

Kannattaa huomioida, että tämä tulos on vain suuntaa-antava. On hyvin pitkälle prosessorin arkkitehtuurista kiinni, miten nopeasti se näistä käskyistä suoriutuu. Järjestys on kuitenkin hyvin pitkälle aina tämä. Kannattaa siis suosia listan alkupään halpoja käskyjä ja välttää loppupään huomattavasti kalliimpia käskyjä.

Yleisin optimointikohde ovat silmukat. Silmukan sisällä käskyt suoritetaan selvästi useammin kuin sen ulkopuolella. Usein on mahdollista siirtää osa laskennasta silmukasta ulos (tai ulompaan silmukkaan). Näin siirretyn käskyn aikavaativuusluokitus (kts. kappale 5) laskee.

Esimerkki:

Tässä alkuperäinen koodinpätkä. Suoritettavien operaatioiden määrä on seuraava:

Kertolasku: 400000000
Yhteenlasku: 400000000 * 2 (+ luupit: 400000000 + 20000)
Vertailu: 400000000 + 20000

int tulos=0;
for (int a=0; a<20000; a++)
{
   for (int b=0; b<20000; b++)
   {
      tulos+=a*20000+b;
   }
}

for (int a=0; a<20000; a++)
{
   const int a2k=a*20000;
   for (int b=0; b<20000; b++)
   {
      tulos+=a2k+b;
   }
}

int a2k=0;
for (int a=0; a<20000; a++)
{
   for (int b=0; b<20000; b++)
   {
      tulos+=a2k+b;
   }
   a2k+=20000;
}

const float PI = 3.14159265358f;

float sincos_lookup[64];

void initialize_lookups()
{
   for (int i=0; i<64; i++) sincos_lookup[i] = sin(PI / 2.0 * (float) i / 64.0);
}

float table_sin(unsigned int angle)
{
   // Rajoitetaan kulma välille 0-255 ( = täyskulma)
   angle &= 0xff;

   if (angle < 64)
   {
      return sincos_lookup[angle];
   }
   else if (angle < 128)
   {
      return sincos_lookup[127 - angle];
   }
   else if (angle < 192)
   {
      return -sincos_lookup[angle - 128];
   }
   else
   {
      return -sincos_lookup[255 - angle];
   }
}

float table_cos(unsigned int angle)
{
   // Rajoitetaan kulma välille 0-255 ( = täyskulma)
   angle &= 0xff;

   if (angle < 64)
   {
      return sincos_lookup[63 - angle];
   }
   else if (angle < 128)
   {
      return -sincos_lookup[angle - 64];
   }
   else if (angle < 192)
   {
      return -sincos_lookup[191 - angle];
   }
   else
   {
      return sincos_lookup[angle - 192];
   }
}

for (int y=0; y<TABLE_DIMENSION; y++)
{
   for (int x=0; x<TABLE_DIMENSION; x++)
   {
      tulos+=data[y*TABLE_DIMENSION+x];
   }
}

for (int x=0; x<TABLE_DIMENSION; x++)
{
   for (int y=0; y<TABLE_DIMENSION; y++)
   {
      tulos+=data[y*TABLE_DIMENSION+x];
   }
}

7. Yhteenveto #

Tärkeintä optimoinnissa on tietää mitä optimoida ja milloin. Optimointi kannattaa aloittaa vasta kun ohjelmakoodi on valmista. Aloita tietorakenteiden optimoinnista, ja siirry siitä alemmaksi ja alemmaksi. On tärkeää, että optimoinnit eivät rampauta ohjelman rakennetta, eivätkä ne näy ulospäin (vaikeuttaen käytettävyyttä). Hyvä optimoitu koodi suorittaa identtisesti sille annetun tehtävän verrattuna optimoimattomaan koodiin.

Optimointitekniikoita on lukuisia erilaisia. Minulle tärkeitä ovat olleet: algoritmien optimointi, aikakriittisyystasojen optimointi, käskyjen optimointi, lookup-taulukot, sekä muistioptimoinnit. Näillä optimoinneilla saadaan vältettyä laitteiston pullonkaulat, ja otettua siitä viimeisetkin tehot irti.