• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Pomiary prędkości kilku PRNG w c++

0 głosów
68 wizyt
pytanie zadane 21 marca w C i C++ przez osobliwy nick Użytkownik (850 p.)

Mam 3 generatory PRNG, których czasy chcę zmierzyć. Xoroshiro128+

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

static inline uint64_t rotl(const uint64_t x, int k) {
	return (x << k) | (x >> (64 - k));
}

static uint64_t s[2] = {9,5};

uint64_t next(void) {
	const uint64_t s0 = s[0];
	uint64_t s1 = s[1];
	const uint64_t result = s0 + s1;

	s1 ^= s0;
	s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
	s[1] = rotl(s1, 37); // c

	return result;
}

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

    uint64_t result;

    for(int i=0; i<320000000; i++)
    {
    result = next();
    //std::cout << result << "\n";
    }
__asm__ volatile("" : "+g" (result) : :);
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);
}

Kod wzięty stąd: https://prng.di.unimi.it/xoroshiro128plus.c. Nie jestem pewny, czy tak to ma być wywoływane w praktyce.

Generator Lehmera 64-bitowy truncated (mój własny kod):

#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";
    }

__asm__ volatile("" : "+g" (wynik) : :);
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);
}


Oraz generator PCG:

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

uint32_t XSLRR(uint64_t xsl)
{
    uint32_t x32;
    uint8_t counter;

    counter = xsl >> 59;
    x32 = xsl ^ (xsl >> 32);
    xsl = (x32 >> counter) | (x32 << (32 - counter)) & 4294967295;
    return xsl;
}

uint64_t RXSMXS(uint64_t rxs)
{
    uint8_t counter;

    counter = rxs >> 59;
    rxs = rxs ^ (rxs >> (5 + counter));
    rxs = rxs*12605985483714917081;
    return rxs^(rxs >> 43);
}

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 = 71911;

    uint32_t result;

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

__asm__ volatile("" : "+g" (result) : :);
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);
}

To też mój własny kod, choć autorka coś tam zamieściła u siebie na stronie: https://www.pcg-random.org/download.html. Nie mogę się tam jednak doszukać normalnego kodu.

Robię pomiary czasu i otrzymałem następujące wyniki dla tych generatorów (PCG testuję tu akurat z mixerem XSLRR): 1.470, 1.063, 1.063. Zauważcie, że xoroshiro128+ ma mniej powtórzeń, bo zwraca liczby 64-bitowe, a ja chcę zmierzyć sekundy na bajt.

Problemy? Po pierwsze to są wyniki prof. Vigny, twórcy większości generatorów z rodziny xoroshiro:

https://prng.di.unimi.it

Są znacząco inne. Jego xoroshiro128+ przegania znacznie PCG 128/64 (wymaga uint128_t, których nie mogę u siebie użyć), który jest szybszy niż implementacja na liczbach 64-bitowych, czyli mój PCG 64/32. Więc w moich wynikach xoroshiro128+ powinien już w ogóle zdecydowanie przegonić PCG 64/32.

To są natomiast wyniki prof. Lemire:

https://opendatascience.com/testing-non-cryptographic-random-number-generators-my-results/

I jeszcze inne jego wyniki tutaj:

https://github.com/lemire/testingRNG

Natomiast tutaj prof. Vigna mocno skrytykował jego testy:

https://www.reddit.com/r/programming/comments/7478ca/xorshift128_xoroshiro128_and_xorshift1024_rngs/

Pisze tam między innymi, że:

he's measuring also a function call per generated number, since he doesn't do inlining (unrealistic) and that is responsible for half of the cycles you see, so differences are flattened?

Nie chciałbym popełnić również tych błędów. Jednocześnie nie wierzę w super-optymistyczne wyniki Vigny. Tak, czy inaczej Lemire nie jest specjalistą od generatorów PRNG i popełnił faktycznie kilka błędów (chociażby twierdząc, że Mersenne Twister zdaje PractRand, bo zrobił testy tylko do 64 GB..., dyskusja tutaj: he's measuring also a function call per generated number, since he doesn't do inlining (unrealistic) and that is responsible for half of the cycles you see, so differences are flattened?). Niewykluczone więc, że popełnił też jakieś błędy w swoich pomiarach prędkości.

