🚀 go-pugleaf

Czasami potrzebuję całkowite liczby pseudolosowe z małego 
przedziału, przy czym losowość tychże liczb nie musi być
wysokiej jakości, ale za to generowanie musi być bardzo 
szybkie. Standardowy sposób na uzyskanie takich liczb jest 
zapewne wszystkim czytelnikom tej grupy znany, ale przypomnijmy:

random() % (MAX-MIN+1) + MIN;

Od razu widać zabójczą dla wydajności operację modulo :/ Co
można na to poradzić? Mój pierwszy pomysł był taki, aby zgrać
do tablicy np. milion liczb, a potem z tej tablicy te liczby w
kółko podawać. Cóż może być wydajniejszego, niż podawanie kolejnych
liczb z pamięci RAM? Niestety tablica o rozmiarze miliona elementów
to lekkie marnotrawienie pamięci RAM i nie wiadomo jak procesor
takie tablice będzie buforował w większych programach. Zastosowałem
więc rozwiązanie z użyciem dwóch buforów:

buff1[SIZE1];
buff2[SIZE2];

( albo jednego łączonego buff[SIZE1+SIZE2] )

przy czym SIZE1 i SIZE2 to są liczby pierwsze z przedziału 
około <100,10000>. Można podawać na przemian liczby z bufora1 i 
bufora2, cykl takiego 'generatora' wyniesie size1*size2 (po
wygenerowaniu tylu liczb można bufory zapełnić nowymi liczbami, to
niewiele spowolni generator, bo jest mało generowania w stosunku
do podawanych liczb).

 
No więc teoria jest prosta, pora zabrać się kodowanie. Jednak są niespodzianki.
Generator std::mt19937_64 wygenerował 4mld liczb z przedziału od 11 do 38 w
około 27 sekund. Natomiast ta sztuczka z dwoma tablicami potrzebowała aż
35 sekund! Czyli zamiast przyspieszenia uzyskałem spowolnienie. Implementacja
tej wersji jest w załączonym kodzie na dole w klasie RndBuff1. Nie poddawałem
się, zamiast statycznej tablicy użyłem dynamicznie przydzielonej przez
new - myślę sobie, a może kompilator lepiej da radę z new. Okazało się, że jest
jeszcze gorzej, czas wzrósł do 38s - to jest w klasie RndBuff2. Dopiero jak
dodałem wskaźniki i kilka usprawnień instrukcji warunkowych, czas spadł do...
zaledwie 4 sekund - to jest w klasie RndBuff3. Dla pewności sprawdziłem jeszcze
kombinację z tablicą (zamiast new) i wskaźnikami. Czas z powrotem wzrósł do
11 sekund - kod w RndBuff4. 

Po 34 pomiarach czasu, wyniki wyglądają tak:
seed [911368664458670987] nr.:34
raw mt start   105226567093 872
RndBuff1 start 105232396785 1210
RndBuff2 start 105232396785 1267
RndBuff3 start 105232396785 127
RndBuff4 start 105232396785 397

Widać że czas pomiędzy najlepszą i najgorszą wersją różni się aż 10 razy, a
kod ciągle bardzo podobny i oczywiste optymalizacje spowalniają!

Suma kontrolna z raw mt jest inna, bo też jest inny algorytm generowania - to
nie stanowi błędu.

Niezrozumiałe jest dla mnie, dlaczego są tak duże różnice w czasie przy
tak niewielkich zmianach.

Pouczające jest to, że jeśli już chcemy mieć kawałek wydajnego kodu, to
niewielkie zmiany mogą dawać  10-krotne przyspieszenie. I to, że oczywista
optymalizacja może tak naprawdę spowolnić nasz kod.

Pozdrawiam


Zawsze mogłem popełnić jakieś błędy (choć sumy kontrolne się zgadzają), więc
będę wdzięczny za krytykę:

#include <iostream>
#include <random>
#include <ctime>

using ultyp = unsigned long long;
using utyp  = unsigned int;
using cultyp = const ultyp;
using cutyp  = const utyp;

