Der Sortieralgorithmus dieser Frage wird doppelt so schnell(!), wenn -fprofile-arcs ist in gcc (4.7.2) aktiviert. Der stark vereinfachte C-Code dieser Frage (es stellte sich heraus, dass ich das Array mit allen Nullen initialisieren kann, das seltsame Leistungsverhalten bleibt bestehen, aber es macht die Argumentation viel einfacher):
#include <time.h>
#include <stdio.h>
#define ELEMENTS 100000
int main() {
int a[ELEMENTS] = { 0 };
clock_t start = clock();
for (int i = 0; i < ELEMENTS; ++i) {
int lowerElementIndex = i;
for (int j = i+1; j < ELEMENTS; ++j) {
if (a[j] < a[lowerElementIndex]) {
lowerElementIndex = j;
}
}
int tmp = a[i];
a[i] = a[lowerElementIndex];
a[lowerElementIndex] = tmp;
}
clock_t end = clock();
float timeExec = (float)(end - start) / CLOCKS_PER_SEC;
printf("Time: %2.3f\n", timeExec);
printf("ignore this line %d\n", a[ELEMENTS-1]);
}
Nachdem ich lange mit den Optimierungsflags gespielt hatte, stellte sich heraus, dass dies der Fall war -ftree-vectorize ergibt auch dieses seltsame Verhalten, damit wir nehmen können -fprofile-arcs Außer Frage. Nach der Profilierung mit perf Das habe ich gefunden Der einzige relevante Unterschied ist:
Schneller Fall gcc -std=c99 -O2 simp.c (läuft in 3,1 s)
cmpl %esi, %ecx
jge .L3
movl %ecx, %esi
movslq %edx, %rdi
.L3:
Langsamer Fall gcc -std=c99 -O2 -ftree-vectorize simp.c (läuft in 6,1 s)
cmpl %ecx, %esi
cmovl %edx, %edi
cmovl %esi, %ecx
Was den ersten Ausschnitt betrifft: Da das Array nur Nullen enthält, springen wir immer zu .L3. Es kann stark von der Verzweigungsvorhersage profitieren.
Ich vermute die cmovl Anweisungen können nicht von der Verzweigungsvorhersage profitieren.
Fragen:
-
Sind alle meine obigen Vermutungen richtig? Macht das den Algorithmus langsam?
-
Wenn ja, wie kann ich verhindern, dass gcc diese Anweisung ausgibt (außer der trivialen
-fno-tree-vectorizationProblemumgehung natürlich), aber immer noch so viele Optimierungen wie möglich? -
Was ist das
-ftree-vectorization? Die Dokumentation ist ziemlich vage, ich bräuchte ein wenig mehr Erklärung, um zu verstehen, was passiert.
Aktualisieren: Da kam es in Kommentaren auf: Das komische Leistungsverhalten bzgl. der -ftree-vectorize Flag bleibt bei zufälligen Daten. Wie Yakk betont, ist es für die Auswahlsortierung tatsächlich schwierig, einen Datensatz zu erstellen, der zu vielen Fehlvorhersagen für Zweige führen würde.
Da es auch aufkam: Ich habe eine Core i5 CPU.
Basierend auf Yakks Kommentar habe ich einen Test erstellt. Der folgende Code (Online ohne Boost) ist natürlich kein Sortieralgorithmus mehr; Ich habe nur die innere Schleife herausgenommen. Sein einziges Ziel ist es, die Wirkung der Verzweigungsvorhersage zu untersuchen: Wir überspringen die if Filiale in der for Schleife mit Wahrscheinlichkeit p.
#include <algorithm>
#include <cstdio>
#include <random>
#include <boost/chrono.hpp>
using namespace std;
using namespace boost::chrono;
constexpr int ELEMENTS=1e+8;
constexpr double p = 0.50;
int main() {
printf("p = %.2f\n", p);
int* a = new int[ELEMENTS];
mt19937 mt(1759);
bernoulli_distribution rnd(p);
for (int i = 0 ; i < ELEMENTS; ++i){
a[i] = rnd(mt)? i : -i;
}
auto start = high_resolution_clock::now();
int lowerElementIndex = 0;
for (int i=0; i<ELEMENTS; ++i) {
if (a[i] < a[lowerElementIndex]) {
lowerElementIndex = i;
}
}
auto finish = high_resolution_clock::now();
printf("%ld ms\n", duration_cast<milliseconds>(finish-start).count());
printf("Ignore this line %d\n", a[lowerElementIndex]);
delete[] a;
}
Die Schleifen von Interesse:
Dies wird als bezeichnet cmov
g++ -std=c++11 -O2 -lboost_chrono -lboost_system -lrt branch3.cpp
xorl %eax, %eax
.L30:
movl (%rbx,%rbp,4), %edx
cmpl %edx, (%rbx,%rax,4)
movslq %eax, %rdx
cmovl %rdx, %rbp
addq $1, %rax
cmpq $100000000, %rax
jne .L30
Dies wird als bezeichnet kein cmovdas -fno-if-conversion Flagge wurde von Turix in seiner Antwort darauf hingewiesen.
g++ -std=c++11 -O2 -fno-if-conversion -lboost_chrono -lboost_system -lrt branch3.cpp
xorl %eax, %eax
.L29:
movl (%rbx,%rbp,4), %edx
cmpl %edx, (%rbx,%rax,4)
jge .L28
movslq %eax, %rbp
.L28:
addq $1, %rax
cmpq $100000000, %rax
jne .L29
Der Unterschied nebeneinander
cmpl %edx, (%rbx,%rax,4) | cmpl %edx, (%rbx,%rax,4)
movslq %eax, %rdx | jge .L28
cmovl %rdx, %rbp | movslq %eax, %rbp
| .L28:
Die Ausführungszeit als Funktion des Bernoulli-Parameters p
Der Code mit der cmov Unterricht ist absolut unempfindlich p. Der Code ohne das cmov Unterricht ist der Gewinner, wenn p<0.26 oder 0.81<p und ist höchstens 4,38x schneller (p=1). Die schlechtere Situation für den Verzweigungsprädiktor liegt natürlich bei ungefähr p=0.5 wobei der Code 1,58x langsamer ist als der Code mit der cmov Anweisung.
Erhalten Sie die gleichen Ergebnisse mit echten (zufälligen) Daten anstelle von Nullen?
– PaulR
10. Januar 2014 um 22:58 Uhr
Nur eine Vermutung, aber ich denke, der Baumteil von tree-vectorize bedeutet, dass es an der “Baum” -Form des Codes arbeitet (gcc konvertiert Ihren Code nach dem Parsen in eine Reihe verschiedener Formen, und Baum ist eine dieser Formen iirc ). Vektorisieren bezieht sich natürlich nur auf die Verwendung von Vektoranweisungen (SSE, MMX, 3D-Now usw.).
– CrazyCasta
10. Januar 2014 um 22:59 Uhr
@PaulR Ja, das tue ich. Andere berichteten dasselbe.
– Ali
10. Januar 2014 um 22:59 Uhr
Vollständig zufällige und gleichförmige Elemente in einer Auswahlsortierung verursachen nicht viele Verzweigungsvorhersagefehler. Das erste Element ist
k_0einheitlich von 0 bis N. Jedes Element danach hat ein ak_0/NWahrscheinlichkeit, kleiner zu sein, was zu einer Verzweigung führt. Dieses Element wird dann einheitlich von 0 bis ausgewähltk_0-1. Stellen Sie sich vor, es würde immer den mittleren nehmen: Dann finden Sie nach einer logarithmischen Anzahl von Schritten den kleinsten übrig. Im Durchschnitt ist das die Leistung, die Sie erhalten. Auf einen100000Anordnung,lgist16was bedeutet, dass der Zweig anfangs 6000 Mal mehr in eine Richtung geht als in die andere.– Yakk – Adam Nevraumont
11. Januar 2014 um 1:27 Uhr
Tatsächlich bedeutet Ihre ineffiziente Sortierung, dass jeder Vergleich wenig Entropie hat, also sehr vorhersehbar ist, sodass die Verzweigungsvorhersage nahezu perfekt ist. Jetzt können wir pathologische Daten arrangieren. Wir möchten, dass jeder Vergleich eine 50:50-Chance hat, größer oder kleiner als der aktuell niedrigste zu sein. Satz
array[i] =+/-iwobei das Zeichen zufällig ausgewählt wird, und reprofilieren (alternierend könnte funktionieren, aber einen Verzweigungsprädiktor zu haben, der alternierend behandelt, wäre in der Hardware einfach, so dass zufällig böse genug ist).– Yakk – Adam Nevraumont
11. Januar 2014 um 1:31 Uhr