Po drugie jest zbyt mała różnica pomiędzy samym LCG a PCG. PCG ma nakładkę w postaci miksera bitów XSLRR (lub nie ucinającego połowy bitów RXSMXS) i ona powinna spowalniać generator. W wynikach Lemire generator lehmer64 osiąga 0.63 cycles per byte, natomiast PCG 128/64 0.97 cycles per byte. Raczej takich różnic powinniśmy się spodziewać. Co zatem robię źle i co można poprawić, by moje wyniki były bardziej obiektywne?

komentarz 21 marca przez adrian17 Ekspert (320,820 p.)
edycja 21 marca przez adrian17

Zakładam że ostatni kod wkleiłeś przypadkiem? Bo on nie ma żadnego związku z PCG. Nie rozumiem też części

Nie mogę się tam jednak doszukać normalnego kodu.

Bo... to co jest centralnie na stronie to jest dokładnie źródło generatora. A niżej opcje pobrania bardziej obszernych gotowych bibliotek z przykładami.

W każdym razie jak wkleiłem PCG stamtąd (i przesunąłem black boxy asemblera) to dostałem na oko sensowne:

xoroshiro: Time measured: 0.489 seconds.
lcg: Time measured: 0.855 seconds.
pcg: Time measured: 0.934 seconds.

wymaga uint128_t, których nie mogę u siebie użyć

Przeinstaluj na kompilator 64-bitowy?

komentarz 21 marca przez osobliwy nick Użytkownik (850 p.)

Zakładam że ostatni kod wkleiłeś przypadkiem? Bo on nie ma żadnego związku z PCG.

To jest PCG, tyle, że wersja z mixerem XSLRR, są różne wersje:

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

Faktycznie ten kod na stronie jest w porządku, kompletnie go zignorowałem, bo szukałem wersji XSLRR w tych plikach do pobrania. A tutaj mamy output function XSHRR. Ta wersja też jest w porządku i dużo się nie różni.

W każdym razie jak wkleiłem PCG stamtąd (i przesunąłem black boxy asemblera) to dostałem na oko sensowne:

Może i tak to się ma. Dla mnie wyniki PCG i LCG są zbyt zbliżone, ale sugeruję się wyłącznie wynikami prof. Lemire, który dla 128-bitowych wersji dostał znaczny rozstrzał między PCG i LCG:

https://github.com/lemire/testingRNG

Choć nie wiem co za wersji mixera w PCG użył (nie mogę się tego doszukać na tej stronie), może bardziej kosztownej. Co to znaczy, że przesunąłeś black boxy asemblera?

Przeinstaluj na kompilator 64-bitowy?

Niedawno pobrałem zdaje się to:

https://sourceforge.net/projects/mingw-w64/

I według jakiegoś poradnika z YT pozaznaczałem jakieś 32-bitowe opcje, bo coś mi nie działało. Ale to jest chyba wersja 64-bitowa.

komentarz 21 marca przez osobliwy nick Użytkownik (850 p.)

Swoją drogą nie potrafię użyć tego kodu:

// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)

typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
    uint64_t oldstate = rng->state;
    // Advance internal state
    rng->state = oldstate * 6364136223846793005ULL + (rng->inc|1);
    // Calculate output function (XSH RR), uses old state for max ILP
    uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
    uint32_t rot = oldstate >> 59u;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

Jak mam wywołać uint32_t pcg32_random_r? To ma przyjmować jakieś argumenty? Napisałem swój kod, w nadziei, że nie będzie znaczących różnic:

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

uint64_t LCG(uint64_t LCG_state)
{
    LCG_state = LCG_state * 6364136223846793005 + 777;
}

