🚀 go-pugleaf

On Thursday, December 26, 2019 at 2:01:35 AM UTC+1, (fir) wrote:
> W dniu wtorek, 24 grudnia 2019 20:25:33 UTC+1 użytkownik M.M. napisał:
> > 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.
> > 
> 
> 4 sekundy na 4G intow to troche malo, wychodzi 1 nanosekunda na inta, czyli z 3 cykle na inta, byc moze jest to mozliwe jak wiekszosc tej roboty to 1 if i 1 inc czy cos takiego ale trzebby zdizasemblowac i zobazyc co to dokladnie jest (zief)

Zdaję sobie sprawę z tego że mogę mieć jakieś błędy w kodzie i rozumowaniu.
Dlatego wyciągnąłem z całości kodu kilka kluczowych wariantów i ich
kod zamieściłem w poście:
[
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
]

127 / 34 < 4 sekundy.

[
constexpr ultyp LOOPS = 1ull << 32;
]

2^32 > 4mld.


[
            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;
]

Wykonuje przez te niecałe 4 sekundy ponad:
12mld inkrementacji
8mld porównań
4mld sumowań
4mld pętli
4mld wyłuskań danych spod wskaźnika
4mld call (albo wstawił inline)
4mld return
4mld operacji bitowych AND


> sam przestalem sie specjalnie przejmowac takimi optymalizacjami po nauczeniu sie samego optymalizowania (tj robilbym je ale glownie w koncowym produkcie byc moze, normalnie to raczej uzywalbym zwyklego randa z modulo, ktory nie jest az tak strasznie wolny, tj pewnie z 10 ns zajmie )

Gdy piszę wspólny kawałek kodu (powiedzmy gdy piszę mikro-bibliotekę) to też
dbam o wydajność. Gdy ma coś w kółko liczyć przez lata (może na kilku
komputerach), to też dbam o wydajność.

Pozdrawiam