Modulo vs. koniunkcja bitowa - co szybsze?

Czasem tak mnie natchnie i napiszę sobie coś głupiego w C++ (bo mądrego nie potrafię ;))
I tak napisałem kod porównujący czas dzielenia modulo przez 2 i koniunkcji bitowej z 1. Z tego, co wiem, to operacje te dają ten sam wynik, natomiast druga jest bardziej pro i szybsza.
Kod wygląda tak:

#include <iostream>

using namespace std;

int main()
{
    const int ILE_RAZY = 1000000000;
    int pocz, kon, wynik;

    cout << "Nacisnij ENTER!\n";
    cin.get();

    pocz = clock();
    for(int i = 0; i < ILE_RAZY; i++)
        wynik = i % 2;
    kon = clock();
    cout << "Czas dzielenia modulo to: " << kon - pocz << endl;

    pocz = clock();
    for(int i = 0; i < ILE_RAZY; i++)
        wynik = i & 1;
    kon = clock();
    cout << "Czas koniunkcji bitowej: " << kon - pocz << endl;

    cin.get();
    return 0;
}

Pisałem w CodeBlocks 8.02, kompilowałem domyślnym w nim GCC.
No i bardzo dziwią mnie wyniki, bo pętla pierwsza wykonuje się jakieś 10 - 20 razy szybciej, niż druga, a przecież powinno być inaczej.
Co zepsułem?

pokaż funkcję clock(), bo tak to ciężko cokolwiek powiedzieć :)

PS. swoją drogą to ciekawe badanie.

Funkcja clock jest tutaj:http://www.cppreference.com/wiki/c/date/clock

Mi z jakiegoś powodu zawsze wyświetla 0 :/

Z tego co wiem to IDIV jest najwolniejszą instrukcją proca do obliczeń. AND jedną z szybszych. Winę ponosi pewnie kompilator, wymuś mu brak optymalizacji przez -O0 (duże o i zero).

@winerfresh - widocznie masz szybszy procek niż mój stary T5600.

manfredek napisał(a)

Winę ponosi pewnie kompilator, wymuś mu brak optymalizacji przez -O0 (duże o i zero).

No tak.

O ile wcześniej miałem czasy rzędu 30 - 60 ms dla modulo i 500 - 600 ms dla koniunkcji, to teraz mam odpowiednio 4500 - 5500 i 3500 - 4000.

Super. To kolejne pytanie - po co w takim razie wyłączać optymalizację?
I po co pisać "mądry" kod, skoro i tak kompilator jest w stanie to zoptymalizować bardziej, niż człowiek?

Pętlę z modulo pewnie kompilator sobie obliczy i wstawi wynik do execa, a na anda już jest za głupi. Zrób jakąś pętlę która coś "sensownego" liczy (a potem korzysta z wyniku) używając dzielenia, a potem zrób taką samą tylko używając and i shr...

Żeby było bardziej obiektywnie, zamiast działania na inkrementowanym i, zrób na jakiejś randomowej liczbie, kompilator wtedy sam z siebie nie będzie mógł zoptymalizować działania i test będzie bardziej miarodajny.

somekind napisał(a)

@winerfresh - widocznie masz szybszy procek niż mój stary T5600.

Nie po prostu po włączeniu optymalizacji clock() wywala mi zawsze 0.

graf.zero napisał(a)

Żeby było bardziej obiektywnie, zamiast działania na inkrementowanym i, zrób na jakiejś randomowej liczbie, kompilator wtedy sam z siebie nie będzie mógł zoptymalizować działania i test będzie bardziej miarodajny.

Na randomie już testowałem - wtedy faktycznie modulo jest wolniejsze.

Po prostu ciekawiło mnie, czemu w tym akurat wypadku jest tak.

w działaniu i % 2 istotnym jest czy i jest liczbą ze znakiem czy bez.
bez znaku myślę że i%2 oraz i&1 kompilator zmieni na dokładnie taką samą sekwencję rozkazów

Ale jakby była taka sama, to chyba czas działania też byłby taki sam. A różnica jest o rząd wielkości.

Czy miliard iteracji może zająć mnij niż kilkaset milisekund?
Zmieniłem nieco kod

