Als Antwort auf eine andere Stack Overflow-Frage ( diese ) Ich bin über ein interessantes Teilproblem gestolpert. Was ist der schnellste Weg, ein Array mit 6 ganzen Zahlen zu sortieren?
Da die Frage sehr niedrigschwellig ist:
- können wir nicht davon ausgehen, dass Bibliotheken verfügbar sind (und der Aufruf selbst ist mit Kosten verbunden), nur einfache C
- um das Leeren der Befehlspipeline zu vermeiden (die eine sehr hohen Kosten) sollten wir wahrscheinlich Verzweigungen, Sprünge und jede andere Art von Unterbrechung des Kontrollflusses (wie jene, die sich hinter Sequenzpunkten in
&&o||). - Wenn der Platz begrenzt ist und es darauf ankommt, die Register und den Speicherverbrauch zu minimieren, ist eine Sortierung an Ort und Stelle wahrscheinlich am besten.
In Wirklichkeit handelt es sich bei dieser Frage um eine Art Golf, bei dem das Ziel nicht darin besteht, die Länge des Quelltextes, sondern die Ausführungszeit zu minimieren. Ich nenne es "Zening"-Code, wie im Titel des Buches verwendet Zen der Code-Optimierung par Michael Abrash und seine Fortsetzungen .
Es gibt mehrere Gründe, warum es interessant ist:
- das Beispiel ist einfach und leicht zu verstehen und zu messen, es sind keine großen C-Kenntnisse erforderlich
- Es zeigt die Auswirkungen der Wahl eines guten Algorithmus für das Problem, aber auch die Auswirkungen des Compilers und der zugrunde liegenden Hardware.
Hier ist meine (naive, nicht optimierte) Referenzimplementierung und mein Testset.
#include <stdio.h>
static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
};
unsigned long long cycles = rdtsc();
for (i = 0; i < 6 ; i++){
sort6(d[i]);
/*
* printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],
* d[i][8], d[i][9], d[i][10]);
*/
}
cycles = rdtsc() - cycles;
printf("Time is %d\n", (unsigned)cycles);
}Rohe Ergebnisse
Da die Anzahl der Varianten immer größer wird, habe ich sie alle in einer Testsuite zusammengefasst, die Sie hier finden können ici . Die tatsächlich verwendeten Tests sind etwas weniger naiv als die oben gezeigten, dank Kevin Stock. Sie können sie in Ihrer eigenen Umgebung kompilieren und ausführen. Ich bin sehr an dem Verhalten auf verschiedenen Zielarchitekturen/Compilern interessiert. (OK Leute, schreibt es in die Antworten, ich werde jeden, der ein neues Resultset beisteuert, mit +1 belohnen).
Die Antwort habe ich vor einem Jahr Daniel Stutzbach (für den Golfsport) gegeben, da er damals die schnellste Lösung hatte (Sortiernetze).
Linux 64 Bit, gcc 4.6.1 64 Bit, Intel Core 2 Duo E8400, -O2
- Direkter Aufruf der Bibliotheksfunktion qsort : 689.38
- Naive Implementierung (Einfügungssortierung) : 285.70
- Einfügungssortierung (Daniel Stutzbach) : 142.12
- Einfügung Sortieren Ungerollt : 125.47
- Rangordnung : 102.26
- Rangordnung mit Registern : 58.03
- Sortierungsnetzwerke (Daniel Stutzbach) : 111.68
- Sortierungsnetzwerke (Paul R) : 66.36
- Sortierung von Netzwerken 12 mit Fast Swap : 58.86
- Sortierung Netzwerke 12 neu sortiert Swap : 53.74
- Sortierung Netze 12 neu sortiert Simple Swap : 31.54
- Neu geordnetes Sortiernetz mit schnellem Tausch : 31.54
- Neu geordnetes Sortiernetz mit schneller Auslagerung V2 : 33.63
- Inlined Bubble Sort (Paolo Bonzini) : 48.85
- Unrolled Insertion Sort (Paolo Bonzini) : 75.30
Linux 64 Bit, gcc 4.6.1 64 Bit, Intel Core 2 Duo E8400, -O1
- Direkter Aufruf der Bibliotheksfunktion qsort : 705.93
- Naive Implementierung (Einfügungssortierung) : 135.60
- Einfügungssortierung (Daniel Stutzbach) : 142.11
- Einfügung Sortierung Ungerollt : 126.75
- Rangfolge : 46.42
- Rangordnung mit Registern : 43.58
- Sortierungsnetzwerke (Daniel Stutzbach) : 115.57
- Sortierungsnetzwerke (Paul R) : 64.44
- Sortiernetze 12 mit Fast Swap : 61.98
- Sortierung Netzwerke 12 neu sortiert Swap : 54.67
- Sortierung Netze 12 neu sortiert Simple Swap : 31.54
- Neu geordnetes Sortiernetz mit schnellem Tausch : 31.24
- Neu geordnetes Sortiernetz mit schneller Auslagerung V2 : 33.07
- Inlined Bubble Sort (Paolo Bonzini) : 45.79
- Unrolled Insertion Sort (Paolo Bonzini) : 80.15
Ich habe sowohl die -O1- als auch die -O2-Ergebnisse einbezogen, weil O2 überraschenderweise für einige Programme weniger effizienter als O1. Ich frage mich, welche spezifische Optimierung diesen Effekt hat?
Kommentare zu Lösungsvorschlägen
Einfügen Sortieren (Daniel Stutzbach)
Wie erwartet ist die Minimierung von Verzweigungen in der Tat eine gute Idee.
Sortierung von Netzwerken (Daniel Stutzbach)
Besser als Insertion Sort. Ich habe mich gefragt, ob der Haupteffekt nicht in der Vermeidung der externen Schleife liegt. Ich habe es mit unrollter Einfügesortierung versucht, um das zu überprüfen, und tatsächlich erhalten wir ungefähr die gleichen Zahlen (der Code ist ici ).
Sortierung von Netzwerken (Paul R)
Das Beste bisher. Der eigentliche Code, den ich zum Testen verwendet habe, lautet ici . Ich weiß noch nicht, warum es fast zwei Mal so schnell ist wie die andere Implementierung des Sortiernetzes. Parameterübergabe ? Schneller Maximalwert ?
Sortierung von Netzen 12 SWAP mit Fast Swap
Wie von Daniel Stutzbach vorgeschlagen, habe ich sein 12-Swap-Sortiernetzwerk mit branchless fast swap kombiniert (Code ist ici ). Er ist in der Tat schneller, der beste bisher, mit einem kleinen Vorsprung (etwa 5 %), wie bei einem Swap weniger zu erwarten wäre.
Es ist auch interessant festzustellen, dass der verzweigungslose Swap viel (4-mal) weniger effizient zu sein scheint als der einfache Swap mit if auf der PPC-Architektur.
Aufruf der Bibliothek qsort
Um einen weiteren Anhaltspunkt zu geben, habe ich auch versucht, wie vorgeschlagen, einfach die Bibliothek qsort aufzurufen (der Code ist ici ). Wie erwartet ist es viel langsamer: 10 bis 30 mal langsamer... wie es mit der neuen Test-Suite offensichtlich wurde, scheint das Hauptproblem das anfängliche Laden der Bibliothek nach dem ersten Aufruf zu sein, und es vergleicht nicht so schlecht mit anderen Versionen. Es ist nur zwischen 3 und 20 mal langsamer auf meinem Linux. Auf einigen Architekturen, die von anderen für Tests verwendet werden, scheint es sogar schneller zu sein (was mich wirklich überrascht, da die Bibliothek qsort eine komplexere API verwendet).
Rangfolge
Rex Kerr schlug eine völlig andere Methode vor: für jedes Element des Arrays wird direkt seine Endposition berechnet. Dies ist effizient, da die Berechnung der Rangfolge keine Verzweigung erfordert. Der Nachteil dieser Methode ist, dass sie die dreifache Menge an Speicher des Arrays benötigt (eine Kopie des Arrays und Variablen zum Speichern der Rangfolgen). Die Leistungsergebnisse sind sehr überraschend (und interessant). Auf meiner Referenzarchitektur mit 32-Bit-Betriebssystem und Intel Core2 Quad E8300 lag die Zykluszahl knapp unter 1000 (wie bei Sortiernetzwerken mit verzweigendem Swap). Aber wenn ich es auf meinem 64-Bit-Rechner (Intel Core2 Duo) kompiliere und ausführe, ist es viel besser: es ist das bisher schnellste Programm. Ich habe schließlich den wahren Grund herausgefunden. Mein 32-Bit-Rechner verwendet gcc 4.4.1 und mein 64-Bit-Rechner gcc 4.4.3, und letzterer scheint diesen speziellen Code viel besser zu optimieren (bei anderen Vorschlägen gab es kaum Unterschiede).
Update :
Wie die oben veröffentlichten Zahlen zeigen, wurde dieser Effekt durch spätere Versionen von gcc noch verstärkt und Rank Order wurde durchweg doppelt so schnell wie jede andere Alternative.
Sortierung der Netze 12 mit neu geordnetem Tausch
Die erstaunliche Effizienz des Vorschlags von Rex Kerr mit gcc 4.4.3 hat mich zum Nachdenken gebracht: Wie kann ein Programm, das dreimal so viel Speicherplatz benötigt, schneller sein als verzweigungslose Sortiernetze? Meine Hypothese war, dass es weniger Abhängigkeiten von der Art "Lesen nach Schreiben" hat, was eine bessere Nutzung des superskalaren Befehlsplaners des x86 ermöglicht. Das brachte mich auf die Idee, Swaps neu anzuordnen, um die Abhängigkeiten zwischen Lesen und Schreiben zu minimieren. Einfacher ausgedrückt: Wenn Sie SWAP(1, 2); SWAP(0, 2); müssen Sie warten, bis der erste Swap beendet ist, bevor Sie den zweiten durchführen, da beide auf eine gemeinsame Speicherzelle zugreifen. Wenn Sie SWAP(1, 2); SWAP(4, 5); kann der Prozessor beides parallel ausführen. Ich habe es ausprobiert und es funktioniert wie erwartet, die Sortiernetze laufen etwa 10% schneller.
Sortierung von Netzwerken 12 mit Simple Swap
Ein Jahr nach dem ursprünglichen Beitrag schlug Steinar H. Gunderson vor, dass wir nicht versuchen sollten, den Compiler zu überlisten und den Swap-Code einfach zu halten. Das ist in der Tat eine gute Idee, denn der resultierende Code ist etwa 40% schneller! Er schlug auch einen von Hand optimierten Swap mit x86-Inline-Assemblercode vor, der immer noch einige Zyklen sparen kann. Das Erstaunlichste (es spricht Bände über die Psychologie der Programmierer) ist, dass vor einem Jahr niemand diese Version von Swap ausprobiert hat. Der von mir zum Testen verwendete Code lautet ici . Andere schlugen andere Wege vor, um einen schnellen C-Swap zu schreiben, aber mit einem anständigen Compiler wird die gleiche Leistung erzielt wie mit der einfachen Variante.
Der "beste" Code lautet nun wie folgt:
static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
const int b = max(d[x], d[y]); \
d[x] = a; d[y] = b; }
SWAP(1, 2);
SWAP(4, 5);
SWAP(0, 2);
SWAP(3, 5);
SWAP(0, 1);
SWAP(3, 4);
SWAP(1, 4);
SWAP(0, 3);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}Wenn wir unserem Testsatz Glauben schenken (und ja, er ist recht dürftig, sein einziger Vorteil ist, dass er kurz, einfach und leicht zu verstehen ist, was wir messen), liegt die durchschnittliche Anzahl der Zyklen des resultierenden Codes für eine Sorte unter 40 Zyklen (6 Tests werden ausgeführt). Das bedeutet, dass jeder Swap im Durchschnitt 4 Zyklen benötigt. Ich nenne das erstaunlich schnell. Sind weitere Verbesserungen möglich?
