Warum ist das Multithreading so langsam?

[blablab]

Hallo!

Ich habe einen PC mit 2 Prozessoren. Deshalb hab ich ein MergeSort mit 2 Threads programmiert und messe die Zeit, die es zum Sortieren eines bestimmten Testarrays braucht. Das Programm bekommt standardmäßig nur Zugriff auf einen Prozessor und benötigt zum Sortieren ca. 1 sek. Wenn ich jetzt im TaskManager die Prozessorzugehörigkeit auf beide Kerne setze und nochmal sortieren lasse, dann benötigt das Sortieren ca. 1,5 sek.
Das verwirrt mich jetzt wirklich sehr, denn eigentlich sollten es ja eher 0,5 sek sein, immerhin benötigt das Programm laut Taskmanager beim 1.Lauf maximal 50% Gesamtauslastung und beim 2.Lauf die vollen 100%. Und das Einzige das ich ändere ist ja nur die Prozessorzugehörigkeit.

Das Mergesort habe ich so implementiert: Ein Merge-Thread wird gestartet, dieser startet zwei weitere Sortier-Threads und lässt den ersten die erste Hälfte sortieren und den zweiten die zweite. Wenn beide Sortier-Threads beendet sind werden die Ergebnisse vom Merge-Thread gemerged und der Thread beendet. Das bedeutet eigentlich sollten sich die zwei Sortier-Threads nicht in die Quere kommen.

Ich verstehe diesen komischen Effekt nicht. Wisst ihr woran das liegen könnte?

Grüße
blablab

[Namenloser]

Ich würde mal den SamplingProfiler nehmen und schauen, wo am meisten Zeit verbraten wird.

Und poste mal den Source Code, ohne kann man nur raten...

[ConnorMcLeod]

Zitat:

Zitat von blablab (Beitrag 1095251)

lässt den ersten die erste Hälfte sortieren und den zweiten die zweite. Wenn beide Sortier-Threads beendet sind werden die Ergebnisse vom Merge-Thread gemerged

Möglich, dass das Mergen auch lange dauert...
Lass vllt mal Log-Meldungen inkl. Zeit in 1000stel Sek. pro Thread rausschreiben und analysier das.

[Blup]

Wenn mehrere Kerne gleichzeitig auf den selben Speicherbereich zugreifen und diesen verändern, treten zwangsläufig Cache misses auf.

[hoika]

Hallo,

Zitat:

messe die Zeit, die es zum Sortieren eines bestimmten Testarrays braucht.

Greifen beide Threads auf das Array zu ?
Wie hast du das Locking implementiert gemacht ?
Was passiert, wenn du das Array in zwei Teil-Arrays (2 Variablen) aufteilst,
und die beiden jetzt getrennten Arrays von den beiden Threads sortieren läßt.
Und was schon gesagt wurde.
Mache ein paar Logs, die dir anzeigen, wann die beiden Threads fertig sind,
und wann das Mergen erledigt ist.


Heiko

[blablab]

Vielen Dank für die vielen Antworten!
Entschuldigt, dass ich erst jetzt antworte, ich hatte vorher nicht genügend Zeit.

Also am Merge liegt es nicht, denn ich hab jetzt mal das merge ausgeklammert und es tritt genau derselbe Effekt auf.
Mein Code ist nicht auf 2 Threads ausgelegt sondern auf "beliebig" viele. Da ich zum ersten Mal mit Threads arbeite wär es schön wenn ihr mir auch sonstige Fehler oder Unschönheiten schreibt, auch wenn sie direkt nichts mit dem Thema zu tun haben...
Hier ist der Code den ich benutze:

Delphi-Quellcode:

type
   TThreadRecord = record
      splits: Cardinal;
      PArr: Pointer;
      len: Integer;
   end;
   PThreadRecord = ^TThreadRecord;

function ThreadFunc(rec: PThreadRecord): Integer;
var
   half: Integer;
   rec1, rec2: PThreadRecord;
   Thread1, Thread2: THandle;
   ThreadId: Cardinal;