template<class TRND,cutyp SIZE1, cutyp SIZE2>
class RndBuff1 {
private:
    TRND  &rnd;   // Pseudo random number generator.
    utyp  min;    // Min range.
    utyp  max;    // Max range.
    utyp  buff[SIZE1+SIZE2];   // N-Cyclic buffer to number generator.
    utyp  i1,i2;  // Index to the next given value.
    utyp  select; // Select first or second buffer.

private:
    void reset() {
        for( utyp i=0 ; i<SIZE1+SIZE2 ; i++ ) {
            buff[i] = rnd() % (max-min+1)+min;
        }
    }
public:
    RndBuff1( TRND &rnd, cutyp min=0, cutyp max=0 ) : rnd(rnd) {
        setMinMax(min,max);
    }
    void setMinMax(cutyp min, cutyp max   ) {
        this->min = min;
        this->max = max;
        i1 = SIZE1;
        i2 = SIZE1+SIZE2;
        select = 0;
    }
    utyp operator()() {
        if( i1 == SIZE1 && i2 == SIZE1+SIZE2 ) {
            reset();
        }
        if( 1 & select++ ) {
            if( i1 == SIZE1 ) {
                i1 = 0;
            }
            return buff[i1++];
        }
        if( i2 == SIZE1+SIZE2 ) {
            i2 = SIZE1;
        }
        return buff[i2++];
    }

};

template<class TRND,cutyp SIZE1, cutyp SIZE2>
class RndBuff2 {
private:
    TRND  &rnd;   // Pseudo random number generator.
    utyp  min;    // Min range.
    utyp  max;    // Max range.
    utyp  *const buff;   // N-Cyclic buffer to number generator.
    utyp  i1,i2;  // Index to the next given value.
    utyp  select; // Select first or second buffer.

private:
    void reset() {
        for( utyp i=0 ; i<SIZE1+SIZE2 ; i++ ) {
            buff[i] = rnd() % (max-min+1)+min;
        }
    }
public:
    RndBuff2( TRND &rnd, cutyp min=0, cutyp max=0 ) : rnd(rnd), buff(new utyp[SIZE1+SIZE2]) {
        setMinMax(min,max);
    }
    ~RndBuff2() {
        delete[]buff;
    }
    void setMinMax(cutyp min, cutyp max) {
        this->min = min;
        this->max = max;
        i1 = SIZE1;
        i2 = SIZE1+SIZE2;
        select = 0;
    }
    utyp operator()() {
        if( i1 == SIZE1 && i2 == SIZE1+SIZE2 ) {
            reset();
        }
        if( 1 & select++ ) {
            if( i1 == SIZE1 ) {
                i1 = 0;
            }
            return buff[i1++];
        }
        if( i2 == SIZE1+SIZE2 ) {
            i2 = SIZE1;
        }
        return buff[i2++];
    }

};


template<class TRND,cutyp SIZE1, cutyp SIZE2>
class RndBuff3 {
private:
    TRND  &rnd;   // Pseudo random number generator.
    utyp  min;    // Min range.
    utyp  max;    // Max range.
    utyp  *const buff;  // N-Cyclic buffer to number generator.
    cutyp *i1;          // Index to the next given value.
    cutyp *i2;
    utyp  select; // Select first or second buffer.

private:
    void reset() {
        for( utyp i=0 ; i<SIZE1+SIZE2 ; i++ ) {
            buff[i] = rnd() % (max-min+1)+min;
        }
    }
public:
    RndBuff3( TRND &rnd, cutyp min=0, cutyp max=0 ) : rnd(rnd), buff(new utyp[SIZE1+SIZE2]) {
        setMinMax(min,max);
    }
    ~RndBuff3() {
        delete[] buff;
    }
    void setMinMax(cutyp min, cutyp max) {
        this->min = min;
        this->max = max;
        i1 = buff+SIZE1;
        i2 = buff+SIZE1+SIZE2;
        select = 0;
    }
    utyp operator()() {
        if( 1 & select++ ) {
            if( i1 == buff+SIZE1 ) {
                if( i2 == buff+SIZE1+SIZE2 ) {
                    reset();
                }
                i1 = buff;
            }
            return *i1++;
        } else {
            if( i2 == buff+SIZE1+SIZE2 ) {
                if(i1 == buff+SIZE1) {
                    reset();
                }
                i2 = buff+SIZE1;
            }
            return *i2++;
        }
    }

};


