Assemblercode - Noch optimierbar?

Oki, hier die EXE meines Assemblercodes als FPU-Lösung aus Post #6 als Consolenanwendung in 1536 Bytes....Der identische Assemblercode, also auch knapp 1kByte in eine AutoIt-EXE kompiliert, ist knapp 1,15MB groß, also ca. 1000 (tausend! ) mal größer
Die in der CMD angegebene Zeit ist natürlich die reine Laufzeit des Codes (ohne das Laden der Exe zu berücksichtigen, das ist imho auch nonsens)
Pi_calc_Andy.zip

Bei mir hat Avira angefangen, irgendwelche Trojaner zu entdecken, als ich in den ASM-Code die Zeile
NUMBER dq 0.0
eingefügt hatte...damit wird nichts weiter gemacht, als 8 Bytes mit Nullen zu füllen
Wer will, kann die Datei einfach in FASMW laden und F9 drücken...

Zitat von chesstiger

Ich probiere morgen mal das ein oder andere hiervon aus und schaue mal, ob das noch was bringt.

Ich werde bei der SSE/SIMD-Version Loop-Unrolling testen, und dann auch nicht die Zeit messen, sondern die benötigten Prozessortakte per RDTSC. Da lässt sich dann wesentlich besser optimieren, wenn man bspw. aus 10 Durchläufen den schnellsten nimmt.
//EDIT Loop unrolling und umsortieren bzw. "parallelisieren" (reorder/pairing) in der Instruction-Pipeline bringt zumindest bei meinem Prozessor nichts...
Ich habe aktuell 5.22 Prozessortakte pro Schleifendurchlauf. Da der sub ecx,1 und das anschließende jnz _loop zusammen 0,77 Takte benötigen, bleiben für die 4 SSE-Befehle 4.5 Prozessortakte.
Jetzt wird es interessant, denn das DIVPD benötigt allein 6.2 Takte!!! Durch die verschiedenen parallel arbeitenden Pipelines werden die Prozessorbefehle nicht "nacheinander" sondern wenn möglich gleichzeitig abgearbeitet. Man kann mehrere Zeilen völlig unnötiger Befehle in die Schleife einfügen, an der Laufzeit ändert sich...nichts!!!
Daher ist es sinnvoll beim Optimieren, wenn man sich die die sog. Serialisierung vornimmt und ausrechnet, welcher Befehl am besten wo in der Reihenfolge steht...um die "teueren" Abhängigkeiten (dependencies) aufzulösen!
http://www.agner.org/optimize/optimizing_cpp.pdf
http://www.agner.org/optimize/optimizing_assembly.pdf
http://www.agner.org/optimize/microarchitecture.pdf <-- DAS ist richtig klasse! Ich gehe davon aus, dass Compilerbauer dieses Dokument unter dem Kopfkissen liegen haben

@Mars, natürlich habe ich deine EXE laufen lassen und auch versucht zu disassemblieren, daher auch die Info, dass die Datei eine 64-Bit-Code-EXE ist und auch SSE-Befehle nutzt!

@Alle interessierten, und vor allem die, welche meinen, ein Compiler würde "automatisch" den besten Code erzeugen, ein (ihr kennt mich ja) ernst gemeinter Hinweis bzw. auch mal ein Grund, "nachzudenken".
Mal angenommen, ein "cleverer" Compiler merkt bei der Analyse des Codes, dass sich eine bestimmte Variable immer weiter an PI annähert.
Mit dem FPU-Befehl FLDPI, der aus 2 Bytes besteht und eine "Laufzeit" von 2-3 Prozessortakten hat, wäre PI auf 80bit genau bestimmt, und man könnte sich den Algorithmus sparen...
Mal weiter angenommen, im Code wäre dieses PI "zu genau" für weitere Berechnungen, dürfte dann der Compiler die ungenaue "Berechnung" von PI mit einem "besseren" PI ersetzen um im Endeffekt ein wesentlich schnelleres und genaueres Ergebnis auszugeben?
Was aber, wenn ich genau diese "ungenauen" Ergebnisse aber benötige, sollte ich als Programmierer dann die Wahl haben, "meinen" und genau diesen MEINEN Code generiert zu bekommen, oder doch den "optimierten" Code des Compilers?

Kurze Frage an alle, hat schon jemand die "neuen" (jaja, die gibts auch schon einige Jahre) AVX und/ oder FMA-Befehle ausprobiert?
Leider unterstützt mein Laptopprozessor diese Features nicht.
Imho sollte sich mit diesen Befehlen erstens alleine durch die Verdopplung der Registerbreite bei AVX (256Bit statt 128 wie bei SSE) die Berechnung durch 4 statt 2 gleichzeitiger Berechnungen verdoppeln! Der RCP (reziprok)-Befehl ist dort auch voerhanden....
Ob dann nochmal durch die Verwendung von FMA (a=b+c*d in einem Takt) eine Beschleunigung erreicht werden könnte, ist die Frage?!

Die innere Schleife zur Berechnung von Pi/4 erfolgt ja zzt in 4 Prozessorbefehlen

1.0 ins Register laden
1.0/positive und 1.0/negative berechnen
positive+4 und negative-4 berechnen
PIpositive+=positive und PInegative+=negative

Diese Schleife kann man bei AVX genau so beibehalten, da man nun aber 4 statt 2 Double in einem Register unterbringen kann, halbiert sich die Anzahl der Schleifendurchläufe =>doppelte Geschwindigkeit! DOPPELT!

Die Frage ist, ob FMA zu benutzen ist, also a=b+c*d in einem Takt und das noch serialisierbar hat ja was!

Zitat von chesstiger

