3. Schnelles erzeugen vieler Zufallswerte

Schnelles erzeugen vieler Zufallswerte

  • T

    Wenn du das erzeugen der Zufallszahlen möglichst gutparallelisieren möchtest würde ich mehrere Threads erzeugen die jeweils vectoren mit einer festen Anzahl von Zufallszahlen erstellen und in eine eigene queue (z.B. boost c++ lock-free queue oder shared queue) stellen. Ein Thread klappert dann die queues ab und verarbeitet die Zufallszahlen.

    0
  • ?

    Danke, denke die Idee mit der festen Anzahl sollte gut und schnell funktionieren 🙂

    0

  • @TNA
    Glaub nicht dass man hier ne lock-free Queue braucht.
    Ausreichend grosse Blöcke und das Bisschen Mutex-gelocke geht in der Messungenauigkeit unter.

    @volkard
    Glaub auch nicht dass das RAM zu belasten so ne Tragik wäre.
    Erstmal hat man ja eh eim paar MB Cache, und dann hat man heutzutage üblicherweise ne Speicherbandbreite jenseits der 20 GB/Sek wenn man linear liest bzw. schreibt. Und das würde man hier ja.

    OK, 1 Mio. Zahlen ist vielleicht übertrieben, aber so ein paar kB pro Block, einfache Producer-Comsumer-Queue (so ganz klassisch mit Mutex+Condition-Variable) and Bob's your uncle.

    0
  • ?

    Hier ist ein XOR-Shift auf AVX Basis. Der erzeugt Dir pro Call 8 32 bit Zufallszahlen. Ob die bits ebenfalls vernuenftig zufallsverteilt sind, muss ein mathematisch Begabterer als ich beurteilen. (Gilt aber auch fuer mt19337 et. al.)

    SSE Code habe ich auch, aber neuere x86 CPUs unterstuetzen ja alle AVX. Der Code ist deutlich schneller als mt19937 aus der stdlib. In Deinem Fall wahrscheinlich erheblich, da Du ja mit einem Aufruf 32 8bit Werte bekommst, die eigentlich immer komplett im 1st level cache liegen sollten. MT19937 erzeugt intern ein viel grosseres Feld von Zahlen mit einem deutlich komplizierteren Algo. Ob Du dessen Verteilung brauchst oder ob Dir XOR Shift reicht, musst Du selbst beurteilen.

    #include <cstdint>

#include "emmintrin.h"

// seed can default to 3141592654
void rng_xorShift_seed( uint32_t seed )
{
	cur_seed_AVX = _mm256_set_epi32( seed, seed<<1, seed>>1, seed^seed+7 , seed^seed+9, seed<<2, seed>>2, seed^seed+13 );
}

/*
 * see:  http://de.wikipedia.org/wiki/Xorshift
 * uint32_t xorshift32() 
 * {
 *     static uint32_t x = 314159265; // seed
 *     x ^= x << 13;
 *     x ^= x >> 17;
 *     x ^= x << 5;
 *     return x;
 * }
 * @param result pointer to an eight element array of 32 bit ints
 */
