[boost] Mutex will nicht so wie ich

[Pikkolini]

XSpille schrieb:

Wenn du folgende Zeile

for (int i = 0; i < interval * tid; i++)

änderst in

for (int i = 0; i < interval * tid; i+=tid)

dann wird mein Programm nur (etwa) linear langsamer, weil die zu berechnenden Daten ebenfalls linear wachsen.

Ich Idiot
Diese Zeile:

for (int i = 0; i < interval * tid; i++)

muss natürlich so heißen:

for (int i = interval * tid - interval; i < interval * tid; i++)

Ansonsten muss ja jeder neue Thread zu dem alten, schon berechneten, nochmehr rechnen, was ja ziemlich sinnlos ist. DIe Threads sollen sich die Arbeit ja teilen. Nach der Änderung ist mein Programm mit mehreren Threads direkt mal um einiges schneller.

Jetzt bleibt eigentlich nurnoch das Problem, dass rand() nicht Threadsicher ist...

[manni66]

Pikkolini schrieb:

Jetzt bleibt eigentlich nurnoch das Problem, dass rand() nicht Threadsicher ist...

Stichwort: rand_r

[Pikkolini]

rand_r klingt in der Theorie zwar ziemlich vielversprechend, aber laut google muss ich dazu die cstdlib einbinden. Doch dort ist rand_r nicht definiert...

[XSpille]

Warum verwendest du nicht konsequent boost?

http://www.boost.org/doc/libs/1_44_0/doc/html/boost_random/tutorial.html#boost_random.tutorial.generating_integers_in_a_range

Du brauchst dann natürlich ein

boost::mt19937 gen;

mit unterschiedlichen seeds pro Thread.

[Pikkolini]

Weil ich alle random Zahlen mit verschiedenen Seeds und Divisionen auflisten will. rand_s() oder boost helfen mir da nicht weiter und rand_r() scheint nur in der Theorie zu existieren, da die C++ Referenz und die MSDN das auch nicht gelistet haben.

[XSpille]

Pikkolini schrieb:

Weil ich alle random Zahlen mit verschiedenen Seeds und Divisionen auflisten will.

Dann betrachte ich das Problem mal theoretisch...
Du willst in verschiedenen Threads Zufallszahlen generieren, die basierend auf
einer globalen Information (seed & der letzten erzeugten Nummer?) arbeiten. Jeder
Zugriff auf die globale Information muss folglich synchronisiert werden.
(Ob explizit durch dich oder die Funktion, die du verwendest sei mal
nebensächlich.)
Ein anderer Thread kann folglich erst auf die globalen Informationen zugreifen,
wenn die neue Zufallszahl komplett berechnet ist. Danach wird sie nur noch an
deine gewünschten Grenzen angepaßt.
(Bitte korrigiert mich, falls die letzte erzeugte Zahl nicht relevant für
die Folgezahl ist)

Jetzt muss also der Aufwand für die Synchronisierung mit dem Anpassen an
deinen gewünschten Bereich verglichen werden.
Als Tipp: Synchronisierung kann sehr teuer sein...

Als Übung für verschiedene Threads ist das ok, in der Praxis ist es jedoch
ziemlich unvorteilhaft...

EDIT: Wenn du jetzt jedem Thread einen anderen seed gibst, lohnt es sich
(evtl.) bis zur Anzahl der Kerne in deinem Rechner...
Du willst doch eh die Ergebnisse für verschiedene seeds berechnen.

[Dravere]

Pikkolini schrieb:

Wieso seltsame Messungen? Ich messe nur die Zeit, und darauf kommt es in meinem Programm ja an.

Die Frage ist aber, ob die Messung auch stimmt? Und wann stimmt sie überhaupt? Und wenn sie nicht stimmt, woran ist sie gescheitert? Wenn man einfach so allgemein misst, kann man meistens so ziemlich wenig Rückschlüsse ziehen und somit keine Erkenntnisse gewinnen. Im allgemeinen stricken sich die Leute dann irgendwelche wilden Erklärungen zusammen, welche noch mit etwas Halbwissen gewürzt sind.

Pikkolini schrieb:

Anscheindend gehör ich zu den vielen
Aber was gehört dann denn noch zu Performanceoptimierung dazu?
Wieso ist Parallelisierung zu probieren blanker unsinn?

Dein Vorgehen ist blanker Unsinn. Du versucht irgendwie wild etwas zu probieren und scheinst nicht viel Ahnung in dem Bereich zu haben. Das führt zu nichts. Wenn man Parallelisierung für Performanceoptimierungen verwenden möchte, muss man ganz gezielt vorgehen und genau wissen, was man tut.

