kiinnostaisi tietää miten optimoida koodia mahd. nopeaksi,
mitä komentoja tulisi välttää ja mitä muotoa suosisi?
- linkit olisi jees.
[hehe pien typo otsikossa :D ]
Koodin nopeus riippuu ensisijaisesti siitä, mitä se tekee, ei niinkään siitä, miten se täsmälleen tehdään. Otetaan esimerkiksi taulukon lajitteleminen: vaikka kuinka optimaalisesti kirjoittaisi kuplalajittelun, se ei pärjää isoilla taulukoilla edes huonosti kirjoitetulle pikalajittelulle.
Ensimmäinen asia on tyhmyyksien välttäminen. Ei pidä kopioida dataa, kun ei tarvitse, ja ei pidä turhaan kutsua funktioita moneen kertaan, jos tulokset jo tiedetään.
// Tässä funktiolle luodaan kopio tekstistä: void tulosta(std::string s); // Tässä taas funktiolle annetaan viittaus (osoitin) tekstiin, tulostuksen tapauksessa nopeus voi hyvinkin lähes kaksinkertaistua: void tulosta(std::string const& s);
if (strlen(a) < strlen(c)) {
if (strlen(b) < strlen(c)) {
printf("c on pisin!\n");
} else if (strlen(b) < strlen(a)) {
printf("b on lyhin!\n");
}
// jatka itse muutkin vaihtoehdot perään...
}
// Entä jos kutsuttaisiinkin strlen-funktiota vain kerran kullekin? Näin: (C:tä)
int len_a, len_b, len_c;
len_a = strlen(a);
len_c = strlen(c);
if (len_a < len_c) {
len_b = strlen(b);
if (len_b < len_c) {
printf("c on pisin!\n");
} else if (len_b < len_a) {
printf("b on lyhin!\n");
}
}C:stä tai muista tämän alueen kielistä puhuttaessa kannattaa huomioida kääntäjän potentiaali. Kun kääntäjän käskee optimoida koodia käännösvaiheessa, se osaa oikein kirjoitetusta ohjelmasta huomioida kohdat, joissa jokin arvo voidaan säilyttää tehokkaasti rekistereissä tai jokin funktiokutsu voidaan jättää välistä. Erilaiset l33t-koodarien "optimointikikat" jopa voivat hidastavat ohjelmaa, koska ne usein rikkovat näitä hyviä koodaustapoja ja estävät kääntäjää optimoimasta koodia vielä paremmin.
Yksi tärkeä asia tähän liittyen on const-avainsanan käyttö olennaisissa kohdissa. Kun esimerkiksi luokan vertailuoperaattoriin liitetään const, kääntäjä tietää, ettei se muuta vertailtavia olioita, jolloin tuloskin säilyy samana, kun vertailu tehdään monta kertaa peräkkäin. Sama pätee muihinkin funktioihin. C99 toi tullessaan restrict-avainsanan, joka on kääntäjän kannalta vielä tätäkin tärkeämpi: sen avulla kääntäjä tietää, että tiettyä muistialuetta käytetään vain tietyn osoittimen avulla, jolloin sen ei tarvitse huomioida, että jonkin toisen osoittimen käyttö muuttaisi ensimmäisen muistia.
No, eipä sen enempää nyt. Pääasia on, että ohjelmoi mahdollisimman järkevästi, selkeästi ja oikeaoppisesti ja miettii logiikan tarkkaan. Liika optimointi usein on enemmän haitaksi kuin hyödyksi, ja siihen kannattaa ruveta vasta, kun on jonkin työkalun avulla selvittänyt, missä kohti ohjelma aikansa tuhlaa.
Metabolix kirjoitti:
Yksi tärkeä asia tähän liittyen on
const-avainsanan käyttö olennaisissa kohdissa. Kun esimerkiksi luokan vertailuoperaattoriin liitetäänconst, kääntäjä tietää, ettei se muuta vertailtavia olioita, jolloin tuloskin säilyy samana, kun vertailu tehdään monta kertaa peräkkäin. Sama pätee muihinkin funktioihin.
Voisitko antaa jonkin konkreettisen esimerkin, jossa jokin käytössä oleva kääntäjä (mielellään GCC) tuottaisi nopeampaa koodia const-sanaa käyttämällä kuin ilman?
Olen jossain määrin kuullut puheita tällaisesta mahdollisuudesta, mutta en koskaan nähnyt käytännössä mitään vaikutusta. Esimerkiksi tuossa vertailuhommassa jos kääntäjä ei näe vertailufunktion määritystä niin se ei tietenkään voi jättää toista kutsua pois (koska vertailufunktiolla voi olla mitä sivuvaikutuksia tahansa), mutta jos se näkee sen niin se pystynee ilman const-sanaakin päättelemään, onko toinen suoritus tarpeen vai ei.
Ps. nopeaan koodiin liittyen mielenkiintoisena löytönä tuli tänään (eilen) vastaan glibc:n strlenin toteutus. Jännää miten noinkin yksinkertaisesta asiasta saa ison purkan kun oikein optimoi. Tuo kyllä osoittautuikin pitkällä merkkijonolla jopa n. 2,5 kertaa niin nopeaksi kuin vastaava OpenBSD:n toteutus.
Sisuaski kirjoitti:
Voisitko antaa jonkin konkreettisen esimerkin, jossa jokin käytössä oleva kääntäjä (mielellään GCC) tuottaisi nopeampaa koodia const-sanaa käyttämällä kuin ilman?
Olen jossain määrin kuullut puheita tällaisesta mahdollisuudesta, mutta en koskaan nähnyt käytännössä mitään vaikutusta. Esimerkiksi tuossa vertailuhommassa jos kääntäjä ei näe vertailufunktion määritystä niin se ei tietenkään voi jättää toista kutsua pois (koska vertailufunktiolla voi olla mitä sivuvaikutuksia tahansa), mutta jos se näkee sen niin se pystynee ilman const-sanaakin päättelemään, onko toinen suoritus tarpeen vai ei.
En kokeillut, mutta tämän luulisi toimivan kuvatulla tavalla:
class luokka{
public:
inline const int funktio(void) const{
return 42 ^ 123 * 123546 + 53435378 % 436754267546 & 7;
}
};
void funktio2(void){
int i = 0;
luokka x;
while(i > x.funktio()) i++;
}ville-v kirjoitti:
En kokeillut, mutta tämän luulisi toimivan kuvatulla tavalla:
No toimii edellä kuvaamallani tavalla siinä mielessä että kääntäjä laskee valmiiksi tuon funktion palautusarvon riippumatta siitä onko siinä constia vai ei, ja assemblykäännös on kummassakin tapauksessa tällainen:
_Z8funktio2v: rep ret
Eli ei ihan sitä mitä kaivattiin...
Miten constant tuon paluuarvon täytyy olla? Saako olla eri paluuarvo eri luokan instansseille? Eli mahtaako seuraava ylipäätään olla laillinen:
class luokka{
int huima;
public:
luokka (int alustusluku) {
huima = alustusluku;
}
inline const int funktio(void) const{
return 42 ^ 123 * huima + 53435378 % 436754267546 & 7;
}
};
void funktio2(void){
int i = 0;
luokka x;
while(i > x.funktio()) i++;
}Sisuaski kirjoitti:
assemblykäännös on kummassakin tapauksessa tällainen:
_Z8funktio2v: rep ret
Ompa kumma käännös :O Mitä toikin varsinaisesti tekee?
Sisuaski kirjoitti:
Eli ei ihan sitä mitä kaivattiin...
Muuttuja on muuttuja, vakio on vakio. Kääntäjälle se tarkoittaa, että muuttujaa on pystyttävä muuttamaan, jolloin kääntäjä varaa sille tarvittavan määrän muistia. const-muuttujaa ei tarvitse (voi) muuttaa, jolloin se voidaan kirjoittaa suoraan osaksi konekielistä käskyjä. Havainnollistetaampas:
int muuttuja = 123; funktio(muuttuja + 100); ------------------ MOV EAX, DWORD PTR [00402000] ; Muuttujan arvo EAX-rekisteriin ADD EAX, 100 ; Lisätään siihen 100 PUSH EAX ; ja annetaan parametriksi funktiolle CALL funktio const vakio = 123; funktio(vakio + 100); ------------------ PUSH 223 ; Fiksu kääntäjä osaa laskea etukäteen: vakio + 100 CALL funktio
Näin siis esimerkiksi. Nykypäivänä kääntäjät saattaa osata ennakoida muuttujan arvon jossain kohtaa koodia, jolloin ne (toivottavasti) käsittelee sitä kuin vakiota. Funktioiden kanssa kai samalla tavalla? (Ok, en tiedä mitä se const siinä funktion määrittelyssä sitten tekee :D Varmaan jotain samantapaista)
Deffi kirjoitti:
Ompa kumma käännös :O Mitä toikin varsinaisesti tekee?
En ole varma mitä varten tuo rep on tuossa mutta käytännössä ei tee yhtään mitään vaan palautuu suoraan funktiosta.
Et maininnut, millä kääntäjällä nuo esimerkkikoodisi olet kääntänyt, mutta ainakaan GCC ei tuolla tavalla toimi, vaan laskee tuon 223 käännösaikana riippumatta onko toisena osana muuttuja vai vakio.
Sisuaski kirjoitti:
Deffi kirjoitti:
Ompa kumma käännös :O Mitä toikin varsinaisesti tekee?
En ole varma mitä varten tuo rep on tuossa mutta käytännössä ei tee yhtään mitään vaan palautuu suoraan funktiosta.
Tein siis hienon funktion, joka odottaa haluamani ajan, ja kääntäjäsi optimoi sen olemattomiin. Miten ihmeessä se saa olettaa, että loppukäyttäjällä on nykyaikainen kone, joka ei ruksuta silmukassa minuuttikaupalla?
Grez kirjoitti:
Miten constant tuon paluuarvon täytyy olla? Saako olla eri paluuarvo eri luokan instansseille?
Ensimmäinen const määrittelee, että arvo muunnetaan vakioksi palautettaessa, jos se sitä ei vielä ole. Toinen ilmoittaa, ettei funktio muuta jäsenmuuttujia, eli että
const luokka x; x.funktio();
on sallittu. Esimerkkikoodisi on siis sallittu, ja ajaa saman asian kuin ilman consteja.
ville-v kirjoitti:
Tein siis hienon funktion, joka odottaa haluamani ajan, ja kääntäjäsi optimoi sen olemattomiin. Miten ihmeessä se saa olettaa, että loppukäyttäjällä on nykyaikainen kone, joka ei ruksuta silmukassa minuuttikaupalla?
Ei se kyllä mitään odota kun whilen ehto on aina epätosi.
EDIT: Ja Grezin esimerkkikoodi ei ole sallittu siltä osin, että luokalta puuttu oletusrakentaja (ja kääntäjähän ei sitä automaattisesti tee, koska on kuitenkin määritelty toinen rakentaja).
ville-v kirjoitti:
Tein siis hienon funktion, joka odottaa haluamani ajan, ja kääntäjäsi optimoi sen olemattomiin.
Ja hyvä niin. Odottaminen tehdään mainitsemalla asiasta käyttöjärjestelmälle asianmukaisella funktiolla (Sleep, usleep, SDL_Delay ...) eikä millään tuollaisella viritelmällä.
Vastauksena alkuperäiseen kysymykseen voisi kai sanoa, että kannattaa ensin keskittyä siihen, että ohjelma toimii oikein ja koodi on selkeää. Silloin touhu on järkevällä pohjalla ja yleiseksi optimoinniksi riittää lähinnä se, ettei tee turhia asioita. Yksinkertaisia turhia asioita ovat esimerkiksi ylimääräinen tietojen kopiointi ja samojen tehtävien tekeminen moneen kertaan.
Todellinen optimointi vaatii yleensä aika vankkaa tietoa ratkaistavasta ongelmasta ja ratkaisuympäristöstä. Se ei ole vaikeaa, vaan vieläkin vaikeampaa. Tämän lisäksi ei pidä luulla, vaan pitää tehdä mittauksia.
C++ ei ole oikein hyvä noissa const-asioissa. Ongelma on siinä, että const ei useinkaan takaa paljon mitään, joten kääntäjä ei voi sen pohjalta paljon mitään tehdäkään. Const-määrittely on melkeinpä vain vahva vihje toivotusta käsittelytavasta koodin lukijalle.
D-kielessä tätä const-kysymystä on yritetty tosissaan ratkaista. Kylläpä siellä sitten onkin sellainen tilanne, että yhteisöstä osa kannattaa kehiteltyjä aika monimutkaisia määreitä yhtä innokkaasti kuin toinen osa niitä vastustaa, ja osa on ihan vaan pihalla.
Jos ajatellaan sitä, kumpi kutsutavoista
void tulosta(std::string s); void tulosta(std::string const& s)
on tehokkaampi/nopeampi, niin asia voi olla monimutkaisempi kuin luulisi. Ja sen sijaan, että luulee, kannattaa tehdä mittauksia.
Jos parametrina välitettävä olio on pieni tai helppo kopioida, niin ensimmäinen on nopeampi; jos taas olio on suuri tai kallis kopioda, niin sitten toinen. Eipä siinä sitten tarvitse enää tietääkään, kuin että minkä kokoinen on pieni tai suuri ja milloin kopiointi on helppoa tai kallista: siis, mittaa.
Lisäkiemura tulee vielä siitä, että jos funktio joka tapauksessa kopioi argumenttina saadun olion, ensimmäinen kutsutapa olisi sillekin usein nopeampi. Mutta älä luule: mittaa.
Ja jos funktio nimensä mukaisesti tosiaan tulostaa argumenttinsa, voi olla yks hailee, miten argumentti välitetään. I/O kun voi olla joka tapauksessa kiljoona kertaa hitaampaa kuin mikään parametrinvälitys. Ja jos haluaa tietää, paljonko kiljoona on, kannattaa mitata. Jokohan alkaa tällä toistolla mennä perille. ;-P
Const-määreet toimivat usein paremmin funktioiden paikallisilla muuttujilla (siis oikeastaan vakioilla) kuin funktioiden parametrien viittauksissa, koska niissä kääntäjä voi paremmin "nähdä" koko tilanteen ja tehdä sen mukaiset optimoinnit. Takeita ei ole, mutta jos asialla on väliä, muista tuo aiemminkin esiintynyt m-verbi. Siis tyyliin
size_t const len_a = strlen(a);
size_t const len_c = strlen(c);
if (len_a < len_c) {
size_t const len_b = strlen(b);
if (len_b < len_c) {
printf("c on pisin!\n");
} else if (len_b < len_a) {
printf("b on lyhin!\n");
}
}Kiitos koolle asiasta. Lisään tähän sen toivotun linkin Intelin ja AMD:n prossujen käyttäjille.
http://www.agner.org/optimize/
lainaus:
Note that these manuals are not for beginners.
Kopeekka kirjoitti:
Ennen kuin kukaan rupeaa muuttamaan koodistaan kaikkia bool-tyyppejä chareiksi (kuten tuolla olevassa C++-oppaassa neuvotaan), niin huomauttaisin että tämänkin oppaan kanssa kanssa kannattaa muistaa koo:n neuvo eli aina testata itse sen sijaan että tekee olettamuksia.
Aloin selaamaan tuota opasta ja aika alkuvaiheessa siellä sanotaan, että kääntäjä ei uskalla olettaa, että bool-arvot olisivat valmiiksi alustettu nollaan tai ykköseen, joten se tekee ylimääräisiä tarkistuksia loogisilla operaattoreilla nopeampien bittioperaattorien sijaan, mikä ei ainakaan GCC:llä näytä pitävän paikkansa.
Edit: Tajusin vasta, että tuosta virheellisestä väitteestä huolimatta kyseinen osio saattaa kyllä silti sisältää ihan asiaakin, sillä esim.
if (a!=b || c!=d)
tuottaa usein hitaampaa koodia kuin
if ((a-b) | (c-d))
Sisuaski kirjoitti:
esim.
if (a!=b || c!=d)tuottaa usein hitaampaa koodia kuin
if ((a-b) | (c-d))
Erisuuruuden muuttaminen xor-operaatioksi ratkaisee ongelman, lopputulos on sama kuin char-versiossa. Erisuuruuden kanssa sekä | että || tuottavat ylimääräisen hyppykäskyn ennen jälkimmäisen ehdon testaamista. Erikoista on, että jälkimmäisen vertailun arvot kuitenkin luetaan rekistereihin jo ennen hyppykäskyä. Ilman optimointilippua muut vaihtoehdot tuottavat vastaavan koodin ja ainoastaan || tuottaa ylimääräisen hyppykäskyn, kuten sen tarkkaan ottaen pitääkin.
Sisuaski kirjoitti:
Aloin selaamaan tuota opasta ja aika alkuvaiheessa siellä sanotaan, että kääntäjä ei uskalla olettaa, että bool-arvot olisivat valmiiksi alustettu nollaan tai ykköseen, joten se tekee ylimääräisiä tarkistuksia loogisilla operaattoreilla nopeampien bittioperaattorien sijaan, mikä ei ainakaan GCC:llä näytä pitävän paikkansa.
En halua nyt erityisesti puolustaa tämän oppaan kirjoittajaa, mutta luulen hänen tietojensa perustuvan hieman syvempään testaamiseen kuin vain jonkinlaiseen arvaukseen siitä, mitä "GCC:llä näyttää pitävän paikkaansa". Aina voi toki olla, että tieto on vanhentunutta tai muuten väärää. Jos oppaassa on virheitä, niihin sopivia korjauksia voi tietenkin lähettää kirjoittajalle.
Jos näitä asioita kerran pitää mitata, niin potentiaaliset mittaajat voisivat opetella miten mittauksia suoritetaan ja miten niistä raportoidaan, että tieto erottuu mutusta. Jätetään se harjoitustehtäväksi ahkerimmille.
Kopeekka kirjoitti:
En halua nyt erityisesti puolustaa tämän oppaan kirjoittajaa, mutta luulen hänen tietojensa perustuvan hieman syvempään testaamiseen kuin vain jonkinlaiseen arvaukseen siitä, mitä "GCC:llä näyttää pitävän paikkaansa".
Pahoitteluni että käyttämäni näyttää-sana oli liian epämääräinen ymmärttettäväksesi.
Tarkoitin tässä, että olen todennut GCC-4.3.2:n tuottamasta assemblykoodista asian tilan, eli kyseessä ei ollut mikään arvaus. Tässä ei siis kirjoittajan ammattitaidolla eikä auktoriteetilla ole mitään merkitystä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.