uint32_t pcg32(uint64_t LCG_state)
{
    uint32_t xorshifted = ((LCG_state >> 18) ^ LCG_state) >> 27;
    uint32_t rot = LCG_state >> 59;
    return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

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

        uint64_t LCG_state = 5;
        uint32_t result;

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

__asm__ volatile("" : "+g" (result) : :);
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);
}

 

1
komentarz 21 marca przez Oscar Nałogowiec (26,110 p.)

Jakos tak:

 

pcg32_random_t rnd_ctx = {1234, 56};


for ()
{
    result = pcg32_random_r(&rnd_ctx);
}
komentarz 21 marca przez adrian17 Ekspert (320,820 p.)
Ja tylko dam uwagę na boku, że fakt że na tym etapie masz problemy z podstawami używania C (i jeszcze dwa dni temu nie wiedziałeś o optymalizacjach kompilatora), automatycznie podaje w wątpliwość jakiekolwiek wyniki jakie dostaniesz - osoba czytająca wyniki będzie miała zero pewności że w ogóle poprawnie użyłeś generatory, a co dopiero kompetentnie wziąłeś pod uwagę technikalia architektury i toolchaina, źródła szumów i błędów pomiarów etc.

Chcę przez to przekazać, że jest na takie badania znacząco za wcześnie :/
komentarz 21 marca przez osobliwy nick Użytkownik (850 p.)
edycja 21 marca przez osobliwy nick

Chcę przez to przekazać, że jest na takie badania znacząco za wcześnie :/

Zgadzam się, ale nie mam wyjścia muszę to zrobić, bo nikt za mnie tego nie zrobi. Tym bardziej, że na razie chodzi tylko o wyniki poglądowe. A potrzebuję tego, by w ogóle wiedzieć, czy pewne projekty, które rozważam są warte rozwijania - tak plus/minus.

Kolejna sprawa, to fakt, że zawracam tym głowę mądrzejszym od siebie. Współpracuję z naukowcem, który pomoże mi wykonać podobne testy profesjonalnie (ostatecznie je zlecimy lub wymyślimy coś innego, jeśli nie będzie miał czasu). Ale obecnie jesteśmy na etapie decyzji co w ogóle jest warte skupienia na tym większej uwagi, a co nie. Mam kilka generatorów, które rozważam i muszę sprawdzić mniej więcej co rokuje, a co nie. To co mogę chciałbym wykonać sam, a jeżeli będę musiał, to resztę zlecę profesjonalistom. Natomiast inicjatywa jest po mojej stronie i pomimo, że tak jak pisałem mam osobę, która w dłuższym horyzoncie czasowym pomoże mi to wykonać profesjonalnie, podstawy muszę zrobić sam, bo po prostu on nie ma dla mnie czasu. Co nie zmienia faktu, że za jakiś czas tak, czy inaczej spojrzy na to profesjonalnym okiem. Na razie to jest mocno wstępny etap prac.

komentarz 23 marca przez osobliwy nick Użytkownik (850 p.)
Wracając do tematu. Dlaczego w moich pomiarach LCG wypada identycznie jak PCG, a xoroshiro128+ jest 1,5-raza wolniejszy? Mierzę to w trybie release.

1 odpowiedź

0 głosów
odpowiedź 21 marca przez edutomek Dyskutant (8,260 p.)

Ciekawa kwestia. Takie dwie uwagi z boku, od osoby, która NIE JEST ekspertem w dziedzinie PRNG, ani nawet w dziedzinie takich pomiarów. Swego czasu też próbowałem mierzyć efektywność różnych algorytmów i stąd moje obecne uwagi. Nie należy ich traktować jako autorytatywnej odpowiedzi - raczej jako pewien głos w dyskusji.

1) Jeśli mierzysz prędkość, to czy uwzględniasz w jakiś sposób wpływ innych procesów działających w systemie operacyjnym na wyniki pomiarów? Jak można wyeliminować, albo choćby oszacować ten "szum"?