Ich habe erst letztens ein schönes Beispiel für Performancoptimierung mit Parallelisierung gesehen. Ein schönes Beispiel war es auf zwei Arten, nämlich dass es zum einen schneller ablief, aber trotzdem nicht so wie gewünscht. Das Beispiel berechnete die Mandelbrot-Menge. Dabei wurden Abschnitte jeweils in Threads ausgelagert. Das ist auch wirklich etwas, was man sehr schön parallelisieren kann, denn die Berechnung braucht Zeit und ist unabhängig von den anderen zu berechnenden Teilen.
Die Erwartung war, dass mehr Threads bedeutet, dass es auch schneller abläuft, bis alle CPUs voll ausgelastet sind (war ein Multi-CPU-System/Server). Die Kurve war aber anders als erwartet. Zuerst gab es eine Beschleunigung, danach aber, obwohl die CPUs noch nicht voll ausgelastet waren, gab es eine deutliche Abflachung, zum Teil brauchte es sogar länger als mit weniger Threads. Und danach wurde es nochmals etwas schneller.
Die Vermutung für diesen Knick in der Kurve war, dass für gewisse Bereiche die Berechnung deutlich schneller ablief. Somit wurde eine grosse Zahl von Threads auf Bereiche losgelassen, welche gar nicht grosser Berechnung bedurften. Der Fehler war also, dass die Berechnungen gleichmässig auf die Threads verteilt wurden. Bei einer gewissen Anzahl von Threads wurden soviele Threads für nichts verbraten, dass sich das Starten von neuen Threads sehr negativ auf die benötigte Zeit ausgewirkt hat.

Einfach parallelisieren bringt nicht immer etwas, weil die Parallelisierung auch Zeit benötigt. Und zwar nicht nur beim Starten von Threads, wogegen man mit Threadpools ein bisschen etwas unternehmen kann, sondern vor allem auch wenn man Bereiche vor parallelem Zugriff schützen muss. Zudem gibt es eben auch Begrenzungen in der Hardware. ProgChild hat da auch ein paar Dinge genannt. Und nicht zuletzt lassen sich viele Bereiche in einem Programm gar nicht sinnvoll parallelisieren oder zumindest nicht mit den heutigen Sprachmittel.

Wir haben übrigens sogar einen kurzen Artikel, welcher vor der unbedachten Parallelisierung warnt (zwar nicht unbedingt mit Threads): Der Dreisatz lügt

Grüssli

[Pikkolini]

@XSpille
Welche globale Informationen?
Ganz zu Beginn werdem dem Thread ein paar globale Informationen zugewiesen, danach greift er aber nurnoch auf seine eigenen zu.

Und mit dem Problem mit rand() und der Threadsicherheit. Nach den ganzen google Ergebnissen, die ich durchforstet habe, deute ich die Threadunsicherheit von rand() so, dass grob gesagt einfach in den verschiedenen Threads die gleichen Zahlen erzeugt werden. Aber wenn ich ich mit srand() vor jedem Aufruf von rand() benutze, sollte das Problem doch behoben sein.
Bitte korrigiert mich, wenn ich falsch liege.

@Dravere
Also die Zeitmessung stimmt. Ich kann auch ohne Timer 0,0005 zwischen 10 Sekunden unterscheiden

Und zu dem blanken Unsinn, den ich angeblich veranstalte. Wie kann man genau wissen, wie man etwas tut wenn man es noch nie vorher gemacht hat? Oder konntest du direkt nach deiner Geburt perfekt programmieren?

Und nachdem ich meinen Logikfehler behoben habe, hatte ich sogar einen ziemlich deutlichen Performance Boost.

[Dravere]

Pikkolini schrieb:

Also die Zeitmessung stimmt.

Woher weisst du, dass deine Messung stimmt? Woher weisst du, dass sie nicht von irgendetwas externen beeinflusst wurde? Wie genau läuft die Messung? usw. usf.
Nur weil Resultate korrekt aussehen, müssen sie nicht korrekt sein.

Pikkolini schrieb:

Und zu dem blanken Unsinn, den ich angeblich veranstalte. Wie kann man genau wissen, wie man etwas tut wenn man es noch nie vorher gemacht hat? Oder konntest du direkt nach deiner Geburt perfekt programmieren?

Ich habe mich jedenfalls nicht an einen Editor gesetzt, dort reingeschrieben "Ich will ein Spiel haben", es dann angestarrt und mich darüber gewundert, dass ich noch kein Spiel vom Editor bekommen habe.
Oder anders gesagt: Bevor die Praxis kommt, muss man zuerst die Theorie lernen, sonst hast du keinen Schimmer, was du eigentlich machst oder machen musst.

Grüssli

[XSpille]

Pikkolini schrieb:

@XSpille
Welche globale Informationen?
Ganz zu Beginn werdem dem Thread ein paar globale Informationen zugewiesen, danach greift er aber nurnoch auf seine eigenen zu.

