Kann man das noch optimieren? (Mandelbrot-Berechnung)

*Q* 1

Hallo zusammen,

ich arbeite zurzeit an einem Madelbrot/Apfelmännchen-Programm.
Das Bottleneck des Programms ist folgendes:

int calculateNumIterations(mandelType x, mandelType y)
{
	mandelType x1=0, x2=0, y1=0;
	for(int i = 0; i < numIterations; ++i)
	{
		x2 = x1*x1 - y1*y1 + x ;
		y1 = 2*x1*y1 + y;
		x1 = x2;
		if(x1*x1 + y1*y1  > 4)
		{
			return i;
		}
	}
	return numIterations;
}

Ich denke eig nicht, dass man da noch viel machen kann, aber falls doch wäre es schön, weil das Programm alles an geschwindigkeit brauchen kann, was möglich ist.
mandelType ist übrigens nen typedef für double im moment.
Würde inline asm was bringen? Vermutlich eher nicht, da der compiler das ja selbst schon gut hinkriegen sollte, oder?

Demnächst stell ich vermutlich auf berechnung im fragment-shader mit fixed-point-arithmetik um (mit single precision hab ich das schon hinbekommen, der Geschwindigkeitsvorteil ist RIESIG aber single precision kann man vergessen...). Aber bis es soweit ist arbeite hier hierdran noch ein wenig.

P.S.: Wenn wer das Programm haben will, einfach Bescheid sagen.

Ich kenne Mandelbrot nur vom Hören.
Wenn wirklich diese simple Funktion die Bremse ist, dann kann man da nicht wirklich viel machen.

Profile mal dein Programm und optimiere dann. Mach dir nicht so viele Gedanken während dem programmieren ob das langsam sein könnte.

SeppJ

Ich fürchte, da lässt sich nichts mehr optimieren, was der Compiler nicht sowieso optimieren würde. Ich nehme an, numIterations ist eine Compilezeitkonstante, die der Compiler kennt? Was nicht so toll ist, ist natürlich ein if in jedem Durchgang. Parallelisierbar ist die Schleife auch nicht . Was Parallelisierbar sein sollte, ist jedoch der Aufruf der Funktion. Das sollte sehr gut skalieren.

Was man noch machen könnte ist, mal darüber nachzudenken, das Problem ganz anders zu formulieren, vielleicht gibt's eine bessere Variante. Ich kenne Mandelbrot selber nicht aus der Praxis, aber da werden andere doch schon viel drüber geschrieben haben:
http://en.wikipedia.org/wiki/Mandelbrot_set#Computer_drawings
http://en.wikipedia.org/wiki/Mandelbrot_set#Optimizations

drakon

Mit Assembler könnte man das in soweit noch optimieren, dass du darauf schaust, dass es möglichst wenig Cache misses gibt und möglichst nur mit Registern arbeitest. Da sind Compiler üblicherweise nicht so gut, weil es dazu oftmals ein Umordnen der Anweisungen erfordert, was nicht immer (für einen Compiler) offensichtlich äquivalent ist.

Du könntest auch mal versuchen mit SSE und ähnlichen Erweiterungen noch was rauszuholen.

@SeppJ
Compiler sind relativ schwache optimierer für solche kleine Sachen, weil sie so verdammt konservativ sind (ist auch gut so). Wenn man solche Stückchen von Auge anschaut kann man da durchaus recht viel rausholen, wenn man sich ein wenig mit der Arbeitsweise von CPUs auskennt (Caching, Pipelineing, Data dependencies, forwarding, aliasing etc.)

pumuckl

wie groß kann numIterations werden?

SeppJ

drakon schrieb:

Du könntest auch mal versuchen mit SSE und ähnlichen Erweiterungen noch was rauszuholen.

Wenn ich im Leben eines gelernt habe, dann dass SSE-Intrinsics bei so Einzelrechnungen eher bremsen. In der Regel machen die Compiler hier wirklich das beste was geht. Eventuell kannst du durch geschickte Compileroptionen noch mal ordentlich was rausholen (5-10%). Viele Leute wissen gar nicht, wie sie das Optimieren optimieren können .

@SeppJ
Compiler sind relativ schwache optimierer für solche kleine Sachen, weil sie so verdammt konservativ sind (ist auch gut so). Wenn man solche Stückchen von Auge anschaut kann man da durchaus recht viel rausholen, wenn man sich ein wenig mit der Arbeitsweise von CPUs auskennt (Caching, Pipelineing, Data dependencies, forwarding, aliasing etc.)

Also ich habe das letzte halbe Jahr damit verbracht, herauszufinden, dass dies nicht so ist.

drakon

SeppJ schrieb:

drakon schrieb:

Du könntest auch mal versuchen mit SSE und ähnlichen Erweiterungen noch was rauszuholen.

Wenn ich im Leben eines gelernt habe, dann dass SSE-Intrinsics bei so Einzelrechnungen eher bremsen. In der Regel machen die Compiler hier wirklich das beste was geht. Eventuell kannst du durch geschickte Compileroptionen noch mal ordentlich was rausholen (5-10%). Viele Leute wissen gar nicht, wie sie das Optimieren optimieren können .

Hmm. Natürlich darf man das nicht einfach stupide ersetzen. Das bringt dann nix, aber wenn man sinnvoll die Anweisungen aufteilen kann, sollte das doch einiges bringen. Man muss natürlich sehr gut darüber nachdenken was man machen kann (vlt. bringts am Ende wirklich nix, wenn es zu viele Abhängigkeiten hat).

Bashar

Da du schon an Inline-Assembler denkst: Hast du dir mal den generierten Code angeguckt?

Ansonsten:
Du berechnest die Quadrate pro Iteration zweimal. Falls der Compiler das nicht optimiert, immerhin ist der Wert iterationsübergreifend, dann könntest du dafür zwei extra Variablen einführen:

int calculateNumIterations(mandelType x, mandelType y)
{
    mandelType x1=0, x2=0, y1=0, x1squared = 0, y1squared = 0;
    for(int i = 0; i < numIterations; ++i)
    {
        x2 = x1squared - y1squared + x;
        y1 = 2*x1*y1 + y;
        y1squared = y1*y1;
        x1 = x2;
        x1squared = x1*x1;
        if(x1squared  + y1squared > 4)
        {
            return i;
        }
    }
    return numIterations;
}

drakon

SeppJ schrieb:

@SeppJ
Compiler sind relativ schwache optimierer für solche kleine Sachen, weil sie so verdammt konservativ sind (ist auch gut so). Wenn man solche Stückchen von Auge anschaut kann man da durchaus recht viel rausholen, wenn man sich ein wenig mit der Arbeitsweise von CPUs auskennt (Caching, Pipelineing, Data dependencies, forwarding, aliasing etc.)

Also ich habe das letzte halbe Jahr damit verbracht, herauszufinden, dass dies nicht so ist.

Also ich habe schon sehr einfache Strukturen gesehen, die sehr gut optimierbar waren, wenn man nur ein paar Anweisungen vertauscht. Wenn man dem nicht bewusst ist, dann verliert man da Power. Kann gut sein, dass du da einiges mehr Erfahrung hast, aber finde es halt auch plausibel, dass man da im feinen einiges besser von Hand optimieren kann als es ein Compiler überhaupt darf.

dot

Die einzelnen Pixel sind völlig unabhängig voneinander. D.h. du kannst mit SSE/AVX und Multithreading potentiell viel rausholen. Gegen eine Lösung im FragmentShader hat die CPU aber sicher keine Chance...

otze

drakon schrieb:

Also ich habe schon sehr einfache Strukturen gesehen, die sehr gut optimierbar waren, wenn man nur ein paar Anweisungen vertauscht.

Dann musst du dem Compiler erlauben Operationen zu vertauschen. Beispiel beim Gcc -Ofast

drakon

otze schrieb:

drakon schrieb:

Also ich habe schon sehr einfache Strukturen gesehen, die sehr gut optimierbar waren, wenn man nur ein paar Anweisungen vertauscht.

Dann musst du dem Compiler erlauben Operationen zu vertauschen. Beispiel beim Gcc -Ofast

Sicher eine Möglichkeit, aber es gibt ja Optimierungen, die eigentlich nicht äquivalent sind, aber dann halt im jeweiligen Fall doch (weil man halt gewisse Umstände kennt, die ein Compiler nicht kenne kann) und da kann man auch mit solchen Einstellungen nichts gewinnen.
Auf die schnelle kann ich kein gutes Beispiel bringen, aber ich denke ihr wisst was ich meine.
Natürlich sollte man zuerst den Compiler ausreizen, aber dann kann es sich schon auch lohnen den generierten Code sehr gut anzuschauen.

*Q* 1

Also erstmal zu multithreading:
Das ganze läuft schon multithreaded. Die schleife wird für jeden Pixel aufgerufen.
Ich habe den Bildschirm in "Tiles" aufgeteilt (je ca. 100x100 Pixel). Dann überegebe ich einem Threadpool die ganzen tiles zum rendern.

NumIterations ist eine kompilezeitkonstante und hat normalerweise einen wert von ca. 500-3000. (Atm verwende ich 800).

