Laden...

Probleme mit Random auf Multicore

Erstellt von Richter vor 13 Jahren Letzter Beitrag vor 13 Jahren 10.410 Views
R
Richter Themenstarter:in
104 Beiträge seit 2006
vor 13 Jahren
Probleme mit Random auf Multicore

Hallo!

Ich habe einen Code in dem ich viele Zufallsgeneratoren brauche. Und damits schneller läúft ist alles mit Linq Parallelisiert.

Eine Instanz von Random ist ja nun nicht threadsave. Und zu allen übel, wenn man viele Instanzen in kurzer Zeit erstellt, sind sie alle gleich. Meine Lösung für das Problem sieht so aus:

static private Random rnd = new Random();
        static Dictionary<int, Random> PrivatRNDGenerators = new Dictionary<int, Random>();
        
        public static Random GetGoodRandomMT()
        {


            int ID = System.Threading.Thread.CurrentThread.ManagedThreadId;
            if(PrivatRNDGenerators.ContainsKey(ID))
            {
                return PrivatRNDGenerators[ID];
            }
            lock (rnd)
            {
                Console.WriteLine("AHA!");
                PrivatRNDGenerators.Add(ID,new Random(rnd.Next()));
                return PrivatRNDGenerators[ID];
            }
            throw new Exception("KA!");
                //return new Random(rnd.Next());
            //}
        }

Aber obwohl ich schön säuberlich nach threads trenne, gibt es Fehler, das heisst, die Instanzen in dem Dictionery geben nur noch Nullen statt Zufallszahlen zurück.

Woran kann das liegen?

Eine Funktionierende Lösung war:


        static private Random rnd = new Random();
        
        public static Random GetGoodRandomMT()
        {

            lock (rnd)
            {
                return new Random(rnd.Next());
            }
        }

Aber das ist zu langsam, da warten sich die Threads tot...

Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!

3.170 Beiträge seit 2006
vor 13 Jahren

Hallo,
hat zwar vermutlich nix mit dem nuller-Problem zu tun, aber eine Anregung:
Du könntest mal versuchen, die ThreadID als Seed zu verwenden, das gibt ja auch für jeden Thread einen anderen Random.
Dann könntest Du Dir den Master-Random und das lock() sparen.

        static Dictionary<int, Random> PrivatRNDGenerators = new Dictionary<int, Random>();

        public static Random GetGoodRandomMT()
        {


            int ID = System.Threading.Thread.CurrentThread.ManagedThreadId;
            if(!PrivatRNDGenerators.ContainsKey(ID))
            {
              Console.WriteLine("AHA!");
              PrivatRNDGenerators.Add(ID,new Random(ID));
            }
            return PrivatRNDGenerators[ID];
        }

Gruß, MarsStein

Edit: wobei zu überlegen wäre, den Add-Vorgang noch mit einem lock auf das Dictionary zu schützen.

Hinweis von herbivore vor 11 Jahren

Wie in den folgenden Beiträgen herausgearbeitet wird, wäre nicht nur ein Lock auf Add erforderlich, sondern auch alle lesenden Zugriffe auf das Dictionary müssten gelockt werden, womit dann aber doch wieder für jede einzelne Zufallszahl ein gelockt werden würde, und somit nichts gewonnen wäre.

Überhaupt sollte man den Thread komplett lesen, weil zu fast allen Vorschlägen weiter unten noch Einwände erhoben oder Anmerkungen gemacht werden. Erst in Probleme mit Random auf Multicore kommt der Thread zu einem abschließenden Ergebnis.

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

1.130 Beiträge seit 2007
vor 13 Jahren

man könnte sich das ganze auch sparen:


[ThreadStatic]
static Random threadRandom=new Random();

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Floste,

was aber das Problem nicht löst, dass mehrere Random-Objekte mit gleichem Seed erzeugt werden (können).

Hallo Richter,

wenn du lock verwendest, musst du das aus meiner Sicht für alle Zugriffe auf das Dictionary tun, nicht nur für die schreibenden.

herbivore

3.170 Beiträge seit 2006
vor 13 Jahren

Hallo herbivore,

ich frage mich, ob hier (in der von mir angebotenen Variant) überhaupt ein lock notwendig ist. Im Grunde ja schon, aber falls diese Methode die einzige ist, die auf das - private - Dictionary zugreift, und ein Löschen von Elementen nicht vorgesehen ist, evtl. auch nicht.
Denn dann wäre ja sichergestellt, dass beim lesenden Zugriff am Ende der Methode das Element existiert, auch unabhängig davon, ob zwischen Schreib- und Lesevorgang weitere Threads weitere Elemente einfügen. Was meinst Du dazu?

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