#include <iostream>
using namespace std;
int main(){
    const int ILE_RAZY = 1000000000;
    unsigned int pocz, kon, wynik;

    cout << "Nacisnij ENTER!\n";
    cin.get();

    wynik=0;                 // 
    pocz = clock();
    for(int i = 0; i < ILE_RAZY; i++)
        wynik += i % 2;    //
    kon = clock();
    cout << "Czas dzielenia modulo to: " << kon - pocz << " " << wynik <<endl;      //

    wynik=0;                  //
    pocz = clock();
    for(int i = 0; i < ILE_RAZY; i++)
        wynik += i & 1;    //
    kon = clock();
    cout << "Czas koniunkcji bitowej : " << kon - pocz << " " << wynik << endl;     //

    cin.get();
    return 0;
}

unsigned int
Czas dzielenia modulo to : 4356 500000000
Czas koniunkcji bitowej _: 1666 500000000
int
Czas dzielenia modulo to : 4436 500000000
Czas koniunkcji bitowej _: 1756 500000000
PIII 1GHz

To jeszcze parę słów o genezie tego wątku i pomyśle na porównywanie modulo z koniunkcją...

Otóż, gdy na innym forum ktoś poprosił o kod na szukanie liczby pierwszej (BTW: to się nudne już robi), to pokazałem mu takie coś:

int CzyPierwsza(int liczba)
{
    //warunki początkowe
    if(liczba <= 1)         return 0;
    if(liczba == 2 || liczba == 3)  return 1;
    //pozbywamy się parzystych
    if(liczba % 2 == 0)     return 0;
    //właściwy algortym - zaczynamy od 3, do pierwiastka ze sprawdzanej liczby, iterujemy co 2
    int d_max = (int) sqrt(liczba) + 1;
    for(int i = 3; i <= d_max; i += 2)
        if(liczba % i == 0) return 0;
    return 1;
}

Zostałem okrzyczany przez pewnego geniusza programistycznego, że mój kod jest beznadziejny i nieoptymalny. Sam zaś zaprezentował taki wypasiony i superoptymalny kod:

int pierwsza(int x)
{
    if(x<=3) return 1; // napewno pierwsza
    if(!(x&1)) return 0; // podielna przez 2
    int imax=(int)sqrt(x); // aby nie liczycz na każdym kroku
    for(int i=3;i<=imax;i+=2) if(!(x%i)) return 0; // lecimy co dwie liczby
    return 1;
}

Nie ukrywam, że w moim kodzie (ma już parę lat) można parę rzeczy poprawić, np. zamienić na negację wszystkie porównania do 0, zamienić ifa z alternatywą, na takiego z jednym porównaniem, ponadto niepotrzebnie dodaję 1 do pierwiastka (robiłem to kiedyś na wszelki wypadek, aby uniknąć jakichś błędów zaokrągleń, ale dla double to chyba jest bez sensu?).

Niemniej jednak, gdy uruchomię sobie taki test:

int main()
{
    const int START = 2, ILE_RAZY = 10000000;
    int pocz, kon, wynik;

    cout << "Nacisnij ENTER" << endl;
    cin.get();

    pocz = clock();
    for(int i = START; i < ILE_RAZY; i++)
        wynik = pierwsza(i);
    kon = clock();
    cout << "Czas pr0: " << kon - pocz << endl;

    pocz = clock();
    for(int i = START; i < ILE_RAZY; i++)
        wynik = CzyPierwsza(i);
    kon = clock();
    cout << "Czas powolnej: " << kon - pocz << endl;

    cout << "Koniec!" << endl;
    cin.get();
    return 0;
}

To różnice w czasie wykonania są minimalne (góra 400ms przy ponad 11s trwania operacji), ale w 4 przypadkach na 5 na moją korzyść.
Czyli to "wina" kompilatora?

To może wklej kod skompilowany (w asm) ?

Poza tym, że kod tego gieniusia jest błędny (-666 jest pierwsze tak samo jak i 1...) to w sumie kod wynikowy powinien być poza tym jednym testem praktycznie identyczny. To dodawanie 1 może mieć sens - obliczanie pierwiastka na FPU nie jest idealnie dokładne, w skrajnym wypadku mogłoby false-positive wystąpić. Chociaż tutaj to 1 jest dodawane naiwnie, powinno być dodawane tylko wtedy gdy pierwiastek jest minimalnie mniejszy od liczby całkowitej - odpadanie jedna 'pusta' iteracja.
Zastępowanie modulo 2^n komiunkcją to jedna z najbardziej podstawowych technik optymalizacji, kompilatory robiły to już zanim się urodziłeś.
W praktyce Twój kod jest minimalnie wolniejszy - niedokładność wynika z programów działających w tle - dodatkowy test i jedna iteracja.

@Hass - zamiast assemblerem lepiej zainteresować się logiką kodu, algorytmem, przy takim kodzie oba algo dadzą kod identyczny poza wymienionymi różnicami... Assembler jest przereklamowany, kolejny mit.

*koniunkcją

asdf napisał(a)

@Hass - zamiast assemblerem lepiej zainteresować się logiką kodu, algorytmem, przy takim kodzie oba algo dadzą kod identyczny poza wymienionymi różnicami... Assembler jest przereklamowany, kolejny mit.

Ja nie mówię żeby program napisać w assemblerze. Ja tylko radzę obejrzeć skompilowany kod w obu wersjach, skoro somekind jest tak bardzo ciekawy skąd biorą się różnice. Wtedy stanie się jasne co i jak zostało zoptymalizowane.

asdf napisał(a)

Poza tym, że kod tego gieniusia jest błędny (-666 jest pierwsze tak samo jak i 1...)

No ja wiem, ale gość i tak będzie się upierał przy swoim, że do tego akurat zadania nie trzeba sprawdzać.

asdf napisał(a)

obliczanie pierwiastka na FPU nie jest idealnie dokładne, w skrajnym wypadku mogłoby false-positive wystąpić.

No tak, dla float chyba mogłoby tak być, ale dla double to chyba cały zakres int mieści się w mantysie, więc błędu zaokrąglenia nie będzie? Czy źle myślę?

asdf napisał(a)

Chociaż tutaj to 1 jest dodawane naiwnie, powinno być dodawane tylko wtedy gdy pierwiastek jest minimalnie mniejszy od liczby całkowitej - odpadanie jedna 'pusta' iteracja.

Za to dojdzie instrukcja logiczna. Będzie z tego jakiś zysk? Możesz pokazać dokładnie o co chodzi?

asdf napisał(a)

Zastępowanie modulo 2^n komiunkcją to jedna z najbardziej podstawowych technik optymalizacji, kompilatory robiły to już zanim się urodziłeś.

No też tak myślałem. Tylko taki geniusz wyłączy optymalizację i zawsze udowodni, że jego kod jest "szybciejszy" od mojego.
Tylko pytanie moje - skoro mądrzy ludzie stworzy kompilatory, które same za programistę potrafią tego typu optymalizację przeprowadzić, to po co się męczyć i z tego nie korzystać?!

asdf napisał(a)

W praktyce Twój kod jest minimalnie wolniejszy - niedokładność wynika z programów działających w tle - dodatkowy test i jedna iteracja.

W praktyce... ale empirycznie mój kod, na moim komputerze jest zazwyczaj minimalnie szybszy. I to mnie właśnie ciekawi.

@Hass - chętnie, ale nie wiem skąd go wziąć :( Używam Code Blocks i kompiluję w GNU GCC

Jak gcc, to możesz z lini poleceń wpisać:
gcc source.c -S -o output.asm

uwaga, wielkość liter w argumentach wywołania ważna.

Jaki bajer.
Dobra, tu jest ASM: http://wklej.org/id/61693/?zawin=0
Niestety intuicyjnie nie jestem w stanie się w tym połapać, więc jakby ktoś wyjaśnił i doszedł do jakichś wniosków, to byłoby miło :)

@Ranides - dzięki za przeniesienie z newbie, miałem sam o to prosić, ale że jestem nieśmiały, to się wstrzymałem ;)

Dorzuć gcc'owi -masm=intel! Składnia AT&T jest szpetna, Intela znacznie lepsza, wielu ludziom się na AT&T patrzeć nie chce a intela ci sprawdzą z chęcią (np. ja).

Wersja Intel tutaj: http://wklej.org/id/61811/?zawin=0

Jeszcze "-fverbose-asm" by nie zaszkodziło :)
Edit:
Zresztą kod o który chodzi jest w obu funkcjach identyczny:

idiv	DWORD PTR [ecx]
	test	edx, edx