Ystävämme Reaktorilla ovat tehneet jo muutamia niin sanottuja fast track -ohjelmointitehtäviä, jotka mahdollistavat nopean reitin rekrytointiin. Ainakin jos ratkaisu tehtävään on raadin mukaan riittävän hyvä. Kolmas ohjelmointitehtävä, jossa piti ratkaista OutRun pelin näennäisen ajoradan Reaktorilaisten tykätyin reitti, nousi Goforella yhdessä lounaskeskustelussa esiin. Lounaan ajan pohdittiin mahdollisia ratkaisualgoritmeja ja seuraavana aamuna kaikilla oli kirkkaana mielessä optimaalinen algoritmi tehtävän ratkaisuun. Enää eivät puuttuneet kuin toteutukset.
Ratkaisuja lähdettiin tekemään eri ohjelmointikielillä, kukin kielellä mikä tuntui itselle sopivimmalta. Ensimmäisissä ratkaisuissa ei kiinnitetty hirveästi huomiota ratkaisun suorituskykyyn, vaan tehtiin valitulla ohjelmointikielellä suhteellisen elegantti ratkaisu. Ongelmaksi muodostui kuitenkin se, että kaikilla oli valittuna sama algoritmi. Algoritmi joka käy tiedostoa läpi alusta alkaen ja muodostaa joka riville aina uudet maksimisummat edellisen rivin reittivaihtoehdoista. Lopulta viimeiseltä riviltä ei tarvitse kuin etsiä maksimiarvo, joka on samalla tehtävän ratkaisu. Goforen algoritmi eroaa Reaktorin esittämästä malliratkaisusta sillä, että tiedostoa luetaan eri suunnasta. Alusta lukeminen mahdollistaa tehokkaan lukujen streamauksen ratkaisijalle. Ratkaisut näyttivät siis hyvin samankaltaisilta, ohjelmointikielestä riippumatta. Goforen toteutukset selvisivät esimerkkitehtävästä muutamassa kymmenessä millisekunnissa. Mutta tämä ei riittänyt Goforelaisille.
Reaktorilla ei ilmeisesti olla kovin hyviä pelaamaan OutRunia, sillä heidän pisin ajosuorituksensa oli tehtävän mukaan 99 esteen väistöä pitkä. Goforella OutRun on hieman paremmin hallussa ja lähdimme ratkomaan tehtävää 30 000 estettä sisältävällä ajoradalla. Reittitiedostolla, jonka koko on noin 1,3GB. Nyt nähdään kenen ratkaisu toimii ja kenen ei. Hyvin nopeasti kävi selväksi, että mitä isommaksi tiedosto kasvaa, sitä kriittisempää on sen tehokas lukeminen. Itse algoritmissa suoritettavat vertailuoperaatiot ovat niin kevyitä, että on tärkeämpää saada syötettyä lukuja nopeasti sisään kuin optimoida itse algoritmia. Tästä seurasi se, että ratkaisut joissa lopulta luettiin tiedostoa tavuina sisään rakentamalla niistä tehokkaasti kokonaislukuja olivat kertaluokkaa nopeampia kuin ratkaisut, joissa luettiin tiedostoa rivi kerrallaan ja muunnettiin rivi sen jälkeen listaksi numeroita.
Kuinka sitten kävi? Ennakkosuosikki C++ piti pintansa loppuun asti ja Teemu ei edes joutunut kaivamaan viimeisiä optimointitemppuja työkalupakistaan, vaikka Jarkon Java 7 -toteutus, joka hyödynsi käyttöjärjestelmätasolla tehtävää tiedoston muistimäppäystä, hätyyttelikin suorituskyvyllään. Jaakko vastasi taas melkoisella uroteolla puristamalla JavaScriptistä irti kaiken mitä ikinä lähti, ja koodi todellakin näyttää siltä. Ei juuri JavaScriptiksi tunnistaisi, vaikka sitä se on. Tapio lähestyi ongelmaa enemmän funktionaalisesta näkökulmasta ja hyödynsi korkeamman tason rajapintoja Java 8 virroilla ja Scalalla pitäen ratkaisut elegantteina, mutta hävisi auttamatta suorituskyvyssä muille. Tekijän nimen takaa löytyy linkki toteutuksen lähdekoodiin.
| Tekijä | Suoritusaika | Toteutuskieli | Huomioita |
|---|---|---|---|
| Teemu Erkkola | 3.31s | C++ | gcc 4.8+ |
| <a href="https://gist.github.com/jhyoty/bf5985cf3ec5646b606f#file-outrunsolver-java"Jarkko Hyöty | 3.68s | Java 7 | nio memory mapped file |
| Jaakko Salonen | 8.51s | JavaScript (node.js) | uh uh uh |
| Tapio Rautonen | 49.63s | Java 8 | Stream API |
| Tapio Rautonen | 80.65s | Scala | funktionaalinen |
Virallisena testikoneena toimi Dell Latitude E6330 Intelin i7 prosessorilla, 8GB keskusmuistilla ja SSD kiintolevyllä. Suoritusajat on otettu keskiarvona kymmenestä ajokerrasta linuxin time komennolla. Ajossa siis huomioidaan esimerkiksi virtuaalikoneen käynnistyminen ja muut alustustoimenpiteet.
Gofore käytti omaa ratageneraattoria, joka ei perustu Reaktorin käyttämään ratageneraattoriin muuten kuin arvauksella siitä miten se oli tehty. Jos haluat testata identtisellä radalla millä Goforen testit on ajettu, tarvitset siihen Java 8:n ja seuraavat komennot:
$ wget https://gist.githubusercontent.com/trautonen/9595293/raw/TrackGenerator.java $ javac TrackGenerator.java $ java TrackGenerator /tmp/track.txt 30000 1395145926030
$ g++ -v
gcc version 4.8.1 (Ubuntu/Linaro 4.8.1-10ubuntu9
$ wget https://gist.githubusercontent.com/bzar/9531212/raw/reaktor_outrun.cpp
$ g++ -Ofast -fomit-frame-pointer -funroll-loops -o reaktor_outrun reaktor_outrun.cpp
$ time for i in {1..10}; do ./reaktor_outrun /tmp/track.txt; done
real 0m33.075s
$ java -version
Java(TM) SE Runtime Environment (build 1.7.0_51-b13)
Java HotSpot(TM) 64-Bit Server VM (build 24.51-b03, mixed mode)
$ wget https://gist.githubusercontent.com/jhyoty/bf5985cf3ec5646b606f/raw/OutrunSolver.java
$ javac OutrunSolver.java
$ time for i in {1..10}; do java OutrunSolver /tmp/track.txt; done
real 0m36.770s
$ node -v
v0.10.25
$ wget http://gist.githubusercontent.com/jsalonen/9547603/raw/outrun.js
$ time for i in {1..10}; do node outrun.js /tmp/track.txt; done
real 1m25.128s
$ java -version
Java(TM) SE Runtime Environment (build 1.8.0-b132)
Java HotSpot(TM) 64-Bit Server VM (build 25.0-b70, mixed mode)
$ wget https://gist.githubusercontent.com/trautonen/9595293/raw/OutRunStream.java
$ javac OutRunStream.java
$ time for i in {1..10}; do java OutRunStream /tmp/track.txt; done
real 8m16.309s
$ scala -version
Scala code runner version 2.10.4 -- Copyright 2002-2013, LAMP/EPFL
$ wget https://gist.githubusercontent.com/trautonen/9617334/raw/OutRunScala.scala
$ scalac OutRunScala.scala
$ time for i in {1..10}; do scala OutRunScala /tmp/track.txt; done
real 13m26.548s
Ongelmaa voi lähestyä monella tavalla ja 80 / 20 sääntö pätee yleensä myös ohjelmointitehtävissä. 20 prosenttia ajankäytöstä kuluu siihen että saadaan 80 prosenttinen ratkaisu. Me käytimme suurimman osan ajasta sen viimeisen 20 prosentin tavoitteluun. Lähtökohtaisesti JavaScript ei ollut omimmillaan esitetyn ongelman ratkaisuun, mutta kun tarpeeksi vääntää ruuvia niin ohjelmointikielestä riippumatta ratkaisuista saatiin puristettua huomattavan tehokkaita. On kuitenkin syytä kysyä, oliko käytetty aika ja ratkaisun selkeys enää sen arvoisia? Kun työn maksajana on joku ulkopuolinen taho, täytyy valittu ratkaisu olla järkevästi perusteltu. Ohjelmistoprojekteissa näitä valintoja pitää tehdä ohjelmointikielten, teknologioiden ja monien muiden asioiden suhteen. Pysähdytäänkö riittävän usein miettimään onko valittu ratkaisu mielekäs tai mitenkään perusteltavissa?
Ennenaikainen suorityskykyoptimointi menee käytännössä aina pieleen ja aiheuttaa enemmän ongelmia kuin hyötyä. Näin totesi Donald Knuth jo vuonna 1974.
”We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.” (Knuth, Donald. Structured Programming with go to Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268.)
Suorituskyvyn nimissä tehtävillä valinnoilla saattaa olla myös vakavampia seurauksia. Heartbleed bugi OpenSSL-salauskirjastossa voidaan osittain laskea tämäntyyppisestä valinnasta johtuvaksi ongelmaksi. Jos muistinvaraus OpenSSL-kirjastossa olisi tehty ilman optimointeja (http://article.gmane.org/gmane.os.openbsd.misc/211963) olisi sitä ajava sovellus kaatunut, eikä vuotanut hyökkääjälle kirjaston käyttämää muistiavaruutta. Lähtökohtaisesti hyvää ja järkevästi koodattua ohjelmakoodia ei kannata optimoida ennen kuin siinä havaitaan suorituskykyongelma. Optimointia ei myöskään saa tehdä ilman riittävää sovelluksen profilointia, sillä usein ongelma piilee jossain muualla kuin yksittäisessä koodirivissä mikä osuu kehittäjän silmään. Suorituskyvyn pullonkaulat on selvitettävä ja toteutetaan ratkaisut, joissa mahdollisimman pienillä muutoksilla saadaan mahdollisimman suuret hyödyt.
P.S. Onko sinulla oma ratkaisu joka on elegantimpi tai tehokkaampi kuin mitä me Goforella saimme aikaan? Liitä oma ratkaisusi esimerkiksi Gist-linkkinä kommentteihin.
