Autor Beitrag
mandras
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 429
Erhaltene Danke: 107

Win 10
Delphi 6 Prof, Delphi 10.4 Prof
BeitragVerfasst: Sa 03.09.16 21:42 
Ich habe die Ausführungen ohne weitere Änderungen als PDF gespeichert.
Ist wie gesagt schon ein paar Jährchen alt.
Einloggen, um Attachments anzusehen!

Für diesen Beitrag haben gedankt: Mathematiker
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1600
Erhaltene Danke: 232


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Sa 03.09.16 23:09 
Tja, vor vielen Jahren - es muß zum Ende der DDR-Zeit gewesen sein - fand ich irgendwo (Computerzeitschrift?) mal ein Beispielprogramm für Fraktale auf der Basis hyperkomplexer Zahlen (vermutlich Quaternionen). Das mußte ich unbedingt haben - für später zum Ausprobieren. Die Kopiertechnik Anfang der 90er (aus der Zeit müßte die Kopie stammen, mir liegt jedenfalls keine Kopie vor, wie ich sie noch aus DDR-Zeiten kannte - da roch das Kopierpapier anfangs immer so gewöhnungsbedürftig) war leider noch nicht so berauschend. Folge war, daß ich das Programm später, als ich selbst einen Computer hatte, leider nicht genau abtippen konnte, ich versuchte es wiederholt, war aber nichts zu machen.

Ich kann mich jedenfalls noch lebhaft daran erinnern, daß die in der Zeitschrift gezeigten Fraktalbilder von atemberaubender Schönheit waren. Da kann das Apfelmännchen, so faszinierend es in seiner ersten Begegnung ist (zugegeben erst mit den Vergrößerungen, zuerst kommt es nur als ausgefranste Kardioide daher) mit seinen "simplen" komplexen Zahlen leider nimmer mithalten.

Schade drum...sonst wäre es wohl auch hier.
Palladin007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1282
Erhaltene Danke: 182

Windows 11 x64 Pro
C# (Visual Studio Preview)
BeitragVerfasst: So 04.09.16 14:35 
Hallo mandras und danke für den Text. Ich schau mir das in einer ruhigen Stunde mal an.


Bis dahin hab ich aber eine Bitte an Mathematiker:
Kannst Du mir deinen Assembly-Code-Schnipsel erklären? :D
Ich hab so meine Schwierigkeiten, da durch zu blicken :/
Bisher kenne ich nur CIL und das ist dann doch etwas anders

Oder zumindest, was Du dort anders gemacht hast, was nur auf Assembly-Ebene geht.
Ich möchte das in CIL nachbauen, dafür muss ich das aber verstehen.
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: So 04.09.16 19:34 
Hallo,
anbei der ASM-Text mit Erklärung
ausblenden volle Höhe Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
      ASM
         FLD     radius    { 9        }
         FLD     a         { cx       9 }
         FLD     b         { cy       cx    9     }
         FLD     st        { y        cy    cx    9    }
         FMUL    st,st     { y²       cy    cx    9    }
         FLD     st(2)     { x        y²    cy    cx    9     }
         FMUL    st,st     { x²       y²    cy    cx    9     }
         FLD     st(2)     { y        x²    y²    cy    cx    9     }
         FLD     st(4)     { x        y     x²    y²    cy    cx    9   }

         XOR     cx,cx
