c++ stackoverflow Branchless interne Zusammenführung langsamer als interne Zusammenführung mit Zweig




stackoverflow--> (2)

Ich habe vor kurzem eine Frage zum Code Review gestellt, um einen Sortieralgorithmus namens QuickMergeSort zu überprüfen . Ich werde nicht auf die Details eingehen, aber irgendwann führt der Algorithmus einen internen Mergesort durch: Anstatt die Daten zum Zusammenführen mit zusätzlichem Speicher zu speichern, vertauscht er die Elemente mit Elementen aus einem anderen Teil der ursprünglichen Sequenz, was isn ist Sonst besorgt über die Zusammenführung. Hier ist der Teil des Algorithmus, mit dem ich mich beschäftige: die Funktion, die das Zusammenführen ausführt:

template<
    typename InputIterator1,
    typename InputIterator2,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    for (; first1 != last1; ++result) {
        if (first2 == last2) {
            std::swap_ranges(first1, last1, result);
            return;
        }

        if (compare(*first2, *first1)) {
            std::iter_swap(result, first2);
            ++first2;
        } else {
            std::iter_swap(result, first1);
            ++first1;
        }
    }
    // first2 through last2 are already in the right spot
}

Diese Funktion wurde von der std::inplace_merge in der libc ++ - Implementierung von std::inplace_merge ; Diese neue Version tauscht Elemente mit einem anderen Teil des ursprünglichen Arrays aus, anstatt Elemente aus dem zusätzlichen Array zu verschieben.

Da die Zusammenführung intern ist , erkannte ich, dass ich eigentlich nicht zwei separate Eingabe-Typen haben musste: InputIterator1 und InputIterator2 sind immer gleich. Dann kam ich zu der Erkenntnis, dass, da die Operationen auf first1 und first2 immer gleich waren, ich sie in einem Array mit zwei Elementen speichern und das Ergebnis des Vergleichs verwenden konnte, um das Array zu indizieren, welchen Iterator zu tauschen und zu inkrementieren. Mit diesem kleinen Trick werde ich den Zweig los und erhalte einen weitgehend zweiglosen Merge-Algorithmus:

template<
    typename InputIterator,
    typename OutputIterator,
    typename Compare = std::less<>
>
auto half_inplace_merge(InputIterator first1, InputIterator last1,
                        InputIterator first2, InputIterator last2,
                        OutputIterator result, Compare compare={})
    -> void
{
    InputIterator store[] = { first1, first2 };

    for (; store[0] != last1; ++result) {
        if (store[1] == last2) {
            std::swap_ranges(store[0], last1, result);
            return;
        }

        bool cmp = compare(*store[1], *store[0]);
        std::iter_swap(result, store[cmp]);
        ++store[cmp];
    }
    // first2 through last2 are already in the right spot
}

Nun, das Ding ist: Mit dieser neuen half_inplace_merge Funktion ist der Gesamtsortieralgorithmus 1,5 mal langsamer als mit der ursprünglichen half_inplace_merge , und ich habe keine Ahnung warum. Ich habe mehrere Compiler-Optimierungsstufen ausprobiert, mehrere Tricks, um mögliche Alias-Probleme zu vermeiden, aber es scheint, dass das Problem von dem Zweiglosen Trick selbst kommt.

Kann also jemand erklären, warum der Branchless-Code langsamer ist?

