Random-Funktion bei Multithread-Anwendungen sehr langsam

[MitjaStachowiak]

Hallo,
ich plane schon seit längerem, mal ein Programm mit Multicore-Unterstützung zu schreiben. Jetzt habe ich für Mathe dieses Programm
http://www.mitjastachowiak.de/?/Project ... Verteilung" onclick="window.open(this.href);return false;
geschrieben, das veranschaulicht, dass das Ergebnis eines Zufallsexperimentes dem wahrscheinlichen Ergebnis (verhältnismäßig gesehen) immer näher kommt, je öfter man den Versuch wiederholt. Wenn man zu einer sehr großen Wiederholungs-Anzahl springt (z.B. 1000000) dann dauert es schon ziemlich lange, bis die Punkte berechnet sind. Ich dachte also, dies wäre eine günstige Gelegenheit, um mal Multicore auszuprobieren.
Zu meiner Überraschung war das Programm dann mit "Multicore" jedoch erheblich langsamer als vorher
Mein Prozessor: Intel Core i7 840QM. Ich habe ewig herumprobiert, bis ich gemerkt habe, dass Random daran schuld ist. Wenn ich für Random überall 0.5 einsetze, ist das Programm viel schneller und dann macht sich auch das "Multicore" bemerkbar.

Also meine Frage: Wie bekomme ich schnelle Random-Werte in verschiedenen Threads gleichzeitig?
Ich nehme mal an, für diesen Zweck muss ich einen eigenen Zufalls-Generator einbauen - hat da jemand eine Empfehlung?

Es geht ja hier nicht darum, dass die Werte ganz besonders zufällig sind, aber wenn man schon dabei ist... In richtigen Profi-PCs gibt es doch bestimmt irgendwo einen Zufallschip, der eben wirklich Zufalls-Werte liefert. Es wäre doch schick, wenn man in diesem Fall auch auf die Hardware zurückgreifen könnte. Hat mal jemand was von einem Standard gehört, das das ermöglicht?

[Scotty]

Basierend auf http://shootout.alioth.debian.org/gp4/b ... ascal&id=2" onclick="window.open(this.href);return false; nutze ich folgenden Code:

Code: Alles auswählen

const
  Seed : integer = 42;
  IM = 139968;
  IA = 3877;
  IC = 29573;
 
function GenRandom(aLimit : longint): longint;
begin
  Seed:=(Seed * IA + IC) mod IM;
  if aLimit>0 then
    Result:=Seed mod aLimit else
    Result:=Seed;
end;
 
procedure GenRandomize;
begin
  Seed:=GetTickCount mod IM;
end;

Mein Random() muss sicher das gleiche Ergebnis liefern (was das interne nicht 100% ig macht).
Allerdings scheint es nicht ganz logisch, dass random() langsam sein soll. Eher randomize oder randseed.

[MitjaStachowiak]

Vielen Dank.
Die Ursache für die langsame Geschwindigkeit bei Multicore war wohl nicht direkt Random, sondern anscheinend die Tatsache, dass ich eine Externe Methode aufgerufen habe...
Aber diese Random-Funktion konnte ich jetzt komplett in meinen Quellcode einarbeiten, sodass das Programm bei Multicore-Bertieb jetzt knapp 3X so schnell ist wie ohne.

Falls jemand weitere Tipps zu Random hat, würde ich die natürlich auch gerne wissen...

[PS:] Ich habe das neue Programm gleich mal hochgeladen.

[ccmueller]

Hallo Mitja,

kannst Du uns den Source Code zur Verfügung stellen? Ich würde gerne lernen wie man das mit dem Multicore macht.

Vielen Dank im Voraus

Carsten

[Scotty]

Ich würde gerne lernen wie man das mit dem Multicore macht.

Lazarus stellt die "multithreadprocs" (inklusive Beispiele) zur Verfügung. Damit ist multithreading sehr einfach.

[MitjaStachowiak]

Ich habe das meiste aus diesem Tutorial:
http://wiki.lazarus.freepascal.org/Mult ... utorial/de" onclick="window.open(this.href);return false;

Was ich nicht gleich geblickt habe: Man darf die Execute-Procedure nicht direkt aufrufen. Entweder man startet den Thread automatisch nach dem Erstellen, oder später mit Resume.
Wenn der Thread nichts zu tun hat, kann man ihn mit Suspend unterbrechen und mit Resume wieder starten. Ich habe den Code in Execute einfach in ein repeat begin [...] end until (Terminated); geschrieben. Wird Execute verlassen, ist der Thread beendet.
Bei mir hat auch das Aufrufen von anderen Funktionen und Prozeduren aus Execute heraus nicht funktioniert Der CPU war auf allen Kernen bei 100%, es war aber langsamer als Single-Core...

Den Quelltext habe ich jetzt auch nochmal rein gestellt: http://www.mitjastachowiak.de/?/Project ... Verteilung" onclick="window.open(this.href);return false;

[ccmueller]

Danke, sehr freundlich!!

[Socke]