Jest to o tyle istotne, że gdyby ktoś zechciał odtworzyć Twoje wyniki (a to jest sens wszystkich badań naukowych), to powinno być to możliwe.

Pytanie takie zadawałem zawsze moim kolegom, zajmującym się m.in. pomiarami szybkości działania różnych procedur przetwarzania obrazów - i nigdy nie uzyskałem na nie satysfakcjonującej odpowiedzi. (Z drugiej strony nie sądzę, aby ta kwestia była bardzo istotna w takich badaniach, więc moje uwagi nie miały charakteru mocno krytycznego.)

Żeby była jasność, o czym piszę: uruchamiam sobie program do pomiarów, a w tle działa mi przeglądarka, z której akurat korzystam. Raz mogę mieć otwartych 10 zakładek, innym razem nawet 50. Jak to wpłynie na wynik pomiarów?

2) Odnośnie tego >>function call<< czy >>function inlining<<, to jako bardziej praktyk, niż teoretyk, zadałbym proste pytanie: który przypadek jest bardziej realistyczny?

Rozumiem, że na potrzeby badań można rozważyć >>function inlining<<, ale w produkcyjnym kodzie może być różnie. Będzie to zależało od tego, jak skompilujemy program, co będzie ważne w konkretnym przypadku. (Wyczytałem nawet kiedyś, że są kompilatory, które same podejmują tego typu decyzje.) Nie zawsze >>function inlining<< będzie najlepszym (najbardziej miarodajnym) rozwiązaniem. Czy wówczas wyniki badań, zrobionych w warunkach >>function inlining<<, będzie można wyrzucić do kosza?

W praktyce może być różnie. A skoro tak, to nie można a priori założyć, że badania zrobione dla >>function call<< są niewiarygodne, bo należało je zrobić dla >>function inlining<<. Należałoby raczej rozpatrzyć problem w obydwu skrajnych przypadkach.

Radziłbym przy tym odpowiednio dobrać kompilator, aby mieć nad tym kontrolę. (Swoją drogą, wcale bym się nie zdziwił, gdyby różne kompilatory, na różnych procesorach, dawały różne wyniki.)

Artykułów autorstwa wspomnianych ekspertów nie czytałem (i nie przeczytam - nie moja działka, brak czasu), ale czy ta krytyka nie dotyczy raczej samej metody badawczej? Jeśli będziesz robił badania stosując inlining, a ja zrobię swoje stosując function call, to wiadomo, że moje wyniki wykażą dłuższe czasy. Rzecz w tym, że takich wyników nie należy w ogóle porównywać.

Jeśli robisz badania na własne potrzeby, należałoby dobrać JEDNĄ metodę badawczą i trzymać się jej konsekwentnie.

3) Tak zupełnie na luźno:

Mam 3 generatory PRNG, których czasy chcę zmierzyć.

Takie sformułowanie na forum przejdzie, ale w pracy naukowej już nie. Bo co to jest czas PRNG?

Zresztą dalej piszesz, że mierzysz szybkość generacji losowych bitów przez różne PRNG - i to już ma sens.

komentarz 21 marca przez osobliwy nick Użytkownik (850 p.)
edycja 21 marca przez osobliwy nick

1) Jeśli mierzysz prędkość, to czy uwzględniasz w jakiś sposób wpływ innych procesów działających w systemie operacyjnym na wyniki pomiarów? Jak można wyeliminować, albo choćby oszacować ten "szum"?

Nie, staram się jedynie zapobiegawczo wyłączyć większość rzeczy działających w systemie. Ale nawet testy PractRand, które niemożebnie grzeją mój komputer paradoksalnie nie zawsze miały wpływ na wyniki. Czasami pomimo, że laptop nie robi nic szczególnego, wyniki skaczą do góry. Co świadczy o tym, że z tego punktu widzenia najprawdopodobniej robię to źle.

