C++ multi threading sinnvoll einsetzten

[Gandalf2210]

Hallo
kurz vorweg: Ich packe die details in einen spoiler, damit es nicht zu unübersichtlich wird.

Spoiler

ich habe mich mit dem Thema multi threading mal befasst und es mittels der Klasse "boost" auch geschafft ein einfaches Programm zu machen, was in vier threads gleichzeitig eine Variable hochzählt.
Hier skaliert die Leistung fast linear mit den Kernen.
Allerdings sah das ganze bei meinem "richtigen" Programm dann nicht mehr so rosig aus.

Ich habe eine thread Gruppe erzeugt

boost::thread_group tgroup;

und dieser Gruppe dann in einer schleife acht threads zuordnen lassen.

tgroup.create_thread(boost::bind(up,i));

Jeder Thread hat eine funktion ausgeführt, die aus ~ 50 schleifen Durchläufen und if abfragen besteht und ein paar array lese und schreib Operationen durchführt.
Alle 8 threads führen die gleiche Funktion aus, in einem anderen Bereich des arrays.
Dann wird mittels

tgroup.join_all();

gewartet bis alle fertig sind, und das Spiel geht wieder von vorne los.

Die erbrachte mir aber nicht den erhofften Effekt der Leistungssteigerung, der Prozessor (i5 3570k) war mit multi core "optimierung" weniger ausgelastet, als bei der reinen single thread anwendung.
Ich könnte mir jetzt vorstellen, dass durch das häufige erstellen und schließen von threads ein so großer overhead entsteht, dass es sich nicht lohnt.

Deswegen jetzt ein paar allgemeine Fragen zur multi thread programmierung:
Wie viele threads sollte man gleichzeitig laufen lassen?
so viele wie möglich, oder so viele wie (virtuelle) Kerne vorhanden sind?
versuchen jeden Thread so lange "am leben zu halten" wie möglich, oder möglichst kurze funktionen in einem thread laufen lassen?(also oft neue threads starten und beenden)
können verschiedene threads gleichzeitig auf einem array lese und schreiboperationen durchführen?
Es geht im allgemeinen also um design fragen, wie man threads "behandelt", nicht wie die programmierung im konkreten aussieht.

Ich hoffe ihr versteht, was ich meine
mfg Gandalf2210

 

[Sheeep]

Deine cpu kann nicht von mehr threads profitieren als sie cores hat. Aber viele threads erhöhen den speicher und verwaltungsbedarf. also lieber nur so viele threads wie (virtuelle) cores.

Threads erstellen und beenden kostet zeit. Halte sie lange am leben wenn das möglich ist.

Verschiedene threads können auf dem gleichen array operieren.
Dabei musst du allerdings aufpassen. Wenn zwei threads auf die gleiche arrayzelle zugreifen, weißt du nicht mit sicherheit welcher thread zu erst zugreift.
daher können ungewollte effekte entstehen. um das zu vermeiden kannst du locks verwenden.
wenn auf ein arrayelement immer nur ein thread zugreift (wie im beschrieben szenario) ist dies nicht erforderlich.

Edit: wenn du schleifendurchläufe parallelisieren willst solltest du dir openmp anschauen.
hiermit ist dies sehr einfach und effizient möglich.
https://de.wikipedia.org/wiki/Openmp

 

[Gandalf2210]

ich habe ein zweidimensionales array, jeder thread nimmt sich eine spalte vor und verändert auch nur werte in seiner Spalte. Die sollten sich also nicht in die quere kommen.
Danke schonmal für deine antwort. Jetzt weiß ich zumindest theoretisch, wie es besser gehen könnte, von der tatsächlichen implementierung mal abgesehen

P.s deine Signatur trifft es ziemlich gut

Cool, sowas gibt es also doch
Das war meine erste Idee, die einzelnen schleifendurchläufe auf verschiedene cores zu verlagern.
Dachte aber das geht nicht, und man kann nur funktionen in threads packen.
Danke dafür, werde ich mich da mal einlesen und versuchen das damit sinnvoll zu machen

 

[Nai]

