Java vs C++ - nopeusero

[rale_pingviini]

Hei,

Kirjoittelin aikoinaan Java-kielellä ohjelman, jossa shakkiruudun hevonen hyppää kaikki ruudut lävitse, niin että se vierailee kussakin ruudussa täsmälleen vain yhden kerran. Nyt sain toteuttaa samaisen algoritmin C++-kielellä, jotta voisin vertaila nopeuseroa. Yllättäin Java-toteutus olikin huomattavasti nopeampi ja tämä takoittanee sitä, että C++ -koodia täytyisi pystyä jotenkin optimoimaan.

Jos kiinnostusta riittää, niin laitoin nuo filut jakoon ja niitä voi tutkailla. Ne ovat aika lyhyitä, joten terävä kaveri varmasti löytää nopeasti, mikä mättää. Itse veikkaisin, että olioiden säilöminen vektoriin ei varmaan ole se optimaalisin tapa. Eli ongelma voi piileä tässä koodin osassa:

Koodia: [Valitse]

void initializeValues(const int width, const int total, Squares & squares){
for (int i=0;i<(width+4);i++){
vector <Square> row;
for (int j=0;j<(width+4);j++){
Square square= Square();
square.setValue(total+1);
row.push_back(square);
}
squares.push_back(row);
}
for (int i=2;i<(width+2);i++)
for (int j=2;j<(width+2);j++)
squares[i][j].setValue(0);
}

Tuossa vielä kellottamani ajat:

Koodia: [Valitse]

time ./main 6 1 1
 -- 15 --  -- 34 --  -- 29 --  -- 22 --  -- 17 --  -- 36 --
 -- 30 --  -- 1 --  -- 16 --  -- 35 --  -- 28 --  -- 21 --
 -- 33 --  -- 14 --  -- 31 --  -- 20 --  -- 23 --  -- 18 --
 -- 8 --  -- 11 --  -- 2 --  -- 25 --  -- 4 --  -- 27 --
 -- 13 --  -- 32 --  -- 9 --  -- 6 --  -- 19 --  -- 24 --
 -- 10 --  -- 7 --  -- 12 --  -- 3 --  -- 26 --  -- 5 --
real 0m15.794s
user 0m15.777s
sys 0m0.000s


Koodia: [Valitse]

time java Lauta 6 1 1
 -- 15 --  -- 34 --  -- 29 --  -- 22 --  -- 17 --  -- 36 --
 -- 30 --  -- 1 --  -- 16 --  -- 35 --  -- 28 --  -- 21 --
 -- 33 --  -- 14 --  -- 31 --  -- 20 --  -- 23 --  -- 18 --
 -- 8 --  -- 11 --  -- 2 --  -- 25 --  -- 4 --  -- 27 --
 -- 13 --  -- 32 --  -- 9 --  -- 6 --  -- 19 --  -- 24 --
 -- 10 --  -- 7 --  -- 12 --  -- 3 --  -- 26 --  -- 5 --
real 0m2.843s
user 0m2.847s
sys 0m0.023s

Eli ero on varsin merkittävä. Täytynee alkaa tutkailemaan, missä vika voisi olla C++-toteutuksen osalta. Laitoin tiedostot tänne: https://www.dropbox.com/sh/obkbaqybk5pfleu/8P9MVETE-K Muuttujien nimet saattavat vaihdella, koska noiden toteusten välillä on vuosia. Viisi vuotta sitten olen näköjään saanut aikaan nohevampaa koodia :p Muuten toteutusten pitäisi olla kutakuinkin yhdenmukaisia, eli kokeillaan eri ruutuja samassa järjestyksessä.

[_Pete_]

Tuollaisenaa c++ versio kääntyy mutta kaatuu ajettaessa.

Koodia: [Valitse]

$ time ./main
terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_S_construct null not valid
Aborted (core dumped)

real    0m0.009s
user    0m0.000s
sys     0m0.004s

Kun lisäsin kääntäjävipuihin -O2 tulee tällaiset varoitukset:

Koodia: [Valitse]

