Keskustelu: Yleinen keskustelu: Koodin optimointi

Olen vuosia tehnyt pikkuohjelmia ja pikkasen isompiakin projekteja. Joskus aloitin tekemään isoa ohjelmaa mutta siltin helppoa mutta alan tutkimusta vaatii paljon (menetin lähdekoodin kun varmuuskopioimage otti ja kuoli); luin Microsoft VisualBasic6 Ohjelmoijan käsikirjasta että kannattaa optimoida koodia välttämällä tiettyä kirjotustapaa, mutta loppujen lopuksi siinä ei kerrottu _minkälaista_ koodia pitää välttää joten haluaisin että joku tekisi oppaan jossa kerrotaan kädestä pitäen ja mahdollisimman yksinkertaisesti millaista koodia täytyy/kannattaa välttää ja millä korvata se.

Ei kai tähän oppaita tarvita. Sinun pitää vain ajaa ohjelmaa ja katsoa, missä kohtaa ohjelma toimii liian hitaasti tai syö liikaa muistia. Jos ohjelma toimii hitaammallakin algoritmilla riittävän sujuvasti, ei sitä kohtaa koodissa kannata ruveta muuttamaan. Yleisesti ottaen sisäkkäisiä silmukoita kannattaa välttää, sillä kokemuksesta voin sanoa, että joskus bugin etsiminen niistä voi olla hankalaa.

Mutta on tähän kuitenkin olemassa jonkinlaista opastusta ja tekniikkaakin. Luin yks päivä wikipediasta hyvän artikkelijoukon optimoinnista.
http://en.wikipedia.org/wiki/Optimization_(computer_science)
Seuraa vain artikkelin tarjoamia linkkejä.

Näin meille kerrottiin:

AMK-opetus kirjoitti:

Nykyään koneissa on niin paljon tehoa ja muistia, ettei mistään tarvitse huolehtia.

Voisi kyllä itsekkin lueskellä vähän optimoinista. Duunissa juurikaan kerkee pohtimaan muuta kuin luettavuutta ja uudelleenkäytettävyyttä.

Optimointia kuitenkin kannattaa tehdä eniten suunnittelussa. UML-kaavoiden yksinkertaistamista. Uudelleenkäytettävien komponenttien hyödyntäminen.

Ensinnäkin on hyvä miettiä, mitä kannattaa optimoida. Käytetyllä algoritmilla on usein ratkaiseva vaikutus ohjelman nopeuteen. Jos ohjelman perusrunko on hidas, jonkin yksittäisen kohdan nopeuttaminen ei juuri auta.

Esimerkiksi käy nimen etsiminen puhelinluettelosta. Jos nimeä etsii lukemalla kaikki nimet läpi alusta alkaen, Virtasen etsiminen kestää esim. 20 tuntia. Tässä ei paljon lohduta, vaikka pystyisi käymään yhden sivun läpi puolet nopeammin, koska aikaa kuluisi silloinkin 10 tuntia. Mutta jos käyttää hyväkseen luettelon aakkosjärjestystä (toinen algoritmi), etsintään kuluukin vain 20 sekuntia.

Optimointi ei siis tapahdu yleensä niin, että koodiin tehdään tiettyjä kaavamaisia muutoksia, joiden jälkeen se on nopea. Yleispäteviä ohjeita optimointiin on vaikea antaa, mutta kyllä asioista pääsee jyvälle ajan myötä, jos harrastaa ohjelmointia.

AMK-opetus kirjoitti:

Nykyään koneissa on niin paljon tehoa ja muistia, ettei mistään tarvitse huolehtia.

Riippuu ihan siitä, mitä tekee. On paljon ongelmia, joiden ratkaisuun ei uusimpienkaan koneiden teho tai muisti riitä. Esimerkiksi käy vaikkapa Rubikin kuutio, asemia on aivan liian paljon. Kun sitten yritetään päästä mahdollisimman lähelle optimaalista ratkaisua, on todella tärkeää käyttää tehokkaita algoritmeja ja optimoida kaikki yksityiskohdat huolellisesti.

