3. Schnelles erzeugen vieler Zufallswerte

Schnelles erzeugen vieler Zufallswerte

  • ?

    Hallo @all,

    ich habe folgendes Problem:
    Mein Programm soll bestimmte Bytes verarbeiten und benötigt für jedes Byte rund 5 zufällige Bytes.
    Es handelt sich um eine hohe Anzahl an Bytes (in meinem aktuellen Test 30.000.000 Bytes -> 150.000.000 Zufallswerte).
    Mit BruteForce (d.h. bei jedem Byte 5-mal mein mt199337 aufrufen) erhöht sich die Laufzeit enorm!!!
    Die Idee ist also eine Möglichkeit zu finden, das Erzeugen der ZUfallswerte zu optimieren.
    Meine Idee war einen std::vector zu benutzen und den in einem Thread zu befüllen und aus meinem eigentlichen Thread die Werte auszulesen. Ich weiß nur nicht ob das wegen der ganzen Synchronisation so viel schneller laufen würde, da das Programm quasi nur noch am "rum-locken" ist 😃
    Die Frage ist nun, gibt es eine schnelle Methode Zufallswerte zu erzeugen bzw. kann ich in einem Thread ein vector befüllen und parallel ohne große Synchonisierung die Werte auslesen?

    mfG

    Hlymur

    0
  • D

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

    0

  • Viel schneller als MT19937 wirds nicht[1].
    Wobei du von MT19937 ja 32 Bit Werte bekommst, da kannst du 4 Bytes draus machen => 4x weniger Zufallszahlen benötigt.
    Und natürlich kannst du das Erzeugen der Zufallszahlen in einen eigenen Thread auslagern, gar kein Problem.
    Locking-Overhead musst du dabei keinen schlimmen machen wenn du nicht willst. Hol dir halt Blöcke zu je 1 Mio. Zahlen vom Thread oder so, und erst wenn ein ganzer Block verbraucht ist musst du wieder locken und nen neuen holen.

    [1] http://www.boost.org/doc/libs/1_57_0/doc/html/boost_random/reference.html#boost_random.reference.generators

    0
  • Mod

    hustbaer schrieb:

    Viel schneller als MT19937 wirds nicht[1].

    Was ist mit Hardwaregeneratoren, wie RdRand?

    0

  • Muss ich jetzt auch überall ein "normale Menschen können hier aufhören zu lesen" an alle meine Beiträge dranschreiben? 🤡

    Ich bin von Softwarelösungen ausgegangen.
    Und RdRand ist mMn. auch noch nicht weit genug verbreitet. UND ich hab genau keine Ahnung wie schnell das ist.

    0
  • Mod

    hustbaer schrieb:

    Muss ich jetzt auch überall ein "normale Menschen können hier aufhören zu lesen" an alle meine Beiträge dranschreiben? 🤡

    Das musst du sowieso, nicht nur wegen mir 😃 . Aber ich verstehe, was du sagen möchtest.

    0
  • V

    hustbaer schrieb:

    Und RdRand ist mMn. auch noch nicht weit genug verbreitet. UND ich hab genau keine Ahnung wie schnell das ist.

    Naja, guten recht Zufall kriegt man mit ein Bißchen * und +, vielleicht ^ und << oder so. Denke nicht, daß RdRand vorläufig da was zu melden hat. Und wenns so weit ist, dann tausch man einfach die Quelle aus.

    Vector-Befüllen und das arme unschuldige behäbige RAM damit zu belästigen ist sicherlich der falsche Weg.

    0
  • 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
Anmelden zum Antworten