[Mikrooptimierung] Pass by-val langsamer?

[Krishty]

Hi,

    struct RGBA {
        uint8_t r;
        uint8_t g;
        uint8_t b;
        uint8_t a;
    };

    void foo_byRef(RGBA const &);
    void foo_byVal(RGBA);

Angenommen, foo verarbeitet intern den übergebenen Farbwert. Wir kennen alle die grundlegenden Unterschiede: foo_byRef() wird ein Zeiger übergeben, während beim Aufruf foo_byVal()s die Farbe im Register kopiert wird. Zweite ist eigentlich zu bevorzugen, weil es die Unkosten eines zusätzlichen Zeigers und das Referenzieren möglicherweise weit entfernten Speichers vermeidet.

Nun aber der Clou: Die Referenzversion ist nicht zwingend langsamer – sie ist sogar sparsamer an Registern und Verarbeitungsschritten, wenn die Farbkomponenten einzeln referenziert werden. Das liegt daran, dass die einzelnen Komponenten via mov byte ptr direkt aus dem Speicher gepopelt werden können. Wird die Farbe hingegen im Register übergeben, muss dieses Register für jede Komponente rotiert werden; was bei einer anderen Reihenfolge als a-b-g-r außerdem erfordert, dass der Originalwert im Register vorgehalten wird.

Ich habe noch keinen realitätsnahen Testfall konstruieren können; aber ich vermute fast, dass die Referenz-Version schneller ist, falls die referenzierte Farbe noch im L1-Cache liegt – und ganz besonders, wenn man die Farbwerte als Indizes einer Nachschlagtabelle nutzt, weil der Speicherzugriff dann nicht mehr von der Rotation abhängig ist.

Gibt es für so einen Fall eine generelle Entscheidungsmöglichkeit, was zu bevorzugen ist; oder eine Taktik, den Compiler zum Optimum aus beidem zu zwingen?

[Schrompf]

Weiß ich ehrlich gesagt nicht. Ich würde aber glaube ich generell einen Datentyp aus vier Bytes vermeiden, wenn ich wirklich Performance brauche. Ich hätte zuviel Sorge, dass der Compiler nicht erkennt, dass man die Struktur als einen uint32_t initialisieren und kopieren kann.

[Niki]

Ich bin nun wahrlich kein Mikrooptimierungsspezialist wie du, Krishty. Deshalb frage ich mich wie foo_byVal schneller sein könnte als foo_byRef. Im Falle von foo_byRef wird doch sicher nur die Adresse des entsprechenden Speicherbereichs auf den Stack gepusht. Und in der Methode wird dann auf die Daten in diesem möglicherweise weit entfernten Speicherbereich zugegriffen. Und jetzt schlag mich tot, aber bei foo_byVal wird doch erstmal eine Kopie der Daten auf dem Stack angelegt, hoffentlich als 32 bit integer, und auch dazu muss auf diesen möglicherweise weit entfernte Speicherbereich zugegriffen werden. Jetzt sag' bloß nicht "Nein, es wird keine Kopie erzeugt", weil dann müsste ich mich jetzt irgendwo in der Ecke verstecken. Meinem Gefühl nach, vorausgesetzt mein Wissen lässt mich nicht auf peinlichste Art im Stich, würde ich fast davon ausgehen, dass foo_byRef schneller ist, sofern denn die Zugriffe auf die einzelnen Komponenten a, r, g, b, innerhalb der Funktion weise benutzt werden. O_O

Ich fange schonmal an zu beten, weil ich mir darüber im klaren bin das Krishty von dem Zeug echt Plan hat...

[Krishty]

Weiß ich ehrlich gesagt nicht. Ich würde aber glaube ich generell einen Datentyp aus vier Bytes vermeiden, wenn ich wirklich Performance brauche. Ich hätte zuviel Sorge, dass der Compiler nicht erkennt, dass man die Struktur als einen uint32_t initialisieren und kopieren kann.

Zumindest VS 2012 schafft das; abgesehen von wenigen umsortierten Befehlen ist der resultierende Maschinentext identisch. So lange man nur mit Ganzzahlen arbeitet und nicht zu stark aliast, optimiert Microsoft da recht gut.