Die Zeitmessung per Linux' time haben wir deswegen gewählt, damit nicht in jeder zu testenden Sprache noch die Zeitmessung selbst implementiert werden muss. Dass da auch einiges an Overhead gemessen wird, ist klar. Das war aber in diesem Moment die praktikabelste Lösung.

Aus dem Bauch raus würde ich vermuten, dass der Overhead Programm laden/starten/beenden im Bereich von 2-4 Millisekunden liegt...und da du bei jedem zu testenden Programm diesen Overhead hast, ist sogar mal egal, wenn der Wert um eine Handvoll Millisekunden driftet. Also alles im grünen Bereich!

Zitat von chesstiger

Ich habe meinen Code nach euren Vorschlägen ein wenig optimiert.

Hut ab!
Nachdem ich deinen ursprünglichen Code nach FASM portiert hatte um direkt zu vergleichen, hatte ich festgestellt, dass dein ursprünglicher Code schon sehr schnell war!
Wenn man die Laufzeiten analysiert (ich benutze dazu keine Zeitmessung, sondern zähle per RDTSC Takte) dann stellt man fest, dass sich die vermeintlichen "teueren" Speicherlese/schreibebefehle gar nicht so arg auswirken. Das hat einfach damit zu tun, dass bspw. die Schleifenzählvariablen in einer extra Pipeline parallel zu den FPU-Befehlen abgewickelt werden. Dazu liegen die Variablen entweder im Level1-Cache oder auf dem Stack, welcher idR. auch immer gecached ist! Ausführungszeit ca. 1-2 Takte pro DWORD laden!
Im Vergleich zu den ca. 30-40 Takten für einen einzigen FDIV/FIDIV fällt das nicht sonderlich ins Gewicht.
Daher hatte ich auch keinerlei Ambitionen, dort in eine Optimierung zu investieren, mein FPU-Code sollte nur zeigen, wie man den FPU-Stack nutzen kann.

Zitat von chesstiger

Allerdings zeigen sich bei mir ein paar interessante Phänomene.

Gratuliere!
Du hast begriffen, um was es geht!
Ich bin davon überzeugt, dass dir die vergangenen Stunden für die Analyse und das rumprobieren an deinem ASM-Code für dein gesamtes weiteres Programmiererleben (vor allem mit HLL´s) viele Vorteile bringen werden.
Wenn schon allein für diese "Pillepalle"-Anwendung mit der sehr kleinen Schleife so immense Unterschiede in der Laufzeit (vgl. UEZ´s erste Compilerversionen) feststellbar sind, was bringen dann erst Optimierungen für lange rechenintensive Schleifen!?

Im Grunde ist natürlich völlig egal, ob das Programm einige Millisekunden mehr oder weniger benötigt. Aber eine Beschleunigung um Faktor 3 für gewisse Anwendungen (bspw. Grafikfilter/analyse) ist ein definitives Kaufkriterium! Und damit wird dann Geld verdient...bestenfalls dein eigenes oder das deines Arbeitgebers

Bin gerade auf einem Tablet mit Atom Z3735F@1300Mhz unterwegs und habe mal die beiden Versionen FPU und SSE verglichen. Ernüchterung sondergleichen, beide annähernd gleich schnell!
Kurz mal bei Agner Fog geblättert, nun ist auch klar warum!
Der SSE Befehl DIVPD, welcher gleichzeitig zwei 64-Bit-Double dividieren kann, wird im Kapitel für den Atom folgendermaßen erwähnt:

Zitat von http://www.agner.org/optimize/microarchitecture.pdf

Division is slow and not pipelined. A single precision scalar floating point division takes 30clock cycles. Double precision takes 60 clock cycles. A 64-bit integer division takes 207clock cycles.

