🚀 go-pugleaf

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)

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 )