Nowe posty

xx Dystrybucja pod HP Omen (6)
Wczoraj o 23:30:08
xx [Poradnik] Wyszukiwanie Sterowników (2)
Wczoraj o 21:08:23
lamp Problem z Linux Lite po instalacji (0)
Wczoraj o 19:50:30
xx Ile pingwinów? (1)
Wczoraj o 08:59:24
xx konfiguracja pale moon (0)
2024-03-24, 21:53:42
xx Plasma 6 w Neonie ssie trochę mniej ... (10)
2024-03-23, 02:38:11
xx problem z instalacja sterowników do karty sieciowej (3)
2024-03-18, 18:10:16
xx Plik abc.001 (1)
2024-03-17, 17:48:27
xx Zlecę dopracowanie programu w MatLab (0)
2024-03-13, 15:28:40
xx Linux Mint 21.3 XFCE brak dźwieku po paru minutach (karta muzyczna zintegrowana) (5)
2024-03-12, 23:07:01

Autor Wątek: przyspieszenie programu  (Przeczytany 4761 razy)

kordi

  • Gość
przyspieszenie programu
« dnia: 2014-02-17, 12:58:00 »
Witam!
Nadal cwicze zadania z projektu Euler.
W tym momencie pojawilo mi sie w glowie pytanie jak przyspieszyc dzialanie takich kodow.

Np. napisalam kod dla zadania nr 14 - Longest Collatz sequence:

#include
#include
int iteration(int value);
int count_iteration(int value);
using namespace std;

int main(){
    int time1, time2;
    time1 = clock(); // za czas1 zostanie wstawiony czas w milisekundach od momentu wlaczenia programu

    const unsigned int NUMBER = 1000000;
    int n = 10 ;
    int lenght;

    lenght = count_iteration(n);
    cout << " DLUGOSC LANCUCHA = " << lenght << endl;

    int max = 0;
    int iteraction = 0;
    int count = 0;

  for (int i = 1; i < NUMBER; i++){
    //cout << "Current iteration : "<< i << endl;
    iteraction = count_iteration(i);
        if (iteraction > max){
            max = iteraction;
            count=i;
           
        }

    }
 
    cout << "SZUKANA LICZBA = " << count << " DLUGOSC LANCUCHA = " << max << endl;

    time2 = clock();
    time2 = time2 - time1;
    cout << "CZAS WYKONYWANIA PROGRAMU " << time2 << "ms "<< endl;
}


int count_iteration(int value){
    int chain = 1;

    while(value!=1){

        value = iteration(value);
        chain++;
    }

return chain;
}

int iteration(int value){
    if(value%2==0)
        return (value/2);
    else
        return (3*value+1);
}
Niestety taki kod wykonuje sie ekstremalnie dlugo...
Od czego powinnam rozpoczac nauke optymalizacji kodu?

Offline mateo86

  • Users
  • Guru
  • *****
  • Wiadomości: 647
    • Zobacz profil
przyspieszenie programu
« Odpowiedź #1 dnia: 2014-02-17, 13:49:44 »
Najlepiej od rzeczy najprostszych, do najbardziej skomplikowanych :)

Sprawdź który blok kodu wykonuje się najdłużej i od niego zaczniej optymalizację

Spróbuj w jakiś sposób uprościć pętle, rozwinąć je. Jeśli zależy na wydajności programu, czasem lepiej jest napisać 50 czy 100 linii kodu więcej, co w rezultacie może przyspieszyć działanie programu.

Może da się zamienić warunek z pętlą? (If coś tam, rób pętlę - przeważnie szybciej działa niż sprawdzanie warunku w każdym obiegu pętli, ale nie zawsze da się zastosować)

Zamiast mnożyć czy dzielić przez potęgi 2 czasem szybciej wykonują się przesunięcia bitowe. Właściwie to przeważnie różne działania bitowe są znacznie szybsze od zwykłej arytmetyki, ale skutecznie zacieminają kod ;)
Ogólnie nie zaszkodzi dobra znajomość matematyki i szybszych, ale dokładnych przybliżeń, zamiast obliczania dokładnych wartości, np. jak to miało miejsce w Quake 3 https://pl.wikipedia.org/wiki/Szybka_odwrotno%C5%9B%C4%87_pierwiastka_kwadratowego. No po prostu majstersztyk :)