void rng_xorShift( uint32_t* result )
{
	// x ^= x << 13;
	cur_seed_AVX = _mm256_xor_si256(cur_seed_AVX, _mm256_slli_epi32( cur_seed_AVX, 13 ));
	// x ^= x >> 17;
	cur_seed_AVX = _mm256_xor_si256(cur_seed_AVX, _mm256_srli_epi32( cur_seed_AVX, 17 ));
	// x ^= x << 5;
	cur_seed_AVX = _mm256_xor_si256(cur_seed_AVX, _mm256_slli_epi32( cur_seed_AVX, 5 ));

	_mm256_storeu_si256( (__m256i*) result, cur_seed_AVX);
}

    Bitte dabei darauf achten, dass result aligned sein muss (align 64, damit das Ergebnis immer auf einer 1st Level cache line liegt):

    __declspec(align(64)) array<uint32_t, 8> result;
    0
  • T

    hustbaer schrieb:

    @TNA
    Glaub nicht dass man hier ne lock-free Queue braucht.
    Ausreichend grosse Blöcke und das Bisschen Mutex-gelocke geht in der Messungenauigkeit unter.

    Da wirst du wohl recht haben, insbesondere wenn jeder Thread seinen eigene Queue hat. Lock-free ist meiner Erfahrung nach insbesondere sinnvoll wenn aus irgendwelchen Gründen viele Threads auf eine Queue zugreifen müssen, ansonsten fährt man besser mit einer Locked queue. die Kann man sich mit C++11 std::condition_variable, std::mutex und std::queue auch recht einfach selber basteln, wenn es kein boost sein soll.

    0
  • ?

    Hab das "ohne" Locking gelöst:

    mit std::future und std::async die entsprechende Erzeugungsfunktion aufgerufen und dann mit std::move effizient bei std::future::get übertragen.

    mit std::packeged_task kann die Funktion auch immer wieder resetten ( zum mehrmaligen aufrufen)

    Zu RdRand:
    Wie verbreitet ist dieser Befehl auf den Chipsätzen?
    Kennt jmd ne gute Referenzseite, wo ich u.a. die Syntax ablesen kann?
    Kann ich das ohne große Probleme mit inline asm aufrufen?

    0
  • E

    Ein linearer Kongruenzgenerator schafft ja wohl doch noch deutlich mehr als ein Mersenne Twister was die Geschwindigkeit angeht.

    Also std::linear_congruential_engine

    0

  • Ethon schrieb:

    Ein linearer Kongruenzgenerator schafft ja wohl doch noch deutlich mehr als ein Mersenne Twister was die Geschwindigkeit angeht.

    Also std::linear_congruential_engine

    Ich sag mal: nein, ganz im Gegenteil. Siehe auch den von mir geposteten Vergleich.

    Ansonsten poste bitte ne URL mit nem Benchmark aus dem das hervorgeht bzw. eigenen Benchmark-Code + Ergebnisse.

    0
  • ?

    In obigem Code fehlte noch:

    __declspec( align(64) ) static __m256i cur_seed_AVX; // seed for 32 bit random numbers

    Will man den Code aus mehreren Threads heraus benutzen packt man die Funktionen und den cur_seed_AVX besser in eine Klasse.

    0
  • O

    @XORSHIFT viel zu kompliziert. wenn du breits AVX hast, hast du oft auch die AES extension. Dan reichts einfach einen zähler hochzuzählen, den seed als schlüssel wählen und 256 pseudo-zufällige bits über AES zu erhalten.

    0
  • ?

    otze schrieb:

    256 pseudo-zufällige bits über AES zu erhalten.

    Das klingt interessant. Leider habe ich keine entsprechenden Befehl gefunden der 256 bit liefert (s. https://software.intel.com/sites/landingpage/IntrinsicsGuide/ ) da gibt es nur 128 bit Befehle, die z.T. deutlich komplexer sind als der gesamte ablauf bei XOR-Shift

    0

  • @otze
    Bleiben zwei Fragen: wie schnell ist die Sache und wie gut ist so ein "AES-Counter-Generator".

    0
  • C

    hustbaer schrieb:

    Bleiben zwei Fragen: wie schnell ist die Sache

    ca. 3.3GB/s auf einem 3570k. (TrueCrypt Benchmark ;))

    hustbaer schrieb:

    und wie gut ist so ein "AES-Counter-Generator".

    Perfekt. Bessere Pseudo-Zufallszahlen wirst du nicht bekommen. Das ist ja der Sinn der Sache, dass man verschluesselte Daten nicht von random Noise unterscheiden kann.

    Aber so viel einfacher als die paar instructions da oben sind die AES instructions jetzt auch nicht, und fuer den TE stellt sich eh die Frage ob seine Anforderungen wirklich nur durch inline-assembler erfuellt werden koennen oder ob die ganz normalen standard Generatoren richtig angewandt nicht schon reichen.

    0

  • cooky451 schrieb:

    hustbaer schrieb:

    und wie gut ist so ein "AES-Counter-Generator".

    Perfekt. Bessere Pseudo-Zufallszahlen wirst du nicht bekommen. Das ist ja der Sinn der Sache, dass man verschluesselte Daten nicht von random Noise unterscheiden kann.

    Öhm.
    Der Sinn dahinter ist es schon. Heisst aber nicht dass es deswegen so ist. Der Sinn von MD5 ist auch dass man keine krummen Sachen machen kann, trotzdem gibt es Attacken die mit durchaus realistischem Rechenaufwand auskommen.

    Ich würde das also nicht einfach als gegeben annehmen, so lange nicht jmd. ne Test-Suite ala DIEHARD drauf losgelassen hat. Ist das bereits geschehen? Vermutlich ja, aber ich weiss es einfach nicht, daher meine Frage. Und wenn ja, kann man sich die Ergebnisse davon irgendwo ansehen?

    0
  • P

    Der Counter-Modus generiert so seine Pseudo-Zufallszahlenfolge. Die Sicherheit von AES-CTR ist somit abhängig von der Qualität dieser Zufallszahlen. Da AES-GCM auf den CTR-Mode aufbaut und AES-GCM in TLS 1.2 enthalten ist und sogar empfohlen wird, denke ich doch, dass das recht sicher ist.

    MD5 dagegen ist schon lange gebrochen und wird heute eigentlich nicht mehr verwendet. Aktuelle Browser sehen MD5-Zertifikate sogar automatisch als ungültig an. Nur noch als HMAC ist MD5 zu gebrauchen.

    Edit: http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf CTR_DRGB (S. 49, 57 im PDF) ist ein Zufallsgenerator, der auf einem Blockcipher im Counter-Mode aufbaut.

    0

  • @patrick246
    Die Theorie dahinter ist mir schon klar.
    Ich würde es trotzdem in der Praxis ausprobieren wollen.

    Speziell bei so Sachen wie der Frage in wie vielen Dimensionen die Zahlen gleichverteilt sind würde ich so einem Generator nicht einfach blind vertrauen. Wenn ich also ne Anwendung habe wo das wichtig wäre, dann würde ich wohl bei 'nem Twister bleiben.

    @cooky451
    Und nochmal was die 3,3 GB/s angeht...
    Hab jetzt keinen Vergleich mit MT, aber so richtig viel kommt mir das nicht vor. Gerade mal ein Byte/Cycle. Würde mich zumindest wundern wenn ein MT das unter gleichen Voraussetzungen (gleiche CPU, Thread-Anzahl etc.) nicht überbieten könnte. Bzw. XORSHIFT's Variante.

    0
  • C

    hustbaer schrieb:

    Speziell bei so Sachen wie der Frage in wie vielen Dimensionen die Zahlen gleichverteilt sind würde ich so einem Generator nicht einfach blind vertrauen.

    Ich bin mir relativ sicher dass die Zahlen so ziemlich jeden statistischen Test den es gibt erfuellen muessen damit AES nicht als broken gilt.

    hustbaer schrieb:

    Und nochmal was die 3,3 GB/s angeht...

    Ich hab das mal getestet:

    #include "utility/stopwatch.hpp"