$ make
g++ -Wall -O2   -c -o square.o square.cpp
g++ -Wall -O2   -c -o main.o main.cpp
main.cpp: In function ‘int startJumping(int, int, int, Squares&)’:
main.cpp:89:21: warning: ‘y2’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (squares[x2][y2].getValue()==0 && !skip){
                     ^
main.cpp:89:17: warning: ‘x2’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   if (squares[x2][y2].getValue()==0 && !skip){
                 ^
g++ -Wall -O2 -o main square.o main.o

+ sama kaatuminen ajettaessa.

[nm]

Virhe johtuu funktiosta Square::getPrevious():

Koodia: [Valitse]

int* Square::getPrevious(){

int table [2];
int* pointer;

table[0]=previousX;
table[1]=previousY;

pointer=table;

return pointer;

}
int table[2] on olemassa pinossa vain funktion suoritusaikana, mutta funktio palauttaa osoittimen siihen. Sitten kun kutsuvassa ohjelmassa yritetään käyttää taulukkoa, osoitin osoittaa olemattomaan sijaintiin (käytännössä juuri kutsuvan funktion pinon ulkopuolelle).

Ongelman voisi korjata muuttamalla int table[2]:n staattiseksi (static int table[2], jolloin se on jatkuvasti olemassa, mutta tämä on rumaa ja virhealtista. Tyylikkäämpää ja helpompaa olisi vain tehdä erilliset getPreviousX ja getPreviousY -funktiot, jotka palauttavat koordinaatit erikseen:

Koodia: [Valitse]

inline int Square::getPreviousX() {
    return this->previousX;
}

inline int Square::getPreviousY() {
    return this->previousY;
}


Tällä muutoksella, sekä käyttäen C++-kääntäjien kanssa optimointitasoa -O3, suoritusajat ovat koneellani:

G++ 4.6.3:     2.34 s
Clang++ 3.3:  2.17 s
OpenJDK 7:     1.98 s


Funktiokutsujen optimointi

C++-koodin ongelmana on Square-luokan funktioiden kutsumisesta aiheutuva overhead. Ilmeisesti Javassa se on huomattavasti vähäisempi, tai kääntäjä pystyy välttämään osan erillisistä metodikutsuista kopioimalla metodien koodin kutsuvaan ohjelmaan (inline). C++:ssa tämän saa aikaan siirtämällä koko Square-luokan koodin funktioineen samaan tiedostoon kutsuvan funktion kanssa, jolloin kääntäjä inline-optimoi kutsut automaattisesti (ainakin optimointitasoilla -O2 ja -O3).

Funktiot voi myös siirtää square.cpp-tiedostosta square.h-tiedostoon, jolloin koodi tulee osaksi main.cpp-käännösyksikköä esiprosessointivaiheessa. Tässä on huomattava, että jos sama square.h sisällytetään moneen eri .c/.cpp-tiedostoon, koodi monistuu useaan paikkaan myös lopullisessa binäärissä ja ajon aikana esimerkiksi staattisista muuttujista on yhtä monta versiota kuin koodista.

Suoritusajat inline-optimoinnin jälkeen:

G++ 4.6.3:     0.99 s
Clang++ 3.3:  0.85 s



Lisäoptimointia

Java vs C/C++ (tai JIT vs. staattinen kääntäjä) on aina mielenkiintoinen aihe, joten tein ohjelmasta vielä perinteisen, jossain määrin optimoidun C-toteutuksen ja siitä suoran Java-porttauksen.

C-version käännös:

Koodia: [Valitse]

gcc -Wall -O3 -o knightstour.o -c knightstour.c
gcc -Wall -O3 -o knightstour knightstour.o

("gcc":n voi tässä korvata komennolla "clang", jos Clang-kääntäjä on asennettuna)

Java-version käännös:

Koodia: [Valitse]

javac KnightsTour.java


GCC:llä käännetyn version suoritus:

Koodia: [Valitse]

time ./knightstour 6 1 1

 -- 15 --  -- 34 --  -- 29 --  -- 22 --  -- 17 --  -- 36 --
 -- 30 --  -- 1 --  -- 16 --  -- 35 --  -- 28 --  -- 21 --
 -- 33 --  -- 14 --  -- 31 --  -- 20 --  -- 23 --  -- 18 --
 -- 8 --  -- 11 --  -- 2 --  -- 25 --  -- 4 --  -- 27 --
 -- 13 --  -- 32 --  -- 9 --  -- 6 --  -- 19 --  -- 24 --
 -- 10 --  -- 7 --  -- 12 --  -- 3 --  -- 26 --  -- 5 --


real    0m0.531s
user    0m0.528s
sys     0m0.000s
Java-version suoritus:

Koodia: [Valitse]

time java KnightsTour 6 1 1

 -- 15 --  -- 34 --  -- 29 --  -- 22 --  -- 17 --  -- 36 --
 -- 30 --  -- 1 --  -- 16 --  -- 35 --  -- 28 --  -- 21 --
 -- 33 --  -- 14 --  -- 31 --  -- 20 --  -- 23 --  -- 18 --
 -- 8 --  -- 11 --  -- 2 --  -- 25 --  -- 4 --  -- 27 --
 -- 13 --  -- 32 --  -- 9 --  -- 6 --  -- 19 --  -- 24 --
 -- 10 --  -- 7 --  -- 12 --  -- 3 --  -- 26 --  -- 5 --


real 0m0.843s
user 0m0.848s
sys 0m0.004s
Kaikki suoritusajat (parametrit 6 1 1):

GCC 4.6.3:  0.53 s
Clang 3.3:   0.49 s
OpenJDK 7: 0.84 s

Suoritusajat vaikeammasta lähtöpisteestä (parametrit 6 1 0):

GCC 4.6.3:  150 s
Clang 3.3:   137 s
OpenJDK 7: 213 s