Eine Zufallszahl errechnet sich aus einer (oder mehreren) zuvor errechneten
Zufallszahl(en). Jetzt brauch der
Generator Informationen, die den Zustand repräsentieren.
In dem Aufruf für die Erzeugung werden diese Informationen ausgelesen und
aktualisiert. In dem rand_r wird vermutlich(!!!) nur ein Mutex um das rand gemacht,
der gleichzeitigen Zugriff verhindert. Aber alle Threads greifen auf die
gleichen Informationen zu.

Hier ist das Prinzip eines einfachen Zufallsgenerator erläutert:
http://www-i1.informatik.rwth-aachen.de/~algorithmus/Algorithmen/algo38/algo38.pdf

[Pikkolini]

Dravere schrieb:

Pikkolini schrieb:

Also die Zeitmessung stimmt.

Woher weisst du, dass deine Messung stimmt? Woher weisst du, dass sie nicht von irgendetwas externen beeinflusst wurde? Wie genau läuft die Messung? usw. usf.
Nur weil Resultate korrekt aussehen, müssen sie nicht korrekt sein.

1. Ich habe den timer, den ich benutze schon sehr oft benutzt und es kamen immer die Ergebnise, welche ich erwartet habe.
2. Interessiert es in diesem Fall niemanden, ob es jetzt 0,0005 oder 0,0006 Sekunden sind.
3. Kann ich auf die Uhr gucken und sagen, dass wen der Timer 10 Sekunden ausgibt, diese 10 Sekunden auch stimmen. Oder willst du jetzt auch noch anzweifeln, ob meine Uhren alle korrekt laufen, und mich mein Zeitgefühl vollkommen täuscht?
4. Was willst du damit eigentlich bezwecken? Das ist keine Zeitkritische Anwendung, wo es auf jede Millisekunde aufkommt. Also ist deine Kleinkrämerei ziemlich sinnlos.

Dravere schrieb:

Pikkolini schrieb:

Und zu dem blanken Unsinn, den ich angeblich veranstalte. Wie kann man genau wissen, wie man etwas tut wenn man es noch nie vorher gemacht hat? Oder konntest du direkt nach deiner Geburt perfekt programmieren?

Ich habe mich jedenfalls nicht an einen Editor gesetzt, dort reingeschrieben "Ich will ein Spiel haben", es dann angestarrt und mich darüber gewundert, dass ich noch kein Spiel vom Editor bekommen habe.
Oder anders gesagt: Bevor die Praxis kommt, muss man zuerst die Theorie lernen, sonst hast du keinen Schimmer, was du eigentlich machst oder machen musst.

Um es ganz kurz zu fassen: Hätte ich mich nicht vorher mit der Theorie befasst wüsste ich jetzt nicht das es boost gäbe, was Threads sind, wie ich diese überhaupt in mein Projekt einbinde etc.
Nur funktioniert eigentlich fast nie was neues direkt beim ersten Versuch. Aber aus seinen Fehler lernt man bekanntlich ja.

[Dravere]

Pikkolini schrieb:

1. Ich habe den timer, den ich benutze schon sehr oft benutzt und es kamen immer die Ergebnise, welche ich erwartet habe.

Das sagt ja schon alles aus. Weil es deinen Erwartungen entspricht, war die Messung richtig. Doch das ist eben völlig falsch. Messungen können auch richtig sein, wenn sie deinen Erwartungen nicht entsprechen. Auch können deine Erwartungen falsch sein.

Pikkolini schrieb:

4. Was willst du damit eigentlich bezwecken? Das ist keine Zeitkritische Anwendung, wo es auf jede Millisekunde aufkommt. Also ist deine Kleinkrämerei ziemlich sinnlos.

Es geht mir darum, dass du falsche Annahmen triffst, weil du nicht korrekt misst/interpretierst. Du führst mit deinem Timer dein Programm auf deinem Computer aus und danach auf dem Laptop und weil es auf diesen beiden Systemen mit den Threads schneller lief, gehst du davon aus, dass es überall schneller laufen wird. Dabei kann es gut sein, dass es anderswo unter anderen Bedingungen langsamer laufen würde. Ich behaupte einfach, dass du zu wenig Wissen hast, um sinnvolle Messungen durchzuführen, bzw. deine Messungen nicht richtig interpretieren kannst.

Pikkolini schrieb:

Um es ganz kurz zu fassen: Hätte ich mich nicht vorher mit der Theorie befasst wüsste ich jetzt nicht das es boost gäbe, was Threads sind, wie ich diese überhaupt in mein Projekt einbinde etc.
Nur funktioniert eigentlich fast nie was neues direkt beim ersten Versuch. Aber aus seinen Fehler lernt man bekanntlich ja.

Das Problem ist, dass du kein sinnvolles Profiling über Threads durchführen kannst mit deinem Grundlagenwissen über Threads. Dazu gehört viel mehr. Dadurch ignorierst du viele Fehlerquellen beim Messen und die Fehler fallen dir gar nicht auf.