Wie wäre es rein theoretisch, wenn man die ganze schleife "entrollen" würde?
Würde das eher schaden oder was bringen? Der code wird dadurch größer, was vermutlich schlecht für den cache ist, aber dann braucht man keine explizite schleife mehr.

Und zum quadrat zweimal berechnen: Ich glaube das geht nicht besser, weil sich die werte zwischendrin auch ändern? Aber ich gucks mir gleich nochmal genau an.

Ok danke für eure hilfe. Aber vermutlich werd ichs dann so belassen, weil ich mich mit asm nicht auskenne und das vermutlich auch nicht soooo viel bringen würde.

Edit: Ich benutz übrigens MSVC. Hab einfach release mode genommen. Was kann man denn da noch so umstellen, was was bringen könnte?

Edit2: Profiler hab ich benutzt (den vom visual studio 2010), der zeigt mir aber immer an das 99% cpu zeit auf einen slot (ich benuitze qt) draufgehen. Aber das zeigt er auch an wenn in dem slot gar kein code steht.
Aber das liegt definitiv an der schleife. Das ist das Herzstück des algorithmus und wird für jeden Pixel aufgerufen.
Setze ich die anzahl der iterationen runter, dann läuft das problem VIEL schneller. Es skaliert also direkt mit der anzahl der iterationen (~linear nehme ich an).

Bashar

Q schrieb:

Und zum quadrat zweimal berechnen: Ich glaube das geht nicht besser, weil sich die werte zwischendrin auch ändern?

Tun sie ja nicht. Klar, innerhalb der Iteration schon, aber nicht von einer Iteration zur nächsten: Die Quadrate in deiner Abbruchbedingung sind die gleichen wie die am Anfang der nächsten Iteration.

drakon

Q schrieb:

Wie wäre es rein theoretisch, wenn man die ganze schleife "entrollen" würde?
Würde das eher schaden oder was bringen? Der code wird dadurch größer, was vermutlich schlecht für den cache ist, aber dann braucht man keine explizite schleife mehr.

Loop unrolling beherrschen Compiler eigentlich recht gut, weil es klar ist, wie man das machen muss.

Aber kannst es ja mal testen. Ich vermute aber, dass es nichts bringt, wenn du das von Hand selber machst.

*Q* 1

Sind compiler denn so "verrückt" und unrollen loops die von 0 bis ~1000 gehen?
Bzw ist sowas gang und gebe oder ist das eher schlecht, weils den code zu sehr aufbläht?

Das mit den quadraten bau ich dann evtl. gleich mal ein.

hustbaer

Ne, kein Compiler wird den loop 1000 fach ausrollen.
Aber vielleicht 4-fach oder so.

Athar

Auf Loopunrolling seitens des Compilers würde ich wegen des ifs nicht gerade setzen.
Man kann es manuell machen und die Tatsache ausnützen, dass die Abbruchbedingung (erst einmal erreicht) auch nach weiteren Iterationen wahr bleiben müsste.

Ein Test auf zwei verschiedenen Prozessoren mit gcc 4.6 (Generierung eines 1680x1050-Bildes im Bereich (-2.1 | -1.3) bis (0.8 | 1.3) mit numIterations=1000):
http://94.23.22.190/etc/phenom-ii-x4.png
http://94.23.22.190/etc/atom.png

Noch einmal mit der auf Wikipedia beschriebenen Optimierung:
http://94.23.22.190/etc/phenom-ii-x4-opt.png
http://94.23.22.190/etc/atom-opt.png

Ich würde für 5-faches Unrolling plädieren.
Ob es Unterschiede beim MSVC gibt, würde mich auch interessieren, allerdings muss ich mein Testsystem vorher noch um Wine-Unterstützung erweitern.

hustbaer

Athar schrieb:

Man kann es manuell machen und die Tatsache ausnützen, dass die Abbruchbedingung (erst einmal erreicht) auch nach weiteren Iterationen wahr bleiben müsste.

Arrr, zu langsam
Genau das ist mir auch gerade eingefallen, wollte ich gerade vorschlagen.

drakon

drakon schrieb:

Sicher eine Möglichkeit, aber es gibt ja Optimierungen, die eigentlich nicht äquivalent sind, aber dann halt im jeweiligen Fall doch (weil man halt gewisse Umstände kennt, die ein Compiler nicht kenne kann) und da kann man auch mit solchen Einstellungen nichts gewinnen.
Auf die schnelle kann ich kein gutes Beispiel bringen, aber ich denke ihr wisst was ich meine.

Athar schrieb:

Man kann es manuell machen und die Tatsache ausnützen, dass die Abbruchbedingung (erst einmal erreicht) auch nach weiteren Iterationen wahr bleiben müsste.

Danke für das gute Beispiel!

Perfect branch predictor gibts leider (noch) nicht.