mit Suspend unterbrechen und mit Resume wieder starten.

Das funktioniert aber nur unter Windows. Unter Linux muss man den Thread neu starten oder andere Techniken (Events) verwenden.

Bei mir hat auch das Aufrufen von anderen Funktionen und Prozeduren aus Execute heraus nicht funktioniert

Prinzipiell ist das möglich. Was definitiv nicht geht, sind Funktionen, die irgendetwas mit dem Benutzer-Interface (Fenster etc.) machen.

[carli]

Basierend auf http://shootout.alioth.debian.org/gp4/b ... ascal&id=2" onclick="window.open(this.href);return false; nutze ich folgenden Code:

Code: Alles auswählen

const
  Seed : integer = 42;
  IM = 139968;
  IA = 3877;
  IC = 29573;

Mein Random() muss sicher das gleiche Ergebnis liefern (was das interne nicht 100% ig macht).
Allerdings scheint es nicht ganz logisch, dass random() langsam sein soll. Eher randomize oder randseed.

Das sind ziemlich kleine Konstanten, damit kann man doch keinen hinreichend großen Körper aufspannen, damit das wirklich zufällig aussieht.

[MitjaStachowiak]

Das sind ziemlich kleine Konstanten, damit kann man doch keinen hinreichend großen Körper aufspannen, damit das wirklich zufällig aussieht.

Ja, in manchen Abschnitten sieht man so Muster...

Ich habe an bestimmten Stellen noch ein InitRandom eingebaut, um dem "echten" Zufall wenigstens ein bisschen näher zu kommen:
Seed := GetTickCount mod IM;
Gegen die Muster hilft das aber nicht.

Ist mit größeren Konstanten gemeint, dass ich IM, IA und IC größer anlege und für Seed ein int64 nehme?

[mschnell]

...

Das darf man bei Multicode / Multithread aber nicht einfach so machen. weil die Rechen-Operation ja von anderen Threads/Cores unterbrochen werden können.

Abhilfe: Seed als Threadvar definieren und in der Initialisierungsphase Seed für jeden Thread in einer mit critcal section beblockten Funktion aus einer einzigen (nicht Threadvar) UrSeed vorbelegen.

Threadvar ist in fpc allerdings nicht iodeal implementiert, Delphi (und gcc) verwendet eine wesentlich fixere Implementierung.

Abhilfe: Seed als Klassenvariable in einem Objekt, das in für jedem Thread instanziiert wird (z.B. TMyThread = class(TThread).

-Michael

[mschnell]

. Wenn man zu einer sehr großen Wiederholungs-Anzahl springt (z.B. 1000000)

Pseudo-Zufallszahlen sind naturgemäß zyklisch. Wenn Du sehr viele Wiederholungen benutzt, muss der Zahlen-Generator mit einer entsprechen großen Periode arbeiten. Das solltest Du prüfen.

-Michael

[Scotty]

Vielleicht nochmal zur Klärung: ich starte ein Spiel auf verschiedenen Clients und brauche unbedingt die gleichen Zufallswerte. Die interne Random-Funktion hat das nicht geliefert. Mein Spiel ist nicht auf eine besonders große Menge verschiedener Werte angewiesen, eine Lottoauslosung würde ich als Veranstalter mit dem Code aber nicht machen. Es gibt eine Reihe von Beispielen im Netz, wie eine Zufallszahl erzeugt wird. Lazarus hat den Mersenne-Twister eingebaut, in der system.inc gibt es weitere Informationen dazu.

[u-boot]

Mein Random() muss sicher das gleiche Ergebnis liefern (was das interne nicht 100% ig macht).

Der Mersenne Twister hat die Eigenschaft, gleiche Ergebnisse bei gleichem Startwert und bei gleicher Anzahl an Durchläufen zu produzieren.
Sinn davon ist ja schließlich "Zufallsexperimente" wiederholbar zu machen.


Ich habe den in Lazarus implementierten Mersenne Twister in eine Klasse gepackt. Wenn interesse an der Unit besteht einfach bei mir melden.
Von der Geschwindigkeit her sind 100.000.000 Aufrufe (ohne reinitialisierung) hier in der ursprünglich implementierten Version in ca. 6 sek. durchgegangen. Bei Verwendung der von mir erstellten Klasse (gefǘllt mit Plagiat) werden dafür ca. 6,3 sek benötigt. (benötigt also nun ca. 5% mehr Zeit). Gemacht habe ich das um in verschiedenen Komponenten voneinander unabhängige Pseudozufallszahlenreihen zu erhalten. Ich habe zwar noch nicht mit Multithread gearbeitet aber evtl. könnte es ja helfen.

[mschnell]

Ich habe zwar noch nicht mit Multithread gearbeitet aber evtl. könnte es ja helfen.

Wenn jeder Thread die Klasse instanziiert und die internen Variablen Klassen-Variablen sind, ist Multhread sicher kein Problem. Nur der Aufruf eines (gemeinsamen) Pseudo-Zufalls-Generator für die Initialisierung muss entsprechend gesichert sein.

-Michael