Jak to omijam? Robię testy kilkunastokrotnie na generatorze odniesienia i patrzę, które wyniki są najbardziej typowe. Gdy komputer zwraca mi nagle zastanawiający wynik i porównam to z moimi typowymi wynikami generatora odniesienia wiem przynajmniej, że akurat z czymś się musi mocno męczyć z tajemniczych przyczyn i test trzeba powtórzyć.

To oczywiście nie ma nic wspólnego z profesjonalnym, naukowym podejściem. Ale na razie chcę oszacować te prędkości tylko mniej więcej, dla własnej informacji i porównać je zwłaszcza z moimi własnymi PRNG, których tu nie przedstawiam.

(Swoją drogą, wcale bym się nie zdziwił, gdyby różne kompilatory, na różnych procesorach, dawały różne wyniki.)

To jest typowe. Autorka PCG wskazała nawet w swojej publikacji kompilatory, z którymi jej algorytmy działają najlepiej:

https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf

W praktyce może być różnie. A skoro tak, to nie można a priori założyć, że badania zrobione dla >>function call<< są niewiarygodne, bo należało je zrobić dla >>function inlining<<. Należałoby raczej rozpatrzyć problem w obydwu skrajnych przypadkach.

Można pójść jeszcze dalej i rozważać w ogóle prędkości przy praktycznych zastosowaniach na co zwrócono uwagę prof. Lemire tutaj:

https://lemire.me/blog/2019/03/19/the-fastest-conventional-random-number-generator-that-can-pass-big-crush/

Running the PRNGs in a tight loop just summing their results is typically not seen in practice: real-world applications perform some (more) computation with the random numbers.
Consider to change your timing setup a little bit and perform some (silly, but yet sufficient) computation, like the MonteCarlo determination of pi:

W tej publikacji autorzy na przykład rozpatrują różne przypadki praktycznych zastosowań w metodzie Monte Carlo (estymacje pi), a także Monte Carlo option pricing:

https://arxiv.org/pdf/2105.09578.pdf

A tutaj autorzy rozważają zastosowania swojego generatora w "small loop", "Fisher-Yates shuffle", "reservoir sampling", Monte Carlo:

https://arxiv.org/pdf/1810.02227.pdf

I oczywiście, nieco dziwnym trafem wychodzi im, iż pomimo, że ich algorytm nie jest najszybszy w małej pętli, to w praktycznych zastosowaniach jest najszybszy. Wniosek? Na pewno wielu autorów nie tylko dobiera sobie testy tak, aby pasowały do ich generatora, ale też dobiera sobie konkurencję, czyli generatory, z którymi się porównuje wybiórczo. Niemniej zwłaszcza ta publikacja pokazuje, że wyniki w praktycznych zastosowaniach mogą się odwrócić.

Tak, czy inaczej ja byłbym zwolennikiem porównywania PRNG raczej właśnie w prostych pętlach, jeżeli tworzymy PRNG ogólnego przeznaczenia, bo to jest chyba najbardziej obiektywne. Co innego, jeżeli ktoś postawi sobie za cel stworzenie PRNG typowo do np. symulacji Monte Carlo, wtedy jest zrozumiałe, że testuje PRNG w takich zastosowaniach.

A tak poza tym, to nie do końca rozumiem o co chodzi z tym function inlining. Domyślam się, iż chodzi o to, że samo wywołanie funkcji zajmuje jakiś czas, tak? Ale jak to pominąć?

Artykułów autorstwa wspomnianych ekspertów nie czytałem (i nie przeczytam - nie moja działka, brak czasu), ale czy ta krytyka nie dotyczy raczej samej metody badawczej? Jeśli będziesz robił badania stosując inlining, a ja zrobię swoje stosując function call, to wiadomo, że moje wyniki wykażą dłuższe czasy. Rzecz w tym, że takich wyników nie należy w ogóle porównywać.

