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 von blablab:

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