5.742 Beiträge seit 2007
vor 13 Jahren

Hallo Richter,

berechne den Seed doch einfach manuell (aus der aktuellen Zeit) und inkrementiere ihn dann für jedes Random.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo MarsStein,

ob ein lock nötig ist, hängt m.E. von Implementierung der Dictionary-Klasse ab. Von der sollte man das aber keinesfalls abhängig machen, weil die sich ja (theoretisch) ändern kann. Vielleicht gibt es aber auch mit der jetzigen Implementierung schon Probleme, wenn die Elemente und vor allem die Bucktes des Dictionaries zwecks Kapazitätsvergrößerung umkopiert werden.

herbivore

3.170 Beiträge seit 2006
vor 13 Jahren

Hallo herbivore,

wenn die Elemente und vor allem die Bucktes des Dictionaries zwecks Kapazitätsvergrößerung umkopiert werden Ok, an sowas hatte ich nicht gedacht - und dann hängt es in der Tat von der Implementierung des Dictionary ab, nämlich davon ob da ein expliziter Zugriffsschutz eingebaut ist für einen solchen Vorgang oder nicht.
Danke für den Hinweis.

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

U
1.688 Beiträge seit 2007
vor 13 Jahren

Hallo,

Floste's Lösung scheint mir doch die beste zu sein. Man müsste nur dafür sorgen, dass der Seed unterschiedlich ist: z. B. die Thread-ID oder Thread-ID mit aktueller Zeit multipliziert o. ä.
Dann braucht man keinerlei lock.

3.170 Beiträge seit 2006
vor 13 Jahren

Hallo,

Floste's Lösung scheint mir doch die beste zu sein.

Dem schliesse ich mich an, kannte das vorher noch nicht. Laut Doku ist das genau wie dafür geschaffen.

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo,

bei ThreadStatic muss dann in jedem Thread die Instanz erstellt werden - siehe Bsp unten.

Thread-ID mit aktueller Zeit multipliziert o. ä.

ich habs bisher immer mit Bit-Shifts gelöst:


[ThreadStatic]
private static Random _rnd = new Random();

static void Main(string[] args)
{
	for (int i = 0; i < 10; i++)
		ThreadPool.QueueUserWorkItem((o) =>
			{
				if (_rnd == null)
				{
					int seed = (int)DateTime.Now.Ticks >> Thread.CurrentThread.ManagedThreadId;
					_rnd = new Random(seed);
				}
			});
}

Im obigen Beispiel könnte auch der Schleifenzähler i verwendet werden (aber auf Closures aufpassen).

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

R
Richter Themenstarter:in
104 Beiträge seit 2006
vor 13 Jahren

Ist diese Lösung so relativ Optimal?

 [ThreadStatic]
        static private Random rnd;

        static Random MasterRnd = new Random();         
        public static Random GetGoodRandomMT()
        {
            
            if (rnd == null)
            {
                Console.WriteLine("HAHAHHAHAHAAAA!");
                lock (MasterRnd)
                {
                    rnd = new Random(MasterRnd.Next());
                }
            }
            return new Random(rnd.Next());
         }

Kann man sich irgendwie den Null-check sparen?

Danke für all eure Kompetente Hilfe!

Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo,

Ist diese Lösung so relativ Optimal?

Relativ optimal schon, aber nicht absolut 😉

Wozu verwendest du überhaupt den MasterRandom? Zufälliger werden die Zufallszahlen dadurch nicht. Jedenfalls nicht solange wie System.Random Donald E. Knuths "Subtractive Random Number Generator Algorithm" verwendet. Es ist vollkommend ausreichend den Seed zu ändern und dies geht wie zB vorhin schon beschrieben wurde.

Kann man sich irgendwie den Null-check sparen?

Nein, denn durch ThreadStatic wird nur sichergestellt dass der Wert für jeden Thread eindeutig ist und das heißt dass sich dieser auf dem lokalen Stack des Threads befindet. Initialisiert muss der Wert jedoch schon noch werden.
Da Random eine Klasse ist ist die "Vorblegung" mit null.

Naja, den Null-check kannst du dir sparen wenn du immer eine neue Instanz erzeugts. Das ist aber nicht immer notwendig da der ThreadPool einen Thread wiederverwenden kann.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo Richter,