Deswegen jetzt ein paar allgemeine Fragen zur multi thread programmierung:
Wie viele threads sollte man gleichzeitig laufen lassen?
so viele wie möglich, oder so viele wie (virtuelle) Kerne vorhanden sind?

Das ist nur teils richtig. Verwendest du Threads für blockierende I/O Operationen wie GPU-Ansteuerung, Netzwerk, Sound usw. benötigst du oft deutlich mehr Threads um die CPU gut auszulasten. Wie viele genau ist meist ein herumprobieren.

versuchen jeden Thread so lange "am leben zu halten" wie möglich, oder möglichst kurze funktionen in einem thread laufen lassen?(also oft neue threads starten und beenden)

Abgesehen davon, was mein Vorrender dazu gesagt hat, gibt es Fälle in denen man Threads wirklich nur kurze Funktionen ausführen lassen will. Für diesem Fall verwendet man Threadpools. Diese verwalten intern mehrere Threads, so dass diese nicht bei jedem Funktionsaufruf neu erstellt werden müssen.

ich habe ein zweidimensionales array, jeder thread nimmt sich eine spalte vor und verändert auch nur werte in seiner Spalte. Die sollten sich also nicht in die quere kommen.

Was ist das Layout dieses Arrays ? Poste mal bitte den Code dazu und wie du darinnen herumschreibst. Denn es könnte sein, dass mehrere Threads in die selbe Cache-Line schreiben, was deine CPU auch nicht mag.

 

[Gandalf2210]

ähh, wie muss ich jetzt layout verstehen?
also mein array sieht so aus

#define HOEHE 8
#define BREITE 8

unsigned int feld[BREITE+2][HOEHE+2];

alle Felder werden mit 0 initialisiert.

hier jetzt beispielhaft eine funktion