#include <cstring>
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <random>

template <typename RNG>
RNG make_rng()
{
	std::random_device rd;
	std::array<typename RNG::result_type, RNG::state_size> seed_data;
	std::generate(seed_data.begin(), seed_data.end(), std::ref(rd));
	std::seed_seq seq(seed_data.begin(), seed_data.end());
	return RNG(seq);
}

template <typename RNG>
void test_rng(RNG& rng, void* buffer, std::size_t size)
{
	while (size >= sizeof(decltype(rng())))
	{
		auto r = rng();
		std::memcpy(buffer, &r, sizeof r);
		buffer = static_cast<char*>(buffer) + sizeof r;
		size -= sizeof r;
	}
}

int main()
{
	const std::size_t mb = 512;
	std::vector<char> buf(mb * 1024 * 1024);
	default_stopwatch sw;
	double t;
	auto rng1 = make_rng<std::mt19937>();
	auto rng2 = make_rng<std::mt19937_64>();
	auto rng3 = std::minstd_rand((std::random_device()()));

	sw.reset();
	test_rng(rng1, buf.data(), buf.size());
	t = float_cast<double>(sw.elapsed());
	std::cout << "mt19937: " << t << " - " << mb / t << " MB/s\n";

	sw.reset();
	test_rng(rng2, buf.data(), buf.size());
	t = float_cast<double>(sw.elapsed());
	std::cout << "mt19937_64: " << t << " - " << mb / t << " MB/s\n";

	sw.reset();
	test_rng(rng3, buf.data(), buf.size());
	t = float_cast<double>(sw.elapsed());
	std::cout << "minstd_rand: " << t << " - " << mb / t << " MB/s\n";
}

    ideone: http://ideone.com/ui7upc

    Ergebnis bei mir (x64, 3570k, VS2015 Preview)

    mt19937: 0.432911 - 1182.69 MB/s
mt19937_64: 0.218933 - 2338.62 MB/s
minstd_rand: 0.48124 - 1063.92 MB/s

    Ist wohl stark implementierungsabhaengig. Bei mir waere zumindest mt19937_64 ueber 4 threads deutlich schneller als AES. Aber wie schon vorher erwaehnt, jede dieser Varianten sollte vermutlich locker fuer den TE reichen.

    0
  • Mod 

    sizeof(decltype(rng()))

    😃

    0
  • Mod

    cooky451 schrieb:

    Aber wie schon vorher erwaehnt, jede dieser Varianten sollte vermutlich locker fuer den TE reichen.

    Bin ich der einzige, der noch immer auf eine Antwort auf die allererste Gegenfrage wartet?

    DarkShadow44 schrieb:

    Wie kommst du darauf dass das erzeugen der Zufallswerte das Problem ist ? Bei mir geht das in unter einer Sekunde.

    Ich gehe davon aus, dass der Threadersteller gar kein Problem mit Zufallszahlen hat, bis nicht das Gegenteil bewiesen wurde.

    0
  • ?

    Mein Testprogramm (teil einer groesseren Suite und die RNG sind stdlib kompatibel aber firmenintern, der XOR Shift AVX Code ist im Kern aber der gepostete):

    core i7 4670k 3.5GHz, single threaded:
    XOR_SHIFT AVX Generation performance for 5.36871e+008 random numbers of 4 byte sized uints is 2.03028e-010s/number <=> 4.92542e+009numbers/s. Total time used = 109ms

    Also:512MB 32bit in 109ms, bei den 8 bit von cooky also <27ms.

    Wobei ich den Ansatz immer noch nicht fuer richtig halte. Da es nur um 8 bit Zufallszahlen geht reicht die 2^31-1 sequenz von XOR-Shift locker aus. Mmn sollte es aber auch eine wesentlich kuerzere Sequenz und damit ein kuerzerer Vektor schon tun (das muss der TO aber mal sagen, sofern er noch mitliest).

    0
Anmelden zum Antworten