[boost] Mutex will nicht so wie ich

Pikkolini

Ich habe es jetzt so wie du ausprobiert und nebenbei aus dem vector eine thread_group gemacht, die so aussieht:

boost::thread_group threads;
for (int i = 0; i < cores; i++)
	threads.create_thread(threadfunc);
threads.join_all();

Aber bei beiden Methoden werden die Threads hintereinander abgefertigt. Oder muss zwischen die beiden Schleifen noch irgendein Breakpoint für die Mainfunktion?

EDIT: Hab jetzt auch den Beitrag von XSpille gelesen und klingt vielversprechend
Da muss ich mich jetzt mal näher mit beschäftigen.

XSpille

ProgChild schrieb:

for (int i = 0; i < cores; i++) {
   threads.push_back(boost::thread(threadfunc));
}
// Jetzt laufen alle Threads

// Sammle die Threads wieder ein...
for (int i = 0; i < cores; i++) {
threads[i].join();
}

Das sollte klappen. Ist aber ungetestet.

Die boost-Doku sagt Folgendes:

Boost-Doku schrieb:

objects of type boost::thread are not copyable.

http://www.boost.org/doc/libs/1_44_0/doc/html/thread/thread_management.html

Folglich wirst du (meiner Meinung nach zumindest ohne C++0x) keine
boost::thread-Objekte in den Vektor packen können...
Mein Compiler meckert auch....

Pikkolini

Hmm mein Compiler meckert nicht
Aber ich benutze jetzt eh thread_group. Jetzt muss ich nurnoch deine Methode ausprobieren und dann meld ich mich wieder.

XSpille

Pikkolini schrieb:

Hmm mein Compiler meckert nicht
Aber ich benutze jetzt eh thread_group. Jetzt muss ich nurnoch deine Methode ausprobieren und dann meld ich mich wieder.

Das Beispiel oben verwendet jetzt auch thread_group.

Pikkolini

So, jetzt habe ich es so wie XSpille gemacht und die Threads laufen jetzt alle schön nebeneinander
Allerdings wird mein Programm immer langsammer, je mehr Threads ich habe auch bei einem Mehrkernprozessor mit Hyperthreading.
Wenn ich bei einem Intel i7 720QM bei den ersten drei Werten in meinem Programm 0 100 und 100 eingebe braucht er mit einem Thread nur 0,0005 Sekunden, bei vier Threads schon 0,5 Sekunden und bei acht Threads (wegen Hyperthreading) dauert es ganze zehn Sekunden
Die zehn Sekunden bei acht Threads lasse ich jetzt mal außen vor, da ich schon öfters gehört habe, dass Hyperthreading nicht wirklich was schneller macht sondern nur langsamer. Aber das das Programm auch bei vier Threads langsamer ist wundert mich ein bisschen.

Pikkolini schrieb:

Allerdings wird mein Programm immer langsammer, je mehr Threads ich habe auch bei einem Mehrkernprozessor mit Hyperthreading.
Wenn ich bei einem Intel i7 720QM bei den ersten drei Werten in meinem Programm 0 100 und 100 eingebe braucht er mit einem Thread nur 0,0005 Sekunden, bei vier Threads schon 0,5 Sekunden und bei acht Threads (wegen Hyperthreading) dauert es ganze zehn Sekunden
Die zehn Sekunden bei acht Threads lasse ich jetzt mal außen vor, da ich schon öfters gehört habe, dass Hyperthreading nicht wirklich was schneller macht sondern nur langsamer. Aber das das Programm auch bei vier Threads langsamer ist wundert mich ein bisschen.

Also... Wenn du Code richtig parallelisierst, wird er schneller auf einem Mehrkernsystem laufen. Das bedeutet, du machst was falsch.

Ich habe deinen Ursprünglichen Code mal überflogen. Und durch deinen Mutex wird dein eigentlich paralleles Programm wieder komplett serialisiert. Nur dass jetzt halt noch ein Overhead durch die Threads hinzukommt. Zumindest für die erste Schleife.

In der zweiten Schleife greifst du aus allen Threads ohne Mutex geschützt auf den gleichen vector zu. Das ist auch keine gute Idee.

Dravere

Pikkolini schrieb:

..., dass Hyperthreading nicht wirklich was schneller macht sondern nur langsamer.

Woher hast du den Unsinn schon wieder?

Pikkolini schrieb:

Allerdings wird mein Programm immer langsammer, je mehr Threads ich habe ...

Erstaunt mich irgendwie nicht. Einfach nur ein paar parallel laufende Threads einzurichten, heisst meistens nicht, dass das Programm schneller wird. Das ist ein grosser Irrtum von vielen. Du hast zum Beispiel sehr viele Locks in deinem Code. Das sind so viele, dass die Thread grundsätzlich so gut wie nichts parallel machen. Dadurch hast du am Ende grundsätzlich zig Threads, welche alle seriell die Aufgabe abarbeiten, weil sie sich immer gegenseitig blockieren. Und das blockieren kostet jeweils auch noch massiv Zeit.