Probier Threads zuerst einmal richtig anzuwenden, bevor du damit probierst die Performance zu verbessern. Man sollte wirklich sattelfest sein und die Threads verstehen (Betriebsystem und Hardware spezifisch), bevor man sich an Performanceoptimierungen durch Threads macht. Sonst rennst du nur in eine Falle nach der anderen und merkst es zum Teil nicht einmal.

Aber gut, ich will dich zu nichts drängen. Es ist alles wirklich nur als guten Raten zu verstehen. Profiling ist ein sehr komplexes Thema, welches viele am Anfang unterschätzen.

Grüssli

[Gast]

XSpille schrieb:

Jeder Thread hat einen eigenen Vektor. Deine Aussage ist daher (wie ich denke) falsch.

Ah ja... War gestern etwas in Eile. Mein Fehler...

Pikkolini schrieb:

Das der Hauptspeicher nicht schneller wird ist klar. Aber wird der schon der Flaschenhals, wenn ich auch nur eine Variable schreiben will?

DDR-400 hat eine Datenrate von 3.2 * 10^9 Bytes pro Sekunde. Eine double Variable hat 8 Bytes. Ein moderner x86 kompatibler Prozessor kann pro Takt und pro Kern 2 Gleitkommaberechnungen durchführen. Gehen wir (der Einfachheit halber) von einem 3.2 GHz Prozessor aus, so kann der Prozessor 16 mal so schnell Gleitkommazahlen berechnen, wie er sie in den Speicher schreiben kann. DDR2-1066 schafft 8.533 ^ 10^9 Bytes pro Sekunde. Da ist der Prozessor immer noch um einiges schneller.

Der Prozessor hat noch einen Cache. Der macht die Sache schneller. Wenn man aufpasst, dann ist das Problem nicht so groß. Wenn man nicht aufpasst, kann es sein, dass der Code durch den Cache langsamer läuft.

Um deine Frage zu beantworten: Falls die Berechnung trivial ist, dann wird der Speicher der Flaschenhals. Du musst auch bedenken: Du schreibst ja nicht nur eine Variable. Der Zustand der rand Funktion muss gesichert werden. Und ein vector<T>::push_back hat auch einiges an Speicher zu verwalten.

Pikkolini schrieb:

Und mit dem Problem mit rand() und der Threadsicherheit. Nach den ganzen google Ergebnissen, die ich durchforstet habe, deute ich die Threadunsicherheit von rand() so, dass grob gesagt einfach in den verschiedenen Threads die gleichen Zahlen erzeugt werden. Aber wenn ich ich mit srand() vor jedem Aufruf von rand() benutze, sollte das Problem doch behoben sein.
Bitte korrigiert mich, wenn ich falsch liege.

Du liegst Falsch.

Mit welchem Parameter willst du denn srand Aufrufen? Macht keinen Sinn.

Und selbst wenn: Wenn du den Aufruf von rand und srand nicht in einen Mutex packst, dann rufen mehrere Threads gleichzeitig srand mit verschiedenen seeds auf und überschreiben gegenseitig jeweils die Werte des anderen. Und wenn du dann rand aufrufst, dann kriegst du im schlimmsten Fall in allen Threads einen Wert von rand zu einem seed, der eine Mischung aus den seeds der Verschiedenen Threads ist. Z.b. die ersten 2 Byte des ersten Threads und die letzten 2 Bytes des zweiten Threads. Aber in allen Threads den selben Wert.

Wenn du aber einen Mutex verwendest, dann läuft dein Code wieder vollkommen seriell ab. D.h. er wird durch die Threads nur langsamer.

Und mal zu dem, vor dem dich die anderen warnen:

Du arbeitest mit Zufallszahlen. Du hast also keine Möglichkeit, überhaupt zu überprüfen, ob die Ergebnisse richtig sind.

Und Threads sind sehr böse. Da jetzt die Reihenfolge der Befehle nicht mehr fest steht, in der die Aktionen ausgeführt werden, kann es sein, dass ein Fehler nur ein einem von zehn Fällen zum Vorschein kommt. Das macht das Debuggen extrem schwierig.

Wenn du also nicht genau weißt, was du tust, wirst du Fehler in deine Programme bauen, die extrem schwer zu finden sind und vollkommen unerwartet auftreten. Und wenn du irgendwelche Berechnungen machst, wird es noch schlimmer. Weil du die Fehler nicht mal mehr siehst. Die Ergebnisse sind einfach hin und wieder mal falsch...

Also achte drauf, nur Funktionen zu verwenden, die als thread-safe ausgewiesen sind! Also z.B. rand_r . Und schau dir ruhig noch ein wenig mehr Theorie zu der Materie an.