ich denke das selbe Problem hattest du schon mal vor gut einem Jahr. Siehe .Next der Klasse Ramdom gibt immer Null zurück

Wo liegt denn das (Verständnis-) Prolem?

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Richter,

Ist diese Lösung so relativ Optimal?

ich denke, sie ist klar, korrekt und effizient.

Allerdings sollte MasterRnd nach Namenskonventionen masterRnd oder sogar masterRandom heißen.

Hallo gfoidl,

Wozu verwendest du überhaupt den MasterRandom? Zufälliger werden die Zufallszahlen dadurch nicht.

zufälliger als was? 😃 Damit ist auf jeden Fall sichergestellt, dass man vernünftige Seeds bekommt.

Thread.ManagedThreadId halte ich dagegen nicht für günstig. In meinem Test starteten die ManagedThreadIds bei jedem neuen Start eines Programms wieder neu bei eins und wird für jeden neuen Thread um eins inkrementiert. Dadurch wären die Seeds der unterschiedlichen Random-Objekte zwar sicher unterschiedlich, aber eben aus dem immer wieder gleichen (kleinen) Wertebereich.

herbivore

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo,

zufälliger als was?

Gegenfrage: Was sind

vernünftige Seeds

?

Ob ich als Seed 1 oder 432987 nehme ist doch völlig egal. Die Wahrscheinlichkeit dass eine Zahl berechnet wird ist in allen Fällen (theoretisch) gleich groß. Daher verstehe ich den zusätzlichen Aufwand nicht.

Thread.ManagedThreadId halte ich dagegen nicht für günstig...aber eben aus dem immer wieder gleichen (kleinen) Wertebereich.

Daher führe ich auch auf die Ticks einen Bit-Shift mit der Thread-ID durch um einen großen Wertebereich zu erhalten.

Letzen Endes sind es aber immer noch Pseudo-Zufallszahlen. Für wirkliche Zufallszahlen bedient man sich zB atmosphärischem Rauschen und diese können zB über das HTTP-API dieses True Randomnumber Generator verwendet werden.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

U
1.688 Beiträge seit 2007
vor 13 Jahren

Dadurch wären die Seeds der unterschiedlichen Random-Objekte zwar sicher unterschiedlich, aber eben aus dem immer wieder gleichen (kleinen) Wertebereich.

Da böte sich dann doch die Multiplikation mit einem Zeitwert an. Schließlich ist auch MasterRnd nicht threadsicher. Wozu sonst der ganze Aufwand?

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo ujr,

Ob ich als Seed 1 oder 432987 nehme ist doch völlig egal.

richtig 😃 Wichtig ist nur, dass möglichst jedesmal andere Seeds verwendet werden. Und das ist bei der Lösung von Richter sichergestellt. Das meinte ich mit "vernünftig".

Daher verstehe ich den zusätzlichen Aufwand nicht.

Welcher zusätzliche Aufwand?

Daher führe ich auch auf die Ticks einen Bit-Shift mit der Thread-ID durch um einen großen Wertebereich zu erhalten.

Ja, kann man machen, aber dadurch wird es nicht zufälliger. Deine Lösung ist von der Gleichverteilung her erstmal weder besser noch schlechter ... solange es nicht annähernd soviele oder sogar mehr Threads gibt, als ein long Bits hat. Dann ist sie nämlich deutlich schlechter.

Hallo ujr,

Da böte sich dann doch die Multiplikation mit einem Zeitwert an.

das wäre eine Möglichkeit. Die halte ich für der von Richter gleichwertig.

Schließlich ist auch MasterRnd nicht threadsicher.

richtig, aber deshalb gibt es ja auch das lock, das wiederum nur bei der Initialisierung ausgeführt wird.

herbivore

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo herbivore,

Welcher zusätzliche Aufwand?

Die Lösung von Richter benötigt 3 Instanzen von Random und ein lock wenns auch einfacher geht. Siehe andere Lösungen.

solange es nicht annähernd soviele oder sogar mehr Threads gibt, als ein long Bits hat.

Dies gilt es allerdings zu berücksichtigen.
Die von ujr vorgeschlagene Multiplikation mit einem Zeitwert ist von der Verteilung sicherlich gleichwertig - hast du ja auch so angemerkt - aber weniger aufwändig.

Ob nun weniger aufwändig oder nicht - das ist meine Sichtweise, wahrscheinlich siehst du diesen Punkt anders. Diesen Punkt will aber jetzt nicht in die Länge ziehen und ausdiskutieren, denn es funktioniert ja 😉