Ich stelle wieder mal fest, du machst völlig seltsame Messungen. Profiling, erst recht Profiling über Threads und Performanceoptimierungen über Threads ist ein sehr fortgeschrittenes Thema. Das was du hier probierst ist blanker Unsinn.

Grüssli

Pikkolini

Dravere schrieb:

Pikkolini schrieb:

..., dass Hyperthreading nicht wirklich was schneller macht sondern nur langsamer.

Woher hast du den Unsinn schon wieder?

Den Unsinn habe ich schon in vielen Foren gelesen, da viele Leute meinten, dass sich zwei Threads trotzdem noch ein Kern teilen müssen und so aufeinander warten müssen. Ob das stimmt keine Ahnung.

Und nun zum Programm. Ich verwende momentan keine Mutex und mit mehreren Threads greife ich auch nicht auf das gleiche zu. Hier mal mein Vollständiger Code:

// MyThread.h

class MyThread
{
public:
	MyThread(int tid, int interval, int maxdiv);
	void startThread(void);
	std::vector<std::string> getValues(void);

private:
	int tid;
	int interval;
	int maxdiv;
	std::vector<std::string> values;
};

// MyThread.cpp
MyThread::MyThread(int tid, int interval, int maxdiv) {
	this->tid = tid;
	this->interval = interval;
	this->maxdiv = maxdiv;
};

void MyThread::startThread(void) {
	for (int i = 0; i < interval * tid; i++) {
		for (int j = 1; j <= maxdiv; j++) {
			srand(i);
			int v = rand() % j;
			std::stringstream ss;
			ss << v << "\n";
			values.push_back(ss.str());
		}
	}
};

std::vector<std::string> MyThread::getValues(void) {
	return values;
};

// Random.cpp

int _tmain(int argc, _TCHAR* argv[])
{
	if (!SetPriorityClass(GetCurrentProcess(), HIGH_PRIORITY_CLASS)) {
		std::cout << "Priorität erhöhen fehlgeschlagen" << std::endl;
		getchar();
		return 0;
	}
	SYSTEM_INFO sysinfo;
	GetNativeSystemInfo(&sysinfo);
	int cores = sysinfo.dwNumberOfProcessors;
	std::cout << "Anzahl der Threads: " << cores << std::endl;
	std::cin >> cores; // nur Testzwecke
	std::cout << "Minimale Systemzeit" << std::endl;
	int mintime;
	std::cin >> mintime;
	std::cout << "Maximale Systemzeit" << std::endl;
	int maxtime;
	std::cin >> maxtime;
	std::cout << "Maximale Division (keine 0)" << std::endl;
	int maxdiv;
	std::cin >> maxdiv;
	if (maxdiv < 1)
		maxdiv = 1;
	int delta = maxtime - mintime;
	int interval = delta / cores;
	std::cout << "Interval: " << interval << std::endl;
	std::vector<std::string> values;
	boost::thread_group threads;
	timer time;
	time.init();
	time.begin();
	for(int i = 0; i < cores; ++i){
		MyThread myThread(i, interval, maxdiv);
		threads.create_thread(boost::bind(&MyThread::startThread,myThread));
	}
	threads.join_all();
	double deltatime = time.stop();
	std::cout << deltatime << std::endl;
	std::cin.clear();
	std::cin.ignore(std::cin.rdbuf()->in_avail());
	getchar();
	return 0;
}

Die Funktion getValues steht da jetzt einfach so, aber ich brauch sie nicht wirklich.

Dravere schrieb:

Ich stelle wieder mal fest, du machst völlig seltsame Messungen. Profiling, erst recht Profiling über Threads und Performanceoptimierungen über Threads ist ein sehr fortgeschrittenes Thema. Das was du hier probierst ist blanker Unsinn.

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

Dravere schrieb:

Erstaunt mich irgendwie nicht. Einfach nur ein paar parallel laufende Threads einzurichten, heisst meistens nicht, dass das Programm schneller wird. Das ist ein grosser Irrtum von vielen.

Anscheindend gehör ich zu den vielen
Aber was gehört dann denn noch zu Performanceoptimierung dazu?

Dravere schrieb:

Das was du hier probierst ist blanker Unsinn.

Wieso ist Parallelisierung zu probieren blanker unsinn?

Pikkolini schrieb:

Dravere schrieb:

Pikkolini schrieb:

..., dass Hyperthreading nicht wirklich was schneller macht sondern nur langsamer.

Woher hast du den Unsinn schon wieder?

Den Unsinn habe ich schon in vielen Foren gelesen, da viele Leute meinten, dass sich zwei Threads trotzdem noch ein Kern teilen müssen und so aufeinander warten müssen. Ob das stimmt keine Ahnung.

Es stimmt nicht. Die Idee hinter Hyperthreading ist folgende. Laufen zwei Threads und der eine wartet muss auf Daten aus dem Hauptspeicher warten (der ist langsam), so kann der andere laufen und Berechnungen durchführen. Die zwei Threads laufen also nie gleichzeitig, aber trotzdem kann es ein Programm schneller machen.

Pikkolini schrieb:

Und nun zum Programm. Ich verwende momentan keine Mutex und mit mehreren Threads greife ich auch nicht auf das gleiche zu.
values.push_back(ss.str());