Chyba nie. Jeżeli same generatory różnią się od siebie prędkościami dwukrotnie, jeden generuje n bitów na sekundę, a drugi na 2 sekundy, a będziemy mierzyć na przykład czas wypisania 1000 liczb, gdzie wpisanie jednej liczby zajmuje 0,1 sekundy, to otrzymamy czasy 101 sekund u 102 sekundy. Wypłaszaczy to wyniki i generatory, które różniły się o czynnik 2 nagle będą różnić się o niecały 1%. Chyba o to chodziło Vignie. Nie mam jednak pojęcia, która metoda jest lepsza. Nie można też zmierzyć działania w taki sposób, którego w ogóle w praktyce nie doświadczymy, bo to trochę jakby mierzyć maks. prędkość auta w tunelu próżniowym, pomijając opory powietrza. Z drugiej strony nie można też zrobić tego zupełnie z marszu i pewne czynniki zakłócające należy wyeliminować. Ale naprawdę nie wiem kto z tej dwójki ma rację.

Takie sformułowanie na forum przejdzie, ale w pracy naukowej już nie. Bo co to jest czas PRNG?

Zresztą dalej piszesz, że mierzysz szybkość generacji losowych bitów przez różne PRNG - i to już ma sens.

Oczywiście masz rację. Chcę zmierzyć konkretnie tak jak Vigna na swojej stronie ns/64 bity lub cykle na bajt. Niemniej na razie zadowolę się prostym execution time, byle wykonać test bez jakichś rażących błędów zakłócających wyniki.

komentarz 21 marca przez edutomek Dyskutant (8,260 p.)

Akurat się wyrobiłem z pewnym nietypowym zleceniem (udało się przed północą, hura!), to postanowiłem przed snem zajrzeć do tego wątku, który mnie tak zaciekawił.

To oczywiście nie ma nic wspólnego z profesjonalnym, naukowym podejściem.

Z ciekawości: wiesz, jak to się robi profesjonalnie i naukowo, czy nie? (Ja nie wiem, to się dopytuję. Akurat tego typu badań nigdy nie prowadziłem.)

To, co napisałeś o wykonywaniu wielu pomariów i odrzucaniu tych skrajnych, jest akurat normalnym podejściem. (Nawet są testy statystyczne pozwalające oszacować prawdopodobieństwo, że wynik jest jakąś "anomalią".)

Sugestia: podawaj wyniki zarówno dla skrajnych wartości pomiarów (min, max), jak i dla średniej.

Swoją drogą, przydałoby się również powtórzyć te testy na jakimś innym komputerze. Uzyskanie podobnych wyników (w sensie porównawczym: np. PRNG1 jest nieco szybszy, niż PRNG2) może sugerować (uwaga: może, nie: sugeruje), że "odszumienie zakłóceń" jest skuteczne.

A tak poza tym, to nie do końca rozumiem o co chodzi z tym function inlining. Domyślam się, iż chodzi o to, że samo wywołanie funkcji zajmuje jakiś czas, tak? Ale jak to pominąć?

inlining = kompilator zastępuje funkcję jej kodem. Wtedy unikamy operacji wykonywanych przez procesor w związku z wywołaniem funkcji (np. odkładania na stosie argumentów; nie pamiętam już dokładnie takich szczegółów niskopoziomowych). To niby mało (krótki czas, kilka cykli procesora?), ale jak robić to kilka tysięcy razy w pętli, a potem porównać z czasem uzyskanym poprzez >>function inlining<<, różnica może być znacząca. Zwłaszcza, gdy istotne są milisekundy.

(Jak to pominąć? To już zależy od kompilatora. Niektóre pewnie mają takie opcje, inne nie. Ale Ty, jako badacz, MUSISZ nad tym panować, MUSISZ wiedzieć, co tam się dzieje.)

Podejrzewam, że o to chodziło jednemu z autorów, którego przytoczyłeś. Mogłoby to wskazywać na istotny błąd związany z metodą wykonywania pomiarów.

Rzecz w tym, że aby coś z czymś porównać, trzeba dobrze ustalić kryteria porównania. To jak z jabłkami i pomarańczami: które są lepsze? Nie da się odpowiedzieć na to pytanie. Ale jeśli zaczniemy je ważyć (masa), to już porównanie będzie miało sens.