template<class TRND,cutyp SIZE1, cutyp SIZE2>
class RndBuff4 {
private:
    TRND  &rnd;   // Pseudo random number generator.
    utyp  min;    // Min range.
    utyp  max;    // Max range.
    utyp  buff[SIZE1+SIZE2];  // N-Cyclic buffer to number generator.
    cutyp *i1;          // Index to the next given value.
    cutyp *i2;
    utyp  select; // Select first or second buffer.

private:
    void reset() {
        for( utyp i=0 ; i<SIZE1+SIZE2 ; i++ ) {
            buff[i] = rnd() % (max-min+1)+min;
        }
    }
public:
    RndBuff4( TRND &rnd, cutyp min=0, cutyp max=0 ) : rnd(rnd) {
        setMinMax(min,max);
    }
    void setMinMax(cutyp min, cutyp max) {
        this->min = min;
        this->max = max;
        i1 = buff+SIZE1;
        i2 = buff+SIZE1+SIZE2;
        select = 0;
    }
    utyp operator()() {
        if( 1 & select++ ) {
            if( i1 == buff+SIZE1 ) {
                if( i2 == buff+SIZE1+SIZE2 ) {
                    reset();
                }
                i1 = buff;
            }
            return *i1++;
        } else {
            if( i2 == buff+SIZE1+SIZE2 ) {
                if(i1 == buff+SIZE1) {
                    reset();
                }
                i2 = buff+SIZE1;
            }
            return *i2++;
        }
    }

};


constexpr ultyp LOOPS = 1ull << 32;
constexpr utyp  MIN = 11;
constexpr utyp  MAX = 38;
constexpr utyp  SIZE1 = 1249;
constexpr utyp  SIZE2 = 1699;


int main() {
    cultyp mainSeed = 1234567890ull;
    time_t times[5] = {0,0,0,0,0};
    std::mt19937_64 rnd, rndSeed(mainSeed);

    for( utyp test=0 ; true ; test++ ) {
        cultyp seed = rndSeed();
        std::cout << "seed [" << seed << "] nr.:" << (test+1) << std::endl;

        {
            std::cout << "raw mt start   ";
            ultyp sum = 0;
            rnd.seed( seed );
            std::uniform_int_distribution<int> dist(MIN,MAX);
            const time_t start = time(NULL);
            for( ultyp loop=0 ; loop<LOOPS ; loop++ ) {
                sum += dist( rnd );
            }
            times[0] += time(NULL) - start;
            std::cout << sum << " " << times[0] << std::endl;
        }
        {
            std::cout << "RndBuff1 start ";
            ultyp sum = 0;
            rnd.seed( seed );
            RndBuff1<std::mt19937_64,SIZE1,SIZE2> rndBuf(rnd,MIN,MAX);
            const time_t start = time(NULL);
            for( ultyp loop=0 ; loop<LOOPS ; loop++ ) {
                sum += rndBuf();
            }
            times[1] += time(NULL) - start;
            std::cout << sum << " " << times[1] << std::endl;
        }
        {
            std::cout << "RndBuff2 start ";
            ultyp sum = 0;
            rnd.seed( seed );
            RndBuff2<std::mt19937_64,SIZE1,SIZE2> rndBuf(rnd,MIN,MAX);
            const time_t start = time(NULL);
            for( ultyp loop=0 ; loop<LOOPS ; loop++ ) {
                sum += rndBuf();
            }
            times[2] += time(NULL) - start;
            std::cout << sum << " " << times[2] << std::endl;
        }
        {
            std::cout << "RndBuff3 start ";
            ultyp sum = 0;
            rnd.seed( seed );
            RndBuff3<std::mt19937_64,SIZE1,SIZE2> rndBuf(rnd,MIN,MAX);
            const time_t start = time(NULL);
            for( ultyp loop=0 ; loop<LOOPS ; loop++ ) {
                sum += rndBuf();
            }
            times[3] += time(NULL) - start;
            std::cout << sum << " " << times[3] << std::endl;
        }
        {
            std::cout << "RndBuff4 start ";
            ultyp sum = 0;
            rnd.seed( seed );
            RndBuff4<std::mt19937_64,SIZE1,SIZE2> rndBuf(rnd,MIN,MAX);
            const time_t start = time(NULL);
            for( ultyp loop=0 ; loop<LOOPS ; loop++ ) {
                sum += rndBuf();
            }
            times[4] += time(NULL) - start;
            std::cout << sum << " " << times[4] << std::endl;
        }

    }


    return 0;
}