Mandelbrot-Menge optimieren

[MrMooed]

Hallo DP ich bin es mal wieder.


Ich bin vor ein Paar Tagen von meiner Informatiklehrerin auf das Apfelmännchen aufmerksam gemacht worden. Als ich es das erste mal gesehen habe, dachte ich einfach nur 'wow! so geil kann Mathe aussehen ?' Habe den relativ simplen Algorithmus auch umgesetzt und dargestellt.

Nun wollte ich das ganze noch etwas schneller rechnen lassen. Zunächst habe ich über Multithreading nachgedacht, aber dann wurde mir bewusst, dass ich damit nicht mein eigentliches Problem löse sondern nur auf die Prozesorkerne auslagere
Nun wollte ich hier mal nachfragen ob evtl. jemand Tipps hat was ich an meiner Berechnung schneller machen (bzw. optimieren) kann.

Delphi-Quellcode:

function Mandelbrot.rechne(X_Ko, Y_Ko, X, Y, A: double; i: Integer): Integer;
var
  nX, nY, nA: double;
begin
  if (i < 50) and (A < 2)
    then begin
           nX := (X*X) - (Y*Y) + X_Ko;
           nY := 2*X*Y + Y_Ko;
           nA := SQRT(nX*nX + nY*nY);
           result := rechne(X_Ko, Y_Ko, nX, nY, nA, i+1);
         end;
end;

