Kann man das noch optimieren? (Mandelbrot-Berechnung)

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.

Bashar

Ich steh wohl grad auf dem Schlauch. Was genau bringt es, dass die Abbruchbedingung erfüllt bleibt, wenn sie es einmal ist?

hustbaer

Dadurch kannst du das machen

loop {
    save_state();
    step();
    step();
    step();
    step();
    step();
    if (cond) {
        restore_state();
        loop {
            step();
            if (cond)
                return;
        }
    }
}

D.h. du musst nur pro N Steps 1x testen.
Sonst könntest du zwar den Loop ausrollen, aber müsstest trotzdem nach jedem Step testen.

(Alternativ zu save/restore/repeat könnte man auch ein Backlog der Z Werte schreiben, dann müsste man in der 2. Schleife nur den Test wiederholen, aber nix mehr rechnen)

Bashar

Oh ja, danke. Wie gesagt, Schlauch...

Athar

Interessanterweise bringen die eingesparten Vergleiche und Multiplikationen weniger als erwartet. Möglicherweise deswegen, weil die Werte schnell +inf erreichen und sich die CPU evtl. bei Berechnungen mit diesen schwertut (geraten, aber unwahrscheinlich). Hat vermutlich eher mit dem Cache bzw. Sprungweiten zu tun.

Der Atom profitiert zwar von den ausgelassenen Vergleichen, der Phenom aber nicht unbedingt. Hier mit Vergleich nach jeder Iteration:

http://94.23.22.190/etc/phenom-ii-x4-opt-f.png
http://94.23.22.190/etc/atom-opt-f.png

Es bleibt aber dabei, dass 5-faches Unrolling mit einem Vergleich alle 5 Iterationen insgesamt am besten zu sein scheint.