Deshalb frage ich mich wie foo_byVal schneller sein könnte als foo_byRef. Im Falle von foo_byRef wird doch sicher nur die Adresse des entsprechenden Speicherbereichs auf den Stack gepusht. Und in der Methode wird dann auf die Daten in diesem möglicherweise weit entfernten Speicherbereich zugegriffen. Und jetzt schlag mich tot, aber bei foo_byVal wird doch erstmal eine Kopie der Daten auf dem Stack angelegt, hoffentlich als 32 bit integer, und auch dazu muss auf diesen möglicherweise weit entfernte Speicherbereich zugegriffen werden.

Stimmt; aber nur so lange du keine Funktionsaufrufe schachtelst:

    RGBA actualColor; // die hier wollen wir
    big1(actualColor); // Los geht’s!

    // wir nehmen an, dass unser Cache 32 KiB groß ist

    void big1(RGBA & color) {

        char flushesHalfCache[16 * 1024] = { };

        // 'actualColor' ist 16 KiB entfernt und damit noch innerhalb des Caches; unsere Referenz 'color' ebenfalls

        big2(color); // jetzt wird unsere Referenz kopiert und ist wieder 0 KiB entfernt

    }

    void big2(RGBA & color) {

        char flushesHalfCache[16 * 1024] = { }; // verdrängt 'actualColor' endgültig, weil jetzt schon >32 KiB dazwischen liegen

        foo_byRef(color); // 'color' ist aber erst 16 KiB entfernt

    }

Beim Aufruf von foo_byRef() ist actualColor schon über 32 KiB weg und damit außerhalb des L1-Caches; die Referenz color ist aber erst 16 KiB entfernt kopiert worden und damit noch drin. Wäre color als Wert übergeben worden, wäre es ebenfalls erst vor 16 KiB kopiert worden und damit noch lokal.

Das ist natürlich ein konstruiertes Beispiel – in tatsächlichen Anwendungen liegen da keine Arrays zwischen sondern Datenverarbeitung und Funktionsaufrufe – die Wirkung ist aber gleich. Schachtelst du Funktionen mehrfach, sind die übergebenen Referenzen immernoch noch lokal, der referenzierte Speicher aber nicht.

[Niki]

Aha! Verstanden! Vielen dank für die absolut spitzenmäßige Erklärung! :) Da muss man ja erst mal drauf kommen überhaupt darüber nachzudenken.

[Krishty]

Noch ein fröhlicher Nachtrag an Schrompf:

    rectangle. width = 128;
    rectangle.height = 128;

    mov dword ptr [rbp+3Ch],800080h

Store Sinking greift scheinbar bei structs ganz gut; kein Grund, alles von Hand in eine Variable zu quetschen.

[TGGC]

Gibt es für so einen Fall eine generelle Entscheidungsmöglichkeit, was zu bevorzugen ist; oder eine Taktik, den Compiler zum Optimum aus beidem zu zwingen?

Nein gibt es nicht. Im Zweifelsfall solltest du in deiner konkreten Situation, d.h. wenn dein Programm zu langsam ist und ein relevant grosser Teil der Zeit in dieser Funktion verschwindet, die verschiedenen Versionen durchprobieren.

[eXile]

Gibt es für so einen Fall eine generelle Entscheidungsmöglichkeit, was zu bevorzugen ist; oder eine Taktik, den Compiler zum Optimum aus beidem zu zwingen?

Nein gibt es nicht. Im Zweifelsfall solltest du in deiner konkreten Situation, d.h. wenn dein Programm zu langsam ist und ein relevant grosser Teil der Zeit in dieser Funktion verschwindet, die verschiedenen Versionen durchprobieren.

Das sehe ich auch so. Boost hat zwar mal die call_traits eingeführt, aber die können ja auch nicht Cache-bezogene Überlegungen miteinbeziehen.

Der einzige, der das neben dem Programmierer wohl könnte, wäre der Compiler im Rahmen der as-if-Optimierungsregel. Visual C++ 2010 macht das aber nicht, außer wenn es gerade Inlining betreibt.