Wstawki assemblerowe również znacznie przyspieszają działanie programu.

No i przede wszystkim warto zadbać o odpowiednie flagi kompilatora. Nawet nie stosując specjalnej optymalizacji kodu samymi flagami też można sporo osiągnąć.

Offline Paweł Kraszewski

  • Administrator
  • Guru
  • *****
  • Wiadomości: 3049
  • Lenistwo jest matką potrzeby = babcią wynalazku
    • Zobacz profil
przyspieszenie programu
« Odpowiedź #2 dnia: 2014-02-17, 20:32:22 »
Pogrzebałem w kodzie... Subtelny ale upierdliwy błąd - danie nie mieściły się w INT i wpadał w jakiś nieskończony cykl. Przy tym zadaniu liczby wędrują czasami dziwnymi ścieżkami.

1. Poprawiłem int-y na uint64_t
2. Przewaliłem funkcje pomocniczne  na górę i dałęm atrybut inline (przy ciasnych, małych funkcjach działa cuda)
3. Działa. Nawet całkiem szybko (testy na i7 pierwszej generacji 3.2GHz):
 * 0.94s na gcc 4.8.2 i standardowych opcjach kompilatora
 * 0.27s na gcc z opcjami -march=native -O4 (-//-)
 * 1.09s na clang 3.3 ze standardowymi opcjami
 * 0.44s na clang  -march=native -O3 (nie chciało mi się walczyć z LTO aby włączyć O4)

#include 
#include
#include

using namespace std;

inline uint64_t iteration( uint64_t value ) {
    if( value % 2 == 0 ) return value / 2;
    else return 3 * value + 1;
} // iteration

inline uint64_t count_iteration( uint64_t value ) {
    uint64_t chain = 1;

    while( value != 1 ) {
        value = iteration( value );
        chain++;
    }

    return chain;
} // count_iteration

int main() {
    int time1, time2;

    time1 = clock(); // za czas1 zostanie wstawiony czas w milisekundach od
                     // momentu wlaczenia programu

    const unsigned int NUMBER = 1000000;
    uint64_t n = 10;
    uint64_t lenght;

    lenght = count_iteration( n );
    cout << " DLUGOSC LANCUCHA = " << lenght << endl;

    uint64_t max = 0;
    uint64_t iteraction = 0;
    uint64_t count = 0;

    for( uint64_t i = 1; i < NUMBER; i++ ) {
        //cout << "Current iteration : " << i << endl;
        iteraction = count_iteration( i );

        if( iteraction > max ) {
            max = iteraction;
            count = i;
        }
    }

    cout << "SZUKANA LICZBA = " << count << " DLUGOSC LANCUCHA = " << max << endl;

    time2 = clock();
    time2 = time2 - time1;
    cout << "CZAS WYKONYWANIA PROGRAMU " << time2 << "ms " << endl;
} // main
Paweł Kraszewski
~Arch/Void/Gentoo/FreeBSD/OpenBSD/Specjalizowane customy

Offline mateo86

  • Users
  • Guru
  • *****
  • Wiadomości: 647
    • Zobacz profil
przyspieszenie programu
« Odpowiedź #3 dnia: 2014-02-19, 16:34:33 »
@pkraszewki:

Cytuj
* 0.27s na gcc z opcjami -march=native -O4 (-//-)
Działa już w gcc optymalizacja większa niż -O3?

Offline Paweł Kraszewski

  • Administrator
  • Guru
  • *****
  • Wiadomości: 3049
  • Lenistwo jest matką potrzeby = babcią wynalazku
    • Zobacz profil
przyspieszenie programu
« Odpowiedź #4 dnia: 2014-02-19, 20:27:58 »
Nie działa. Była propozycja, aby O4 robiło to samo, co teraz robi w Clangu (zanim w ogóle clang powstał), tj optymalizację między modułami wynikowymi (link time optimization, LTO). Umarło na listach dyskusyjnych w okolicach GCC 3.3 bodaj.
Paweł Kraszewski
~Arch/Void/Gentoo/FreeBSD/OpenBSD/Specjalizowane customy