Wie aber vorhin schon angemerkt können richtige Zufallszahlen über Rauschen erzeugt werden.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo gfoidl,

Die Lösung von Richter benötigt 3 Instanzen von Random und ein lock wenns auch einfacher geht. Siehe andere Lösungen.

upps, ich habe immer nur zwei gesehen. Drei sind natürlich Quatsch. Was ich mir die ganze Zeit eingebildet hatte und worauf sich alle meine Aussagen und Bewertungen bezogen, war folgender Code:


        [ThreadStatic]
        static private Random rnd;

        static Random masterRnd = new Random();
        public static Random GetGoodRandomMT()
        {
            if (rnd == null) {
                lock (masterRnd)
                {
                    rnd = new Random(masterRnd.Next());
                }
            }
            return rnd;
         }

herbivore

5.742 Beiträge seit 2007
vor 13 Jahren

@herbivore: Wo ist da jetzt der Unterschied?

Ich persönlich halte eher so etwas für zweckmäßig:


public static class RandomFactory
{
    private static int _seed = Environment.TickCount;

    public static Random CreateRandom()
    {
        int seed = Interlocked.Increment(ref _seed);
        return new Random(seed);
    }
}

Das mit dem ThreadStatic ist ja schön und gut, allerdings leidet a) die Performance darunter IMHO ziemlich und b) macht es das ganze nur unnötig komplex.

1.130 Beiträge seit 2007
vor 13 Jahren

Hab nen speedtest gemacht 1000Threads (die threads aber nacheinander, die zeit zwischen den threads nicht gemessen) mit jeweils 100000 aufrufen dauern:
static, lokale variable, klassenvariable: 1,5s
threadStatic: 4,8s
dictionary: 6,7s
winsharp: 414s
static+lock: 7,8s

ergebnisse sind sehr konstant.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

R
Richter Themenstarter:in
104 Beiträge seit 2006
vor 13 Jahren

herbivore, deine Lösung funktionier zumindest bei meinen Tests nicht!
Ich vermute es kommt durch den Prozessorcach zu Unstimmigkeiten, da der Thread unsinniger Weise von Core zu Core springt und alles ein wenig inkonsitent sein kann.

Es braucht also vorsichtshalber trozdem jeweils eigenständige Instanzen um ganz auf Nummer sicher zu gehen. Und wahrscheinlich ist das auf sehr Lange sicht noch immer nicht ganz Sicher...

Ich wünsche mir die 90er mit immer schneller werdenden Singlecores zurück ;D

Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!

5.742 Beiträge seit 2007
vor 13 Jahren

static, lokale variable, klassenvariable: 1,5s
threadStatic: 4,8s

Das meinte ich

winsharp: 414s

Ähm - jeder Thread sollte sein Random natürlich selber speichern (sonst ist das ja witzlos).
Zum Beispiel also irgendwas in diese Richtung:


List<int> result = new List<int>(10000);

Parallel.For(0, 100000, () => new
{
    List = new List<int>(),
    Random = RandomFactory.CreateRandom()
}, (i, s, r) =>
{
    r.List.Add(r.Random.Next());
    return r;
}, r =>
{
    lock (result)
    {
        result.AddRange(r.List);
    }
});

1.130 Beiträge seit 2007
vor 13 Jahren

Ähm - jeder Thread sollte sein Random natürlich selber speichern (sonst ist das ja witzlos).

Genau dafür ist threadstatic immernoch besser, als mehrfach ein neues random zu erstellen!
Er will es ja von mehreren stellen aus verwenden.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

5.742 Beiträge seit 2007
vor 13 Jahren

Er will es ja von mehreren stellen aus verwenden.

Das kommt jetzt darauf an, wie man das versteht 😁
Ich hatte es zunächst mal so verstanden, dass er einfach relativ viele Zufallszahlen "am Stück" braucht. Daraufhin ist mein Code auch optimiert.

Aber wahrscheinlich hast du Recht und es werden zu mehren Zeiten Zufallszahlen benötigt.
Trotz allem ist es auch dann sinnvoll, das Random wo möglich zu cachen und nicht jedesmal das von GetGoodRandomMT zu verwenden.

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo winSharp93,

auch wenn die Frage direkt an herbivore geht hoffe ich dennoch antworten zu dürfen 😉

Wo ist da jetzt der Unterschied?