begin
   with rec^ do begin
      if splits = 0 then begin
         Sortiere(PArr, len);
      end else begin
         Dec(splits);
         half := len shr 1;

         //Starte Thread1 mit 1. Hälfte des Arrays
         New(rec1);
         rec1^ := rec^;
         rec1^.len := half;
         Thread1 := BeginThread(nil, 0, @ThreadFunc, rec1, 0, ThreadID);

         //Starte Thread2 mit 2. Hälfte des Arrays
         New(rec2);
         rec2^ := rec^;
         rec2^.PArr := Pointer(Integer(PArr) + SizeOf(Pointer)*half);
         rec2^.len := len - half;
         Thread2 := BeginThread(nil, 0, @ThreadFunc, rec2, 0, ThreadID);

         WaitForSingleObject(Thread1, INFINITE);
         WaitForSingleObject(Thread2, INFINITE);
         CloseHandle(Thread1);
         CloseHandle(Thread2);

         //Merge zu Testzwecken ausgeklammert
         //...
      end;
   end;
   Result := 0;
end;

procedure SortiereParallel;
var
   Thread: THandle;
   ThreadId: Cardinal;
   rec: PThreadRecord;
begin
   new(rec);
   with rec^ do begin
      splits := mySplits;
      PArr := PointerToArray;
      len := AnzahlFelder;
   end;
   Thread := BeginThread(nil, 0, @ThreadFunc, rec, 0, ThreadID);
   WaitForSingleObject(Thread, INFINITE);
   CloseHandle(Thread);
end;

"Sortiere" sortiert den Array mit einem bestimmten Algorithmus (zb BubbleSort, MergeSort), der an einer anderen Stelle angegeben wird. Das bedeutet es wird nur auf die 4*len Bytes an der Stelle "PArr^" zugegriffen und je nach Algorithmus zusätzlicher Speicher benutzt. Da PArr und len angepasst werden, sollten sich die einzelnen Threads also nicht in die Quere kommen...

[EWeiss]

OT:
Unfein ist auf jedenfall schon mal
das du mehrere threads erstellst diese anschließend schließt
ohne vorher geprüft zu haben ob die Handles überhaupt existieren.

gruss

[Namenloser]

Delphi-Quellcode:

         WaitForSingleObject(Thread1, INFINITE);
         WaitForSingleObject(Thread2, INFINITE);

könntest du zumindest schon mal ersetzen durch WaitForMultipleObjects.

Desweiteren würde ich schauen, nicht für jede „Ebene“ 2 neue Threads anzulegen, sondern z.B. nur, wenn die Anzahl der Elemente eine bestimmte Schwelle überschreitet. Im Prinzip müsstest du einen Dualcore sogar schon ausreizen können, wenn du nur die aller erste „Ebene“ aufsplittest (einen Quadcore respektive mit den ersten zwei Ebenen).

Das Erzeugen und Verwalten von Threads bedeutet einen nicht zu unterschätzenden Overhead. Wahrscheinlich ist dein Programm deshalb so langsan. Es gibt/gab sogar mal eine Richtlinie, dass ein Prozess nicht mehr als 16 Threads haben sollte – ob das noch aktuell ist, weiß ich nicht. Aber man sollte jedenfalls nicht übertreiben.

[blablab]

Da ich nur einen DualCore habe benutze ich nur 2 Threads (abgesehen vom 1. Thread der immer gestartet wird). Die Schwelle werde ich noch einbauen, sobald der Code funktioniert. Bis dahin arbeite ich mit genügend großen Arrays, bei denen sich das aufsplitten eigentlich lohnen sollte.
Und WaitForMultipleObjects werde ich gleich mal ausprobieren :-D

[Blup]

Zitat:

Zitat von blablab (Beitrag 1096217)

Da PArr und len angepasst werden, sollten sich die einzelnen Threads also nicht in die Quere kommen...

Zumindest liegt das Array in einem zusammenhängenden Speicherbereich, wenn ein Prozessor dort etwas ändert und der andere auf Daten zugreifen will, die im selben Adressegment des eigenen Cache liegen, hat er erst einmal Pause.

Versuchsweise könnte jeder Thread eine Kopie des zu sortierenden Teilarray erstellen, diese Kopie sortieren und zum Schluss zurückschreiben. Allerdings müsste man sicherstellen, das jede Kopie aus Sicht des Cache in einem anderen Adressegment liegt.