Warum ist das Multithreading so langsam?

[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

[Blup]

Zitat von blablab:

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.

[Neutral General]

@Blup: Das könnte man dann ja mit VirtualAlloc sicherstellen.

Allerdings klingt das für mich schon etwas übertrieben... Mhh..

[blablab]

wie groß ist denn so ein adresssegment?

[Neutral General]

Im Normalfall (unter Windows) 4KiB (4096 Bytes)