bei herbivores Lösung wird rnd zurückgegeben und bei der Lösung von Richter new Random(rnd.Next()). Das Erzeugen noch einer Instanz ist eben nicht nötig.

Es stimmt auch dass die Performance durch ThreadStatic leidet. Der Zugriff auf das Feld ist ca. 6x langsamer als ohne Threadstatic. Der Grund dafür ist, dass der geJITete Zugriffscode für das threadstatische Feld aus zwei Teilen besteht:1.ermitteln der Adresse des Feldes über dessen Token mit Hilfe einer Systemroutine 1.üblicher Zugriff auf das Feld (über die unter Punkt 1 ermittelte Addresse)

Somit ist der 1. Punkt zusätzlicher Aufwand im Vergleich zu nicht-Threadstatic.

Ob das hier allerdings ins Gewicht fällt bezweifle ich.

RandomFactory:
Edit 28.07.2012: Nachfolgendes ist nicht korrekt, da ohne atomaren Vorgang und ohne volatile Reads die Seeds von mehreren Threads gleich sein könnten. D.h. das Interlocked (od. eine andere Synchronisation) darf nicht weggelassen werden.
Das Interlocked könnte man sich sogar sparen, denn es geht nur darum dass die Seed anders wird. D.h. selbst wenn die Threadausführung unterbrochen wird ein anderer Seed erzeugt - ist halt nicht +1, aber was solls: er ist anders.

Hallo Floste,

den Test kann ich nicht nachvollziehen. Welche Variante ist was? Ich kann mir auch nicht vorstellen dass die RandomFactory langsamer ist. Es kommt darauf wie den Test durchgeführt hast (Code).

Der Unterschied ist jener dass bei Threadstatic nur bei einem neuen Thread eine neue Instanz erstellt werden muss. Kommt dieser Thread zurück in den Threadpool und wird (später) wiederverwendet so existiert die Instanz von Random schon und daher wird einfach der Verweis auf diese Instanz zurückgegeben ohne dass was neues erstellt werden muss.
Wenn so getestet wurde dass die RandomFactory immer eine Instanz erstellt dann verfälscht das die Ergebnisse allerdings.

Hallo Richter,

funktionier zumindest bei meinen Tests nicht!

Wie äußerst sich das. Ich glaube das nämlich nicht.

Es braucht also vorsichtshalber trozdem jeweils eigenständige Instanzen um ganz auf Nummer sicher zu gehen. Und wahrscheinlich ist das auf sehr Lange sicht noch immer nicht ganz Sicher...

Ganz sicher bezogen auf Periodizität sind Pseudo-Zufallsgeneratoren sowieso nicht, denn die Zufallszahlen werden nach einem deterministischen Algorithmus berechnet. Daher auch mein Link zu den True-Random-Numbergenerators.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

R
Richter Themenstarter:in
104 Beiträge seit 2006
vor 13 Jahren

Das äußert sich, indem irgendwann nur noch Nullen zurück gegeben werden. Das Seedarray entleert sich. Man kann nicht einfach hoffen das alles Pro Tread konsistent ist! Denn auch dann gibt es noch Seiteneffekte! Dies ist sogar auf einem Singlecore möglich wenn aus mehreren Threads auf eine Variable zugegriffen wird. Manchmal kommen die Daten dann eben aus dem Cach und manchmal aus dem Ram! Dadurch gehen Updates verloren! ähnliches scheint bei 2 Cores und einem Thread zu passieren. Oder ist dies Unmöglich? ich glaube leider nicht.

Ich benutze die Zufallsgeneratoren um einen Spielkartenstapel für ein Pokerspiel zu simmulieren.

Das ist wohl die Kritiche Stelle:


int CallWin = (from a in ParallelEnumerable.Range(0, Params.SerchStructure[Params.Level]) select WinningOfMove(eMove.Call, GameState.Clone(), this.Clone(), Stats.Clone(), BetterHands.Clone())).Sum();

In WinningOfMove Brauche ich dann jeweils die Zufalszahlen. Sonst ist nichts Nebenläufig

Wie man sieht, nichts Weltbewegendes, alles hat seine eigenen Instanzen.

Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo Richter,

Pro Tread konsistent

Was soll das bedeuten?

Das Seedarray entleert sich.

Warum sollte das passieren? Da muss dir irgendwo ein gewaltigen Fehler mit der Threadsicherheit unterlaufen sein. Das Erzeugen der Random-Instanz in unseren Vorschlägen ist jedenfalls threadsicher.

