std::mt19937



  • Die Threadsicherheit müsste schon gewährleistet sein.

    In ein paar Tagen weiss ich mehr darüber, und zwischenzeitlich kann ich mich ein bisschen mit dem std::mt19937 befassen.

    Danke wachs



  • @wachs
    Von der Performance her wäre sicher ein Generator pro Thread ideal. Weil dann die (teure) Synchronisierung entfallen kann. Also wenn Zahlen mit einer sehr hohen Frequenz gezogen werden. Wenn der Thread bloss pro >= 1 Mio. CPU Cycles eine Zahl zieht ist das eher nicht so wichtig.
    Und normalerweise braucht man auch keine garantierte Gleichverteilung zwischen unterschiedlichen Threads.

    Und ein Generator für mehrere Threads hat auch den Nachteil die Gleichverteilung innerhalb eines Threads zu zerstören. Weil ja dadurch dass mehrere Threads sich beim selben Generator bedienen, aus Sicht jeweils eines einzigen Threads Werte aus der Sequenz "verschwinden".

    Langer Rede kurzer Sinn: so lange es keinen wichtigen Grund dagegen gibt einen Generator pro Thread. Bzw. auch genre mehr als ein Generator pro Thread - z.B. wenn man im selben Thread verschiedene Dinge berechnet die jeweils für sich alleine gleichverteilt sein sollen/müssen.

    Und BTW, nur falls es für dich relevant ist, und du es noch nicht weisst: MT ist so ziemlich das genaue Gegenteil von cryptographisch sicher. Super für Monte-Carlo Simulationen. Ganz ganz schlecht (=völlig unbrauchbar) für Cryptographie. Und auch - je nachdem wie gross man die Ranges der gezogenen Zahlen macht - nicht optimal bis sehr schlecht für Glücksspiel.
    Grund ist: Wenn man genug "rohe" Zahlen (=vor Zusammenkürzen auf die gewünschte Range) aus dem Generator in Folge kennt, kann sehr einfach den internen Zustand des Generators berechnen, und dann alle weiteren Zahlen vorhersagen.
    (Und "genug Zahlen in Folge" ist bei mt19937 IIRC so ~~1000 Zahlen.)



  • hustbaer schrieb:

    Und normalerweise braucht man auch keine garantierte Gleichverteilung zwischen unterschiedlichen Threads.

    Du kennst doch überhaupt nicht den Algorithmus, der hier verwendet wird.

    hustbaer schrieb:

    Und ein Generator für mehrere Threads hat auch den Nachteil die Gleichverteilung innerhalb eines Threads zu zerstören. Weil ja dadurch dass mehrere Threads sich beim selben Generator bedienen, aus Sicht jeweils eines einzigen Threads Werte aus der Sequenz "verschwinden".

    Das wäre nur relevant, wenn systematisch bestimmte Werte verschwinden würden. Wenn die Auswahl des jeweils nächsten Threads nicht vom Generator beeinflusst wird, werden die Zahlen durch mehrere Konsumenten nicht schlechter. Wenn die Threads selber die Berechnung durchführen und diese nicht in einen dritten Thread auslagern, sehe ich spontan keine Möglichkeit für eine Beeinflussung, weil der Thread vor der Berechnung der nächsten Zahl schon ausgewählt war. Und bei einem vernünfigen Generator gibt es keine signifikanten Abhängigkeiten zwischen den Elementen der Reihe, also kann so etwas wie "Thread A bekommt öfter die geraden Zahlen" nicht passieren.



  • TyRoXx schrieb:

    hustbaer schrieb:

    Und normalerweise braucht man auch keine garantierte Gleichverteilung zwischen unterschiedlichen Threads.

    Du kennst doch überhaupt nicht den Algorithmus, der hier verwendet wird.

    Und du kennst anscheinend nicht die Bedeutung des Wortes "normalerweise".

    TyRoXx schrieb:

    Das wäre nur relevant, wenn (...) Und bei einem vernünfigen Generator gibt es keine signifikanten Abhängigkeiten zwischen den Elementen der Reihe, also kann so etwas wie "Thread A bekommt öfter die geraden Zahlen" nicht passieren.

    OK. Ich hätte schreiben sollen: Es zerstört die Garantie von MT19937 dass die gezogenen Zahlen in bis zu 623 Dimensionen gleichverteilt sind. Worst-Case könnte es, je nach Zugriffsmuster, sogar messbare Abweichungen geben. Wobei ich zugebe dass das schon sehr blöd hergehen müsste.

    Mir ist klar dass das - speziell bei MT19937 - kaum praktische Relevanz haben wird. Die grundsätzliche Überlegung ist mMn. allerdings alles andere als uninteressant/unwichtig.



  • Danke euch für Tips und Infos

    Ich hab mich jetzt auch durch ein paar Treads hier im Forum gewühlt, da ich bis jetzt std::mt19937 gar nie genutzt habe. Im Prinzip bestätigen die alten Threads genau das was von euch geschrieben wird. Es ist und bleibt ein interessantes Thema.

    Wie ich die std::mt19937 nun genau einsetzen werde, halte ich noch offen. Ich möchte zuerst noch ein wenig damit rumexperimentieren. Gut zu Wissen ist natürlich, dass es probleme geben könnte mit der Threadsicherheit. Das werde ich mir darum auch noch anschauen.

    Ich werde mich wieder melden, wenn ich nicht weiter komme. Dann weiss ich auch mehr darüber.

    wachs



  • TyRoXx schrieb:

    wachs schrieb:

    Wenn ich das bräuchte würde ich das wahrscheinlich über eine Singleton lösen.

    Ein Singleton ist ein weiteres Problem, keine Lösung.

    Könntest du das begründen? Ich schreibe gerade ein kleines Spiel und brauche dafür "Zufallszahlen", nach einiger recherche im Internet hat das Singleton Pattern meiner Meinung nach am besten gepasst, da ich für die Game Engine ein State Pattern verwende und ich auf jeder State die gleiche Instanz ansprechen möchte:

    #ifndef RANDOM_H
    #define RANDOM_H
    
    #include <random>
    
    class Random
    {
    public:
        Random(const Random&) = delete;
    
        Random& operator=(const Random&) = delete;
    
        static Random& getInstance()
        {
            static Random instance{};
    
            return instance;
        }
    
        template<typename T>
        T getIntValue(T min, T max)
        {
            std::uniform_int_distribution<T> dis(min, max);
    
            return dis(m_gen);
        }
    
        template<typename T>
        T getRealValue(T min, T max)
        {
            std::uniform_real_distribution<T> dis(min, max);
    
            return dis(m_gen);
        }
    
    private:
        Random()
            : m_gen(m_rd())
        {
        }
    
    private:
        std::random_device m_rd;
    
        std::mt19937 m_gen;
    };
    
    #endif //RANDOM_H
    

    Ist das schlechter Stil und wenn ja warum?



  • singletonPattern schrieb:

    Ist das schlechter Stil und wenn ja warum?

    deshalb: https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Ri-singleton
    "Singletons are basically complicated global objects in disguise."



  • Außerdem ist zumindest mal die Member-Variable

    std::random_device m_rd;
    

    völlig überflüssig - du willst doch den Generator nur einmalig seeden und brauchst diese Variable nicht im State!



  • singletonPattern schrieb:

    Ist das schlechter Stil und wenn ja warum?

    Die Methoden sind aus jedem Thread aufrufbar, aber nicht thread-safe.

    Funktionen, die den Generator benutzen, sind völlig unnötigerweise nicht-deterministisch. Nachvollziehbarkeit und Testbarkeit gehen ohne Grund flöten.



  • Hab mir das nochmals angeschaut. Ich denke ich nimm den generator rein in den Thread.

    Anderseits habe ich mir noch ein paar Gedanken zum zentralen Generator gemacht. Was meint ihr könnte man den in etwa so machen? Das sollte mMn threadsicher sein.

    std::mutex mtx;
    int rnd_value2(int min,int max,unsigned long const &cseed){
    	static __declspec(thread) std::mt19937 *re=nullptr;
    	if(!re)re=new std::mt19937(cseed);
    	std::uniform_int_distribution<int>ui(min,max);
    
    	std::lock_guard<std::mutex> mtx_lock(mtx);
    	return ui(*re);
    }
    

    wachs



  • Was ist denn das jetzt wieder für eine Krücke? Guck dir doch nur mal das Interface an. Du musst immer 3 Dinge (min, max, seed) übergeben, ob der dritte aber benutzt wird oder nicht, hängt davon ab, ob zuvor schon einmal die Funktion aufgerufen wurde?! Das führt doch nur dazu, dass man einfach immer seed=0 setzt in der Hoffnung, dass der generator schon existiert.

    Wenn du eh einen mutex verwendest, dann gib doch den Generator von außen in den Thread rein. Wenn du thread-local Variablen hast, warum dann mutex?



  • @wob das stimmt doch nicht

    Ab der ersten Instanzierung von re ist die Instanzierung so nicht mehr beeinflussbar, da es static und auch eine if() vorhanden ist.

    Als Krücke kann man es schon ansehen, aber es ist grundlegend das Prinzip das mich interessiert. Und so funktioniert das Bestens.



  • Was stimmt nicht von dem, was ich geschrieben hatte?

    Ab der ersten Instanzierung von re ist die Instanzierung so nicht mehr beeinflussbar, da es static und auch eine if() vorhanden ist.

    Das war ja gerade meine Kritik. Von außen sieht man es nicht. Daher muss man entweder jedes Mal einen sinnvollen Seed mitgeben oder alternativ irgendwo speichern, ob man schon irgendwann mal die Funktion aufgerufen hat. Man wird dann gerne sagen "ach, wurde bestimmt schon mal initialisiert, ich übergebe als Seed einfach 0", denn jedes Mal einen neuen Seed zu ermitteln wäre ja komplett bescheuert.

    Und ein weiteres Problem: Du gibst den Speicher nie frei und kannst es auch nicht.

    => Es funktioniert also alles andere als bestens.



  • Ach so sorry, hab da was falsch verstanden.

    Ich hab das Prinzip vorher schon in eine Klasse umgebaut, und eine Belastungsprobe mit 20 Threads a je 1 mio. Zufallszahlen mit unterschiedlichen min/max Werten gemacht. Funkst Bestens.

    Das war auch der Grund warum ich random_device rausgeschmissen habe. Ich finde den so Performancelastig, dass ich den seed-Wert nun selber eingebe. (Dafür gibt es viele Möglichkeiten um einen neuen Seed zu wählen, hash, clock etc.)

    In der Klasse kann auf Wunsch Seed problemlos jederzeit geändert werden. Es wird dazu keine neue Instanz erzeugt. operator()() oder operator()(min,max) spucken die Zufallswerte aus. Sobald das Programm aus dem letzten Scope austritt, wir auch der Destruktor der Klasse aufgerufen.

    Scheint mir für den ersten Moment eine gute Sache zu sein.

    wachs



  • Damit dass du den Generator in die Hilfsfunktion verschiebst, trennst du bloss 'was auf was mMn. nicht aufgetrennt werden sollte. Nämlich die Entscheidung welcher Generator verwendet wird von dem Code der den Generator eben verwendet.

    Gleichzeitig vermischt du zwei Dinge die mMn. nicht vermischt werden sollten, nämllich wie der Generator geseedet wird mit allen Stellen wo er verwendet wird.

    Softwaredesignmässig sind das zwei schlimme Dinge.
    Rein technisch betrachtet ist es natürlich "OK", in dem Sinn dass es funktionieren wird.

    ps: Was das Freigeben des Speichers angeht, das ist wirklich ein Problem. Wäre es nen normales Singleton, könnte man es vernachlässigen. Aber eine geleakte Instanz pro Thread, das kann sich schnell summieren. Zumal MT19937 Generatoren ja nicht gerade ganz klein sind (IIRC ~4 KB pro Instanz).



  • Da kann ich dir nur recht geben, dass es Designmässig nicht der Hit ist.

    Geseedet wird bei der Instanzierung, also im Thread selber. Diese könnte indivuduelle, für jede Thread umgeändert werden, wie die min + max auch. Wenn Singleton genutzt werden würde, währe wahrscheinlich eine einheitliche Seed über alle Threads vorhanden.

    Ich wollte das einfach nur mal ausprobieren, rein aus Neugier. Für mich kommt diese Variante sowieso nicht in Frage.

    Gruss wachs


Anmelden zum Antworten