60 Takte für eine Division....ohne Worte...die "richtigen" Prozessoren machen das in 15-20 Takten (//EDIT wenn pipelined genaugenommen dann in 6-7 Takten) , also mindestens 3-4x schneller! Weiterhin sind auch die ADDPD nicht pipelined, das fällt aber garnicht ins Gewicht!

Wenn man optimiert, sollte man also auch die Plattform im Auge behalten, ansonsten kann man sich die Arbeit sparen
Allerdings kann es aber auch sein, dass man auf einem bestimmten Prozessor ohne großartigen Gewinn optimiert, und dieser Code aber auf einer anderen Maschine eine immense Beschleunigung erlebt!
Knowhow ist durch nichts zu ersetzen, außer durch mehr Knowhow

Zitat von Andy

Knowhow ist durch nichts zu ersetzen, außer durch mehr Knowhow

Oder einen besseren Prozessor, das ist heute üblich.

Zitat von Andy

Wenn schon allein für diese "Pillepalle"-Anwendung mit der sehr kleinen Schleife so immense Unterschiede in der Laufzeit (vgl. UEZ´s erste Compilerversionen) feststellbar sind, was bringen dann erst Optimierungen für lange rechenintensive Schleifen!?

Was lernen wir daraus? Shit in - Shit out. Ergo, der Compiler schafft keine Wunder.

Zitat von UEZ

Was lernen wir daraus? Shit in - Shit out. Ergo, der Compiler schafft keine Wunder.

Ergo kein Widerspruch zu meiner Behauptung.
Übrigens mal Daumen hoch, tolle Optimierung die ihr betrieben habt
Ein Gedanke zum loop unrolling noch @Andy - Angenommen du weißt wie viel stages deine Pipeline hat, für die Division, dann könntest du den Loop meines Theorieverständnisses nach auf diese Abrollen und als Step Größe die Anzahl der Stages nehmen.
Andererseits Frage ich mich ob das wirklich einen Unterschied macht, da die Heuristik der Pipeline in dem Falle nur 1, maximal 2 Mal falsch liegt, und das ist wenn auf einmal nicht gesprungen sondern die Schleife verlassen wird.

Und wir sind hier nur langweilige Skriptsprachenkiddies (wie uns die "richtigen" Programmierer gerne nennen), was würde erst passieren, wenn jemand der auch Ahnung hat den Code optimieren würde [PLENK][/ironie] ?

Jedenfalls Gute Arbeit Leute

lg
M

Zitat von Xorianator

Oder einen besseren Prozessor, das ist heute üblich.

Und, wie oben anhand der Beispielcodes gezeigt, meistens überflüssig und falsch!
Wohin ging denn die Entwicklung zu "besseren" Prozessoren in den letzten Jahren? Stromsparen, ok! Schneller deswegen? Kein Stück! Mal abgesehen von technischen Machbarkeitsstudien (bspw. Intel 6950X (10 Kerne, 20 Threads) für atm 1700€), die aufgrund von Strukturverkleinerungen in der Fertigung nun einige Megaherz höher getaktet werden können.
Mehr Prozessor-Cache wo es nur geht...macht Sinn, denn die Compiler werfen Unmengen an Code/Daten in den Ring.
Und um mal zu vergleichen: der 1700€ teuere 6950X schlägt den 200€ teuren i5-6500 bei Single-Thread-Anwendungen nicht! Oha! Wieso auch Single Thread? Werden denn nicht sämtliche Anwendungen schon so compiliert, dass sie die vielen Prozessorcores und die darin enthaltenen SIMD-Funktionen "optimal" ausnutzen? Eben nicht....
Und genau deshalb macht es auch keinen Sinn, einen "besseren" Prozessor zu kaufen um eine Software zu beschleunigen, wenn diese Software nicht in der Lage ist die Features des Prozessors auch nur ansatzweise auszunutzen!
Spielehersteller haben erst in den letzten Jahren begonnen, ihre Software auf Multicore/thread umzustellen. Man konnte auch den Kunden schlecht erklären, wieso für das Daddeln eines 50€-Spiels eine 1500€ teure und hunderte von Watt elektrischer Leistung verballernde Maschine gekauft werden muss!
Die dann aber, was für ein hochgradig geistiger Dünnschiss, beim (Script-)Programmieren per Sleep() permanent im Tiefschlaf gehalten werden muss. "...Quiiiiieeek, meine Prozessorlast liegt bei 8%, quiiieeekkk, ogottogott, mein Prozessor arbeitet für das viele Geld was er gekostet hat, DAS kann und darf ja nicht sein!!!..."
Da wird der Prozessor bis an die Grenzen übertaktet, um dann in den untersten P-states vor sich hinzuschlafen......

Was mich an dieser Stelle bzgl. Prozessor/Hardwareverbesserung wirklich gefreut hat, war bspw. die Beschleunigung des DIV/IDIV-Befehls. Der war schon immer "teuer" und hat, nachdem u.a. dieser eine Befehl innerhalb des Prozessors beschleunigt wurde, für teilweise immense Beschleunigungen der (nicht veränderten) Software gesorgt! Wenn man sich klar macht, dass dieser Schritt ca. 30 Jahre dauerte, kann man ermessen, welche Fortschritte Software gemacht haben könnte, wenn in dieser Zeit die in den Prozessoren NICHT GENUTZTEN FEATURES benutzt worden wären...

Warum bei einem "aktuellen" und unverschämt billigen Atom-Prozessor diese schnell abgearbeiteten Befehle nicht implementiert sind, sollte klar sein. NIEMAND aber auch niemand würde einen zehnfachen Preis für gerade mal 30 bis 40% mehr Leistung ausgeben! Intel käme sicherlich mit der Produktion von Atom-Prozessoren nicht mehr hinterher, davon würde jeder PC-Hersteller 8-10 in eine Kiste packen und so einen "Superserver" für wenig Geld bereitstellen können...

Zitat von Mars

Und wir sind hier nur langweilige Skriptsprachenkiddies

Ein wichtiger Grundsatz in der Optimierung lautet: "Zuerst die großen Brocken!"
Man muss herausfinden, wo eine Optimierung am meisten lohnt. Und das ist unabhängig davon, ob bei Hardware, Software oder in jedem anderen beliebigen Arbeitsablauf optimiert werden soll. Irgendwann ist ein Punkt erreicht, wo man die nur immer kleiner werdende "Verbesserung" den hohen Kosten/Aufwand gegenüberstellen muss,
Dann macht es meistens Sinn, die Optimierung an ein weiteres, bis dato zu diesem Prozess unvoreingenommenes, Team abzugeben. Oft werden dann durch andere Lösungsansätze noch einmal Verbesserungen erreicht.

Zitat von Xorianator

Ein Gedanke zum loop unrolling noch @Andy - Angenommen du weißt wie viel stages deine Pipeline hat, für die Division, dann könntest du den Loop meines Theorieverständnisses nach auf diese Abrollen und als Step Größe die Anzahl der Stages nehmen.
Andererseits Frage ich mich ob das wirklich einen Unterschied macht, da die Heuristik der Pipeline in dem Falle nur 1, maximal 2 Mal falsch liegt, und das ist wenn auf einmal nicht gesprungen sondern die Schleife verlassen wird.

Ja, die Frage, ob es einen Unterschied macht, kann man ja ausprobieren
Das habe ich auch gemacht, für SSE/SIMD. Da der Loop aber nur aus 4 Befehlen besteht, und auch Abhängigkeiten (Dependencies) innerhalb des Codes bestehen, lohnt sich das unrolling hier nicht.
Die 10-20 Takte für den DIVPD sind zu "fett", um mit anderen Befehlen parallelisiert zu werden. Das macht in langen Sequenzen sicherlich mehr Sinn.
Bei der Sprungvorhersage (branch-prediction) sieht es ähnlich aus. Da die handvoll Befehle sowieso alle in die Befehls-Ausführungspipeline passen, ist es auch völlig egal, ob die Sprungvorhersage IMMER FALSCH liegt! Die 4 Befehle für die "falsche" Vorhersage laufen ja parallel mit....der Inhalt der Pipelines muss nie umsortiert werden.

Was sicherlich eine Option wäre, ist Multithreading. Man müsste mal probieren, inwieweit sich dieser Schritt bei der vergleichsweise "billigen" Berechnung lohnt.
Durch Overhead und Threadgedöns vermute ich mal Faktor +0,7 für jeden zusätzlichen Thread. Bei einem Quadcore also ca. Faktor 3.
Da mit AutoIt ja Multithreading in Kombination mit ( idR IMMER threadsicherem) Assemblercode ziemlich easy ist, sollte man das mal ins Auge fassen.
Dann wäre imho für eine CPU das Limit erreicht.

#Region                                                                      ;**** Directives created by AutoIt3Wrapper_GUI ****
#AutoIt3Wrapper_UseUpx=n
#EndRegion                                                                   ;**** Directives created by AutoIt3Wrapper_GUI ****
;~ #include "AssembleIt2.au3"
#include <Array.au3>


;struct mit Buchstaben erstellen, um die unterschiedliche Laufzeit der beiden Threads darzustellen
$struct = DllStructCreate("char[4]")                                         ;platz für 4 Buchstaben
$ptr = DllStructGetPtr($struct)


;platz für Bytes, der gleiche code wird von jedem Thread einzeln aufgerufen
;~ $ret = _AssembleIt2("retbinary", "testthreads")                              ;assemblieren
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $ret = ' & $ret & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
$ret = "0x8B74240489F1C1E1028B7C24080F3189D30F3129DA39CA7CF889F083C0408886CFE4AD02C3"
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $ret = ' & $ret & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
$thread1_struct = DllStructCreate("byte[" & StringLen($ret) / 2 - 1 & "]")   ;asmcode
$ptr_asm = DllStructGetPtr($thread1_struct)
;bytecode in struct schreiben
DllStructSetData($thread1_struct, 1, $ret)




#cs testthreads
    use32
    mov esi,[esp+4]                                                          ;parameter laufzeit
    mov ecx,esi                                                              ;
    shl ecx,2                                                                ;vervierfachen, thread 1 soll doppelt so lange laufen wie thread 2
    mov edi,[esp+8]                                                          ;Integer belegen
    ;Zeitschleife
    rdtsc                                                                    ;counter in eax
    mov ebx, edx                                                             ;obere 32 Bit merken  ebx=timerinit()
    _wait:
    rdtsc                                                                    ;counter in eax
    sub edx,ebx                                                              ;timerdifferenz von aktuellem timestamp zum gemerkten timestamp ebx=timerdiff(ebx)
    cmp edx,ecx                                                              ;ecx einheiten (2^32 Takte) vergangen?
    jl _wait                                                                 ;wenn weniger, dann _wait
    ;zeitschleife ende
    mov eax,esi                                                              ;parameter in eax
    add eax,64                                                               ;einen ansi-Buchstaben machen
    mov byte[$ptr-1+esi],al                                                   ;buchstabe in struct schreiben
    ret
#ce


$hgui = GUICreate("Multithread Test", 400, 400)
$lbl = "Es werden mehrere Threads gestartet, währendessen " & @CRLF & "läuft das AutoIt-Script weiter..."
$lbl = GUICtrlCreateLabel($lbl, 10, 10, 400, 50)
$btn = GUICtrlCreateButton("Los gehts!", 200, 300, 100, 30)




$uhr = GUICtrlCreateLabel("", 10, 60, 200, 30)                               ;uhr


$lbl_struct = GUICtrlCreateLabel("", 10, 100, 200, 30)
$lbl_runtime = GUICtrlCreateLabel("", 10, 150, 200, 100)
$lbl_ende = GUICtrlCreateLabel("", 10, 250, 200, 30)


GUISetState()




While Sleep(10)
    $msg = GUIGetMsg()
    If $msg = -3 Then Exit
    If $msg = $btn Then _threads()
    $zeit = "Zeit: " & @HOUR & ":" & @MIN & ":" & @SEC & ":" & @MSEC
    GUICtrlSetData($uhr, $zeit)
WEnd






Func _threads()
    ;3 Threads vom gleichen Maschinencode aufrufen, das Autoitscript läuft weiter
    ;der zweite Thread läuft doppelt so lange wie der erste
    ;jeder Thread schreibt nach einer gewissen Zeit einen Buchstaben ascii(64+param) in die struct
    ;der erste Thread schreibt ein A an die erste Position
    ;der zweite Thread schreibt ein C an die 3. Position
    ;der dritte Thread schreibt ein B an die 2. Position


    DllStructSetData($struct, 1, "XXXX")


    $param = 2                                                               ;B
    $ret3 = DllCall("kernel32.dll", "hwnd", "CreateThread", "ptr", 0, "dword", 0, "long", $ptr_asm, "ptr", $param, "long", 0, "int*", 0)
    $param = 3                                                               ;C
    $ret1 = DllCall("kernel32.dll", "hwnd", "CreateThread", "ptr", 0, "dword", 0, "long", $ptr_asm, "ptr", $param, "long", 0, "int*", 0)
    $param = 1                                                               ;A
    $ret2 = DllCall("kernel32.dll", "hwnd", "CreateThread", "ptr", 0, "dword", 0, "long", $ptr_asm, "ptr", $param, "long", 0, "int*", 0)


    $t = TimerInit()
    Local $flag1 = 0, $flag2 = 0, $flag3 = 0, $runtime = ""
    While Sleep(10)                                                          ;threads are running
        $zeit = "Zeit: " & @HOUR & ":" & @MIN & ":" & @SEC & ":" & @MSEC
        GUICtrlSetData($uhr, $zeit)
        GUICtrlSetData($lbl_struct, DllStructGetData($struct, 1))


        $eax1 = DllCall("Kernel32.dll", "int", "GetExitCodeThread", "ptr", $ret1[0], "dword*", 0) ;Rückgabe (EAX) aus den Threads
        $eax2 = DllCall("Kernel32.dll", "int", "GetExitCodeThread", "ptr", $ret2[0], "dword*", 0)
        $eax3 = DllCall("Kernel32.dll", "int", "GetExitCodeThread", "ptr", $ret3[0], "dword*", 0)
        ToolTip("AutoIt ist nicht geblockt!" & @CRLF & "EAX1 = " & $eax1[2] & "     EAX2 = " & $eax2[2] & @CRLF & "     EAX3 = " & $eax3[2] & @CRLF & "structinhalt: " & DllStructGetData($struct, 1))


        ;sind die threads alle fertig?
        $m = TimerDiff($t)
        If ($eax1[2] <> 259) And $flag1 = 0 Then
            $runtime &= "1. Thread fertig: " & Int($m) & " ms" & @CRLF
            $flag1 = 1
        EndIf
        If ($eax2[2] <> 259) And $flag2 = 0 Then
            $runtime &= "2. Thread fertig: " & Int($m) & " ms" & @CRLF
            $flag2 = 1
        EndIf
        If ($eax3[2] <> 259) And $flag3 = 0 Then
            $runtime &= "3. Thread fertig: " & Int($m) & " ms" & @CRLF
            $flag3 = 1
        EndIf
        GUICtrlSetData($lbl_runtime, $runtime)
        If ($eax1[2] <> 259) And $eax2[2] <> 259 And $eax3[2] <> 259 Then ExitLoop ;so lange, wie noch keine Rückgabe aus den Threads erfolgt
    WEnd
    DllCall("Kernel32.dll", "int", "TerminateProcess", "ptr", $ret1[0], "uint", 0) ;Threads löschen
    DllCall("Kernel32.dll", "int", "TerminateProcess", "ptr", $ret2[0], "uint", 0)
    DllCall("Kernel32.dll", "int", "TerminateProcess", "ptr", $ret3[0], "uint", 0)
    ToolTip("")




    GUICtrlSetData($lbl_ende, "Geschafft!")
    ;MsgBox(0, "Structinhalt nach dem Beenden der beiden Threads", DllStructGetData($struct, 1))








EndFunc                                                                      ;==>_threads

Da aber der Leibniz-Algorithmus sehr gut zu parallelisieren ist, wäre es interessant, mal OpenCL auszuprobieren. Leider unterstützen die meisten Grafikkarten keine (dann nur per Softwareemulation) oder nur sehr langsame Double-Berechnungen. Die Beschleunigung durch die hunderte GPU-Prozessoren würde imho durch die Emulation von Double-Berechnungen mehr als aufgefressen.

Ein Thema ist mir noch in den Sinn gekommen -> Multithreading.

Ich habe mal mit FB verglichen, wie schnell 1 Thread zu 4 Threads sind.

Hier das Resultat:

x86:

1 Thread  PI: 3.14159265258805            11998.85867815465 ms for 1000000000 iterations.
4 Threads PI: 3.14159266258921            3342.891288688406 ms for 1000000000 iterations.

x64:

1 Thread  PI: 3.14159265258805            5485.781099298038 ms for 1000000000 iterations.
4 Threads PI: 3.14159266258921            2726.45756660495 ms for 1000000000 iterations.

Ich habe 1.000.000.000 (eine Milliarde) Durchgänge gewählt, dass man die Auslastung der CPU mitverfolgen kann -> Faktor ca. 3.6!

Source Code:

Type tParam
	ende As UInteger
	start As UInteger
	result As Double
End Type
Sub Thread_Leibniz_PI(ByVal pParam As tParam Ptr)
	Dim As Double fPI = 0.0, fSign = 1.0
	Dim As UInteger k
	For k As UInteger = pParam->start To pParam->ende
		fPI += fSign / ((k Shl 1) + 1)
		fSign = -fSign
	Next
	pParam->result = fPI * 4.0
End Sub
Function Leibniz_PI(n As UInteger) As Double
	Dim As Double fPI = 0.0, fSign = 1.0
	For k As UInteger = 0 To n - 1
		fPI += fSign / ((k Shl 1) + 1)
		fSign = -fSign
	Next
	Return 4 * fPI
End Function
Dim As UInteger iterations = 1000000000
Dim As Double fTimer = Timer
Print "1 Thread  PI: " & Leibniz_PI(iterations), 1000 * (Timer - fTimer) & " ms for " & iterations & " iterations."
Dim As Any Ptr pThread1, pThread2, pThread3, pThread4
Dim As tParam tParams(0 To 3)
tParams(0).start = 0
tParams(0).ende = iterations / 4
tParams(1).start = iterations / 4 + 1
tParams(1).ende = iterations / 2
tParams(2).start = iterations / 2 + 1
tParams(2).ende = iterations * 3 / 4
tParams(3).start = iterations * 3 / 4 + 1
tParams(3).ende = iterations - 1
fTimer = Timer
pThread1 = ThreadCreate(@Thread_Leibniz_PI, @tParams(0))
pThread2 = ThreadCreate(@Thread_Leibniz_PI, @tParams(1))
pThread3 = ThreadCreate(@Thread_Leibniz_PI, @tParams(2))
pThread4 = ThreadCreate(@Thread_Leibniz_PI, @tParams(3))
ThreadWait(pThread1)
ThreadWait(pThread2)
ThreadWait(pThread3)
ThreadWait(pThread4)
Print "4 Threads PI: " & tParams(0).result + tParams(1).result + tParams(2).result + tParams(3).result, 1000 * (Timer - fTimer) & " ms for " & iterations & " iterations."
Sleep

Vergleich Andy's ASM Code:

: $pi Leibnitz = 3.14159265258555
: Time [ms] = 2631.10135102957

Selbst 4 Threads schlagen den ASM Code von Andy nicht!

Oder ich den nehme gleich den ASM Code von Andy als Thread_Leibniz_PI Funktion. Dann sollte es brutal abgehen...

Zitat von UEZ

Code

1 Thread  PI: 3.14159265258805            12060.16655091662 ms for 1000000000 iterations.
2 Threads PI: 3.141592650585555           4845.030240947381 ms for 1000000000 iterations.

Wodurch kommt das unterschiedliche Ergebnis zustande? Die 9. Nachkommastellen stimmen nicht überein (sowie der Rest danach).
Ist er durch die 2. Threads durch doppelt so viele Iterationen gegangen und demnach genauer berechnet?

@alpines: ich habe den Code jetzt auch 4 Threads modifiziert. Ich vermute, dass die Unterschiede von der Addition der Teilergebnisse kommen.

Zitat von alpines

Wodurch kommt das unterschiedliche Ergebnis zustande? Die 9. Nachkommastellen stimmen nicht überein (sowie der Rest danach).

Das hatte ich in meinem Post zum SSE/SIMD-Code schon dargestellt!
Die FPU rechnet intern mit 80 Bit Genauigkeit, die SSE-Register sind 128 Bit breit und somit je nur 64 Bit (Double)!
Bei 10 Millionen Durchgängen summiert sich der "Rundungsfehler".
Abhilfe schafft, die FPU zum Rechnen mit 64Bit zu zwingen, aber wer macht das schon, die FPU ist sowieso schon schneckenlahm, da kann das Ergebnis wenigstens "genau"(er) sein....

Ich werden mal den ASM-SSE-Code per Autoit in Threads aufsplitten lassen, schaumamal...

Sodele, das ist imho das Ende der Fahnenstange...Multithreading in AutoIt

Ich lasse einfach Threads von 1 bis 24 laufen, ist natürlich Quatsch, idR sollte "Otto-Normalo-PC-User" Quad-, Hex-, oder Octa-Cores haben.
Bei mir zumindest bringen viele Threads nichts, ist auch klar, der Overhead frisst irgendwann den Gewinn völlig auf...aber spielt selbst mal rum.

Für meinen Laptop-Quadcore AMD @2.3Ghz:
Ich habe 1000000000 Durchläufe eingestellt, da bekomme ich folgendes Ergebnis für die ersten 10 Threads

Bei den aus dem Startpost vorgegebenen 10000000 Durchläufen erhalte ich

was man feststellen kann ist maximal ein Faktor 3 an Geschwindigkeit durch Multithreading! Aber auch nicht schlecht....

OpenCL anyone?

;aligncomment=50
;~ #include <assembleit2_64.au3>


#AutoIt3Wrapper_UseX64=n




#cs Pi_Leibnitz
    Use32                                          ;32Bit!


    mov eax,[esp+4]                                ;pointer auf die param[$i]-struct
    mov esi,eax                                    ;sichern


    mov ecx,[esi]                                  ;n
    mov ebx,[esi+4]                                ;Startpos
    mov edx,[esi+8]                                ;Step


    shr ecx,1                                      ;n/2 es werden pro schleifendurchgang das positive und negative aufsummiert


    xorpd xmm4,xmm4                                ;0.0 _ 0.0 die summe dieser beiden wird PI/4


    mov eax,4
    movd xmm6,eax
    pshufd xmm6, xmm6, 0xE0
    CVTDQ2PD xmm6, xmm6                            ;4.0 _ -4.0


    mov eax,1
    movd xmm0,eax
    pshufd xmm0, xmm0, 0xE0                        ;1   _ 1
    CVTDQ2PD xmm0, xmm0                            ;1.0 _ 1.0
    ;~      _asmdbg_()
    neg edx                                        ;step
    mov eax,edx
    movd xmm1,eax
    CVTDQ2PD xmm1, xmm1                            ;0.0 _ -4.0
    neg edx                                        ;4
    movd xmm2,edx
    CVTDQ2PD xmm2, xmm2                            ;0.0 _ -4.0
    PSLLDQ xmm2, 8                                 ;4.0 _ 0.0
    paddq xmm1,xmm2                                ;4.0 _ -4.0




    ;startpos positiv
    movd xmm2,ebx
    CVTDQ2PD xmm2, xmm2
    PSLLDQ xmm2, 8                                 ;1.0 _ 0
    add ebx,2
    neg ebx
    movd xmm3,ebx
    CVTDQ2PD xmm3, xmm3                            ;0.0 _ -3.0
    paddq xmm2,xmm3                                ;1.0 _ -3.0


    _loop:                                         ;so lange, bis ecx=0
    ;~         _asmdbg_("$ecx=1")
    movdqa xmm3,xmm0                               ;1.0 _ 1.0
    divpd xmm3,xmm2                                ;1/1 _ 1/-3
    addpd xmm2,xmm1                                ;positive um 4 erhöhen, negative 4 subtrahieren
    addpd xmm4,xmm3                                ;links positive rechts negative, die summe ist PI/4
    sub ecx,1                                      ;n=n-1


    ;~      _asmdbg_()
    jnz _loop                                      ;wenn ecx<>0 dann _loop


    pshufd xmm5, xmm4, 0x4E
    addpd xmm4,xmm5                                ;PI/4 _ -PI/4
    mulpd xmm4,xmm6                                ;PI _ -PI
    movhpd qword[esi+12],xmm4                      ;PI in struct speichern


    ;~     fld qword[esi+12]
    ret


#ce


;#############################################
$n = 10000000                                      ;Anzahl Durchläufe, wird an die Anzahl der Threads angepasst! Bei 3 Threads also nur 9999999
$pi = 0.0
$Threads_all = 24
;#############################################




;oder für das dllcalladdress
;~ $binarycode = _AssembleIt2("retbinary", "Pi_Leibnitz") ;gibt nur den assemblierten code zurück
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $binarycode = ' & $binarycode & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $binarycode = ' & $binarycode & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
;nur für dllcalladdress() benötigt, den binarycode braucht man nur ein mal erstellen




$binarycode = "0x8B44240489C68B0E8B5E048B5608D1E9660F57E4B804000000660F6EF0660F70F6E0F30FE6F6B801000000660F6EC0660F70C0E0F30FE6C0F7DA89D0660F6EC8F30FE6C9F7DA660F6ED2F30FE6D2660F73FA08660FD4CA660F6ED3F30FE6D2660F73FA0883C302F7DB660F6EDBF30FE6DB660FD4D3660F6FD8660F5EDA660F58D1660F58E383E90175EB660F70EC4E660F58E5660F59E6660F17660CC3"
$tCodeBuffer = DllStructCreate("byte[" & StringLen($binarycode) / 2 - 1 & "]") ;reserve Memory for opcodes
DllStructSetData($tCodeBuffer, 1, $binarycode)
$ptr_asm = DllStructGetPtr($tCodeBuffer)






For $number_Threads = 1 To $Threads_all
    PI_Leibniz($number_Threads)
Next










Func PI_Leibniz($number_Threads)
    $pi = 0
    $cycles = Int($n / $number_Threads / 4) * 4    ;Anpassen....easy way^^
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $cycles = ' & $cycles & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console


    Dim $Thread[$number_Threads]
    Dim $Threadexit[$number_Threads]
    Dim $Thread_struct_number[$number_Threads]
    Dim $para_struct[$number_Threads]
    Dim $param[$number_Threads]


    For $i = 0 To $number_Threads - 1
        $para_struct[$i] = DllStructCreate("uint n;uint Startpos;uint Step;align 4;double SumThread") ;n=anzahl durchläufe ; Startpos =startziffer ; Step= Schrittweite;sumThread =PI/4-Summe des Threads
        DllStructSetData($para_struct[$i], "n", $cycles) ;eax
        DllStructSetData($para_struct[$i], "Startpos", 1 + $i * 4) ;eax+4
        DllStructSetData($para_struct[$i], "Step", $number_Threads * 4) ;eax+8
        $param[$i] = DllStructGetPtr($para_struct[$i])
    Next


;~ $ret = _AssembleIt2("double", "Pi_Leibnitz", "ptr", $param[0])
;~ ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $ret = ' & $ret & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console


;~ $pi = 0
;~ ;Ergebnisse auslesen
;~ For $i = 0 To $number_Threads - 1
;~     $pi = $pi + DllStructGetData($para_struct[$i], "SumThread") ;alle Ergebnisse sammeln
;~ Next
;~ exit
;~ MsgBox(262144, 'Debug line ~' & @ScriptLineNumber, 'Selection:' & @CRLF & '$pi' & @CRLF & @CRLF & 'Return:' & @CRLF & $pi) ;### Debug MSGBOX




    $flag = 0
    $sum_Threads = 0
    $loops = 0


    $sum_Threadnumber = 0
    $sum_Threadnumber += 0                         ;summe aller Threadnummern
    For $i = 1 To $number_Threads
        $sum_Threadnumber += $i
    Next


    $t = TimerInit()


    For $i = 0 To $number_Threads - 1              ;anzahl threads starten
        $ret = DllCall("kernel32.dll", "hwnd", "CreateThread", "ptr", 0, "dword", 0, "long", $ptr_asm, "ptr", $param[$i], "long", 0, "int*", 0)
        $Thread[$i] = $ret[0]
;~     ConsoleWrite('@@ Debug(' & @ScriptLineNumber & ') : $Thread[$i] = ' & $Thread[$i] & @CRLF & '>Error code: ' & @error & @CRLF) ;### Debug Console
    Next




    Do                                             ;threads are running
        For $i = 0 To $number_Threads - 1
            $Return = DllCall("Kernel32.dll", "uint64", "GetExitCodeThread", "ptr", $Thread[$i], "dword*", 0) ;Rückgabe (EAX) aus den Threads
            If ($Return[2] <> 259) And $Threadexit[$i] = "" Then ;ist Thread bereits fertig?
                $Threadexit[$i] = $Return[2]
                $sum_Threads += $i + 1             ;summe aller Threads
                If $sum_Threadnumber = $sum_Threads Then ;alle Threads sind fertig
                    $flag = 1
                    ExitLoop                       ;alle Threads fertig
                EndIf
            EndIf
        Next
    Until $flag = 1                                ;so lange, wie noch keine Rückgabe aus den Threads erfolgt


    For $i = 0 To $number_Threads - 1              ;alle threads terminieren
        $ret = DllCall("Kernel32.dll", "int", "TerminateProcess", "dword", $Thread[$i], "uint", 999) ;Threads löschen
        $pi = $pi + DllStructGetData($para_struct[$i], "SumThread") ;alle Ergebnisse sammeln
    Next


    $m = TimerDiff($t)
    ConsoleWrite(StringFormat("Threads: %3s   Time: %4.1fms   PI: %.12f ", $number_Threads, $m, $pi) & @CRLF)
EndFunc                                            ;==>PI_Leibniz

Top

$n = 1000000000 -> Intel(R) Core(TM) i5-4300U CPU:

Threads:   1   Time: 2922.8ms   PI: 3.141592652586 
Threads:   2   Time: 1786.9ms   PI: 3.141592652591 
Threads:   3   Time: 1485.4ms   PI: 3.141592652598 
Threads:   4   Time: 1383.9ms   PI: 3.141592652593 
Threads:   5   Time: 1476.1ms   PI: 3.141592652591 
Threads:   6   Time: 1398.5ms   PI: 3.141592652588 
Threads:   7   Time: 1439.3ms   PI: 3.141592652589 
Threads:   8   Time: 1397.7ms   PI: 3.141592652586 
Threads:   9   Time: 1385.6ms   PI: 3.141592652587 
Threads:  10   Time: 1388.6ms   PI: 3.141592652590

Wieder mal sehr interessant die unterschiedlichen Ergebnisse, obwohl ich für eine "schöne" Darstellung die letzten 3 Nachkommastellen schon abgeschnitten hatte. Ggf. habe ich ja Lust, die entsprechenden Bits (wie hier http://www.plantation-productions.com/Webster/www.ar…Arithmetic.html beschrieben gibts das auch für SSE/SIMD) zu setzen....

Ich habe mal den FB Code als x64 laufen lassen -> Resultat siehe oben Post#31.

Bei einem Thread die Laufzeit mehr als halbiert!

Hier mal die Resultate von Andys Post auf meinem Intel Core i7-4790. Schon krass wie sehr der Faktor abnimmt wenn man über 3 Threads hinaus geht.

Threads:   1   Time: 19.1ms   PI: 3.141592553586 
Threads:   2   Time: 10.0ms   PI: 3.141592553591 
Threads:   3   Time:  7.2ms   PI: 3.141592553590 
Threads:   4   Time:  7.4ms   PI: 3.141592553589 
Threads:   5   Time:  7.7ms   PI: 3.141592553590 
Threads:   6   Time:  6.6ms   PI: 3.141592553590 
Threads:   7   Time:  8.6ms   PI: 3.141592553589 
Threads:   8   Time:  7.5ms   PI: 3.141592553590 
Threads:   9   Time:  7.9ms   PI: 3.141592553589 
Threads:  10   Time:  7.0ms   PI: 3.141592553590 
Threads:  11   Time:  6.8ms   PI: 3.141592553589 
Threads:  12   Time:  5.7ms   PI: 3.141592553589 
Threads:  13   Time:  6.3ms   PI: 3.141592553589 
Threads:  14   Time:  5.7ms   PI: 3.141592553590 
Threads:  15   Time:  5.7ms   PI: 3.141592553589 
Threads:  16   Time:  5.5ms   PI: 3.141592553590 
Threads:  17   Time:  6.0ms   PI: 3.141592553589 
Threads:  18   Time:  5.8ms   PI: 3.141592553589 
Threads:  19   Time:  5.7ms   PI: 3.141592553589 
Threads:  20   Time:  6.1ms   PI: 3.141592553590 
Threads:  21   Time:  5.8ms   PI: 3.141592553589 
Threads:  22   Time:  6.2ms   PI: 3.141592553589 
Threads:  23   Time:  5.9ms   PI: 3.141592553589 
Threads:  24   Time:  5.7ms   PI: 3.141592553589

Ich vermute, bei einem Quadcore-Prozessor (ggf auch Dual-Core mit HT) liegt die Grenze bei 3 Threads, weil Windows sich immer einen Thread "reserviert", um das System laufen zu lassen. Sicher wird es auch trotzdem "Core-Hopping" geben, das müsste man mal genauer profilen. Aber Faktor 3 ist definitiv eine Hausnummer!

Für eine Compilersprache ist die Optimierung per Multithreading ziemlich einfach, Schalter setzen, fettich!

Zitat von UEZ

Ich habe mal den FB Code als x64 laufen lassen -> Resultat siehe oben Post#31.

Bei einem Thread die Laufzeit mehr als halbiert!

Naja, das demonstriert nur, wie "langsam" der erzeugte 32Bit-Code ist, obwohl, wenn SSE eingeschaltet, der SSE-Code in 32Bit genauso schnell läuft wie im 64Bit-Modus! Für die SSE-Befehle bleibt die Laufzeit in beiden Modi ja gleich!
Wenn man anfängt zu "handoptimieren", wird der Abstand zum vom Compiler erstellten Code immer größer. Es macht also in einer Compilersprache Sinn, die Funktionsweise des Compilers wenigstens zu kennen und zu wissen, an welchem "Rädchen" man drehen muss, um dessen Code schneller laufen zu lassen.
Wenn man sich jetzt noch verdeutlicht, wie viel schneller der Code wäre, wenn (wie schon weiter oben erwähnt) AVX/FMA verwendet wird, dann ist auch klar, warum auch der Abstand von "Profi-Compilern" und dessen Einsatz auf den neuesten Prozessoren zum "Otto-Normalo-F5-Drücker" mit seinem 200-€-Prozessor immer größer wird (werden muss).