Dies ist sogar auf einem Singlecore möglich wenn aus mehreren Threads auf eine Variable zugegriffen wird.

Darum gehts ja die Threadsicherheit zu beachten bzw. herzustellen.

Ich benutze die Zufallsgeneratoren um einen Spielkartenstapel für ein Pokerspiel zu simmulieren.

Kann das nicht sequentiell erfolgen? [Senf] Für die paar Karten rentiert sich parallel arbeiten nicht - höchstwahrscheinlich ist das sogar langsamer. [/Senf]

Dein Code-Snippschel sagt mir garnichts (und so wies da steht wäre das was für Coding Styles Horror 😉

Und warum wird fast jeder Satz mit einem Rufzeichen beednet!?

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

R
Richter Themenstarter:in
104 Beiträge seit 2006
vor 13 Jahren

Weil das Cool ist! 😉

Ich habe mehrere Kartendecks gleichzeitig, nicht eines an dem Parallel herrum gedoktert wird...ich bin kein bloedie 😉

Das Seedarry entleert sich wenn parallel aus einer Randominstanz Zufallszahlen erzeugt werden. Ich denke es pasiert Folgendermassen:

Thread ruft auf Core 1 rnd.Next() auf. Mitten in der Erzeugung wechselt der Thread von Core 1 auf Core 2 dabei *mysterioese hexenmagie * teil des Seedarrys ist verloren. Wenn das oft genug passiert, ist das Seedarry irgendwann nur noch mit Nullen gefuellt, ergo werden nur noch Nullen zurueck gegeben. Wenn ich viele Randominstanzen habe, verkleiner sich die Gefahr, da diese auch nur eine Begrenzte Lebensdauer haben und nicht so lange leben wie ein Thread!

Das ist alles recht schmutzig, fuer ein Privatprojekt aber ausreichend ;D

Pro Thread konsistent sollte soviel bedeuten, wie alles was im Threat passiert ist save. Besser waere vielleich In thread konsisten...naja nicht wichtig.

Mein Code ist nicht schoen aber dafuer selten 😛

Nevu - Intelligente Maschinen, die Zukunft alles rund um das Thema Künstliche Intelligenz!

6.911 Beiträge seit 2009
vor 13 Jahren

Hallo Richter,

Weil das Cool ist!

Dachte ich mir 😉

Jetzt versteh ich gar nichts mehr. Der ganze Thread (hier ist der Forenbeitrag gemeint 😄) geht um das Thema dass jeder Thread eine eigenene Instanz von Random verwendet. Das steht im Widerspruch zu

wenn parallel aus einer Randominstanz Zufallszahlen erzeugt werden .

Thread ruft auf Core 1 rnd.Next() auf. Mitten in der Erzeugung wechselt der Thread von Core 1 auf Core 2

Hier hast du wohl ein Verständnisproblem. Der Thread selbst ist eine Ausführungseinheit und führt folglich Code aus. Der Code ruft eine Methode auf nicht der Thread.
Jeder Thread hat seinen eigenen Speicher indem Zustand, Daten, etc. gespeichert werden. Wird Threadstatic verwendet ist auch dieses statische Feld im Speicher des Threads. Selbst wenn der Thread von einem Core zum anderen wechseln sollte - für solche Aufgaben ist übrigens der Scheduler des Betriebssystems zuständig - nimmt der Thread seine Daten mit. Verloren geht dabei nichts, das wäre ja ein grober Designfehler im Betriebssystem.

Das ist alles recht schmutzig, fuer ein Privatprojekt aber ausreichend

Nochmals der Vorschlag es sequentiell durchzuführen, dann ersparst du dir die ganzen Probleme die du hiermit hast. Hast du außerdem schon mal getestet ob es parallel wirklich um so viel schneller ist?

Ohne es persönlich zu meinen, aber da passiert genau das was ich befürchtet hatte als Mircosoft die Task Parallel Libary ins FX aufnahm -> "jeder" versucht parallel zu arbeiten und der Großteil hat davon keine Ahnung was dabei passiert und auf was aufgepasst werden muss.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

3.971 Beiträge seit 2006
vor 13 Jahren

class MyRandom {
  private static Random s_rnd = new Random();

  public int Buffer { get; set; }

  private Queue<int> m_rnds = new Queue<int>();

  public int Next() {
    if (m_rnds.Count == 0) {
      FillRnds();
    }

    return m_rnds.Dequeue();
  }

  private void FillRnds() {
    lock (s_rnd) {
      while (m_rnds.Count < this.Buffer) {
         m_rnds.Enqueue(s_rnd.Next());
      }
    }
  }
}

Ich denke man muss hier nicht viel sagen. Jeder Thread bekommt seine eigene MyRandom-Instanz. Wenn Buffer richtig (je nach Anwendung) gesetzt wird, wenig Lockoverhead und man muss sich nicht mit dem richtigen Seeds rumschlagen - denke gerade für Anfänger ist das sehr geeignet.

Besonders hübsch wird das ganze, wenn man s_rnd durch Func<int> ersetzt und so die eigentliche Implementierung austauschen kann.

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo winSharp93,

gerade wenn du sagt, dass jeder Thread GetGoodRandomMT nur einmal oder zumindest möglichst selten aufrufen sollte, spielt doch die Performance der Methode keine Rolle.

Hallo kleines_eichhoernchen,

ich bin der Meinung, dass auch die lesenden Zugriffe auf die Queue gelockt werden müssen. Und zwar übergreifend, sonst kann es passieren, dass ein Thread im Next feststellt, dass Count == 1 ist, aber wenn er beim Dequeue ankommt, hat ihm ein anderer Thread, der ebenfalls bei Count == 1 in Next angekommen ist, möglicherweise schon das letzte Element weggeschnappt ==> Peng!

Außerdem finde ich es nicht so schick, dass alle Threads sich ein Random-Objekt teilen, was ja bedeutet, dass die Zugriffe darauf (auch wenn du sie durch die Queue zusammengefasst hast) immer wieder synchronisiert werden muss.

Mal abgesehen davon, dass man eben extra eine Funktion braucht, um zu bestimmen, aus welchem Bereich die Zufallszahlen stammen sollen und da nicht mal jeder Thread, seinen eigene Funktion angeben kann, sondern sich alle auf eine globale einigen müssen. Das finde ich unpraktikabel.

Die obige Lösung, das jeder Thread sein eigenes Random-Objekt bekommt und danach exklusiv darauf zugreift, gefällt mir deutlich besser ...

Hallo Richter,

... und ich stimme gfoidl zu, dass es dann nicht zu dem von dir beschriebenen Effekt kommen kann. Auch den gfoidl letzten Aussage muss ich unterstreichen. Wenn man sich mit Synchronisierung noch nicht auskennt, sollte man besser die Finger von Multi-Threading lassen. Einen ersten Einstieg findest du in [Artikel] Multi-Threaded Programmierung.

herbivore

3.971 Beiträge seit 2006
vor 13 Jahren

ich bin der Meinung, dass auch die lesenden Zugriffe auf die Queue gelockt werden müssen

Wenn jeder Thread seine eigene MyRandom-Instanz bekommt dann nicht. Man natürlich auch direkt Random für jeden Thread benutzen, hat dann allerdings das Problem, wenn man merkt der Seed war doch nicht so prickelnd. Über MyRandom wäre das ganze jederzeit spielend austauschbar.

Mit dem Puffer ist meiner Meinung nach auch ein gutes Beispiel für den multithread Zugriff auf IO Daten und das mit relativ wenig lock-Overhead.

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

U
1.688 Beiträge seit 2007
vor 13 Jahren

Hallo Richter,

leider kann man Dein Beispiel ohne Kenntnis der Klassen weder richtig verstehen, noch ausprobieren. Bau doch mal ein minimales, komplettes Codestück, das den Fehler mit der obigen Implementierung zeigt.

Ohne es persönlich zu meinen, aber da passiert genau das was ich befürchtet hatte als Mircosoft die Task Parallel Libary ins FX aufnahm -> "jeder" versucht parallel zu arbeiten und der Großteil hat davon keine Ahnung was dabei passiert und auf was aufgepasst werden muss.

Kann ich leider genauso unterschreiben. Vor allem - das ist erst der Anfang 😉

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo kleines_eichhoernchen,

Wenn jeder Thread seine eigene MyRandom-Instanz bekommt dann nicht.

wenn jeder Thread seine eigene MyRandom-Instanz bekäme, wäre gar kein lock erforderlich, auch nicht beim Schreiben. Und außerdem wäre dann wieder das Problem, dass die internen Random-Objekte wieder zu gleichen Zeit erzeugt werden und damit auch denselben Seed erhalten. Das kann also erst recht nicht die Lösung sein.

herbivore

3.971 Beiträge seit 2006
vor 13 Jahren

Hallo Herbivore,
in meinem Beispiel ist Random static. Der Puffer, wenn leer, holt sich anschließend mit lock ein dutzend neue Werte und dieser Vorgang muss weil nur eine Instanz gelockt werden.

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

5.742 Beiträge seit 2007
vor 13 Jahren

gerade wenn du sagt, dass jeder Thread GetGoodRandomMT nur einmal oder zumindest möglichst selten aufrufen sollte, spielt doch die Performance der Methode keine Rolle.

Da gebe ich dir recht.
Allerdings kann man dann auch gleich "meine" Variante verwenden.

Ich meinte nur, dass man sich jedenfalls nicht dazu verleiten lassen sollte, Code wie den folgenden zu schreiben; lieber das Random cachen.


for (int i = 0; i < count; i++)
{
   int rnd = GetGoodRandomMT().Next();
   //...
}

6.911 Beiträge seit 2009
vor 13 Jahren

@winSharp93 😁

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

1.130 Beiträge seit 2007
vor 13 Jahren

Wer hätte gedacht, das dieses thema dermnaßen viel gesprächsstoff liefern würde 😁
btw: wieviele forenmitglieder braucht man um eine glühbirne zu wechseln?

@winSharp93

lieber das Random cachen.

warum nicht zusätzlich im getter cachen?

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

5.742 Beiträge seit 2007
vor 13 Jahren

warum nicht zusätzlich im getter cachen?

Inwiefern meinst du das jetzt?

Alles, was ich sagen wollte (und was wohl irgendwie falsch rübergekommen zu sein scheint 😉 ) war, dass man eine ThreadStatic Variable nicht einfach so benutzen sollte wie eine normale, sondern der Zugriff auf sie so weit wie möglich vermieden werden sollte.

Aber was ist daran jetzt so lustig? 🤔

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo kleines_eichhoernchen,

ok, jetzt habe ich den besonderen Kick deines Vorschlags verstanden, der auf der Kombination eines statischen Random-Objekts, das sich alle Threads teilen, und einer Queue pro Thread, die die Anzahl Synchronisationsoperationen auf das gemeinsame Random-Objekt reduziert, basiert.

Ich stimme dir zu, dass wenn jeder Thread seine eigene MyRandom-Instanz hat, keine Synchronisation beim Lesen erforderlich ist und auch jeder Thread seine eigene Funktion (und damit den gewünschten Zahlenbereich) angeben.

Bleibt noch das Problem, dass bei Änderung der Funktion der Buffer gelöscht werden muss (ok, das für sich ist noch kein Problem), aber dann muss spätestens beim nächsten Abruf einer Zahl der Buffer mit mindestens einem Element wieder gefüllt werden und dazu ist eine Synchronisation erforderlich. Wenn man nun bei jedem Abruf eine Zahl aus einem anderen Zahlenbereich will, geht es richtig zur Sache. Und es ist ja nichts ungewöhnliches, wenn sich der Zahlenbereich bei jedem Zugriff ändert. Dann setzt so eine Art Trashing ein.

Im Ergebnis bleibe ich dabei, dass es besser ist, wenn man thread-lokale Random-Objekte erstellt. Wie man dabei sicherstellt, dass deren Seed unterschiedlich ist, wurde ja schon beschrieben.

herbivore

PS: Die beste Variante sicherzustellen, dass der Seed für alle (thread-lokalen) Random-Objekte unterschiedlich ist, ist den Seed ausgehend von Environment.TickCount inkrementieren. Dort kommt es zu Clashes nur bei einem Wraparound, der frühestens nach ca. 12,5 Tagen ununterbrochener Uptime des Rechner eintritt und auch dann nur für wenige Millisekunden, also extrem unwahrscheinlich, auf jeden Fall viel unwahrscheinlicher als alle anderen in diesem Thread vorgeschlagenen Varianten, inkl. der noch nicht genannten Möglichkeit Guid.GetHashCode zu verwenden.

Der folgende, alle gemachten Vorschläge gegeneinander abwägende und damit empfohlene Code ist eine Kombination aus dem Vorschlag von winSharp93 (Increment) und dem Vorschlag von Floste (ThreadStatic).

[ThreadStatic]
private static Random _rnd;

private static int _seed = Environment.TickCount;
public int GetThreadSafeRandomNumber()
{
    if (_rnd == null)
    {
        int seed = Interlocked.Increment(ref _seed);
        _rnd     = new Random(seed);
    }
    return _rnd.Next();
}