Yhdessä kirjassa muuten sanottiin, että kun koneiden kapasiteetti kasvaa, oikean algoritmin valinta on entistäkin tärkeämpää. Väite on toisaalta ihan looginen. Esimerkiksi pienellä datamäärällä O(n²) saattaa olla riittävän nopea. Mutta kun tietokoneilta vaaditaan yhä enemmän ja n kasvaa yhä suuremmaksi, algoritmi ei ole enää riittävän nopea, vaan täytyy keskiä parempi.

Putkapostien ratkominen ja erilaisiin algoritmeihin tutustuminen on todella hyödyllistä.

Annan tästä esimerkin suoraan kirjasta kopioituna jonka toista ratkaisumallia en tajua alkuunkaan.

Tälläinen koodi on erittäin hidas:

For i = 0 To 10
   picIcon(i).Left = picPallete.Left
Next i

Uudelleenkirjoitettuna koodi on paljon nopeampi:

picLeft = picPallete.Left
For i = 0 To 10
   picIcon(i).Left = picLeft
Next i

Samoin koodi, kuten tämä:
Do Until EOF(F)
   Line Input #F, nextLine
   Text1.Text = Text1.Text + nextLine
Loop

Mod. Edit. Kooditagit.

Oletan, että VB:ssä objektit ovat muistiosoittimia. Tällöin tuossa on kyse vain kääntäjän optimointikyvystä. Jos kääntäjä on huono, ensimmäisessä koodissa haetaan joka kierroksella tietystä muistipaikasta picPallete-olion osoite, sitten lisätään tähän vakioarvo, että saadaan Left-jäsenen osoite, ja lopuksi haetaan tästä osoitteesta itse arvo (picPallete.Left). Voi olla, että parempikin kääntäjä joutuu tekemään tämän näin hitaasti, jos on mitenkään mahdollista, että picPallete olisi sama kuin jokin picIcon(i). Toisessa koodissa taas otetaan tämä arvo talteen varmasti omaan paikkaansa, jolloin sen hakeminen joka kerta käy vain yhdellä muistiviittauksella. Kolmas koodi on oma esimerkkinsä luultavasti aivan vastaavasta aiheesta, siinä ei vain kerrota oikeaa (tai väärää) ratkaisua.

Kaikkiaan asiana siis on selvästikin se, että koodista kannattaa tehdä sellaista, että kääntäjä saa sen mahdollisimman hyvin optimoitua. Tässä auttavat toisinaan sopivat väliaikaismuuttujat tai joissakin kielissä (kuten C:ssä) tietyt avainsanat, C:ssä esimerkiksi const, joka takaa, ettei arvo muutu, ja C99:n uusi tulokas restrict, joka takaa, ettei tietyn osoittimen osoittamalle alueelle kirjoiteta muista osoittimista käsin. Pieniä optimointikikkoja on varmasti lukemattomia, ja monet niistä ovat nykyprosessoreista puhuttaessa niin erikoisia, ettei niitä voi järjellä päätellä.

Tuollaisen optimoinnin ajatuksena on siis, että jos jonkin asian voi laskea silmukan ulkopuolella, sitä on turha laskea joka kerta silmukassa uudestaan. Eli tuon mukaan kuvaolion leveyden hakeminen on huomattavasti hitaampaa kuin suoran muuttujan käyttäminen (johon leveys haetaan kerran ennen silmukan alkua). Ajatus on ihan viisas, mutta monessa tapauksessa tuollainen optimointi on merkityksetöntä.

rautamiekka kirjoitti:

Samoin koodi, kuten tämä:
Do Until EOF(F)
   Line Input #F, nextLine
   Text1.Text = Text1.Text + nextLine
Loop

Tässä luultavasti käy niin, että merkkijonojen jatkuva ketjuttaminen aiheuttaa liikaa kopiointia. En tunne VB:n sisuksia, joten arvailen. Ketjutus on siis merkkijonojen peräkkäin asettamista.

Kun merkkijonot a ja b ketjutetaan, pitää ohjelmassa varata uusi muistialue, jonka koko on tarpeeksi iso pitämään a:n ja b:n ketjutus sisällään. Sen jälkeen a ja b kopiodaan siihen yhdeksi merkkijonoksi.