Doch tust du. Genau an der obigen stelle. Und genau da kann eine Menge schief gehen. Mit großer Wahrscheinlichkeit steht, wenn alle Threads fertig sind, nicht das im Vektor, was vorher rein geschrieben wurde.

Und noch eine Stelle

int v = rand() % j;

Die Funktion rand ist nicht thread-save. Wenn du aus mehreren Threads die Funktion rand aufrufst, zerstörst du die internen Strukturen der Funktion.

Pikkolini schrieb:

Dravere schrieb:

Erstaunt mich irgendwie nicht. Einfach nur ein paar parallel laufende Threads einzurichten, heisst meistens nicht, dass das Programm schneller wird. Das ist ein grosser Irrtum von vielen.

Anscheindend gehör ich zu den vielen
Aber was gehört dann denn noch zu Performanceoptimierung dazu?

Du kannst mehrere Threads schon verwenden, um ein Programm schneller zu machen. Mal abgesehen von den Fehlern oben, wird dein Programm nicht schneller durch mehrere Threads, weil der Hauptspeicher nicht schneller wird. Und der ist wahrscheinlich der Flaschenhals bei der Anwendung.

Je nach dem, was du für einen Prozessor hast, können die dauernden Cache-Synchronisationen deinen Code auch noch stark ausbremsen.

XSpille

ProgChild schrieb:

Pikkolini schrieb:
Und nun zum Programm. Ich verwende momentan keine Mutex und mit mehreren Threads greife ich auch nicht auf das gleiche zu.
values.push_back(ss.str());
Doch tust du. Genau an der obigen stelle. Und genau da kann eine Menge schief gehen. Mit großer Wahrscheinlichkeit steht, wenn alle Threads fertig sind, nicht das im Vektor, was vorher rein geschrieben wurde.

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

ProgChild schrieb:

Und noch eine Stelle
int v = rand() % j;
Die Funktion rand ist nicht thread-save. Wenn du aus mehreren Threads die Funktion rand aufrufst, zerstörst du die internen Strukturen der Funktion.

Genau... Hier ist der kritische Punkt...

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.

Nach der Synchronisierung des Zufallszahlengenerators wird es jedoch wohl etwas anders aussehen.

Pikkolini

ProgChild schrieb:

Pikkolini schrieb:

Dravere schrieb:

Pikkolini schrieb:

..., dass Hyperthreading nicht wirklich was schneller macht sondern nur langsamer.

Woher hast du den Unsinn schon wieder?

Den Unsinn habe ich schon in vielen Foren gelesen, da viele Leute meinten, dass sich zwei Threads trotzdem noch ein Kern teilen müssen und so aufeinander warten müssen. Ob das stimmt keine Ahnung.

Es stimmt nicht. Die Idee hinter Hyperthreading ist folgende. Laufen zwei Threads und der eine wartet muss auf Daten aus dem Hauptspeicher warten (der ist langsam), so kann der andere laufen und Berechnungen durchführen. Die zwei Threads laufen also nie gleichzeitig, aber trotzdem kann es ein Programm schneller machen.

Ok danke. Würde es dann in meinem Programm Sinn machen oder nicht?

ProgChild schrieb:

Pikkolini schrieb:
Und nun zum Programm. Ich verwende momentan keine Mutex und mit mehreren Threads greife ich auch nicht auf das gleiche zu.
values.push_back(ss.str());
Doch tust du. Genau an der obigen stelle. Und genau da kann eine Menge schief gehen. Mit großer Wahrscheinlichkeit steht, wenn alle Threads fertig sind, nicht das im Vektor, was vorher rein geschrieben wurde.

Wird in der for-Schleife nicht für jeden Thread ein eigenes Klassenobjekt erstellt? Wenn die for-Schleife acht mal durchläuft, werden doch auch acht unterschiedliche Objekte erstellt oder nicht?

ProgChild schrieb:

Und noch eine Stelle
int v = rand() % j;
Die Funktion rand ist nicht thread-save. Wenn du aus mehreren Threads die Funktion rand aufrufst, zerstörst du die internen Strukturen der Funktion.

Gibts denn eine Alternative dafür? rand_s suche ich nicht, da das die eigentlich Idee meines Programm zerstören würde.

ProgChild schrieb:

Pikkolini schrieb:

Dravere schrieb:

Erstaunt mich irgendwie nicht. Einfach nur ein paar parallel laufende Threads einzurichten, heisst meistens nicht, dass das Programm schneller wird. Das ist ein grosser Irrtum von vielen.

Anscheinend gehör ich zu den vielen
Aber was gehört dann denn noch zu Performanceoptimierung dazu?

Du kannst mehrere Threads schon verwenden, um ein Programm schneller zu machen. Mal abgesehen von den Fehlern oben, wird dein Programm nicht schneller durch mehrere Threads, weil der Hauptspeicher nicht schneller wird. Und der ist wahrscheinlich der Flaschenhals bei der Anwendung.

Je nach dem, was du für einen Prozessor hast, können die dauernden Cache-Synchronisationen deinen Code auch noch stark ausbremsen.

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

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...

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