@itloop: INC     cx        // CX ist der Iterationszähler
         CMP     cx,it     // überschreitet CX den Wert it,
         JE      @noloop   // dann keinen Bildpunkt setzen.

         { y = 2xy + cy }
         FMUL              { xy       x²    y²    cy    cx    9     }
         FADD    st,st     { 2xy      x²    y²    cy    cx    9     }
         FADD    st,st(3)  { (y)      x²    y²    cy    cx    9     }
         { x = x² - y² + cx }
         FLD     st(1)     { x²       (y)   x²    y²    cy    cx    9     }
         FSUB    st,st(3)  { x²-y²    (y)   x²    y²    cy    cx    9     }
         FADD    st,st(5)  { (x)      (y)   x²    y²    cy    cx    9     }
         { x² = x*x }
         FST     st(3)     { (x)      (y)   x²    (x)   cy    cx    9     }
         FMUL    st,st     { (x²)     (y)   x²    (x)   cy    cx    9     }
         FSTP    st(2)     { (y)      (x²)  (x)   cy    cx    9     }
         { y² = y*y }
         FLD     st        { (y)      (y)   (x²)  (x)   cy    cx    9     }
         FMUL    st,st     { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         { x² + y² < 9 ??? }
         FADD    st,st(2)  { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FCOM    st(6)     { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FSTSW   ax
         FSUB    st,st(2)  { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         FXCH    st(3)     { (x)      (y)   (x²)  (y²)  cy    cx    9     }
         AND     ah,1
         JNZ     @itloop   { falls Folge innerhalb des Kreises, dann weiter }
@noloop: MOV     i, cx
         FINIT
      END;


Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Palladin007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1282
Erhaltene Danke: 182

Windows 11 x64 Pro
C# (Visual Studio Preview)
BeitragVerfasst: So 04.09.16 22:41 
Tut mir Leid, wenn ich mich so blöd anstelle, aber ich versteh deine Beschreibung mit den geschweiften Klammern nicht :D

Vielleicht hilfts ja, wenn ich die Befehle verstehe.

FLD - Ich dachte, dass das ein Feld lädt/setzt, aber was passiert dann z.B. bei Zeile 7?
FMUL - Multiplikation der beiden angegebenen Felder
XOR - Exclusive Or, aber warum dann zwei mal das gleiche Feld?
INC - Um eins erhöhen
CMP - Vergleicht zwei Werte (und legt das Ergebnis -1/0/1 auf den Stapel?)
JE - Springt zu einer Stelle im Code
FADD - Addiert die Werte - Aber auch hier die Frage: Was bedeutet die Zahl in den Klammern?
FSUB - Subtrahiert die Werte

Und bei dem Rest steig ich aus :D


Kennst Du eine gute Liste, wo die ganzen Befehle aufgeführt sind?
Ich hab keine gefunden :/
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 05.09.16 08:34 
Hallo,
user profile iconPalladin007 hat folgendes geschrieben Zum zitierten Posting springen:
versteh deine Beschreibung mit den geschweiften Klammern nicht :D

In den Klammern steht die jeweilige Belegung des Stacks nach(!) der Operation.
FLD transportiert den jeweiligen Wert auf den Stack. Alle Rechenoperationen werden hier mit Werten auf dem Stack durchgeführt.

Es ist zwar lustig, den meine ASM-Kenntnisse sind auch nur rudimentär, aber ich versuche eine Erklärung. Sollte irgendetwas nicht exakt sein, bitte nicht "schlagen". :mrgreen:

ausblenden Delphi-Quelltext
1:
2:
3:
         FLD     radius    { 9        }
         FLD     a         { cx       9 }
         FLD     b         { cy       cx    9     }
Laden der Abbruchbedingung (hier 9 (nicht wie sonst 4, warum eigentlich, im Moment weiß ich es selbst nicht mehr) und Real- cx und Imaginärteil cy der Konstanten auf den Stack

ausblenden Delphi-Quelltext
1:
         FLD     st        { y        cy    cx    9    }					
Holt den Stackwert cy und legt ihn zusätzlich als Variable y auf den Stack

ausblenden Delphi-Quelltext
1:
         FMUL    st,st     { y²       cy    cx    9    }					
Der obere Stackwert wird quadriert

ausblenden Delphi-Quelltext
1:
         FLD     st(2)     { x        y²    cy    cx    9     }					
Der obere Stackeintrag ist st(0), d.h. mit st(2) wird cx, der dritte Wert im Stack, geladen und zusätzlich als x oben auf den Stack gelegt

ausblenden Delphi-Quelltext
1:
         FMUL    st,st     { x²       y²    cy    cx    9     }					
x² wird berechnet

ausblenden Delphi-Quelltext
1:
2:
         FLD     st(2)     { y        x²    y²    cy    cx    9     }
         FLD     st(4)     { x        y     x²    y²    cy    cx    9   }
die Größen für y und x werden nochmals auf den Stack kopiert

ausblenden Delphi-Quelltext
1:
         XOR     cx,cx					
der Iterationszähler (CX-Register) cx soll garantiert 0 sei, mit XOR wird cx 0, gleichgültig was vorher in cx steht

ausblenden Delphi-Quelltext
1:
2:
3:
@itloop: INC     cx        // CX ist der Iterationszähler
         CMP     cx,it     // überschreitet CX den Wert it,
         JE      @noloop   // dann keinen Bildpunkt setzen.
CMP prüft, ob der Registerinhalt CX größer wird als die maximale Iterationszahl it. Wenn ja, wird zum Ende der ASM-Routine gesprungen

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
         { y = 2xy + cy }
         FMUL              { xy       x²    y²    cy    cx    9     }
         FADD    st,st     { 2xy      x²    y²    cy    cx    9     }
         FADD    st,st(3)  { (y)      x²    y²    cy    cx    9     }
         { x = x² - y² + cx }
         FLD     st(1)     { x²       (y)   x²    y²    cy    cx    9     }
         FSUB    st,st(3)  { x²-y²    (y)   x²    y²    cy    cx    9     }
         FADD    st,st(5)  { (x)      (y)   x²    y²    cy    cx    9     }
         { x² = x*x }
         FST     st(3)     { (x)      (y)   x²    (x)   cy    cx    9     }
         FMUL    st,st     { (x²)     (y)   x²    (x)   cy    cx    9     }
         FSTP    st(2)     { (y)      (x²)  (x)   cy    cx    9     }
         { y² = y*y }
         FLD     st        { (y)      (y)   (x²)  (x)   cy    cx    9     }
         FMUL    st,st     { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         { x² + y² < 9 ??? }
         FADD    st,st(2)  { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FCOM    st(6)     { (x²+y²)  (y)   (x²)  (x)   cy    cx    9     }
         FSTSW   ax
         FSUB    st,st(2)  { (y²)     (y)   (x²)  (x)   cy    cx    9     }
         FXCH    st(3)     { (x)      (y)   (x²)  (y²)  cy    cx    9     }
         AND     ah,1
         JNZ     @itloop   { falls Folge innerhalb des Kreises, dann weiter }
Die ganzen Befehle berechnen "kryptisch" die neuen Werte (x)=x²-y²+cx und (y)=2xy+cy und die Abbruchbedingung x²+y² durch ständiges Holen und Ablegen von Werten auf dem Stack.

FCOM führt einen Vergleich durch (courses.engr.illinoi...l/inst-ref-fcom.html, unter dieser Adresse gibt es eine lange Liste von ASM-Befehlen mit Beschreibung), FSTP kopiert auf dem Stack (x86.renejeschke.de/h...dule_x86_id_117.html), FSTSW siehe x86.renejeschke.de/h...dule_x86_id_120.html und FXCH tauscht Werte (x86.renejeschke.de/h...dule_x86_id_126.html).

ausblenden Delphi-Quelltext
1:
2:
3:
@noloop: MOV     i, cx
         FINIT
      END;
Austritt aus der Berechnung mit Kopieren der Anzahl von Iterationen cx in die Variable i.

Ich vermute, meine "Erklärung" hilft nicht so richtig weiter. Aber, wie gesagt, meine ASM-Kenntnisse sind nicht gerade berauschend.
Ich denke, hier müssen die Profis 'ran. Wahrscheinlich können sie es besser erklären.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Palladin007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1282
Erhaltene Danke: 182

Windows 11 x64 Pro
C# (Visual Studio Preview)
BeitragVerfasst: Mo 05.09.16 09:07 
Kann es sein, dass es schnellerläuft, weil Du komplett auf dem Stack arbeitest?
Du baust im Prinzip darauf, dass der Stack im Cache landet, was ja deutlich schneller ist als der "langsame" RAM.
Du hast nämlich kaum die eigenen Variablen vom Code darüber verwendet, stattdessen arbeitest Du nur auf dem Stack, was ich eher umständlich finde. Wenn der Stack auf dem Cache landet, wäre das aber ein deutlicher Vorteil.

Den ersten Teil hab ich denke ich kapiert, bei dem zweiten Teil hab ich noch so meine Probleme :D
Aber ich schau mir mal die ASM-Befehls-Liste an, vielleicht hilft das weiter.


Eine Frage, die mir aber immer wieder kommt:
ausblenden Delphi-Quelltext
1:
2:
FLD     st        { y        cy    cx    9    }
FMUL    st,st     { y²       cy    cx    9    }

Entfernt FMUL (und auch andere) den letzten Stack-Wert vom Stack, bevor es sein Ergebnis drauf legt?
So sieht das nämlich auch an anderer STelle aus und da frage ich mich: Warum? Ist das nicht langsamer, weil eine zusätzliche Operation ausgeführt wird?
Bei IL wird (wenn ich mich nicht irre) einfach nur weiter gestapelt.



PS:
Und danke für die viele Mühe :)
OlafSt
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 486
Erhaltene Danke: 99

Win7, Win81, Win10
Tokyo, VS2017
BeitragVerfasst: Mo 05.09.16 09:44 
Nein, Freunde. Alle auf dem Holzweg.

Der gezeigte Assemblercode ist 80x87-Code, also Assemblercode für den mathematischen Coprozessor von Intel, der seit dem 80486 (abgesehen vom 80486SX, wo die FPU abgeschaltet wurde) fest in die Standard-CPU integriert ist. Davor mußte die FPU, wie man das Ding heute nennt, extra dazugekauft werden, hatte folglich einen Extra-Sockel (der dann meistens aus Kostengründen weggelassen wurde) und schweineteuer war. So kostete der 8086 damals 400DM, der passende 8087 dazu fast 2000DM. Dafür waren Fließkommaberechnungen aber auch Faktor 200 schneller. Dies brachte die Apfelmännchenberechnung von knapp 24 Stunden auf etwa 30 Minuten Rechenzeit herunter.

Der 8087 arbeitet Stack-orientiert und nicht, wie die normalen 80x86-CPUs, registerorientiert. Ergo muß man die Werte, mit denen man rechnen will, erstmal auf den FPU-Stack pushen (der nichts mit dem normalen Stack zu tun hat), was mit FLD (Floating Point Load) passiert. Alle anderen Operationen in der FPU arbeiten mit dem Top-Of-Stack-Wert, der grundsätzlich als "ST" bezeichnet wird. Damit man auch andere Stack-Werte ansprechen kann, gibt es auch ST(1), ST(2) etcpp. IIRC hat der FPU-Stack 8 Plätze.

Ergo wird ein FMUL ST,ST den Top-Of-Stack-Wert mit dem Top-Of-Stack-Wert multiplizieren - was dem quadrieren entspricht. Der Rest ist in der Befehlsreferenz zum 8087 nachlesbar. Ansonsten hat man sich da an die Intel-Konvention gehalten: Das F steht als Kennzeichen für FPU immer vor dem eigentlichen Mnemonic, als erstes wird das Ziel der Operation genannt.

Die meisten FPU-Befehle haben einen "Partner", der mit einem abschließenden "P" gekennzeichnet ist (FMUL und FMULP z.B.). Dieses P steht für "Pop" und zieht den obersten Wert vom FPU-Stack herunter. Somit würde ein

FLD 9
FMUL ST,ST

zwar die 9 quadrieren, auf dem FPU-Stack läge aber nun die 81, gefolgt von der 9. Mit

FLD 9
FMULP ST,ST

wird die 9 auch quadriert, aber vor Ablage des Ergebnisses vom FPU-Stack genommen. Ergo liegt dort nur noch die 81.

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.

Für diesen Beitrag haben gedankt: Mathematiker
Mathematiker
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 2622
Erhaltene Danke: 1447

Win 7, 8.1, 10
Delphi 5, 7, 10.1
BeitragVerfasst: Mo 05.09.16 09:58 
Hallo OlafSt,
Danke für die ausführliche Erklärung.
Ich nutze diese ASM-Routine seit vielen, vielen Jahren (mindestens seit 2000) und habe nie richtig verstanden, was da eigentlich geschieht; und mir auch keine große Gedanken gemacht. :autsch:

Interessant wäre für mich nun, wie eine für die 80x86-CPUs optimierte Routine aussehen würde. Könnte man da noch einmal etwas Geschwindigkeit herausholen?
Bei der Berechnung von Mandelbrotmengen wäre dies sicher interessant.

Beste Grüße
Mathematiker

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Palladin007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1282
Erhaltene Danke: 182

Windows 11 x64 Pro
C# (Visual Studio Preview)
BeitragVerfasst: Mo 05.09.16 10:57 
Auch von mir ein Danke :)

Das erklärt auch, warum ich so wenig über die Befehle gefunden habe :D



Aber dennoch ist die Berechnung bei Mathematikers Programm deutlich schneller als bei mir.
Allerdings hab ich bei mir alles mir bekannte optimiert, was ich optimieren konnte, die Berechnung bei max. 100 Durchläufen und Vollbild dauert ja auch "nur" 100ms.
OlafSt
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 486
Erhaltene Danke: 99

Win7, Win81, Win10
Tokyo, VS2017
BeitragVerfasst: Mo 05.09.16 13:13 
IMHO ist in Sachen Fließkommaberechnung die FPU noch immer das Maß der Dinge. Keine noch so schnelle x86-Routine kann so schnell multiplizieren wie ein FMUL der FPU. Das liegt einfach daran, das die x86-CPUs reine Integer-ALUs haben, die ganzen Fließkommaoperationen also manuell nachbilden müßten. Dies kann unmöglich schneller sein als eine FPU-Operation, die direkt "in Transistoren gebaut" ist.

Was aber schneller sein könnte, wäre eine optimiertere Version der schon bestehenden Routine. Wenn ich daran denke, das man mit SSE4-Befehlen heutzutage 4 Doubles auf einen Schlag miteinander multiplizieren kann... Dies wurde bedeuten, das hier mit einem Befehl 4 Pixels des Apfelmännchens zugleich berechnet. Dies allein wäre ja ein Faktor 4 schneller, dann kommt ja noch die extrem verbesserte Implementierung der SSE-Befehle hinzu. Da ließe sich also sicher noch ordentlich Luft rausquetschen - erfordert dann aber auch eine SSE4-taugliche CPU (Core2 Duo und aufwärts, wenn ich das recht im Kopf habe).

Fragt mich nicht, wie so was aussehen würde - ich bin zu lange aus der Materie raus ;)

Ach ja: Noch mehr Speed kann man rausholen, wenn man die Grafikkarte den ganzen Kram berechnen läßt (CUDA ist das Zauberwort). Die Grafikchips sind nochmal einige dutzen mal schneller als die Intel-FPUs, weil sie eben extrem spezialisiert sind. Dafür kann auf einem Radeon X9 leider kein Windows laufen ;)

[Edit]

ich habe mal etwas geforscht. hier findet sich ein Programm mit SSE/SSE2-Instruktionen, das ein Apfelmännchen berechnet. 1024x768, 256 Iterationen, 30ms. Auf einem Pentium IV, der schon 8 CPU-Generationen zurück ist ;)

Der Autor zeigt auch sehr eindrücklich, wie extrem kompliziert Assemblerprogrammierung schon damals war, wenn man es wirklich schnell haben wollte. Da mußte man das Pipelining und die Caches beachten, damit möglichst viele Operationen nebeneinander verarbeitet werden konnten. Heute wäre das nochmal einige Nummern komplexer, weil man ja nun mehrere CPU-Kerne hat, die jeder für sich mehrere Instruktionen parallel laufen lassen können und diese in ihren Pipelines quasi nebeneinander verarbeiten...

Wäre sicher mal spannend, sich 6 Monate Auszeit zu nehmen, und sich da reinzufuchsen... :D Wer will, kann hier einsteigen in die Materie.

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.

Für diesen Beitrag haben gedankt: Mathematiker
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Mo 05.09.16 14:00 
user profile iconOlafSt hat folgendes geschrieben Zum zitierten Posting springen:
IMHO ist in Sachen Fließkommaberechnung die FPU noch immer das Maß der Dinge. Keine noch so schnelle x86-Routine kann so schnell multiplizieren wie ein FMUL der FPU. Das liegt einfach daran, das die x86-CPUs reine Integer-ALUs haben, die ganzen Fließkommaoperationen also manuell nachbilden müßten. Dies kann unmöglich schneller sein als eine FPU-Operation, die direkt "in Transistoren gebaut" ist.
Für die Fraktalberechnung als Ganzes muß das Rechnen mit FPU nicht unbedingt schneller sein, früher gab's FRACTINT das nur mit Integer-Rechnungen wesentlich schneller Bilder berechnet (mit Hilfe kluger Heuristiken). Ich habe es schon lange nicht mehr benutzt, aber es scheint noch weiterentwickelt zu werden (siehe www.fractint.org/ oder de.wikipedia.org/wiki/Fractint).
OlafSt
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 486
Erhaltene Danke: 99

Win7, Win81, Win10
Tokyo, VS2017
BeitragVerfasst: Mo 05.09.16 19:19 
Das mag sein - doch ist dies ein Spezialfall. Ein Spezialfall kann niemals allgemeingültig sein und ich bin fest überzeugt, das FractInt nie und nimmer gegen eine SSE4-Version oder gar CUDA/OpenCL ankäme ;)

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.
Delphi-Laie
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1600
Erhaltene Danke: 232


Delphi 2 - RAD-Studio 10.1 Berlin
BeitragVerfasst: Mo 05.09.16 22:30 
user profile iconOlafSt hat folgendes geschrieben Zum zitierten Posting springen:
Heute wäre das nochmal einige Nummern komplexer, weil man ja nun mehrere CPU-Kerne hat, die jeder für sich mehrere Instruktionen parallel laufen lassen können und diese in ihren Pipelines quasi nebeneinander verarbeiten...


Das Zauberwort heißt Multithreadingprogrammierung; das Betriebsprogramm kümmert sich dabei darum, daß alle Prozessoren/Prozessorkerne genug zu tun haben. Solang es aber Ausgaben auf dasselbe Gerät, vorzugsweise Bildschirm, gibt, muß synchronisiert werden, und der "Flaschenhals" ist da.

Für die Assemblerprogrammierung empfehle ich die Bücher des Autors Peter Monadjemi.
jfheins
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 918
Erhaltene Danke: 158

Win 10
VS 2013, VS2015
BeitragVerfasst: Mo 05.09.16 22:44 
So richtig flott wird es doch erst, wenn du alle 8 Therad der CPU mit SSE (oder AVX) Code fütterst, der in 2 Takten 4 Pixel auf einmal ausrechnet.

Ein Bild ist ja auch sehr einfach parallelisierbar, du zerteilst es einfach in Streifen und gibt jedem Thread einen Teil des Bildes.
Klar, fertig ist es erst, wenn alle Threads fertig sind. Aber wenn das schnell genug läuft, merkt man von der Synchronisierung wenig.

Von Intel gibt es da auch interessante Balkendiagramme: software.intel.com/e...s#highlighter_339467
Gibt es eigentlich eine Möglichkeit, von AVX/SSE in Delphi Gebrauch zu machen, ohne direkt Assembler benutzen zu müssen?
Palladin007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1282
Erhaltene Danke: 182

Windows 11 x64 Pro
C# (Visual Studio Preview)
BeitragVerfasst: Di 06.09.16 03:07 
Ich bin auf meinem System jetzt bei ca. 190ms, wenn das Fenster Vollbild geöffnet wird.
Ca. 5ms wären zwar noch drin, aber dadurch wird der Code nur unübersichtlicher, daher hab ich das gelassen.
Maximale Iterationen hab ich auf 100 stehen, auf 1000 braucht's dann rund 1200ms.

Ich hab den Code versucht, so zu kommentieren, damit auch reine Delphi-Jünger damit klar kommen:

ausblenden volle Höhe C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
public abstract class Fractal
{
    private static Color[] BlackWhiteColorSet { get; } = new Color[] { Color.Black, Color.White };

    private double _minX, _minY, _maxX, _maxY;
    private Color[] _colorSet;

    // Maße des Koordinatensystems
    public double MinX
    {
        get { return _minX; }
        set { _minX = value; }
    }
    public double MinY
    {
        get { return _minY; }
        set { _minY = value; }
    }
    public double MaxX
    {
        get { return _maxX; }
        set { _maxX = value; }
    }
    public double MaxY
    {
        get { return _maxY; }
        set { _maxY = value; }
    }

    public int MaxIterations { get; set; }
    public Color[] ColorSet
    {
        get { return _colorSet; }
        set
        {
            // Ist value == null, dann wir ein ColorSet mit schwarz/weiß verwendet
            _colorSet = value ?? BlackWhiteColorSet;
        }
    }

    protected Fractal()
    {
        ColorSet = BlackWhiteColorSet;
        MaxIterations = 100;
    }
        
    // zoomt schrittweise in das Koordinatensystem
    public void Zoom(double zoomRate)
    {
        Zoom(ref _minX, ref _maxX, zoomRate);
        Zoom(ref _minY, ref _maxY, zoomRate);
    }
    public void Zoom(double zoomRate, double centerX, double centerY)
    {
        Zoom(ref _minX, ref _maxX, zoomRate, centerX);
        Zoom(ref _minY, ref _maxY, zoomRate, centerY);
    }

    private void Zoom(ref double min, ref double max, double zoomRate)
    {
        Zoom(ref min, ref max, zoomRate, max + (max - min) / 2);
    }
    private void Zoom(ref double min, ref double max, double zoomRate, double center)
    {
        var distanceX = max - min;
        var newDistanceX = distanceX / zoomRate;
        var oldCenter = min + (max - min) / 2;

        min = min + (distanceX - newDistanceX) / 2 + center - oldCenter;
        max = min + newDistanceX;
    }

    public Bitmap DrawBitmap(int width, int height)
    {
        // Stellt im RAM ein Bild dar, auf dem gezeichnet werden kann
        var bitmap = new Bitmap(width, height);

        try
        {
            DrawFractal(bitmap);
        }
        catch
        {
            // Tritt ein Fehler auf, wird das Bild nicht mehr benötigt und frei gegeben werden
            bitmap.Dispose();
            throw;
        }

        return bitmap;
    }
    public unsafe void DrawFractal(Bitmap bitmap)
    {
        var width = bitmap.Width;
        var height = bitmap.Height;

        // Wie viele Pixel gibt es pro Coordinaten-Schritt
        var xSteps = (MaxX - MinX) / width;
        var ySteps = (MaxY - MinY) / height;

        // blockiert die Menge der Pixel von dem Bild im RAM und macht sie über das zurückgegebene Objekt änderbar
        // Dadurch kann ich die Pixel direkt im RAM setzen und manuell optimieren
        var bitmapData = bitmap.LockBits(new Rectangle(00, bitmap.Width, bitmap.Height), ImageLockMode.ReadWrite, bitmap.PixelFormat);

        try
        {
            var pixelFormatSize = Bitmap.GetPixelFormatSize(bitmap.PixelFormat);
            var bytesPerPixel = pixelFormatSize / 8;
            var firstPixelPtr = (byte*)bitmapData.Scan0;
                
            // Parallel.For ist eine for-Schleife, welche die Durchläufe in eigenen Threads ausführt
            // Beginnt bei 0, endet bei (width * height)
            // Der Zähler ist pixelId
            Parallel.For(0, width * height, pixelId =>
            {// begin Parallel.For

                // Da ich durch die gesamte Menge der Pixel zähle, muss die eigentliche Position berechnet werden
                var yPos = pixelId / width;
                var xPos = pixelId - width * yPos;
                    
                var xCoord = xPos * xSteps + MinX;
                var yCoord = yPos * ySteps + MinY;
                    
                var line = firstPixelPtr + yPos * bitmapData.Stride;
                var byteX = xPos * bytesPerPixel;
                var color = CalculateColor(xCoord, yCoord);

                // Farb-Werte setzen:
                // Je nach Pixel-Format ist ein Pixel unterschiedlich groß
                // 32bit - 4 Byte - ARGB
                // 24bit - 3 Byte - RGB
                // 8bit  - 1 Byte - Alle Farbwerte sind gleich
                if (pixelFormatSize == 32)
                {
                    line[byteX] = color.B;
                    line[byteX + 1] = color.G;
                    line[byteX + 2] = color.R;
                    line[byteX + 3] = color.A;
                }
                else if (pixelFormatSize == 24)
                {
                    line[byteX] = color.B;
                    line[byteX + 1] = color.G;
                    line[byteX + 2] = color.R;
                }
                else if (pixelFormatSize == 8)
                    line[byteX] = color.B;

            }); // end Parallel.For
        }
        finally
        {
            // Sicher stellen, dass die Bild-Daten auch bei einer Exception wieder frei gegeben werden
            bitmap.UnlockBits(bitmapData);
        }
    }
    private Color CalculateColor(double xCoord, double yCoord)
    {
        // Berechnung für das Fractal
        var iterations = IterateFractal(xCoord, yCoord);
        // Ein bisschen Prozentrechnung
        var colorIndex = (double)iterations / MaxIterations * (ColorSet.Length - 1);
        return ColorSet[(int)colorIndex];
    }

    protected abstract int IterateFractal(double x, double y);
}


Die Ableitung für die Mandelbrot-Menge:

ausblenden volle Höhe C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
public class MandelbrotFractal : Fractal
{
    public MandelbrotFractal()
    {
        // Standart-Werte setzen
        MaxIterations = 100;
        MinX = -2;
        MinY = -1;
        MaxX = 1;
        MaxY = 1;
    }

    protected override int IterateFractal(double x, double y)
    {
        // Die Berechnung
        var xBuffer = x;
        var yBuffer = y;
        var maxIterations = MaxIterations;
        var usedIterations = 0;

        while (usedIterations < maxIterations && xBuffer * xBuffer + yBuffer * yBuffer < 4)
        {
            var newXBuffer = xBuffer * xBuffer - yBuffer * yBuffer + x;
            var newYBuffer = xBuffer * yBuffer * 2 + y;

            yBuffer = newYBuffer;
            xBuffer = newXBuffer;

            usedIterations++;
        }

        return usedIterations;
    }
}


Ich hoffe, das kann man gut lesen und jemand macht sich die Mühe, sich das mal anzuschauen :D


Wirklich zufrieden bin ich mit der Performance noch nicht. 190ms bei Vollbild und max. 100 Iterationen klingt zwar schnell, aber Mathematikers Variante braucht bei maximal 10000 Iterationen nur rund 3 Sekunden, das ist immer noch viel schneller als meine Variante. Auf Assembler-Ebene (bzw. IL) weiß ich nicht, was ich da groß optimieren kann. Ich muss mir Mathematikers ASM-Code nochmal ruhig zu Gemüte führen, damit ich den endlich bis ins Detail verstehe, vielleicht kann ich dann ja doch was raus ziehen.


Was mich auch stört:
Durch die Prozentrechnung beim Bestimmen, welche Farbe verwendet wird, verändert sich die Färbung bei hohen maximalen Iterationen natürlich.
Wenn ich z.B. eine Mischung aus Schwarz und verschiedenen Orange/Rot-Werten nehme (Mathematiker hat das in seinem Programm unter Feuer aufgeführt), dann habe ich bei max. 100 Iterationen ein schönes Bild, bei 1000 aber beinahe komplett schwarz.
Hat jemand eine Idee, wie ich das anpassen kann?
Blup
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 173
Erhaltene Danke: 43



BeitragVerfasst: Di 06.09.16 16:59 
Die Multiplikationen beim Vergleich können eingespart werden.
ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
 var xBuffer2 = xBuffer * xBuffer;
 var yBuffer2 = yBuffer * yBuffer;

 while (usedIterations < maxIterations && xBuffer2 + yBuffer2 < 4)
        {
            yBuffer = xBuffer * yBuffer * 2 + y;
            xBuffer = xBuffer2 - yBuffer2 + x;

            usedIterations++;

            xBuffer2 = xBuffer * xBuffer;
            yBuffer2 = yBuffer * yBuffer;
        }

 return usedIterations;


Warum überhaupt Prozentrechnung für das bestimmen der Farbe? Üblicherweise wird der Farbindex aus der Anzahl der Iterationen modulo der Größe der Farbpalette bestimmt.

Moderiert von user profile iconTh69: Code- durch C#-Tags ersetzt
Palladin007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1282
Erhaltene Danke: 182

Windows 11 x64 Pro
C# (Visual Studio Preview)
BeitragVerfasst: Di 06.09.16 17:42 
Der Vorschlag, das Quadrat nur einmal zu berechnen, bringt kaum eine Verbesserung, vielleicht zwei, drei Millisekunden.
Wenn ich auf max. 1000 Iterationen stelle, kriege ich etwa 50ms raus geschlagen.
Das liegt aber auch daran, dass Du in der Schleife nicht zwischenspeicherst, das hab ich also auch wieder raus genommen.

Wirklich herausragend ist das aber auch noch nicht.
Ich könnte mir auch vorstellen, dass dort garnicht so groß optimiert werden muss, sondern das Abarbeiten der Schleife bzw. das Zeichen vom Bild, allerdings kenne ich da keine Technik, wie ich noch mehr Zeit raus holen kann.

Zitat:
Warum überhaupt Prozentrechnung für das bestimmen der Farbe? Üblicherweise wird der Farbindex aus der Anzahl der Iterationen modulo der Größe der Farbpalette bestimmt.


Das wusste ich nicht. DIe Prozentrechnung hab ich aus einem Beispiel, das ich anfangs nach WPF portiert habe.

Wenn ich so den colorIndex berechne:
ausblenden C#-Quelltext
1:
colorIndex = iterations % ColorSet.Length;					

Dann sieht das bei hoher Genauigkeit auch deutlich besser aus bzw. so wie ich es eben erwarte.
Bei niedriger Genauigkeit ist das Weiß aber nicht mehr wirklich weiß. Ich hab mal zwei Bilder angehängt mir Vorher/Nachher.

Modulo ist aber auch ein bisschen schneller, bei max. 1000 Iterationen sind das rund 10ms.
Einloggen, um Attachments anzusehen!
OlafSt
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 486
Erhaltene Danke: 99

Win7, Win81, Win10
Tokyo, VS2017
BeitragVerfasst: Di 06.09.16 22:01 
Blöde Frage: Würde dies hier nicht auch genügen ?

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
protected override int IterateFractal(double x, double y)
    {
        // Die Berechnung
        var xBuffer = x;
        var yBuffer = y;
        var maxIterations = MaxIterations;
        var usedIterations = 0;

        while (usedIterations < maxIterations && xBuffer * xBuffer + yBuffer * yBuffer < 4)
        {
            xBuffer = xBuffer * xBuffer - yBuffer * yBuffer + x;
            yBuffer = xBuffer * yBuffer * 2 + y;

            usedIterations++;
        }

        return usedIterations;
    }


Dann braucht die IL nicht ständig neue Temp-Variablen erstellen, die der GC dann wieder wegräumen muß, außerdem sparen wir uns die ständige Zuweisung an die Buffervariablen, die ansonsten nie mehr benutzt werden...

Weiterhin frage ich mich, ob man mit Math.Pow(xBuffer,2) nicht schneller wäre.

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.
Palladin007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1282
Erhaltene Danke: 182

Windows 11 x64 Pro
C# (Visual Studio Preview)
BeitragVerfasst: Di 06.09.16 22:26 
Das hab ich schon gemacht, danke

Der Gedanke kam mir auch, als ich den Vorschlag von Blup ausgetestet habe.