Nachtrag: für diejenigen, die den gleichen Benchmark wie ich haben wollen ... nun, es wird ein bisschen schwierig: Ich habe die Benchmarks aus einer persönlichen Bibliothek verwendet, die viele Dinge beinhaltet; Sie müssen die Bibliothek herunterladen, diese Datei irgendwo hinzufügen und diesen Benchmark ausführen, nachdem Sie die entsprechende Zeile zum Aufrufen von quick_merge_sort in der Nähe des markierten Bereichs hinzugefügt haben (Sie müssen die Standardausgabe des Programms in eine Datei in einer Unterverzeichnis " profiles ). Dann müssen Sie dieses Python-Skript ausführen, um die Ergebnisse quick_merge_sort , und quick_merge_sort zur markierten Zeile hinzufügen. Beachten Sie, dass NumPy und Matplotlib installiert werden müssen.


Ein solch großer Unterschied ist das Produkt zweier Bedingungen.

Die erste Bedingung bezieht sich auf den ursprünglichen Code. Die In-Place-Zusammenführung ist so effizient, dass es schwierig wäre, alles wesentlich schneller zu entwickeln, selbst wenn das Codieren manuell auf Assemblerebene erfolgt. Die Anwendung von Generika ist einfach, daher hat der Compiler ** dieselbe Assembly mit oder ohne Item erzeugt. Da die Algorithmusimplementierung effizient ist, können nur wenige Maschinenanweisungen, die in die Schleife eingefügt werden, die signifikante proportionale Änderung erzeugen, die in der Frage angegeben ist.

** Kompilierungsspezifikationen in dieser Antwort verwendeten g ++ 6.2.1 20160916, das standardmäßige Fedora 24 dnf-Paket, zusammen mit LINUX Kernel 4.8.8-200.fc24.x86_64. Laufzeit war Intel i7-2600 8M Cache. Auch zu Atmel SAM3X8E ARM Cortex-M3 mit arm-none-eabi-g ++ 4.8.3-2014q1.

Die zweite Bedingung bezieht sich auf die Zusammenstellung des in Absatz 3 Satz 2 der Frage beschriebenen zweiten Stichs. Der erste Trick, die Reduktion von Typen in der Vorlage, führte zu keiner wesentlichen Änderung der Assemblersprache. Der zweite Trick führte zu flopbeeinflussenden Assemblerpegelunterschieden in der Compilerausgabe für die zwei Aufrufe.

Dieser Precompiler-Hack kann das Testen erleichtern.

#ifdef ORIG
#define half_inplace_merge half_inplace_merge_orig
#else // ORIG
#define half_inplace_merge half_inplace_merge_slow
#endif // ORIG
...
half_inplace_merge(niInA.begin(), niInA.end(),
        niInB.begin(), niInB.end(),
        niOut.begin(), compare);

Ausführung und Vergleich unter Verwendung dieser Befehle in einer Bash-Shell nutzt den Precompiler-Hack.

g++ -DORIG -S -fverbose-asm -o /tmp/qq.orig.s /tmp/qq.cpp
g++ -DSLOW -S -fverbose-asm -o /tmp/qq.slow.s /tmp/qq.cpp
araxis.sh /tmp/qq.orig.s /tmp/qq.slow.s  # to run Araxis Merge in Wine

Diese Anweisungen sind ein Ergebnis der Initialisierung des InputIterator-Speichers [], der sich jedoch außerhalb der Schleife befindet.

leaq    -48(%rbp), %rax #, _4
movq    -64(%rbp), %rdx # first1, tmp104
movq    %rdx, (%rax)    # tmp104, *_5
leaq    8(%rax), %rdx   #, _9
movq    -96(%rbp), %rax # first2, tmp105
movq    %rax, (%rdx)    # tmp105, *_9

Die primäre Verlangsamung tritt bei der Dereferenzierung der beiden Elemente auf, die in store [] enthalten sind, wie es beim Vergleichen und Tauschen benötigt wird, und das ist innerhalb der Schleife. Diese Anleitung existiert in der Version ohne den zweiten Trick nicht.

movb    %al, -17(%rbp)  # _27, cmp
movzbl  -17(%rbp), %eax # cmp, _29
cltq
...
movzbl  -17(%rbp), %edx # cmp, _31
leaq    -48(%rbp), %rax #, tmp121
movslq  %edx, %rdx  # _31, tmp122
salq    $3, %rdx    #, tmp123
addq    %rdx, %rax  # tmp123, _32

Obwohl Code in den Körpern der Bedingung für die Version ohne den Trick doppelt vorhanden ist, wirkt sich dies nur auf die Kompaktheit des Codes aus, indem zwei Aufrufe, fünf Züge und eine Vergleichsanweisung hinzugefügt werden. Die Anzahl der CPU-Zyklen, die erforderlich sind, um die In-Place-Zusammenführung durchzuführen, ist die gleiche zwischen den Zweigen, die sich aus dem Vergleich ergeben, und beiden fehlen die oben aufgeführten Anweisungen.

Für jeden von mehreren Syntaxpermutationen, die versucht werden, führt das Entfernen der Redundanz in den Zweigen zur Verbesserung der Kompaktheit zwangsweise zu zusätzlichen Befehlen, die entlang des Ausführungspfades benötigt werden.

Die Details der Anweisungssequenzen für die verschiedenen Permutationen, die bisher diskutiert wurden, werden von Compiler zu Compiler, Auswahl der Optimierungsoption und sogar den Bedingungen zum Aufruf der Funktionen variieren.

Es ist theoretisch für einen Compiler möglich, eine AST (abstrakter Symbolbaum) Refactoring-Regel (oder das Äquivalent) zu verwenden, um sowohl Programmspeicher- als auch CPU-Zyklusanforderungen für jede Version der Funktion zu erkennen und zu reduzieren. Solche Regeln haben Antezedenzien (Suchmuster), die mit dem zu optimierenden Muster innerhalb des Codes übereinstimmen.

Die Optimierung der Geschwindigkeit für den Code mit dem zweiten Trick würde eine Regelvoraussetzung erfordern, die bei der atypischen score [] -Abstraktion sowohl innerhalb als auch außerhalb der Schleife übereinstimmt. Die Erkennung der Zweigredundanz ohne den zweiten Trick ist ein vernünftigeres Ziel.

Durch die Integration der beiden Anweisungen in jeder Verzweigung kann man sehen, wie die zwei ähnlichen Muster in der AST einfach genug sein können, damit eine Refactoring-Regelvorgeschichte mit der gewünschten Code-Größenreduktion übereinstimmt und diese durchführt. Für diesen Fall würde es, wenn überhaupt, nur wenig Geschwindigkeitsgewinn geben.

if (compare(*first2, *first1)) {
    std::iter_swap(result, first2 ++);
} else {
    std::iter_swap(result, first1 ++);
}

Das Folgende ist nur eine kurze intuitive Erklärung:

Wenn wir alles wegskalieren und annehmen, dass die Iteratoren normale Zeiger sind, können wir im ersten Beispiel alle Iteratoren in Registern speichern.

Im branch less-Code können wir dies aufgrund von store[cmp] und ++store[cmp] nicht so einfach machen - und das bedeutet einen Overhead für die gesamte Verwendung von store[0] und store[1] .

Daher ist es in diesem Fall wichtiger, die Register zu maximieren als Zweige zu vermeiden.





branch-prediction