Keskustelu: Ohjelmointikysymykset: C++: Shakin hevosen hyppelyn optimointi

Hei,

Linkkasin tännekin Ubuntufoorumilla esittämäni ongelman, jossa yritän optimoida C++ -koodia toteuttamassani algoritmissa. Keskustelu löytyy täältä:
http://forum.ubuntu-fi.org/index.php?topic=46327.0

C++-toteutus on hidas. Olisiko teillä antaa parannusehdotuksia? Todennäköisesti en osaa käyttää toteutuksessa olioita tarpeeksi tehokkaalla tavalla hyödyksi.

Pikemminkin olioita kannattaa välttää, jos tavoitteena on tehokas koodi. Tein iltapuhteeksi seuraavan koodin:

#include <cstdio>
#include <cstdlib>

#define N 6
int lauta[N][N];

void haku(int y, int x, int k) {
    if (y < 0 || x < 0 || y >= N || x >= N) return;
    if (lauta[y][x]) return;
    lauta[y][x] = k;
    if (k == N*N) {
        for (int i = 0; i < N*N; i++) {
            printf("%4d", lauta[i/N][i%N]);
            if ((i+1)%N == 0) printf("\n");
        }
        exit(0);
    }
    static int s[] = {1, 2, -1, 2, 1, -2, -1, -2, 1};
    for (int i = 0; i < 8; i++) haku(y+s[i], x+s[i+1], k+1);
    lauta[y][x] = 0;
}

int main() {
    haku(1, 1, 1);
}

Koodi tulostaa salamannopeasti tämän ruudukon:

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

Suuremmissa tapauksissa koodia voisi optimoida merkittävästi pyrkimällä katkaisemalla hakuhaaran, jos ratkaisun muodostaminen ei ole mahdollista. Tällainen tilanne on esimerkiksi silloin, jos johonkin on jäänyt yksittäinen tyhjä ruutu, johon ei pääse hyppäämään mistään toisesta ruudusta.

Olioiden käyttö ei C++:ssa (toisin kuin javassa) itsessään hidasta juurikaan koodia, kunhan luokka on tehokkaasti toteutettu. Esim. jos luokka sisältää vain yhden int-muuttujan, on luokan olioiden käyttö suunnilleen yhtä tehokasta kuin tavallisen intin käyttö. Isojen olioiden kopiointi ympäriinsä vie toki jonkin aikaa, ja Square-luokka sisältää jo kohtalaisen määrän dataa, joten varmaan se jonkin verran hidadstaa.

Tuon koodin kohdalla pahin hidaste vaikuttaa olevan Square-luokan jäsenfunktioiden kutsuminen:
jäsenfunktiot on määritetty eri tiedostossa, kuin missä niitä kutsutaan, joten kääntäjä ei pysty sisentämään kutsuja main.cpp:stä.

Yksi ratkaisu on siirtää funktioiden määrittelyt suoraan luokan määrittelyn yhteyteen square.h-tiedostoon. Toinen vaihtoehto on kääntää linkkausaikaista optimointia gcc:n lipulla -flto.

Itselläni C++-ohjelman ajo parametreilla 6 1 1 vie oletuskääntölipuilla n. 8,2 sekuntia, mutta kun ohjelma käännetään kunnollisilla optimoinneilla, tulee ajaksi 1,0s (~sama kuin Java-versiolla). Käännöskomento:

g++ main.cpp square.cpp -flto -O3 -o main

Lisäys: Kannattaa myös käyttää uutta standardia, se onnistuu kääntölipulla -std=c++11. Uudessa standardissa on nimittäin joitakin suorituskykyä nopeuttavia lisäyksiä, ennen kaikkea rvalue-viittaukset jotka vähentävät tarpeetonta kopiointia, ja uuden standardin kanssa kääntämällä ohjelman ajoajaksi tulee 0.75s.

Se on tuo -O3, mikä pudottaa suoritusaikaa tuntuvasti. Itse asiassa -flto poisti vain pari sadasosaa ainakin minun koneellani.

The Alchemist kirjoitti:

Se on tuo -O3, mikä pudottaa suoritusaikaa tuntuvasti. Itse asiassa -flto poisti vain pari sadasosaa ainakin minun koneellani.

Jännää, mitä kääntökomentoa tarkalleen käytit? Itselläni nimittäin on tulee aika huomattavasti hitaampi jos tuosta kääntörivistäni poistaa -flto:n.

No ihan käänsin flageilla -Wall -O3 -flto ja ilman tuota -flto:ta. Ajat olivat 3,39 ja 3,43 sekuntia eli ihan yksittäisiä sadasosia tosiaan. Ilman -O3:a aika pompsahti jonnekin kahdeksaan sekuntiin.

Edit: unohdin toki poistaa square.o:n tuossa välissä testatessani, koska poistin filut manuaalisesti kun en älynnyt make cleania ajaa. Eihän sitä edes käännetty uusiksi noiden optimointien kanssa...

Puhtaalla käännöksellä aika putosi tosiaan 0,8 sekuntiin.