Multithreading

[Gruber_Hans_12345]

Hallo kann mal wer einen Blick auf meinen Code werfen - irgendwo habe ich da einen Denkfehler.

Das ist meine Threadklasse

Delphi-Quellcode:

type
    TTestThread = class(TThread)
    protected
        fWaitFinish         : THandle;
        fResumeEvent        : THandle;
        procedure Execute; override;
    public
        constructor Create();
        destructor Destroy; override;
    end;

destructor TTestThread.Destroy;
begin
    CloseHandle(fWaitFinish);
    CloseHandle(fResumeEvent);
    inherited;
end;

constructor TTestThread.Create();
var
    i           : integer;
begin
    fResumeEvent        := 0;
    fWaitFinish             := CreateEvent(nil, TRUE, FALSE, nil);
    FreeOnTerminate     := FALSE;
    inherited Create(TRUE);
end;

procedure TTestThread.Execute;

    procedure internalExecute;
    var
        i       : integer;
        x       : Byte;
    begin
        x   := 9;
        for i:=1 to 10000000 do begin
            x   := x xor (Random(9999999) mod 255);
        end;
        SetEvent(fWaitFinish);
    end;

begin
    fResumeEvent    := CreateEvent(nil, TRUE, FALSE, nil);
    repeat
        internalExecute;
        if Terminated then break;
        WaitForSingleObject(fResumeEvent, INFINITE);
        ResetEvent(fResumeEvent);
    until Terminated;
    SetEvent(fWaitFinish);
end;

Und so rufe ich das mit einer Art Threadpool auf

Delphi-Quellcode:

procedure TfrMDIChild.Button19Click(Sender: TObject);
var
    maxThreads      : integer;
    tempFunc        : TInterpreterFunDesc;
    hArrWait        : array of THandle;
    threadList      : array of TTestThread;

    function GetIdleThread : integer;
    var
        i           : integer;
    begin
        for i:=0 to maxThreads-1 do
            if hArrWait[i] = 0 then begin
                threadList[i]           := TTestThread.Create();
                hArrWait[i]             := threadList[i].fWaitFinish;
                Result  := i;
                exit;
            end;
        repeat
            Result  := WaitForMultipleObjects(length(hArrWait), @hArrWait[0], FALSE, INFINITE);
        until (Result >= 0) and (Result < maxThreads);
        Result  := Result - WAIT_OBJECT_0;
    end;

    procedure InitThreads;
    var
        i       : integer;
    begin
        setlength(threadList, maxThreads);
        setlength(hArrWait, maxThreads);
        for i:=0 to maxThreads-1 do
            hArrWait[i]     := 0;
    end;
    
var
    i               : integer;
    threadIdx       : integer;
    perfFreq        : int64;
    perfStart       : int64;
    perfEnd         : int64;
begin
    QueryPerformanceFrequency(perfFreq);

    QueryPerformanceCounter(perfStart);
    maxThreads      := TButton(Sender).Tag;
    InitThreads;
    for i:=0 to 100 do begin
        threadIdx   := GetIdleThread;
        if threadList[threadIdx].fResumeEvent = 0 then begin
            threadList[threadIdx].Resume;
        end
        else begin
            ResetEvent(threadList[threadIdx].fWaitFinish);
            SetEvent(threadList[threadIdx].fResumeEvent);
        end;
    end;
    QueryPerformanceCounter(perfEnd);

    setlength(threadList, 0);
    setlength(hArrWait, 0);
    QueryPerformanceCounter(perfEnd);
    Memo1.Lines.Add('Threading ('+IntToStr(maxThreads)+' Threads : '+FormatFloat('0.00', (perfEnd-perfStart) * 1000 / perfFreq)+' ms');
end;

Den Testbutton rufe ich einmal mit einem Thread auf und einmal das er acht Threads machen soll
Das Ergebnis ist dann

Code:

Threading (1 Threads : 4446,57 ms
Threading (8 Threads : 5980,15 ms

Was übersehe ich da das er bei 8 gleichzeitigen Threads die Dauer so lange ist? (Die CPU Auslastung geht aber da schön auf fast 100% hoch)

[Stevie]

Wie viele Kerne hat die CPU, auf der du das ausführst?

[Gruber_Hans_12345]

Entwicklungsrechner ist ein virtualisierter mit 4 Kerne
Aber auch auf meinem Rechner hier dann direkt die EXE getestet und der hat 8 "echte" Kerne.
Bei beiden das gleiche - mit einem Thread ist es am schnellsten

[fisipjm]

Hey Hans,

wenn ich deinen Code beim Überfliegen richtig verstanden habe, erzeugst du doch im

Delphi-Quellcode:

InternalExecute

Teil immer die gleiche Aufgabe, für egal wie viele Threads. Spich jeder Thread hat die gleich Aufgabe und bei dem 8 Thread Pool kommt dann eben noch der Overhead drauf für das Threadhandeling.

Oder hab ich da was übersehen?

Edit: Code nicht verstanden :oops:

[Stevie]

Wenn er 8 Kerne hat, dann musst du schon sicher stellen, das gar nix anderes läuft, damit er dieselbe Aufgabe 8mal durchführen kann auf 8 Threads, damit er genauso schnell ist, wie die Aufgabe 1mal auszuführen.
Ich habe das bei mit einem 12Kerner versucht bei mir (i7-12700, was nen 12-Kerner mit 8 P-Cores ist) und sehe in etwa die selbe Dauer mit einem oder mit acht Threads.

[Gruber_Hans_12345]

JA es soll im prinzip ienfahc 100 mal der code vom internalExecute ausgeführt werden - in dem Fall eine einfachste Version - die nichts anderes macht ausser primitive Berechnungen.

Daher sollte er mit 8 Threads ja meiner Meinung nach 8 mal so schnell sein wie mit einem Thread - okay ganzer Overhead und co aber zumindest 4 mal so schnell.

Und nicht wie in meinem Fall das es sogar langsamer ist diese 100 mal internalExecute auszuführen

[dummzeuch]

Was fisipjm schon schrieb: Solange Du die auszüführende Aufgabe nicht auf mehrere Threads verteilst sondern jeden Thread die komplette Aufgabe machen lässt, wird sich die Laufzeit nicht ändern. Im Gegenteil: Jeder zusätzliche Thread erhöht den Overhead.

Edit: Mist, gepennt. Man sollte nicht kommentieren, wenn man den Code nicht verstanden hat.

[Gruber_Hans_12345]

Hmm verstehe ich nicht ganz

Ich möchte 100 mal die funktion internalExecute aufrufen

bei einem thread wird der eine Thread das 100 mal aufrufen

bei 8 Threads verteilt es sich, und im idealfall muss jeder Thread die funktion nur 12.5 mal aufrufen

[himitsu]

Mir war so, als sei der Zufallsgenerator je Thread unabhängig,
aber wenn es nur einen Globalen gäbe, dann wäre die Sache klar.

* in aufgerufenen Funktionen kann eine Synchronisierung drin sein
* und dann die Speicherzugriffe ... wenn alle Kerne auf den selben Speicher zugreifen, dann blocken viele CPUs hier auch gern

[Gruber_Hans_12345]

Zitat:

Zitat von himitsu (Beitrag 1524839)

Mir war so, als sei der Zufallsgenerator je Thread unabhängig,
aber wenn es nur einen Globalen gäbe, dann wäre die Sache klar.

* in aufgerufenen Funktionen kann eine Synchronisierung drin sein
* und dann die Speicherzugriffe ... wenn alle Kerne auf den selben Speicher zugreifen, dann blocken viele CPUs hier auch gern

Danke das wars
Ohne Random verhält es sich nun wie ich es erwarte ...
Komisch im Source vom Randsom sieht man keine CriticalSections oder co


Aber nun kann ich weiter testen danke

[himitsu]

Wenn es eine globale Variable ist, dann streiten sich die Kerne darum.

Aber mir war so, als wären es Threadvars ...


[edit]
Bin erschreckt, aber ErrorAddr und RandSeed sind wirklich

Delphi-Quellcode:

var

anstatt

Delphi-Quellcode:

threadvar

:shock:

[Gruber_Hans_12345]

Hmmm blöd gefragt ich dachte wenn es eine 0815 globale Variable ist, dann greifen die Threads einfach direkt darauf zu, und es kann passieren das da dann Müll rauskommt wenn einer schreibt und einer liest und nicht das sich das ganze dann so verhält wie wenn es in einer criticalsection stehen würde?

dh meiner Meinung nach dürfte eine "normale" variable den Thread nicht verlangsamen sondern es kann passieren das irgendwelche komischen Fehler passieren (wenn die nicht in einer CriticalSection sind)

[Uwe Raabe]

Das Problem entsteht durch die unterschiedlichen Caches der Kerne. Die CPU liest ja nicht von und schreibt ja nicht in den tatsächlichen RAM-Bereich, sondern wickelt das über den Cache ab. Dazu wird ein Bereich des RAM in den Cache transferiert (die sogenannte Cache Line) und später wieder geschrieben. Die dabei unweigerlich entstehenden Zugriffsprobleme werden durch das Sperren des zugehörigen RAM-Bereich vermieden. Deswegen müssen die Kerne manchmal eben warten - auch beim Lesen.

Wegen der Größe der Cache Line (i.d.R. 64 Bytes) kommt der Effekt auch zum tragen, wenn nicht mal nur dieselbe Variable verwendet wird, sondern sich z.B. auch zwei Variablen in derselben Cache Line befinden.

[himitsu]

Die Threads prinzipiell ja, außer im Maschinencode/Assembler gibt man z.B. LOCK an ( MOV a, b -> LOCK MOV a, b ).

Aber dennoch kann nicht jeder Thread Kern einfach so gleichzeitig auf jegliche "externe" Hardware zugreifen, wie z.B. den RAM.

zugeteilte Speicherseiten, vorhandener Cache Cacheline usw ... macht jeder Prozessor-Architektur eventuell auch noch jeweils anders.
Es gibt ja auch nicht für jeden Kern ein eigenes Kabel zu jedem Speicherchip.



Oder anders gesagt, so lange jeder Thread möglichst GARNICHTS mit anderen Threads teilt, dann ist es optimal. (bzw. auch nichts, was nur zufällig in der Nähe liegt)

[Stevie]

Zitat:

Zitat von Gruber_Hans_12345 (Beitrag 1524840)

... im Source vom Randsom ...

OT: Putziger Verschreiber ;)

Zum Thema: Davon abgesehen, dass Random nicht threadsafe ist, hast du hier den klassischen Fall von Code, dessen Multithreadgeschwindigkeit davon gebremst wird, dass shared memory immer übern RAM zu jedem Kern wandern muss.

Auch wenn hier RandSeed, was innerhalb von Random genutzt wird, nicht irgendwie abgesichert wird, ist es doch so, dass jeder Schreibvorgang der CPU signalisiert, dass der Speicher geschrieben wurde, was dazu führt, dass jeder andere Kern, der diesen Wert liest, ihn erst wieder aus dem RAM lesen muss. In deinem Fall führt das dazu, dass die verschiedenen Kerne massiv davon gebremst werden, dass der Wert dieser globalen Variable tausendfach über den RAM zwischen den Kernen hin und her wandert.

Im VTune kann man das sehr schön sehen - siehe Anhang

[Gruber_Hans_12345]

Okay Danke das ist echt "krass" das durch den Cache das sooo extremst langsam wird dann.

jeweils 100 Durchgänge auf 8 Kerne - dh mit 8 Threads dauert ein einzelner Durchgang ca 16 mal so lange - (er sollte ja 8 mal schneller sein und braucht doppelt so lang)

Threading (1 Threads) : 3199,55 ms
Threading (2 Threads) : 5985,58 ms
Threading (4 Threads) : 6630,61 ms
Threading (8 Threads) : 6957,30 ms

[Gruber_Hans_12345]

Hab jetzt nur zum Gegencheck den Ransom ähmm Random als lokal funktion eingebaut

Delphi-Quellcode:

procedure internalExecute;
    var
        i       : integer;
        x       : Byte;
        dummy   : int64;
        RandSeed : integer;

        function myRandom(const ARange: Integer): Integer;
        asm
        {     ->EAX     Range   }
        {     <-EAX     Result  }
                PUSH    EBX
                XOR     EBX, EBX
                IMUL    EDX,[EBX].RandSeed,08088405H
                INC     EDX
                MOV     [EBX].RandSeed,EDX
                MUL     EDX
                MOV     EAX,EDX
                POP     EBX
        end;
        
    begin
        QueryPerformanceCounter(dummy);
        RandSeed    := dummy;

        x   := 9;
        for i:=1 to 1000000 do begin
            x   := x xor (myRandom(23223) mod 255);
            //x   := x xor (i mod 255);
        end;
        //*)
        SetEvent(fWaitFinish);
    end;

und siehe da nun stimmen die Zeiten zu dem was ich mir vorgestellt habe :D

Code:

Threading (1 Threads : 3289,73 ms
Threading (2 Threads : 1670,74 ms
Threading (4 Threads : 851,50 ms
Threading (8 Threads : 426,44 ms

Damit ich es nochmal verstehe das genau das das Problem ist.

Kern 1 lädt die 64Byte wo die variable RandSeed ist in die CacheLine des Kern1
Kern 2 ... Kern 4 machen das gleiche
da nun einer der Kerne die Variable Randseed ändert, muss der Kern nun die 64Byte aus der CacheLine wieder zurück in den RAM speichern - und dabei markiert er bei allen anderen Kernen nun das die 64 Byte die die anderen Kerne in der Cacheline haben ungültig sind und diese müssen die nun erneut laden.

1. Das passiert aber nur wenn der Kern auch Daten ändert, ein nur lesen wäre kein Problem gewesen
2. Je mehr Kerne da nun das ausgeführt hätten, desto langsamer würde das werden (die Anzahl der Threads ist nebensächlich, da wenn 10 Threads auf einem Kern laufen es ja auch nur eine CacheLine gibt) nur die echten Kerne die auch eine CacheLine haben zählen hier
3. Wie sicher ist die 64Byte Grenze, und wie kann man das im echten Leben dann sicherstellen das die Variablen sich nicht überschneiden?

[himitsu]

Inzwischen kann man in Delphi ein eigenes Random registrieren.
Dort könnte man Eines mit TheadVar bauen. (und wenn noch RandSeed=0, dann darin zuerst noch ein Randomize)

[Uwe Raabe]

Delphi-Quellcode:

System.TMonitor

hat das in

Delphi-Quellcode:

CacheLineSize

stehen, aber da kommt man wegen

Delphi-Quellcode:

strict protected

nicht so einfach ran. Intern wird das benutzt, damit ein

Delphi-Quellcode:

TMonitor

Record immer mindestens so groß ist wie eine Cache Line.

Du kannst dir aber den entsprechenden Code in

Delphi-Quellcode:

GetCacheLineSize

oder

Delphi-Quellcode:

GetCacheSize

abgucken.

[himitsu]

Wie läuft es mit den Zeiten, wenn

Delphi-Quellcode:

SetThreadAffinityMask(GetCurrentThread {oder Self.Handle}, $00000001);

als Erstes im Execute, mit originalem Random.

Gilt nur, wenn du maximal 64 Kerne hast, sonst fängt man eventuell auch noch mit Prozessorgruppen an.

[Stevie]

Zitat:

Zitat von Gruber_Hans_12345 (Beitrag 1524847)

Damit ich es nochmal verstehe das genau das das Problem ist.

Kern 1 lädt die 64Byte wo die variable RandSeed ist in die CacheLine des Kern1
Kern 2 ... Kern 4 machen das gleiche
da nun einer der Kerne die Variable Randseed ändert, muss der Kern nun die 64Byte aus der CacheLine wieder zurück in den RAM speichern - und dabei markiert er bei allen anderen Kernen nun das die 64 Byte die die anderen Kerne in der Cacheline haben ungültig sind und diese müssen die nun erneut laden.

Korrekt, das ganze nennt sich Cache-Kohärenz

Zitat:

Zitat von Gruber_Hans_12345 (Beitrag 1524847)

1. Das passiert aber nur wenn der Kern auch Daten ändert, ein nur lesen wäre kein Problem gewesen
2. Je mehr Kerne da nun das ausgeführt hätten, desto langsamer würde das werden (die Anzahl der Threads ist nebensächlich, da wenn 10 Threads auf einem Kern laufen es ja auch nur eine CacheLine gibt) nur die echten Kerne die auch eine CacheLine haben zählen hier
3. Wie sicher ist die 64Byte Grenze, und wie kann man das im echten Leben dann sicherstellen das die Variablen sich nicht überschneiden?

1. korrekt, wenn sich nix ändert, muss auch nichts abgeglichen werden
2. richtig
3. "Niemand wird mehr als 64Byte große Cachelines benötigen" - Spaß beiseite, derzeit ist das auf allen gängigen CPUs (zumindest auf denen Delphi läuft) ausschließlich so. Man kann das nun so machen wie das, was Uwe schon erwähnt hat, oder man setzt fest auf 64 Byte und kümmert sich darum, das anzupassen, sollte es mal passieren, dass CPUs rauskommen, bei denen das anders ist.
Hier ist ein Beispiel, wie ich das in Spring gelöst habe, damit sich Daten nicht überschneiden. Beim Allokieren des Speichers muss ich dann noch den Speicher auf 64byte alignen, damit die Daten immer genau in einer Cacheline liegen.

[himitsu]

Statt "blind" 64 Byte, kannst'e auch einfach 8KB oder 64KB nehmen oder Sicherheitshalber 1GB :lol:

Da belegt zwar die Variable bissl unnötig viel Speicher, aber was soll's. :stupid:

Nja 64 bzw 8 KB sind die Größen, wie Windows den RAM verwaltet.
64KB die Mindestgröße beim VirtualAlloc, aber intern dennoch nochmal in 8KB Stückchen verwaltet.
Größer wird wohl keiner "diesesn" Cache bauen.
* erstmal unnötig viel Platz in der CPU und wenn die CacheLine abgeglichen werden muß, müsste dann auch noch viel mehr geladen werden, was dann wiederrum auch viel mehr Zeit verschlampt.

[Gruber_Hans_12345]

Zitat:

Zitat von himitsu (Beitrag 1524851)

Wie läuft es mit den Zeiten, wenn

Delphi-Quellcode:

SetThreadAffinityMask(GetCurrentThread {oder Self.Handle}, $00000001);

als Erstes im Execute, mit originalem Random.

Gilt nur, wenn du maximal 64 Kerne hast, sonst fängt man eventuell auch noch mit Prozessorgruppen an.

Also damit braucht er mit egal wievielen Threads immer annähernd gleich lang (bisschen overhead)
Ist aber doppelt so schnell wie wenn sich die verschiedenen Kerne den Cache ständig ungültig machen.

[himitsu]

Ja, so lange es gleich schnell ist, ist alles OK. (sind ja auch alle Threads an den selben Kern gebunden :lol:)
Schlimm wäre es nur, wenn es bei mehr Threads viel langsamer würde. (ein Bissl ist klar, durch die Overhad der Threadverwaltung)