Myślę, że nie chodzi o to, aby dyskutować o inliningu, czy o function call, tylko o to, aby wybrać JEDNĄ z tych metod i wszystkie pomiary przeprowadzić w taki sam sposób. Takie wyniki będzie można ze sobą porównać.


Jeszcze jedna uwaga od praktyka: poczas pomiarów czasu nie zapisuj nigdzie liczb. Żadne stdout, żaden plik - to wszystko są operacje i/o, które zajmują czas i zwiększają szum. "Byłem tam, robiłem to", wiem, że nie warto. (No, chyba że człowiek chce zmierzyć prędkość i/o.)

 

A na marginesie dyskusji o praktycznych zastosowania PRNG: kiedyś używałem PRNG w taki sposób, że wygenerowałem pewną liczbę liczb pseudolosowych (np. 10000) i używałem tej sekwencji aż do momentu, kiedy potrzebowałem kolejnych. Potem generowałem kolejne 10000 i tak dalej. I co Ty na to? Wpadłbyś na taki przypadek użycia?

Życie bywa zaskakujące.

Dlatego wybierz jedną metodę i tego się trzymaj. Bo nie przewidzisz, co takiemu edutomkowi jutro do łba strzeli i jak mu się spodoba PRNG wykorzystać.

Dzięki za ciekawą dyskusję!

komentarz 21 marca przez osobliwy nick Użytkownik (850 p.)
edycja 21 marca przez osobliwy nick

Z ciekawości: wiesz, jak to się robi profesjonalnie i naukowo, czy nie? (Ja nie wiem, to się dopytuję. Akurat tego typu badań nigdy nie prowadziłem.)

Nie wiem. Pomiary czasu działania programów są dla mnie czymś obcym. A też programista ze mnie słaby. Moje zainteresowania skupiają się na hipotezie Collatza (i jej generalizacjach), generatorach PRNG i algorytmach szyfrujących. Jak dotychczas analiza matematycznych zależności, artefaktów w tego rodzaju ciągach, struktur\hierarchii bitów nie wymagała ode mnie za wiele umiejętności programistycznych. Ale im dalej w las, tym trudniej. Pewnych badań nie da się uniknąć, jeśli chce się rozwijać, zwłaszcza praktyczne pomysły (i do tego potrzebne jest programowanie). O ile moje pomysły praktycznych zastosowań algorytmów z pogranicza obszarów, które wymieniłem mają raczej solidne matematyczne podstawy - mniej pewne jest, czy faktycznie mogą być wydajne i tym samym przydatne w praktyce. To po prostu trzeba zaprogramować i zmierzyć. Tak więc nieco z konieczności muszę chociaż poskrobać po powierzchni i zrobić przynajmniej przybliżone szacunki.

A na marginesie dyskusji o praktycznych zastosowania PRNG: kiedyś używałem PRNG w taki sposób, że wygenerowałem pewną liczbę liczb pseudolosowych (np. 10000) i używałem tej sekwencji aż do momentu, kiedy potrzebowałem kolejnych.

Moim celem jest stworzenie generatora przede wszystkim do zastosowań w obliczeniach równoległych (Massively Parallel Processing), łatwego i szybkiego w parametryzacji (większość generatorów nawet nie jest parametryzowalnych, choć pozwala zwykle na przeskoczenie o pewną liczbę liczb do przodu, w celu uruchomienia kolejnego strumienia bez ryzyka nakładania się i kolizji, czyli, który będzie praktycznie niezależny, ale zwykle albo robi to wolno, albo wymaga użycia generatora o względnie dużym stanie). W tego rodzaju prostych zastosowaniach jak powyżej właściwie każdy generator będzie dobry. Jak to powiedział George Marsaglia

A random number generator is like sex; When it's good, it's wonderful, And when it's bad, it's still pretty good.