void up(int a)
{
int nullen=0;
															
		for(int j=1;j<HOEHE+1;j++)
		{
			if(feld[j][a]==0)											
			{
				while ((feld[j+nullen][a]==0)&&(nullen<=HOEHE+1))
				nullen++;
			
			for(int push=j;push<HOEHE+1;push++)							
				{
					if ((push+nullen)<(HOEHE+1))                               //abfrage ob außerhalb des arrays
					{
						feld[push][a]=feld[push+nullen][a];
						if (feld[push][a]!=0)
							zug=1;                                                 
					}
					else
						feld[push][a]=0;							
				}
			nullen=0;
			}

			
		}

Diese funktion läuft eine array spalte durch und schiebt alle zahlen "nach oben" also wenn es eine Null findet rücken die nachfolgenden zahlen auf;

for(int j=1;j<HOEHE+1;j++)
		{
			if ((feld[j][a]==feld[j+1][a])&&(feld[j][a]!=0))
			{
			zug=1;														
			feld[j][a]++;
			for(int k=j+1;k<HOEHE+1;k++)
				{
					feld[k][a]=feld[k+1][a];
				}
			}
		}

hier werden gleiche Zahlen "vereinigt" und die nachfolgenden Zahlen rücken auf. Es ist ein art simulation für das android spiel "2048"

 

[Nai]

Dein Array unsigned int Feld[BREITE+2][HOEHE+2] liegt wie folgt im linearen Speicher:
Feld[0][0] ; Feld[0][1] . . . . . . Feld[0][HOEHE+1] ; Feld[1][0] . . . . . .
Unter der annahme eine Cache-line habe 128 Bytes liegt das ganze vereinfacht wie folgt im Cache:
Cache-Line-0: Feld[0][0] bis Feld[0][31]
Cache-Line-1: Feld[0][32] bis Feld[0][63]
.....

In deiner Funktion schreiben und lesen die Threads per Feld[j][a] aus dem Array wobei a konstant ist. Dadurch schreiben mehrere Threads in die selben Cache-Lines; z.B. bei j = 0 und a = 0 oder a= 1 oder a=2 . . . . Dadurch muss die CPUs die Caches irgendwie kohärent halten, was für sie recht kostspielig ist.
Außerdem selbst wenn du nur einen Thread hast, so hast du bei dieser Iteration einen sehr großen Abstand zwischen zwei Speicherzugriffen (Stride) von HOEHE+2 wenn du per Feld[j][a] über das Array iterierst. Das mögen deine Caches ebenfalls nicht.

Deshalb wäre es viel besser die beiden Indexe zu vertauschen und per Feld[a][j] zu iterieren.

 

[Gandalf2210]

Das Problem hab ich dann aber, wenn ich seitwärts schieben will. Bei einer Operation muss ich doch zwangsläufig "blöd" zugreifen, oder?

 

[firespot]

threads erstellen und verwalten / terminieren sind an sich relativ teure Operation, d.h. bei einer 8x8 Matrix kann es leicht sein dass der ganze overhead dafür gleich mal deutlich mehr Zeit verbrät als wenn du es einfach single-threaded belässt. Je größer die Datenmatrix desto geringer wird aber der relative Anteil dieses overheads, und desto mehr zahlt es sich aus. Bei einer z.B. 1000000 x 100 Datenmatrix schaut die Sache dann aber schon ganz anders aus.
Gerade wenn die zu threadenden Operationen eher klein sind können sich die schon genannten thread-pools enorm auszahlen.

Die ideale thread-zahl kann man, ebenfalls schon gesagt, nur durch probieren herausfinden. Schreib dein Programm so dass sowohl die Matrixdimension wie auch die Thread-anzahl ein zur Laufzeit setzender input-Parameter ist (bei K threads arbeitet jeder davon halt 1/K der gesamten Matrix durch) und probier einfach verschiedene Werte durch. Ist die Datenmatrix sehr klein so mag, wie oben gesagt, alles ohne threading oder max. 2 threads am schnellsten sein (weil eben der overhead alles wegfrisst). Ist sie gross probier mal die Anzahl an cores + hyperthreading units als Startwert, und vergleich das dann gegen niedere Zahlen oder höhere Zahlen.

 

[Gandalf2210]

Wie kann ich denn herausfinden, ob mein Programm gut läuft? Wenn der Prozessor laut taskmanager möglichst hoch ausgelastet ist?

 

[Green Mamba]

Nein, wenn dein Problem möglichst schnell gelöst wird. Hohe Auslastung kann ja auch bloß vom Overhead zeugen.

 

[Gandalf2210]

Das ist seltsam, weil nach meiner "Optimierung" der Prozessor weniger ausgelastet war als vorher, obwohl er Unmengen an overhead haben sollte

 

[firespot]

Die Erstellung von threads in deiner thread_group, das join etc. läuft ja alles single-threaded ab (im main thread). Da wird das Gros vom overhead drinnen sein.
Und die ganze Menge an Funktionen in boost / OS, welche geladen werden müssen, wird der CPU Auslastung nicht guttun.

Nichtsdestotrotz bleibt eine 8x8 Matrix ein schlechtes Beispiel für Performancevergleich.

 

[Gandalf2210]

ich würde ja auch noch größere simulieren, aber bereits bei 8x8 kommt der innerhalb einer Stunde zu keinem Ergebnis, weshalb sich größere Matrizen bei der aktuellen Laufzeitentwicklung erstmal erübrigen

 

[firespot]

Auch bei single-threaded?

Und du bist GANZ SICHER dass da nirgends eine Endlosschleife oder sonstiger bug ist?

 

[Gandalf2210]

jup, auch bei single thread, da die Zahlen größer werden, die entstehe können, da mehr felder verfügbar sind.

1.Größere Felder, mehr abfrage, schleifendurchläufe. ist schonmal O(n³) wobei n die Spalten/Zeilenanzahl der Matris ist.
2. Späteres game over, wenn kein zug mehr möglich ist, da mehr Felder vorhanden.
3. größere Zahlen die entstehen können, da mehr platz zum kombinieren ist. eine kombination mehr heißt doppelt so lange laufzeit. also aus einer 1024 eine 2048 zu machen dauert doppelt solange wie aus einer 512 eine 1024 zu machen. Da ist schonmal min. ein exponential Term drinnen, wenn nicht sogar irgend eine fakultät, womit wir dann so ziemlich beim worst case sind, was laufzeiten in der Informatik angeht.
Wobei ich aber leider kein Mathematiker/Informatiker bin, der über dieses (statistische) Problem eine genauere aussage machen könnte.

Und nein, ich bin mir leider nicht GANZ sicher, dass der algorhythmus 100% korrekt läuft, aber für alle eingabegrößen von eins bis sieben tut er es (anscheinend)
Ich kann nciht jeden schritt per hand nachvollziehen, dann bräuchte ich kein Programm dafür, aber das endergebnis, wo er sagt: game over stimmt soweit, da geht echt nix mehr.

 

[firespot]

Was verhindert in diesen Zeilen

	while ((feld[j+nullen][a]==0)&&(nullen<=HOEHE+1))
nullen++;

dass nullen so gross werden kann, dass feld[j + nullen][a] damit out-of-bounds gerät (weil j + nullen nicht < HOEHE + 2 bleibt)?

 

[Gandalf2210]

gute frage, die ich mir auch schon mal gestellt habe
Der aufwand ein 9 mal so großes array zu erstellen, und nur den mittleren Teil zu verwenden kam mir auch schon, allerdings habe ich festgestellt, dass das Programm auch zuverlässig funktioniert, wenn ich es so lasse. Fahrlässig, da hast du recht.
Aber du hast recht, ich sollte nullen+j<=HOEHE+1 abfragen, dann bleibe ich brav in meinen grenzen.

EDIT:
Ich habe meinen code angepasst, die abfrage habe ich bei den anderen funktionen, die nach links, rechts und unten schieben sollen nur unzureichend angepasst, und vollkommenen blödsinn abgefragt.

 

[firespot]

OK, du hast also an threads gedacht weil du ein generelles performance Problem hast. Wie du aber schon selber rausgefunden hast, sind die Funktionen so 'klein' dass dir threading alles langsamer macht weil dessen overhead überwiegt. Unter Umständen kann man bei wenigen (z.B. 2) threads und thread-pools was gewinnen, aber primär solltest mal deinen jetzigen Code überarbeiten, denn da ist eine ganze Menge rauszuholen.

Erstmal und am wichtigsten: Schau dass keine bugs drinnen sind (so offensichtlich es klingen mag, so dezent kann der Unterschied in der Praxis sein )

Die ungewöhnliche Indizierungen mit 1 beginnend sei mal dahingestellt.

Du kannst Variablen zwischenspeichern. Statt etwa ständig array-Zugriffe wie

feld[push][a]

zu machen, kann man

unsigned int & Wert = feld[push][a];

verwenden und dann einfach auf Wert zugreifen (mag sein dass das automatisch optimiert wird oder nicht).

Du kannst dein 2-D array gegen ein 1-D array tauschen, am besten column-major, und dann Iteratoren (pointer sind genauso welche) nutzen um effizient über die Datenelemente zu traversieren.

[weitere Mini-optimierungen lass ich mal weg]

Und dann kann man sicher an der ganzen Logik ansetzen. Ich verstehe etwa die verbale Beschreibung deiner Funktion "up" nicht genau, doch der Code verwirrt mich und ich denke da sind mehr Schleifen und ifs drinnen als notwendig. Kannst du mal ein Bsp. posten, wie eine input und eine output-Spalte vor bzw nach 'up' aussehen soll? Ich glaube man kann der Funktion eine gehörige Verschlankungsdiät verpassen.

 

[Gandalf2210]

hier kannst du es selbst spielen
http://gabrielecirulli.github.io/2048/

mit den Pfeiltasten verschiebst du alle zahlen.
meine funktion macht das, was passiert, wenn du pfeiltaste hoch drückst, allerdings nur für eine Spalte, da ja jede Spalte einen eigenen thread hatte.
In der single thread version ist da noch eine große schleife drum, damit du über jedes Fedl iterierst, nicht nur die Felder einer Spalte.

Ich dachte mir das in zwei teile zu teilen.
Der erste verschiebt die zahlen, der zweite kombiniert sie.
Der einzige unterschied ist, dass ich nur den exponenten speicher, da das wohl schneller geht als ne shiftoperation

mit der Indizierung bei eins habe ich angefangen, weil ich gern einen Rand voll Nullen um das Spielfeld hätte, sonst muss ich bei jeder schiebe operation abfragen, ob sie innerhalb der grenzen ist, so greife ich im zweifel einmal auf ein element außerhalb meines spielfelds zu (wenn das abzufragende element am Rand liegt) und habe dort trotzdem eine Null stehen. Der "Nachfolger" meiner Rand Zahl ist also eine Null, logisch, weil die Zahl am Rand ist, und somit keinen Nachfolger hat

Ach ja, bevor es zu missverständnissen kommt, das ist NICHT meine Version, die ist rein konsole

 

[firespot]

OK, ich hab mir das Spiel nur kurz angeschaut, aber mir hier mal die Mühe gemacht und einen KOMPLETT UNGETESTETEN Vorschlag (also keine Garantie für irgendwas; bitte gehe es selber ausführlich durch und teste es) Vorschlag für die Implementierung von up zusammengeschustert:

int LetztePos = 1;

for (int j = 2; j <= HOEHE; ++j)
{
  unsigned int & Wert = feld[j][a];
  
  if (Wert != 0)
  {
   unsigned int & LetztePosWert = feld[LetztePos][a];
	
    if (LetztePosWert == 0)
       {
	  LetztePosWert = Wert;
	  Wert = 0;
	}
	else
	{
	  if(LetztePosWert == Wert)
	  {
	    ++LetztePosWert;
		++LetztePos;
		Wert = 0;
            
            assert(feld[LetztePos][a] == 0);
	  }
	  else
	  {
		++LetztePos;
		if (LetztePos != j) // check to not overwrite itself with 0
		{
                  assert(feld[LetztePos][a] == 0);

		  feld[LetztePos][a] = Wert;
		  Wert = 0;
		}
	  }
	}
  }
}

LetztePos speichert immer die letzte Stelle in die hineingeschrieben werden kann -> entweder eine 0 die aufgefüllt werden muss, oder ein mögliches Feld für merge. Steht dort keine Null so ist es immer die letzte vorangegangene Zeile ohne Null (also ab dieser Zeile bis zur aktuellen müssen alle Werte dazwischen 0er sein).
Am Beginn ist LetztePos immer die 1. Zeile. Von der der 2. Matrixzeile weg wird immer geschaut ob die aktuelle Zahl keine 0 ist. Falls dem so ist gibt es 3 Möglichkeiten:
a) War an LetztePos eine Null, so muss diese aufgefüllt werden. Der aktuelle Wert wird dorthin verschoben (und daher selbst durch eine Null ersetzt).
War dort keine Null so ist u.U. ein merge möglich:
b) sind die Zahlen ident findet der merge statt, und die Schreibpos wandert eins weiter (ich gehe davon aus dass pro Feld und Spielzug nur ein einziger merge möglich ist). Diese weitergewanderte Pos muss entweder das aktuelle Feld sein (was mit 0 überschrieben wurde) oder ein vorhergehender Nuller-Platz -> in jedem Fall muss da jetzt eine 0 stehen, daher das assert.
c) sind die Zahlen nicht ident so wandert die Schreibpos ebenfalls eins weiter. Falls diese Pos die aktuelle ist geschieht nichts (der Wert ist schon an seinem richtigen Platz), ansonsten muss es wieder ein Nuller-Platz sein (erneut assert), und dort wird der aktuelle Wert reingeschrieben und gleichzeitig an der eigenen Stelle durch 0 ersetzt (der Pos-Vergleich ist notwendig, damit sich das eigene Feld nicht irrtümlich selbst mit 0 überschreibt falls der Wert überhaupt nicht bewegt wird).

Alle unteren Zeilen werden automatisch mit 0ern aufgefüllt.

Ich hab die Indizierung mit 1 beginnend und bis HOEHE laufend beibehalten, aber man kanns leicht auf [0, HOEHE - 1] umstellen da ich kein anderes Feld außer den eigentlichen Spielfeldern brauche.

Bitte teste das ausführlich ob es stets das richtige macht -> zusammenfassen, verschieben, Rest per 0 auffüllen. Wie gesagt, KEINE GARANTIE für irgendwas, eher Denkanstoß für die weitere Entwicklung. Auf jeden Fall sollte es deutlich schneller sein.