Erklärung:
der Rückgabewert wird später zur Darstellung der Farben benutzt.
i ist die Anzahl der Iterationen. Je höher desto genauer das Bild.
(X_Ko | Y_Ko) sollen mit dem Punkt (X | Y) verglichen werden. (normalerweise ist dies der Ursprung (0 | 0)
A bzw. nA sind der Abstand zu (X | Y) - Satz des Pythagoras, wenn ich das nicht falsch verstanden habe

Aufruf:
Aufrufen tue ich die Funktion mit einer case .. of Anweisung.

Delphi-Quellcode:

case rechne(x, y, 0, 0, 0, 0) of
          0..10:  Bild.Canvas.Pixels[x,y] := clBlack;
          11..20: Bild.Canvas.Pixels[x,y] := clOlive;
          21..30: Bild.Canvas.Pixels[x,y] := clYellow;
          31..40: Bild.Canvas.Pixels[x,y] := clLime;
          41..50: Bild.Canvas.Pixels[x,y] := clGreen;
          else    Bild.Canvas.Pixels[x,y] := $000000;

Und bei einem hohen 'i' hat mein Rechner dann ein bisschen viel zu rechnen..

Danke im Voraus schonmal.

Was ist ein Apfelmännchen ?

[Valle]

Hallo,

dein Problem ist nicht die Berechnung der Menge, sondern die grafische Darstellung. Pixels ist sehr langsam. Du solltest dir hier etwas anderes suchen. Es könnte zum Beispiel helfen, ein TBitmap zu erstellen, dieses zu befüllen und erst anschließend darzustellen. (das nennt man Buffer) Außerdem gibt es eine wesentlich schnellere Alternative zu Pixels, die nennt sich Scanline. Mit Google und Co. wirst du dazu sicher einiges finden.

Wenn du dann noch die Berechnung optimieren willst, solltest du erstmal schauen, ob die iterative Variante des Algorithmus eventuell schneller ist.

Liebe Grüße,
Valentin

[MrMooed]

Zitat von Valle:

Hallo,

dein Problem ist nicht die Berechnung der Menge, sondern die grafische Darstellung. Pixels ist sehr langsam. Du solltest dir hier etwas anderes suchen. Es könnte zum Beispiel helfen, ein TBitmap zu erstellen, dieses zu befüllen und erst anschließend darzustellen.

Habe wohl vergessen zu erwähnen, dass 'Bild' eine TBitMap ist die anschließend auf die Form gemalt wird

Zitat von Valle:

Außerdem gibt es eine wesentlich schnellere Alternative zu Pixels, die nennt sich Scanline. Mit Google und Co. wirst du dazu sicher einiges finden.

Ok werde ich mir direkt mal ansehen

Zitat von Valle:

Wenn du dann noch die Berechnung optimieren willst, solltest du erstmal schauen, ob die iterative Variante des Algorithmus eventuell schneller ist.

Prinzipiell sollten Iterative und Rekursive Algorithmen doch gleichschnell sein oder ?
So etwas wird einem leider in der Schule nicht vermittelt und habe mir das "Wissen" selbst angeeignet, kann sein dass ich mich da total irre

[Valle]

Beim Aufruf einer Funktion müssen alle zu übergebenden Variablen auf den Stack geschoben werden. Das allein kostet schon Zeit. Die Frage sollte also sein, ob der iterative Overhead das ausgleichen kann. Es gibt hier aber sicher einige mit abgeschlossenem Informatikstudium, die dir das besser erklären können als ich. Des Weiteren hat man bei Rekursion das Problem, dass es eine maximale Rekursionstiefe hat, die die Menge an verschachtelten Aufrufen stark beschränkt.

Rekursive Lösungen sind meist viel lesbarer und "schöner" als ihre iterativen Pendanten.

Ob das in der Praxis bei deinem Beispiel wirklich viel Unterschied macht kann ich dir nicht sagen. Aber wenn es dich interessiert kannst du es natürlich herausfinden. Es gibt Möglichkeiten, die Zeit einer Berechnung zu messen. Das kannst du für beide Verfahren durchführen, wenn du magst. Theoretisch meinte selbst der Prof an der FH, an der ich ein Semester lang ein Frühstudium abgelegt habe, dass die rekursive Variante unschlagbar toll wäre. Praktisch hatte er aber öfter mal Unrecht.

[MrMooed]

Tatsache
Nach meinen Messungen beträgt die Mittlere Zeit um 20 mal das Selbe Bild zu rechnen:

Rekursiv: 423,55ms
Iterativ: 412,65ms

kleiner aber feiner Unterschied Werde das ganze nachher nochmal testen wenn ich auf ScanLine umgestellt habe.

[Neutral General]

Hi,

Scanline wird dir einen großen Geschwindigkeitsschub geben.
Mit Multithreading lässt sich das auch beschleunigen.
Du teilst das bild einfach unter den Kernen auf und jeder Kern berechnet einen Teil des Bildes.
Im Hauptthread fügst du die Teile zusammen und zeichnest (Das Zeichnen ist normalerweise leider nicht threadsafe)

[MrMooed]

Eigentlich wollte ich Multithreading erst am Schluss machen, da ich sonst schlechten Code mit Hardware kompensiere

Nun gut .. ich würde es dann so machen, dass jeder Thread einen Streifen des Bildes rechnen muss. Also 'Fensterbreite / CPUKerne' dann muss ich ihm noch den ganzen Algorithmus und die Zeichenfunktion in den Thread packen oder ?
Somit muss dem Thread dann noch übergeben werden von welchem xMin - xMax er rechnen soll.
Aber auf meine Form kann der Thread nicht selber zeichnen - eine TBitMap als Rückgabe

Hatte vor langer Zeit mal einen Link zum multithreading gefunden, vllt kennt jemand etwas noch verständlicheres ?
Multithreading

[Valle]

Zitat von MrMooed:

Eigentlich wollte ich Multithreading erst am Schluss machen, da ich sonst schlechten Code mit Hardware kompensiere

Richtig so!

Vielleicht machst du es auch gleich in zwei Schritten. Erst die Threads alle Werte berechnen lassen und in einem Array zwischenspeichern. Und dann den Main-Thread alles zeichnen lassen. Letzteres lässt sich ja via Multithreading vermutlich sowieso nicht beschleunigen. Höchstens noch via OpenGL, aber das ist ... weit gegriffen.

[Namenloser]

Ich habe mal Mandelbrot programmiert, auch mit Multithreading. Ich habe einfach ein Bitmap genommen und dann jeden Thread jeweils die n-te, n+1-te, n+2-te usw. Scanline berechnen lassen. Also z.B. bei 4 Threads wäre der 1. Thread zuständig für die 0, 4, 8, ... Scanline, der 2. Thread für die 1, 5, 9, ..., der 3. für die 2, 6, 10, ..., und der 4. für die 3, 7, 11, ...

Das ist leicht zu implementieren und hat den Vorteil, dass die Threads alle in etwa gleich viel Arbeit verrichten müssen (wenn man das ganze Bild nur in 4 große Teile aufteilen würde, könnte es sein, dass auf 3 Teilen fast nichts zu berechnen ist und dann doch wieder nur ein Thread die ganze Arbeit macht).

Man sollte das Bild übrigens auf jeden Fall in Zeilen aufteilen, nicht in Spalten wie in #7 impliziert, da das Bild zeilenweise im Speicher liegt, d.h. man spart dadurch eine Menge TBitmap.Scanline-Aufrufe und außerdem reduziert man Cache-Misses.

[sx2008]

Das Wurzelziehen mit SQRT() sollte man bei der Mandelbrotmenge unbedingt vermeiden, denn es kostet viel Zeit.
In der rekursiven Variante wird ja auf (A < 2) abgefragt.
Lässt man das Wurzelziehen weg, dann muss auch die Konstante quadriert werden (2*2=4):

Delphi-Quellcode:

if (nX*nX + nY*nY) >= 4.0 then
  exit;