Dopiero, gdy przychodzi do symulacji, które robią np. naukowcy z CERN w celu symulowania eventów wysokiej energii, rozwiązywania lattice QCD w chromodynamice kwantowej, modelowanie Isinga albo renderowanie dużych chmur punktów (gdzie potrzeba np. tasowania 100 mln punktów na sekundę), czy metoda Monte Carlo Tree Serach w AI, pewne przewagi mogą mieć znaczenie - zarówno, jeśli chodzi o jakość, jak i o prędkość.

komentarz 22 marca przez Oscar Nałogowiec (26,110 p.)
Mam taki pomysł: może zamiast mierzyć czas analizujcie uzyskany kod maszynowy. W sumie te pokazane funkcje są proste, to pewnie nie więcej niż kilkadziesiąt instrukcji procka, jak wspomniano wcześniej trudno mierzyć czas wykonania takiego kodu bo to bardzo mało i nawet proste dodatkowe czynności, jak np wywołanie funkcji wpływają istotnie na wynik. Oczywiście dzisiejsze procki mają na tyle skomplikowaną architekture, że nawet ten sam kod może mieć różny czas wykonania w zależności od różnych czynników (różne cache itp). Wydaje mi się jednak, że porównanie uzyskanych kodów jest bardziej niezależne od sprzętu i systemu (jak wiadomo, komputery są coraz szybsze i wyniki sprzed roku mogą nie nadawać się do porównania z aktualnymi).

A jeśli już pozostawać przy testach praktycznych to niektóre procki mają liczniki taktów zegara - zamiast czytać zegarek RTC może lepiej tak sprawdzać czas wykonania.
komentarz 22 marca przez osobliwy nick Użytkownik (850 p.)

Szacowałem w ten sposób na oko kod:

#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[])
{
    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()
{
    double a = 0;

    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;
    uint64_t result;

    for(int i=0; i<100; i++)
    {
    auto begin = std::chrono::high_resolution_clock::now();
    for(int i=0; i<5000000; 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;
        }
    }
    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);
    a = a + (elapsed.count() * 1e-9);
    }
__asm__ volatile("" : "+g" (result) : :);
std::cout << a/100;
}

Będąc przekonanym, że będzie praktycznie nie różnił się od:

#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();

    double a = 0;
    uint64_t LCG_state = 333;
    uint32_t result;

    for(int i=0; i<100; i++)
    {
    auto begin = std::chrono::high_resolution_clock::now();
    for(int i=0; i<640000000; i++)
    {
        LCG_state = LCG(LCG_state);
        result = LCG_state >> 32;
    }
    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);
    a = a + (elapsed.count() * 1e-9);
    }
__asm__ volatile("" : "+g" (result) : :);
std::cout << a/100;
}

Oba programy robią przez większość czasu to samo, mnożą liczby. Jeden robi to zgodnie ze wzorem:

LCG_state = (LCG_state * 2862933555777941757 + 1422359891750319841);

A drugi:

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

Co można też rozpisać jako:

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

Przy czym x >> 63 raz jest równe 1, a raz 0. Więc niezależnie od wyniku nie dokładamy programowi mnożeń z dodawaniem (zawsze wykonuje tylko jedno mnożenie i jedno dodawanie). I co się okazało? Że ten kod jest prawie 1.5-2 razy wolniejszy, tylko dlatego bo mamy tam warunek. Także na nic się zdały szacunki, a wyniki okazały się dość paradoksalne.

Podobne pytania

0 głosów
2 odpowiedzi 180 wizyt
pytanie zadane 13 kwietnia 2019 w C i C++ przez Pirat150 Nowicjusz (120 p.)
0 głosów
2 odpowiedzi 529 wizyt
0 głosów
3 odpowiedzi 155 wizyt
pytanie zadane 26 lipca 2017 w Nasze projekty przez Lebowski Początkujący (330 p.)

88,381 zapytań

136,985 odpowiedzi

305,727 komentarzy

58,643 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...