Jos tämä tehdään silmukassa useita kertoja peräkkäin, niin että jokaisella kerralla ketjutetaan samaan jonoon lisää tavaraa, siirtyy ketjun alussa oleva merkkijono paikasta toiseen lukuisia kertoja ihan turhaan.

Esimerkki. Olkoot ensimmäinen merkkijono "hirvi" ja toinen "peura". Kun nämä ketjutetaan, saadaan "hirvipeura". Molemmat piti kopioida kerran. Seuraavaksi tähän ketjutetaan "kettu", jolloin "hirvipeura" pitää taas kopioida kerran. Nyt siis "hirvi" on jo kopioitu kaksi kertaa, ja olemme vasta kolmannessa alkiossa. Helppohan se on nähdä, että jos alkioita on 10 miljoonaa, "hirvi" joutuu vaeltamaan paikasta toiseen 10 miljoonaa miinus yksi kertaa. Jalat siinä väsyy.

Siksipä kielessä on jokin valmis tapa yhdistää monta merkkijonoa kerralla. Tehokas tapa laittaisi ensimmäisen merkkijonon "hirvi" heti paikkaan, jossa sen lopulta pitää olla, kun koko massaketjutus on valmis. Näin sitä ei tarvitse kopioda kuin kerran, mikä säästää huomattavasti aikaa.

Tämä kopionti ym. tapahtuu itse suoritettavassa koodissa, eikä näy suoraan lähdekoodista, jos asiaa ei tiedä. Tämän matalan tason vaikutuksen takia on hyvä opetella jonkin verran ainakin C:tä, tai jopa Asmia, että tajuaa, mitä se kone tekee siellä taustalla, kun käyttää valmiita muun kielen ominaisuuksia. Vaikka itse C-kieltä ei sitten käyttäisikään koskaan, oppi on hyväksi. (Toki tässä tapauksessa voi lisätä, etteivät kaikki kielet käytää samaa merkkijonototeutusta kuin C.)

Ennen C-opasta suosittelen kuitenkin tutustumista johonkin hyvään algoritmikirjaan, joka opettaa, mitä O()-merkintä tarkoittaa. Algoritmeja ei tarvitse itse oppia analysoimaan, mutta on suuri apu, kun osaa lukea ja ymmärtää, mitä muut sanovat, jos analysoivat. Sen jälkeen voi tutustua matalan tason asioihin, joilla valmiista algoritmista hiotaan vielä erikoistarkoitukseen parhaiten sopiva sporttiversio. Sitä taitoa eivät kaikki toki tarvitse, kuten yllä jo sanottiin.

Kyseessä on oikeastaan vain liuta asioita, jotka pitää tietää. Onneksi ne muodostavat sangen loogisen kokonaisuuden. Homma palautuu aina tähän: Ota selvää, mitä ajon aikana tapahtuu, kun sanot kielessä näin tai noin. Jos tehdään turhaa työtä, korjaa asia.

Joku on sanonut, että kaikki ohjelmointi on oikeastaan välitulosten tehokasta tallentamista. Se on ihan mukava ajatus, näin yleistyksenä. (enkuksi "caching")

VB6:ssa merkkijonojen liittäminen toisiinsa on nopeaa noin 64 kt saakka. Sen jälkeen VB:n oma sisäinen cache loppuu ja merkkijonojen yhdistäminen toisiinsa hidastuu huomattavasti ja muistia varataan ja vapautetaan jatkuvasti uudelleen ja uudelleen kun suurta merkkijonoa kasvattaa luupissa. Postitin tässä taannoin koodivinkkeihin merkkijonoluokan, joka korjaa tämän ongelman tarjoamalla joustavan välimuistin (ja ihan kokeilun vuoksi sisältää myös muita ominaisuuksia).

Kuitenkin, tiedoston lukemisen tekstilaatikkoon voi tehdä paljon tehokkaammin:

Text1.Text = Input(LOF(1), 1)

Lukee siis kerralla koko tiedoston muistiin. Toisaalta, tekstilaatikko pystyy pitämään sisällään vain 64 kt dataa, joten sinällään tämä ei ole vielä merkittävä optimointi. RichTextBox ei sekään pysty kovin montaa megaa ottamaan dataa hidastumatta merkittävästi.