- Liittynyt
- 22.10.2016
- Viestejä
- 11 811
Optimoinneista ja monisäikeistyksestä:
Koodasinpa tuossa jonkin aikaa sitten todennäköisyyslaskurin World In Flames-lautapelin ilmataisteluun. Kyseisen pelin säännöt ovat melko monimutkaiset ja edes yhden ilmataistelun todennäköisyyksien laskeminen ei ole helppo ongelma. Ensimmäinen versioni tuosta todennäköisyyslaskurista oli tehty puhtaalla rekursiolla ja se teki turha työtä samojen asioiden laskemiseen uudestaan kun rekursioitavaa funktiota kutsuttiin välillä uudestaan samoilla parametreilla, kun samaan paikkaan tultiin eri haaran kautta. Tiesin toteutuksen epäoptimaaliseksi, mutta kun koodi ajautui ensin kokeilemillani pienillä syötteillä (muutama konelaivue/puoli) tarpeeksi nopeasti, en aluksi jaksanut optimoida.
Suurensin vähän syötettäni, ja suuremmilla syötteillä koodi kävi vähän hitaaksi. Optimoin hiukan tietorakenteita, että dataa ei tarvinnut kopioida uudestaan aina funktiota kutsuessa, ja vältyin erään huonosti optimoidun kirjastorutiinin kutsumiselta, ja sain koodini nopeutettua n. kaksinkertaiseksi.
Sitten lautapelissämme tuli vastaan tilanne, että seuraavan viikon sessiolla oli ehkä edessä paljon isompia ilmataisteluita, ja halusin laskea niiden todennäköisyyksiä. Näillä isommilla syötteellä koodi ajautui aivan liian hitaasti, ja sain sen ajautumaan jopa puolitoista tuntia.
n. minuutin ajan harkitsin, että monisäikeistän koodin. Monisäikeistys pitäisi kuitenkin tehdä vain ylimmällä tasolla (jokainen taso rekursioi eli kutsuu itseään 5-15 kertaa riippuen syötteistä, eli tuolla saisi 5-15 säiettä), koska säikeiden määrä räjähtäisi käsille, ja ohjelma kaatuisi resurssien puutteeseen (muisti loppuisi ja käyttiksen rajat säikeiden määrälle tulisi vastaan) jos joka tasolla loisi uusia säikeitä , ja liiallisten säikeiden luominen myös vaan hidastaisi. Joten koodiin olisi pitänyt lisätä ylimääräinen parametri jolla erotella ylin taso.
.. kunnes totesin, että paljon fiksumpaa on nyt vaan tehdä se algoritmillinen optimointi ja olla laskematta samoja tuloksia turhaan moneen kertaan. Lisäsin koodiin hajautustaulupohjaisen softavälimuistin, jonne talletetaan jo lasketut osatulokset. Tein näitä varten oman hajautustaulutietorakenteen, jossa otetaan funktion parametreistä hajautusarvo, ja indeksoidaan sillä taulukkoa, joka sisältää osoittimet laskettuihin tuloksiin. Noin 19 miljoonalla(256*256*17*17) mahdollisella hajautusarvolla sain tehtyä hajautusfunktion jolla millään laillisella järkevän kokoisella (max 8+8+8+8 lentolaivuetta) syötteellä törmäyksiä ei voi tulla, jolloin ei tarvi mitään ylimääräistä monimutkaistavaa logiikkaa niistä selviämiseen.
Lopputuloksena koodi, jossa varattiin n. 300 megaa muistia sitä hajautustaulua varten(mutta suurinta osaa tästä muistista ei koskaan käytetä, se voi osoittaa käyttiksen nollasivuun eikä siihen oikeasti kulu 300 megaa muistia), mutta ohjelman ajoaika ennen puolitoista tuntia kestäneellä syötteellä lyheni n. 20 millisekuntiin.
Eli koodi siis tällä isolla syötteellä nopeutui tästä optimoinnista n. 16 MILJOONAA kertaa nopeammaksi.
Tämän koko optimoinnin miettimiseen ja koodaamiseen meni alustavasti puoli tuntia, sen ekan version bugien korjaamiseen muutamaa päivää myöhemmin n. toiset puoli tuntia (siellä ekassa versiossa oli sittenkin hajautusfunktiossa törmäyksiä, ja lisäksi se turhaan antoi välillä eri hajautusarvoa samalle syötteelle kun se tuli sisään eri muodossa, johtaen tiettyjen syötteiden laskemiseen useaan kertaan).
Tämän jälkeen en kokenut enää tarpeellisesti monisäikeistää koodia, koska optimoitu versio on varmasti tarpeeksi nopea. Mutta tämä softavälimuisti myös tarkoittaa sitä, että enää nuo rekursio-funktiokutsut eivät olekaan matemaattisen puhtaita funkltionaalisia funktiota, vaan niillä on sivuvaikutuksia, ne kaikki ronkkivat tuota hajautustaulukkoa. Ja tämä tarkoittaa sitä, että alkuperäisen koodin olisi voinut rinnakkaistaa triviaalisti ilman lukituksia säikeiden välillä, mutta tätä optimoitua koodia ei saisi rinnakkaistaa ilman, että koodiin lisäisi lukituksia tuon hajautustaulukon käyttämisen ympärille.
Johtopäätökset:
Tässä tuli taas hyvin esille tämä koodin optimoinnin oleellinen pointti: Kertaluokalla on hyvin paljon väliä, Ylivoimaisesti tärkein asia koodin optimoinnissa/järkevännopeuksisen koodin kirjoittamisessa on järkevän algoritmin käyttö.
Ja kun koodi optimoidaan muuten järkevästi, rinnakkaistaminen voi samalla muuttua sekä vaikeammaksi että turhemmaksi. Sillä, montaako säiettä koodi "osaa käyttää" on vain hyvin vähän korrelaatiota sen kanssa, kuinka hyvin softa on oikeasti optimoitu.
Jos olisin vaan monisäikeistänyt alkuperäisen puhtaan rekursiivisen algoritmini, olisin saanut sen n. 5-15-kertaisen nopeutuksen, eli koodini suurimmalla syötteelläni olisi ollut n. 1-3 miljoonaa kertaa hitaampi, kuin mitä algoritmillisesti optimoimani koodi oli. Koodin määrä ja koodaukseen käytetty vaiva olisi molemmissa ollut samaa luokkaa.
Koodasinpa tuossa jonkin aikaa sitten todennäköisyyslaskurin World In Flames-lautapelin ilmataisteluun. Kyseisen pelin säännöt ovat melko monimutkaiset ja edes yhden ilmataistelun todennäköisyyksien laskeminen ei ole helppo ongelma. Ensimmäinen versioni tuosta todennäköisyyslaskurista oli tehty puhtaalla rekursiolla ja se teki turha työtä samojen asioiden laskemiseen uudestaan kun rekursioitavaa funktiota kutsuttiin välillä uudestaan samoilla parametreilla, kun samaan paikkaan tultiin eri haaran kautta. Tiesin toteutuksen epäoptimaaliseksi, mutta kun koodi ajautui ensin kokeilemillani pienillä syötteillä (muutama konelaivue/puoli) tarpeeksi nopeasti, en aluksi jaksanut optimoida.
Suurensin vähän syötettäni, ja suuremmilla syötteillä koodi kävi vähän hitaaksi. Optimoin hiukan tietorakenteita, että dataa ei tarvinnut kopioida uudestaan aina funktiota kutsuessa, ja vältyin erään huonosti optimoidun kirjastorutiinin kutsumiselta, ja sain koodini nopeutettua n. kaksinkertaiseksi.
Sitten lautapelissämme tuli vastaan tilanne, että seuraavan viikon sessiolla oli ehkä edessä paljon isompia ilmataisteluita, ja halusin laskea niiden todennäköisyyksiä. Näillä isommilla syötteellä koodi ajautui aivan liian hitaasti, ja sain sen ajautumaan jopa puolitoista tuntia.
n. minuutin ajan harkitsin, että monisäikeistän koodin. Monisäikeistys pitäisi kuitenkin tehdä vain ylimmällä tasolla (jokainen taso rekursioi eli kutsuu itseään 5-15 kertaa riippuen syötteistä, eli tuolla saisi 5-15 säiettä), koska säikeiden määrä räjähtäisi käsille, ja ohjelma kaatuisi resurssien puutteeseen (muisti loppuisi ja käyttiksen rajat säikeiden määrälle tulisi vastaan) jos joka tasolla loisi uusia säikeitä , ja liiallisten säikeiden luominen myös vaan hidastaisi. Joten koodiin olisi pitänyt lisätä ylimääräinen parametri jolla erotella ylin taso.
.. kunnes totesin, että paljon fiksumpaa on nyt vaan tehdä se algoritmillinen optimointi ja olla laskematta samoja tuloksia turhaan moneen kertaan. Lisäsin koodiin hajautustaulupohjaisen softavälimuistin, jonne talletetaan jo lasketut osatulokset. Tein näitä varten oman hajautustaulutietorakenteen, jossa otetaan funktion parametreistä hajautusarvo, ja indeksoidaan sillä taulukkoa, joka sisältää osoittimet laskettuihin tuloksiin. Noin 19 miljoonalla(256*256*17*17) mahdollisella hajautusarvolla sain tehtyä hajautusfunktion jolla millään laillisella järkevän kokoisella (max 8+8+8+8 lentolaivuetta) syötteellä törmäyksiä ei voi tulla, jolloin ei tarvi mitään ylimääräistä monimutkaistavaa logiikkaa niistä selviämiseen.
Lopputuloksena koodi, jossa varattiin n. 300 megaa muistia sitä hajautustaulua varten(mutta suurinta osaa tästä muistista ei koskaan käytetä, se voi osoittaa käyttiksen nollasivuun eikä siihen oikeasti kulu 300 megaa muistia), mutta ohjelman ajoaika ennen puolitoista tuntia kestäneellä syötteellä lyheni n. 20 millisekuntiin.
Eli koodi siis tällä isolla syötteellä nopeutui tästä optimoinnista n. 16 MILJOONAA kertaa nopeammaksi.
Tämän koko optimoinnin miettimiseen ja koodaamiseen meni alustavasti puoli tuntia, sen ekan version bugien korjaamiseen muutamaa päivää myöhemmin n. toiset puoli tuntia (siellä ekassa versiossa oli sittenkin hajautusfunktiossa törmäyksiä, ja lisäksi se turhaan antoi välillä eri hajautusarvoa samalle syötteelle kun se tuli sisään eri muodossa, johtaen tiettyjen syötteiden laskemiseen useaan kertaan).
Tämän jälkeen en kokenut enää tarpeellisesti monisäikeistää koodia, koska optimoitu versio on varmasti tarpeeksi nopea. Mutta tämä softavälimuisti myös tarkoittaa sitä, että enää nuo rekursio-funktiokutsut eivät olekaan matemaattisen puhtaita funkltionaalisia funktiota, vaan niillä on sivuvaikutuksia, ne kaikki ronkkivat tuota hajautustaulukkoa. Ja tämä tarkoittaa sitä, että alkuperäisen koodin olisi voinut rinnakkaistaa triviaalisti ilman lukituksia säikeiden välillä, mutta tätä optimoitua koodia ei saisi rinnakkaistaa ilman, että koodiin lisäisi lukituksia tuon hajautustaulukon käyttämisen ympärille.
Johtopäätökset:
Tässä tuli taas hyvin esille tämä koodin optimoinnin oleellinen pointti: Kertaluokalla on hyvin paljon väliä, Ylivoimaisesti tärkein asia koodin optimoinnissa/järkevännopeuksisen koodin kirjoittamisessa on järkevän algoritmin käyttö.
Ja kun koodi optimoidaan muuten järkevästi, rinnakkaistaminen voi samalla muuttua sekä vaikeammaksi että turhemmaksi. Sillä, montaako säiettä koodi "osaa käyttää" on vain hyvin vähän korrelaatiota sen kanssa, kuinka hyvin softa on oikeasti optimoitu.
Jos olisin vaan monisäikeistänyt alkuperäisen puhtaan rekursiivisen algoritmini, olisin saanut sen n. 5-15-kertaisen nopeutuksen, eli koodini suurimmalla syötteelläni olisi ollut n. 1-3 miljoonaa kertaa hitaampi, kuin mitä algoritmillisesti optimoimani koodi oli. Koodin määrä ja koodaukseen käytetty vaiva olisi molemmissa ollut samaa luokkaa.
Viimeksi muokattu:
