Przyspieszenie if/else, gdy warunek jest nieprzewidywalny

Question

Mam taką funkcję:

uint64_t funct()
{
    if(x >> 63)
    {
        x = x * a + b;
    }
    else
    {
        x = (x >> 1) * c + d;
    }
    return x;

x,a,b,c,d to liczby 64-bitowe. x jest liczbą pseudo-losową (generowaną za pomocą generatora PRNG), a zatem nie jesteśmy w stanie przewidzieć jej ostatniego bitu obliczanego w warunku x >> 63.

Czy to da się zaprogramować szybciej? Próbowałem kilku najprostszych rozwiązań, np. zapisania tego tak:

x = ((x >> 63) * (x * key[0] + key[1])) + ((1^(x >> 63)) * ((x >> 1) * key[2] + key[3]));

Próbowałem też usunąć else. Wszystko to działa nawet wolniej niż proste if/else. Czytałem trochę o branching i powoli tracę nadzieję, że da się to przyspieszyć. Jeżeli w warunku znajdzie się z np. k & 1, gdzie k zmienia się od 0 do 3: 0,1,2,3,0,1,2,3,... to kod przyspiesza znacząco. A zatem samo mnożenie z dodawaniem zajmuje tylko połowę tego co instrukcja if/else - tak kosztowna jest ona w tym przypadku.

Ponoć takie problemy można przyspieszyć w ramach mikro-optymalizacji, ale jak dokładnie się to robi? To jest wąskie gardło programu i ta funkcja jest wykonywana bez przerwy, jeżeli jej nie przyspieszę, to niewiele jest do optymalizacji w reszcie kodu.

Comments

Przede wszystkim... ta funkcja nie bierze w ogóle argumentów? `x, a, b, c, d` to jest stan globalny w pamięci?

---

Bo to co napisałeś oryginalnie to przepięknie się kompiluje z normalnymi argumentami:

https://godbolt.org/z/79caebnje

---

Tak, można równie dobrze podawać x,a,b,c,d jako argumenty. Ja akurat używam x,a,b,c,d jako zmiennych globalnych.

---

Tamtą schowałeś więc tutaj:

Nie kompiluję z optymalizacjami

To... nie ma sensu mówić o przyśpieszaniu, porównywaniu lub mierzeniu czegokolwiek. Włącz optymalizacje (profil release w C::B) i dopiero wtedy na to patrz.

Answer 1

Ja akurat używam x,a,b,c,d jako zmiennych globalnych.

To przestań :) To prawdopodobnie jedna z większych barier optymalizacji. Bez tego Twoja oryginalna funkcja jest na tyle prosta, że kompilator bez problemu ją elegancko zoptymalizuje.

Możesz pokazać, co testujesz, że wg Ciebie to jest bottleneck?

(sanity check: kompilujesz z optymalizacjami, nie? :))

Comments

@adrian17, jeszcze raz zamieszczam kod. Pozbyłem się zmiennych globalnych, poza tymi, których chyba nie da się pozbyć:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>

uint8_t count1;
uint8_t count2;
uint16_t low16;
uint16_t high16;
uint16_t x1;
uint16_t x2;

uint32_t XSLRRRR(uint32_t xsl)
{
    count1 = xsl >> 28;
    x1 = xsl ^ (xsl >> 16);
    low16 = (x1 >> count1) | (x1 << (16 - count1)) & 65535;
    x2 = xsl >> 16;
    count2 = low16 & 15;
    high16 = (x2 >> count2) | (x2 << (16 - count2)) & 65535;
    xsl = (high16 << 16) | low16;
    return xsl;
}

uint32_t funct(uint32_t x, uint32_t key[4])
{
    if(x >> 31)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    return x;
}

uint32_t LCG(uint32_t LCG_state)
{
    LCG_state = LCG_state + 2654435769;
    return LCG_state;
}

uint32_t keymix(uint32_t x, uint32_t key[4], uint32_t coefficients[4], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 4294967295;
    return key[4];
}

int main()
{
    uint32_t LCG_state = 11555;
    uint32_t coefficients[4] = {3,5,7,9};
    uint32_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint32_t x;
    int k = 0;
    uint16_t result;


    while (true)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    key[4] = keymix(x,key[4],coefficients[4],k);
    k = (k+1) & 3;

        for(int j=0; j<32; j++)
        {
        x=funct(x,key[4]);
        result = x >> 16;
        //std::cout << result << "\n";
        }
    }
}

Ale nie działa, bo nie mogę podać jako argumentów key[4] i coefficients[4] w key[4] = keymix(x,key[4],coefficients[4],k).

Czy w celu optymalizacji mam włączyć te flagi -O1, -O2, etc.? Mam sprawdzić, która działa najlepiej, czy któraś powinna być najlepsza z definicji?

Wstępnie kod działa szybciej (na pewno dwie z tych flag robią ogromną różnicę - rząd wielkości), choć wciąż nie robi dokładnie tego co powinien. Swoją drogą próbowałem włączać niedawno te flagi bez pozbycia się zmiennych globalnych i nie robiły one różnicy, teraz robią.

Czytam, że:

C++ does not allow to pass an entire array as an argument to a function. However, You can pass a pointer to an array by specifying the array's name without an index.

Czyli moich list chyba nie da się podać jako argumentów, chyba, że z pointerem, który nic mi nie daje, bo wskazuje ciągle na tę samą listę zdefiniowaną na początku, a key ma się zmieniać.

Tych key nie da się chyba zdefiniować lokalnie, ja przynajmniej nie wiem jak to zrobić, więc na razie porzucam ten pomysł. W tej chwili kod wygląda tak:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>

uint8_t count1;
uint8_t count2;
uint32_t low32;
uint32_t high32;
uint32_t x1;
uint32_t x2;

uint64_t coefficients[4] = {3,5,7,9};
uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

uint64_t XSLRRRR(uint64_t xsl)
{
    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = (high32 << 32) | low32;
    return xsl;
}


uint64_t funct(uint64_t x)
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    return x;
}

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

uint64_t keymix(uint64_t x, int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
    return key[4];
}

int main()
{
    uint64_t LCG_state = 999111;

    uint64_t x;
    int k = 0;
    uint32_t result;


    for(int i=0; i<5000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG(LCG_state);

    key[4] = keymix(x,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x);
        result = x >> 32;
        //std::cout << result << "\n";
        }
    }
}

Teraz wyniki są zbliżone do prostego generatora LCG:

#include <iostream>
#include <cmath>
#include <stdio.h>

uint64_t LCG_state = 333;
uint32_t wynik;

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    return LCG_state;
}

int main()
{
    for(int i=0; i<320000000; i++)
    {
    LCG(LCG_state);
    wynik = LCG_state >> 32;
    //std::cout << wynik << "\n";
    }
}

I to jest dokładnie to, czego się spodziewałem, bo oba programy przez większość czasu liczą dokładnie to samo - czyli wykonują mnożenie z dodawaniem. Oczywiście mój program jest bardziej skomplikowany, ale dodatkowe rzeczy, które oblicza robi tylko raz na 64 iteracje, zaś przez większość czasu wykonuje funct, która jest, gdyby nie liczyć branching, praktycznie tylko mnożeniem z dodawaniem.

---

Czy w celu optymalizacji mam włączyć te flagi -O1, -O2, etc.? Mam sprawdzić, która działa najlepiej, czy któraś powinna być najlepsza z definicji?

Wystarczyło na górze w C::B przełączyć z Debug na Release.

Czyli moich list chyba nie da się podać jako argumentów, chyba, że z pointerem, który nic mi nie daje, bo wskazuje ciągle na tę samą listę zdefiniowaną na początku, a key ma się zmieniać.

Co, nie, przekombinowałeś; wskaźnik to dokładnie to co miałeś i używałeś, tylko trochę błędnie.

uint32_t funct(uint32_t x, uint32_t key[4])

To było ok (to [4] tutaj nic nie robi w zasadzie, bo `key` jest po prostu wskaźnikiem - ale ok)

key[4] = keymix(x,key[4],coefficients[4],k);

Wystarczyło tutaj po prostu przekazać tablice zamiast ich "4ty element".

bo wskazuje ciągle na tę samą listę zdefiniowaną na początku, a key ma się zmieniać.

No... wskazuje na tą samą tablicę, którą zawartość zmieniasz; wszystko jest ok.

Więc powtórzę: wyrzuć te _wszystkie_ zmienne globalne.

A jak coś się w ogóle nie zmienia (coefficients?) to zadeklaruj jako const.

I ostatnia rzecz: nie wiem po co Ci key[4] bo nic z nim nie robisz, ale ewidentnie wychodzisz poza tablicę, bo tablica key ma rozmiar 4.

---

(a na dłuższą metę, najlepiej by cały ten stan LCG wrzucić w jedną strukturę i operować na nim funkcjami/metodami)

---

Wystarczyło na górze w C::B przełączyć z Debug na Release.

Nie widzę takiej opcji. Pod debug mam active debuggers, toggle breakpoint itd.

 

Wystarczyło tutaj po prostu przekazać tablice zamiast ich "4ty element".

To key[4] nie wskazuje na całą tablicę, tylko na 4-ty element? Zmieniłem to i nie działa:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>

uint8_t count1;
uint8_t count2;
uint32_t low32;
uint32_t high32;
uint32_t x1;
uint32_t x2;

uint64_t XSLRRRR(uint64_t xsl)
{
    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = (high32 << 32) | low32;
    return xsl;
}


uint64_t funct(uint64_t x, uint64_t key)
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    return x;
}

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

uint64_t keymix(uint64_t x, uint64_t key, uint64_t coefficients, int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
    return key[4];
}

int main()
{

    uint64_t LCG_state = 999111;
    const uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;


    for(int i=0; i<5000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    key[4] = keymix(x,&key,&coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,&key);
        result = x >> 32;
        //std::cout << result << "\n";
        }
    }
}

error: invalid type 'uint64 (aka long long unsigned int)[int] for array subscript

I ostatnia rzecz: nie wiem po co Ci key[4] bo nic z nim nie robisz, ale ewidentnie wychodzisz poza tablicę, bo tablica key ma rozmiar 4.

Wydawało mi się, że definiując key[4] definiuję tablicę 4-elementową, a później mogę ją wywoływać używając key[4].

Więc powtórzę: wyrzuć te _wszystkie_ zmienne globalne.

A czy key i coefficients da się w ogóle wyrzucić ze zmiennych globalnych? Nie da się ich podać jako argumenty do funkcji, więc jak ich użyć jak nie zmienne globalne? Nawet, gdybym nie deklarował ich w tablicy, to potrzebuję tablicę w funkcji XSLRRRR(x^coefficients[k]), więc i tak muszę je znowu przekonwertować na tablicę i podobnie tutaj: key[4] = keymix(x,k).

Nic więcej nie da się tu nic zrobić na moje oko.

---

@adrian17, nie wiem jeszcze co to jest klasa i metoda w c++, czym się różnią od funkcji i po co lub jak ich używać. Jak na razie wszystko jest dla mnie funkcją ;)

---

To key[4] nie wskazuje na całą tablicę, tylko na 4-ty element? Zmieniłem to i nie działa:

Wiesz co... może po prostu powtórz temat tablic i wskaźników przed zabieraniem się za to, bo widać że mało to wciąż rozumiesz. Jeśli key[0] to pierwszy element, to dlaczego key[4] by miało być całą tablicą?

uint64_t funct(uint64_t x, uint64_t key)

Teraz to już w ogóle nie przekazujesz tablicy ani wskaźnika.

Wydawało mi się, że definiując key[4] definiuję tablicę 4-elementową, a później mogę ją wywoływać używając key[4].

Tablica (i jednocześnie wskaźnik na nią) to `key`. Pisząc `cos = key[0]` lub `key[0] = cos` lub `funkcja(key[0])` używasz jej pierwszy element; pisząc `key[1]` to drugi, etc. To że liczba w nawiasach kwadratowych wpisałeś 4 to nie znaczy nagle zupełnie czegoś innego - to znaczy "piąty element tablicy z czteroma elementami", co jest oczywiście błędne.

Jedyne miejsce gdzie `[4]` to rozmiar, to przy pierwszej deklaracji `int tab[4];` - ale przy każdym kolejnym użyciu tej zmiennej to jest indeks elementu.

A czy key i coefficients da się w ogóle wyrzucić ze zmiennych globalnych?

Tak, ten kod nie powinien mieć ani jednej zmiennej globalnej; ba, nie powinieneś nawet wiedzieć że istnieją :V

Nie da się ich podać jako argumenty do funkcji

Bez problemu da się, patrz wyżej.

key[4] = keymix(x,k).

Twoja funkcja keymix modyfikuje istniejącą tablicę, to przypisanie więc naprawdę nie jest potrzebne i ogólnie nie ma sensu. Powtarzam, powtórz temat tablic :(

nie wiem jeszcze co to jest klasa i metoda w c++, czym się różnią od funkcji i po co lub jak ich używać

Dlatego napisałem "strukturę" a nie "klasę" ;)

---

Nie widzę takiej opcji. Pod debug mam active debuggers, toggle breakpoint itd.

Tutaj: https://puu.sh/IPF4T/51d3544138.png

Jeszcze jako przykład jakie śmieszne rzeczy mogą się dziać gdy wyjdziesz poza tablicę:

int tab[4];
int liczba;

int main()
{
    liczba = 5;
    tab[4] = 7;

    cout << "zmienna liczba ma wartosc " << liczba;
}

W niektórych konfiguracjach może wypisać "zmienna liczba ma wartosc 7" :)

---

Wiesz co... może po prostu powtórz temat tablic i wskaźników przed zabieraniem się za to, bo widać że mało to wciąż rozumiesz. Jeśli key[0] to pierwszy element, to dlaczego key[4] by miało być całą tablicą?

Dobre pytanie. Pytanie też też dlaczego tablicę 5-elementową deklaruje się tak:

https://www.cplusplus.com/doc/tutorial/arrays/

int foo[5];   

A nie jest to zdeklarowanie po prostu 5 elementu tablicy. Nie znalazłem jednego przykładu w Internecie, w którym ktoś pokazywałby jak użyć tablicy jako argumentu w funkcji. Metodę prób i błędów wyczerpałem. Zresztą użycie key[4] to wynik tylko prób i błędów, bo wszystko inne się wykrzacza, to się nie wykrzaczało. Nie podejrzewałem tego koniecznie o jakikolwiek sens, po prostu działało jakoś.

Jedyne miejsce gdzie `[4]` to rozmiar, to przy pierwszej deklaracji `int tab[4];` - ale przy każdym kolejnym użyciu tej zmiennej to jest indeks elementu.

No tak, teraz to rozumiem, tzn. jestem tego pewien, bo podejrzewałem już wcześniej, że coś tu jest nie tak. Co nie zmienia faktu, że użycie tablic jako argumentów nadal kończy się błędami.

Bez problemu da się, patrz wyżej.

No więc podaję:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>

uint64_t LCG_state = 999111;

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = (high32 << 32) | low32;
    return xsl;
}

uint64_t funct(uint64_t x, uint64_t key)
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    return x;
}

uint64_t LCG()
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

uint64_t keymix(uint64_t x, int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
    return key[4];
}

int main()
{

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<50000000; i++)
    {
    x = LCG();

    keymix(x,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key);
        result = x >> 32;
        //std::cout << result << "\n";
        }
    }
}

I dostaję error: invalid types 'uint64_t (aka long long unsigned int)[int]' for array subscript.

Twoja funkcja keymix modyfikuje istniejącą tablicę, to przypisanie więc naprawdę nie jest potrzebne i ogólnie nie ma sensu. Powtarzam, powtórz temat tablic :(

Ok, usunąłem to przypisanie. Co do tematu tablic nie widziałem nigdzie kodu, który używałby tablic w funkcjach, a czytanie piąty raz poradnika jak zdefiniować tablicę, wypisać, czy wywołać element nic mi nie pomoże.

Większość tych poradników ma po prostu absolutnie niekompetentne, bezużyteczne przykłady. Pamiętam, gdy kiedyś ktoś pokazał mi jak zaprogramować mały algorytm szyfrujący w Pythonie. Pomimo, że 90% z kodu nie rozumiałem, to po kilku tygodniach byłem w stanie nauczyć się z niego praktycznie wszystkiego, co było w nim zawarte. To był właśnie dobry przykład. Z przykładami w Internecie jest odwrotnie. Pomimo, że wszystko jest w nich zrozumiałe, niewiele można się z nich nauczyć.

---

Pytanie też też dlaczego tablicę 5-elementową deklaruje się tak:

int foo[5];

A nie jest to zdeklarowanie po prostu 5 elementu tablicy.

Po prostu w kontekście deklaracji składnia ma trochę inne znaczenie niż przy użyciu. Z tego samego powodu na przykład... przy deklarowaniu funkcji `f(asdf)` "asdf" to typ argumentu, ale przy wołaniu funkcji `f(asdf)`, "asdf" to nazwa zmiennej z argumentem funkcji, co nie?

Nie znalazłem jednego przykładu w Internecie, w którym ktoś pokazywałby jak użyć tablicy jako argumentu w funkcji. 

uh... To jest dośc wczesny temat w każdym poradniku, książce, tutorialu ;)

pierwszy wynik z gugla "c++ przekazywanie tablicy do funkcji"

https://cpp0x.pl/kursy/Kurs-C++/Poziom-2/Przekazywanie-tablic-jednowymiarowych-do-funkcji/324

pierwszy wynik z gugla "c++ pass array to function"

https://www.tutorialspoint.com/cplusplus/cpp_passing_arrays_to_functions.htm

 

---

Tutaj: https://puu.sh/IPF4T/51d3544138.png

Mam to nieaktywne:

https://i.ibb.co/1v7zcxr/nieaktywne.png

---

Uh... trudno mi powiedzieć czemu. Gdybyś pokazał pełny screenshot to może bym coś zauważył.

---

uh... To jest dośc wczesny temat w każdym poradniku, książce, tutorialu ;)

pierwszy wynik z gugla "c++ przekazywanie tablicy do funkcji"

https://cpp0x.pl/kursy/Kurs-C++/Poziom-2/Przekazywanie-tablic-jednowymiarowych-do-funkcji/324

Faktycznie jest to tam wyjaśnione i chyba zrozumiałem, bo kod działa:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = (high32 << 32) | low32;
    return xsl;
}

uint64_t funct(uint64_t x, uint64_t key[])
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    return x;
}

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

uint64_t keymix(uint64_t x, uint64_t key[], uint64_t coefficients[], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
    return key[4];
}

int main()
{
    uint64_t LCG_state = 999111;

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<50000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    keymix(x,key,coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key);
        result = x >> 32;
        //std::cout << result << "\n";
        }
    }
}

Nie wiem, czy to powinno być tak, że:

uint8_t count1;
uint8_t count2;
uint32_t low32;
uint32_t high32;
uint32_t x1;
uint32_t x2;

deklaruję w funkcji. W każdym razie chyba już nie ma globalnych zmiennych. Wcześniej trafiałem na poradnik typu:

https://cpp0x.pl/kursy/Kurs-C++/Dodatkowe-materialy/Tablice-zmiennych/298

Nomen omen z tej samej strony, dlatego pisałem o złych, bezużytecznych przykładach.

---

Uh... trudno mi powiedzieć czemu. Gdybyś pokazał pełny screenshot to może bym coś zauważył.

Pełne zdjęcie:

https://i.ibb.co/dKc2dFY/nieaktywne.png

Swoją drogą, czy włączenie flagi -O3 jest równoważne temu rozwiązaniu, czy to jeszcze inna kategoria optymalizacji?

---

Pełne zdjęcie:

A, bo działasz na pojedynczym .cpp, bez projektu. Normalnie w C::B się tworzy projekt, to masz więcej konfiguracji i ustawień per projekt zapamiętanych - no i więcej domyślnych opcji, jak konfiguracje Debug/Release. Na ekranie startowym jest: https://puu.sh/IPFZv/4d7ec85615.png

Ale to nie jest obowiązkowe :)

Nie wiem, czy to powinno być tak, że:

uint8_t count1;

deklaruję w funkcji.

Czemu nie? Jak nie są używane zupełnie nigdzie indziej, to to jest dokładnie to miejsce gdzie powinny być. Ba, powinny być deklarowane jak najbliżej miejsca użycia a nie na samej górze funkcji więc nawet ładniej by było:

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1 = xsl >> 59;
    uint32_t x1 = xsl ^ (xsl >> 32);
    uint32_t low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    uint32_t x2 = xsl >> 32;
    uint8_t count2 = low32 & 31;
    uint32_t high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    return (high32 << 32) | low32;
}

A na boku, nie ignoruj ostrzeżeń kompilatora które widać na dole screenshota. Ma jak najbardziej rację, że `high32 << 32` nie ma zbytnio sensu, skoro `high32` jest 32-bitowe.

---

I powtarzam, że ten `return key[4];` jest błędne; nie tylko wychodzi poza tablicę, ale jest też ogólnie niepotrzebne, bo już nie używasz wartości zwracanej z funkcji keymix - już nic nie musisz zwracać.

---

A na boku, nie ignoruj ostrzeżeń kompilatora które widać na dole screenshota. Ma jak najbardziej rację, że `high32 << 32` nie ma zbytnio sensu, skoro `high32` jest 32-bitowe.

Ale wynikowe xsl jest 64-bitowe. Nie mogę zrobić przesunięcia o 32 bity, skoro high32 jest 32 bitowe? Powinno być 64-bitowe?

I powtarzam, że ten `return key[4];` jest błędne; nie tylko wychodzi poza tablicę, ale jest też ogólnie niepotrzebne, bo już nie używasz wartości zwracanej z funkcji keymix.

Próbowałem to zmienić, ale return key nie działa, return key[] też nie działa. W każdym razie jak rozumiem funkcja może zwracać po prosu 0?

A, bo działasz na pojedynczym .cpp, bez projektu. Normalnie w C::B się tworzy projekt, to masz więcej konfiguracji i ustawień per projekt zapamiętanych - no i więcej domyślnych opcji, jak konfiguracje Debug/Release.

Udało się. W tej chwili te szacunki dot. prędkości chyba nie są zbyt obiektywne, bo nie dość, że wahają się od  0.01 s do nawet 0.015 s, to są to niewielkie liczby. A pętle zdaje się nie mogą działać dla wartości znacznie większych niż 640000000, z kolei zrobienie pętli w pętli znów z jakichś tajemniczych powodów nie zmienia wyników:

#include <iostream>
#include <cmath>
#include <stdio.h>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    return LCG_state;
}

int main()
{
    uint64_t LCG_state = 333;
    uint32_t wynik;

    for(int i=0; i<1000; i++)
    {
    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        //std::cout << wynik << "\n";
    }
    }
}

W każdym razie wyniki mojego programu są wreszcie podobne jak w przypadku:

#include <iostream>
#include <cmath>
#include <stdio.h>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    return LCG_state;
}

int main()
{
    uint64_t LCG_state = 333;
    uint32_t wynik;

    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        //std::cout << wynik << "\n";
    }
}

I to jest to czego się spodziewałem.

 

---

Ale wynikowe xsl jest 64-bitowe. Nie mogę zrobić przesunięcia o 32 bity, skoro high32 jest 32 bitowe? Powinno być 64-bitowe?

Tak, musisz zrobić cast na uint64_t przed <<, nie po. (nie musisz na to osobnej zmiennej robić, może być wszystko w jednej linii)

Próbowałem to zmienić, ale return key nie działa, return key[] też nie działa. W każdym razie jak rozumiem funkcja może zwracać po prosu 0?

...nic nie zwracać. Dosłownie.

void funkcja() {
    cout << "nic nie zwracam!";
}

z kolei zrobienie pętli w pętli znów z jakichś tajemniczych powodów nie zmienia wyników:

Jeśli wszystkie couty masz zakomentowane, to możliwe że kompilator podczas optymalizowania że wyniki nie są do niczego nie używane i kompletnie wyrzuca pętle. Spróbuj wrzucić cout wyniku po wszystkich pętlach.

(Ale to tylko mój strzał, co się może dziać. )

---

Wypisuje liczby, ale nie mierzy czasu poprawnie:

#include <iostream>
#include <cmath>
#include <stdio.h>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    return LCG_state;
}

int main()
{
    uint64_t LCG_state = 333;
    uint32_t wynik;

    for(int i=0; i<50; i++)
    {
    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        //std::cout << wynik << "\n";
    }
    std::cout << wynik << "\n";
    }
}

Niezależnie ile się wpisze powtórzeń do pierwszej pętli, zawsze jest to około 0,028 s. Takiego problemu nie ma w moim kodzie:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = ((uint64_t)high32 << 32) | low32;
    return xsl;
}

uint64_t funct(uint64_t x, uint64_t key[])
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    return x;
}

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

void keymix(uint64_t x, uint64_t key[], uint64_t coefficients[], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
}

int main()
{
    uint64_t LCG_state = 999111;

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<50; i++)
    {
    for(int i=0; i<10000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    keymix(x,key,coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key);
        result = x >> 32;
        //std::cout << result << "\n";
        }
    }
    }
}

 

---

A jednak wygląda na to, że te wyniki mogą być niepoprawne i nie można im ufać. Można w różny sposób zmodyfikować kod, powtórzyć niektóre operacje, a czas i tak się nie zmieni. Co więcej sposób mierzenia czasu za pomocą chrono daje 0 sekund:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <chrono>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    return LCG_state;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();
    uint64_t LCG_state = 333;
    uint32_t wynik;

    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        //std::cout << wynik << "\n";
    }

auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
}

Więc właściwie nie da się porównać obu kodów, skoro jeden wykonuje się ciągle w 0 sekund.

---

Kod z __asm__ volatile("" : "+g" (result) : :); mierzy czas poprawnie:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>
#include <chrono>

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = ((uint64_t)high32 << 32) | low32;
    return xsl;
}

uint64_t funct(uint64_t x, uint64_t key[])
{
    if(x >> 63)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    //x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));
    return x;
}

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

void keymix(uint64_t x, uint64_t key[], uint64_t coefficients[], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();

    uint64_t LCG_state = 999111;

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<10000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    keymix(x,key,coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key);
        result = x >> 32;
        __asm__ volatile("" : "+g" (result) : :);
        //std::cout << result << "\n";
        }
    }
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
}

Niestety ten branching jest bardzo kosztowny. Czasy, które uzyskuję to ok. 3,382 sekund. Natomiast dla LCG:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <chrono>

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    //if (LCG_state >> 63)
    //{
    //    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    //}
    //else
    //{
    //    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    //}
    //LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841) * (LCG_state >> 63) + (LCG_state * 2862933555777941757 + 1422359891750319841) * (~LCG_state >> 63);
    return LCG_state;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();

    uint64_t LCG_state = 333;
    uint32_t wynik;
    int r;

    //for(int i=0; i<10; i++)
    //{
    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        wynik = LCG_state >> 32;
        __asm__ volatile("" : "+g" (wynik) : :);
        //std::cout << wynik << "\n";
    }
    //}

auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
//std::cout << wynik << "\n";
}

Jest to około 0,967 sekund. Nieco lepiej jest po usunięciu warunków i zastosowaniu wzoru:

x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));

Ale niewiele lepiej. Kosztowny nie jest sam warunek, bo, gdy w LCG użyjemy:

if (LCG_state >> 63)
    {
        LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    }
    else
    {
        LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    }

Czas niemal się nie zmienia. Ale w tym przykładzie, co nie będzie wynikiem warunku, program w każdym przypadku liczy to samo. Jednak, gdy zmienimy jedną z instrukcji tak, aby nie były identyczne:

if (LCG_state >> 63)
    {
        LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);
    }
    else
    {
        LCG_state = (LCG_state * 2862933555777941757 + 555);
    }

To staje się to ok. 2,5-krotnie wolniejsze. Przy czym ostatni bit, który jest w warunku LCG_state >> 63 zmienia się praktycznie losowo. I ta nieprzewidywalność chyba ma znaczenie. Bo na przykład użycie bitu liczby k, która zmienia się regularnie od 0 do 3, znacznie przyspiesza program:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <stdint.h>
#include <chrono>

uint64_t XSLRRRR(uint64_t xsl)
{
    uint8_t count1;
    uint8_t count2;
    uint32_t low32;
    uint32_t high32;
    uint32_t x1;
    uint32_t x2;

    count1 = xsl >> 59;
    x1 = xsl ^ (xsl >> 32);
    low32 = (x1 >> count1) | (x1 << (32 - count1)) & 4294967295;
    x2 = xsl >> 32;
    count2 = low32 & 31;
    high32 = (x2 >> count2) | (x2 << (32 - count2)) & 4294967295;
    xsl = ((uint64_t)high32 << 32) | low32;
    return xsl;
}
uint64_t funct(uint64_t x, uint64_t key[], int k)
{
    if(k & 1)
    {
        x = x * key[0] + key[1];
    }
    else
    {
        x = (x >> 1) * key[2] + key[3];
    }
    //x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));
    return x;
}

//x = (x >> 63) * (x * key[0] + key[1]) + ((~x >> 63) * ((x >> 1) * key[2] + key[3]));

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;
}

void keymix(uint64_t x, uint64_t key[], uint64_t coefficients[], int k)
{
    key[3] = key[2];
    key[2] = key[1];
    key[1] = key[0];
    key[0] = ((XSLRRRR(x^coefficients[k]) << 1) ^ 1) & 18446744073709551615;
}

int main()
{
auto begin = std::chrono::high_resolution_clock::now();

    uint64_t LCG_state = 999111;

    uint64_t coefficients[4] = {3,5,7,9};
    uint64_t key[4] = {coefficients[0],coefficients[1],coefficients[2],coefficients[3]};

    uint64_t x;
    int k = 0;
    uint32_t result;

    for(int i=0; i<10000000; i++)
    {
    LCG_state = LCG(LCG_state);
    x = LCG_state;

    keymix(x,key,coefficients,k);
    k = (k+1) & 3;

        for(int j=0; j<64; j++)
        {
        x=funct(x,key,k);
        result = x >> 32;
        __asm__ volatile("" : "+g" (result) : :);
        //std::cout << result << "\n";
        }
    }
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
printf("Time measured: %.3f seconds.\n", elapsed.count() * 1e-9);
}

Więc na tę chwilę istnienie warunku if/else znacznie spowalnia kod w porównaniu do prostego LCG. I wydaje się tak być nie z powodu samego if/else, tylko dlatego, że musi być testowany bit, który zmienia się praktycznie losowo (tak jak pisałem, to są generatory liczb pseudolosowych, są zaprojektowane, by generować liczby właśnie w taki sposób, by symulować losowość), dopóki nie obliczymy liczby x, nie wiemy jaki bit się tam pojawi (0, czy 1).

Wydaje się, że w przypadku normalnych programów, czy nawet zwykłego generatora LCG, pewne instrukcje są wykonywane z wyprzedzeniem, podobnie jak w przypadku:

https://en.wikipedia.org/wiki/Branch_predictor

The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor.

Natomiast w przypadku mojego kodu to po prostu jest niemożliwe. Oczywiście kod można bardzo łatwo zwektoryzować/zrównoleglić, czego nie można zrobić z LCG. Wystarczy w moim kodzie z wyprzedzeniem obliczyć kilka:

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state + 11400714819323198486;
    return LCG_state;

A później dla każdego LCG_state równolegle pętle:

for(int j=0; j<64; j++)
        {
        x=funct(x,key,k);
        result = x >> 32;
        }

Ale w normalnym kodzie raczej nie da się wykorzystać tego podejścia.

---

Kosztowny nie jest sam warunek, bo, gdy w LCG użyjemy:

if (LCG_state >> 63) {

    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);

} else {

    LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);

}

Tu akurat wytłumaczenie jest proste - kompilator zauważa że oba wyrażenia są identyczne i wyrzuca ifa - więc procesor w ogóle nie widzi warunku.

I nie rób tego black boxa na wartość w środku ciasnej pętli, wystarczy ją uzyć raz na końcu pętli.