Beantwortung einer anderen Frage zum Stapelüberlauf ( dieser ) bin ich auf ein interessantes Unterproblem gestoßen. Was ist der schnellste Weg, um ein Array von 6 ganzen Zahlen zu sortieren?
Da die Frage sehr niedrig ist:
- Wir können nicht davon ausgehen, dass Bibliotheken verfügbar sind (und der Aufruf selbst hat seine Kosten), nur einfaches C.
- Um zu vermeiden, dass die Anweisungspipeline geleert wird (was sehr hohe Kosten verursacht), sollten wir wahrscheinlich Verzweigungen, Sprünge und jede andere Art von Unterbrechung des Kontrollflusses minimieren (wie die, die hinter Sequenzpunkten in
&&
oder versteckt sind||
). - Der Platz ist begrenzt und die Minimierung der Register und der Speichernutzung ist ein Problem. Idealerweise ist die Sortierung an Ort und Stelle wahrscheinlich am besten.
Wirklich ist diese Frage eine Art Golf, bei dem das Ziel nicht darin besteht, die Quelllänge, sondern die Ausführungszeit zu minimieren. Ich nenne es 'Zening'-Code, wie er im Titel des Buches Zen of Code Optimization von Michael Abrash und seinen Fortsetzungen verwendet wird .
Warum es interessant ist, gibt es mehrere Schichten:
- Das Beispiel ist einfach und leicht zu verstehen und zu messen, es sind nicht viele 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 Referenzimplementierung (naiv, nicht optimiert) 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);
}
Rohergebnisse
Da die Anzahl der Varianten immer größer wird, habe ich sie alle in einer Testsuite zusammengefasst, die gefunden werden kann ist . Die tatsächlich verwendeten Tests sind dank Kevin Stock etwas weniger naiv als die oben gezeigten. Sie können es in Ihrer eigenen Umgebung kompilieren und ausführen. Das Verhalten auf verschiedenen Zielarchitekturen / Compilern interessiert mich sehr. (OK Leute, geben Sie es in Antworten, ich werde +1 jeden Mitwirkenden einer neuen Ergebnismenge).
Ich habe Daniel Stutzbach (zum Golfen) vor einem Jahr die Antwort gegeben, da er zu dieser Zeit die Quelle der schnellsten Lösung war (Sortieren von Netzwerken).
Linux 64 Bit, gcc 4.6.1 64 Bit, Intel Core 2 Duo E8400, -O2
- Direkter Aufruf der qsort-Bibliotheksfunktion: 689.38
- Naive Implementierung (Einfügesortierung): 285,70
- Einfügungssortierung (Daniel Stutzbach): 142.12
- Einfügungssortierung Abgerollt: 125,47
- Rangfolge: 102,26
- Rangfolge mit Registern: 58.03
- Sorting Networks (Daniel Stutzbach): 111,68
- Sortieren von Netzwerken (Paul R): 66,36
- Sortieren von Netzwerken 12 mit schnellem Austausch: 58,86
- Sorting Networks 12 reordered Swap: 53.74
- Sorting Networks 12 neu angeordnet Simple Swap: 31.54
- Neu geordnetes Sortiernetzwerk mit schnellem Austausch: 31.54
- Neu geordnetes Sortiernetzwerk mit schnellem Tausch V2: 33.63
- Inlined Bubble Sort (Paolo Bonzini): 48,85
- Abgerollte Einfügungssortierung (Paolo Bonzini): 75,30
Linux 64 Bit, gcc 4.6.1 64 Bit, Intel Core 2 Duo E8400, -O1
- Direkter Aufruf der qsort-Bibliotheksfunktion: 705.93
- Naive Implementierung (Einfügesortierung): 135,60
- Einfügungssortierung (Daniel Stutzbach): 142.11
- Einfügungssortierung Abgerollt: 126,75
- Rangfolge: 46,42
- Rangfolge mit Registern: 43,58
- Sorting Networks (Daniel Stutzbach): 115,57
- Sortieren von Netzwerken (Paul R): 64,44
- Sortieren von Netzwerken 12 mit schnellem Austausch: 61,98
- Sorting Networks 12 reordered Swap: 54.67
- Sorting Networks 12 neu angeordnet Simple Swap: 31.54
- Neu geordnetes Sortiernetzwerk mit schnellem Austausch: 31.24
- Neu geordnetes Sortiernetzwerk mit schnellem Tausch V2: 33.07
- Inlined Bubble Sort (Paolo Bonzini): 45,79
- Abgerollte Einfügungssortierung (Paolo Bonzini): 80,15
Ich habe sowohl -O1- als auch -O2-Ergebnisse eingeschlossen, da O2 überraschenderweise für mehrere Programme weniger effizient ist als O1. Ich frage mich, welche spezifische Optimierung diesen Effekt hat.
Kommentare zu Lösungsvorschlägen
Einfügungssortierung (Daniel Stutzbach)
Wie erwartet ist es in der Tat eine gute Idee, Zweige zu minimieren.
Sortieren von Netzwerken (Daniel Stutzbach)
Besser als Einfügungssortierung. Ich fragte mich, ob der Haupteffekt nicht darin bestand, die externe Schleife zu umgehen. Ich habe es durch Abrollen der Einfügungssortierung versucht, um zu überprüfen, und tatsächlich erhalten wir ungefähr die gleichen Zahlen (Code ist hier ).
Netzwerke sortieren (Paul R)
Das beste bis jetzt. Der eigentliche Code, den ich zum Testen verwendet habe, ist hier . Ich weiß noch nicht, warum es fast doppelt so schnell ist wie die andere Implementierung des Sortiernetzwerks. Parameterübergabe? Schnelles Maximum?
Sortieren von Netzwerken 12 SWAP mit Fast Swap
Wie von Daniel Stutzbach vorgeschlagen, habe ich sein 12-Swap-Sortiernetzwerk mit einem branchless Fast Swap kombiniert (Code ist hier ). Es ist in der Tat schneller, das bisher beste mit einer kleinen Marge (ungefähr 5%), wie es mit 1 Swap weniger zu erwarten war.
Es ist auch interessant festzustellen, dass der branchless Swap viel (viermal) weniger effizient zu sein scheint als der einfache Swap, der in einer PPC-Architektur verwendet wird.
Aufrufen der Bibliothek qsort
Um einen weiteren Bezugspunkt zu geben, habe ich auch versucht, einfach die Bibliothek qsort aufzurufen (Code ist hier ). Wie erwartet ist es viel langsamer: 10 bis 30 Mal langsamer ... wie sich bei der neuen Testsuite herausstellte, scheint das Hauptproblem das anfängliche Laden der Bibliothek nach dem ersten Aufruf zu sein, und es ist nicht so schlecht mit anderen zu vergleichen Ausführung. Unter meinem Linux ist es nur drei- bis zwanzigmal langsamer. Bei einigen Architekturen, die von anderen für Tests verwendet werden, scheint sie sogar schneller zu sein (ich bin wirklich überrascht, da die Bibliothek qsort eine komplexere API verwendet).
Rangordnung
Rex Kerr schlug eine andere völlig andere Methode vor: Berechnen Sie für jedes Element des Arrays direkt seine endgültige Position. Dies ist effizient, da für die Berechnung der Rangfolge keine Verzweigung erforderlich ist. Der Nachteil dieser Methode besteht darin, dass das Dreifache des Speichers des Arrays benötigt wird (eine Kopie des Arrays und der Variablen zum Speichern von Rangfolgen). Die Leistungsergebnisse sind sehr überraschend (und interessant). In meiner Referenzarchitektur mit 32-Bit-Betriebssystem und Intel Core2 Quad E8300 lag die Zykluszahl leicht unter 1000 (wie beim Sortieren von Netzwerken mit Verzweigungs-Swap). Beim Kompilieren und Ausführen auf meiner 64-Bit-Box (Intel Core2 Duo) lief es jedoch viel besser: Es wurde das bisher schnellste. Ich habe endlich den wahren Grund herausgefunden. Meine 32-Bit-Box verwendet gcc 4.4.1 und meine 64-Bit-Box gcc 4.4.
Update :
Wie die oben veröffentlichten Zahlen zeigen, wurde dieser Effekt durch spätere Versionen von gcc noch verstärkt, und die Rangfolge wurde durchweg doppelt so schnell wie bei jeder anderen Alternative.
Sortieren von Netzwerken 12 mit neu angeordnetem Swap
Die erstaunliche Effizienz des Rex Kerr-Vorschlags mit gcc 4.4.3 hat mich gefragt: Wie kann ein Programm mit dreimal so viel Speicherauslastung schneller sein als verzweigungslose Sortiernetzwerke? Meine Hypothese war, dass es weniger Abhängigkeiten von der Art hatte, die nach dem Schreiben gelesen wurde, was eine bessere Verwendung des superskalaren Befehlsplaners des x86 ermöglichte. Das brachte mich auf die Idee: Swaps neu anordnen, um Lese- und Schreibabhängigkeiten zu minimieren. Einfacher ausgedrückt: Wenn Sie dies tun SWAP(1, 2); SWAP(0, 2);
, müssen Sie warten, bis der erste Austausch abgeschlossen ist, bevor Sie den zweiten ausführen, da beide auf eine gemeinsame Speicherzelle zugreifen. Wenn Sie dies tun, kann SWAP(1, 2); SWAP(4, 5);
der Prozessor beide parallel ausführen. Ich habe es versucht und es funktioniert wie erwartet, die Sortiernetzwerke laufen etwa 10% schneller.
Sortieren von Netzwerken 12 mit Simple Swap
Ein Jahr nach dem ursprünglichen Beitrag schlug Steinar H. Gunderson vor, den Compiler nicht zu überlisten und den Swap-Code einfach zu halten. Es ist in der Tat eine gute Idee, da der resultierende Code etwa 40% schneller ist! Er schlug auch einen von Hand optimierten Austausch unter Verwendung des x86-Inline-Assembly-Codes vor, der noch einige Zyklen ersparen kann. Das Überraschendste (es heißt Bände über die Psychologie des Programmierers) ist, dass vor einem Jahr keiner der Verwendeten diese Version des Austauschs ausprobiert hat. Der Code, den ich zum Testen verwendet habe, ist hier . Andere schlugen andere Möglichkeiten vor, einen C-Fast-Swap zu schreiben, aber er liefert die gleichen Leistungen wie der einfache mit einem anständigen Compiler.
Der "beste" Code lautet jetzt 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 glauben, dass unser Testsatz (und ja, es ist ziemlich schlecht, es ist nur ein Vorteil, kurz, einfach und leicht zu verstehen, was wir messen), liegt die durchschnittliche Anzahl von Zyklen des resultierenden Codes für eine Sorte unter 40 Zyklen ( 6 Tests werden ausgeführt). Damit lag jeder Swap bei durchschnittlich 4 Zyklen. Ich nenne das erstaunlich schnell. Weitere Verbesserungen möglich?
x-y
undx+y
kein Unterlauf oder Überlauf verursacht wird?__asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
dass rdtsc die Antwort in EDX: EAX ablegt, während GCC sie in einem einzelnen 64-Bit-Register erwartet. Sie können den Fehler sehen, indem Sie bei -O3 kompilieren. Siehe auch unten meinen Kommentar zu Paul R über einen schnelleren SWAP.CMP EAX, EBX; SBB EAX, EAX
setzt entweder 0 oder 0xFFFFFFFF ein,EAX
je nachdem, obEAX
es größer oder kleiner alsEBX
ist.SBB
ist "mit leihen subtrahieren", das Gegenstück zuADC
("mit Carry addieren"); Das Statusbit, auf das Sie sich beziehen, ist das Übertragsbit. Andererseits erinnere ich mich daranADC
undSBB
hatte eine schreckliche Latenz und einen schrecklichen Durchsatz auf dem Pentium 4 im Vergleich zuADD
undSUB
und war auf Core-CPUs immer noch doppelt so langsam. Seit dem 80386 gibt es auch Anweisungen zumSETcc
bedingten Speichern und zumCMOVcc
bedingten Verschieben, aber sie sind auch langsam.Antworten:
Für jede Optimierung ist es immer am besten zu testen, zu testen, zu testen. Ich würde versuchen, zumindest Netzwerke zu sortieren und Einfügungen zu sortieren. Wenn ich wetten würde, würde ich mein Geld auf die Einfügungssortierung setzen, basierend auf früheren Erfahrungen.
Wissen Sie etwas über die Eingabedaten? Einige Algorithmen arbeiten mit bestimmten Arten von Daten besser. Beispielsweise ist die Einfügesortierung bei sortierten oder fast sortierten Daten besser, sodass sie die bessere Wahl ist, wenn die Wahrscheinlichkeit für fast sortierte Daten überdurchschnittlich hoch ist.
Der von Ihnen veröffentlichte Algorithmus ähnelt einer Einfügesortierung, aber es sieht so aus, als hätten Sie die Anzahl der Swaps auf Kosten weiterer Vergleiche minimiert. Vergleiche sind jedoch weitaus teurer als Swaps, da Verzweigungen dazu führen können, dass die Anweisungspipeline blockiert.
Hier ist eine Implementierung zum Einfügen von Sortierungen:
So würde ich ein Sortiernetzwerk aufbauen. Verwenden Sie diese Site zunächst , um einen minimalen Satz von SWAP-Makros für ein Netzwerk mit der entsprechenden Länge zu generieren. Wenn ich das in eine Funktion packe, habe ich:
quelle
n < SMALL_CONSTANT
.Hier ist eine Implementierung mit Sortiernetzwerken :
Sie benötigen dafür wirklich sehr effiziente Verzweigungs-
min
undmax
Implementierungen, da dies genau das ist, worauf sich dieser Code beschränkt - eine Folge vonmin
undmax
Operationen (jeweils 13 von insgesamt). Ich überlasse dies dem Leser als Übung.Beachten Sie, dass sich diese Implementierung leicht für die Vektorisierung eignet (z. B. SIMD - die meisten SIMD-ISAs haben Vektor-Min / Max-Anweisungen) und auch für GPU-Implementierungen (z. B. CUDA - da keine Verzweigung vorliegt, gibt es keine Probleme mit Warp-Divergenz usw.).
Siehe auch: Schnelle Implementierung des Algorithmus zum Sortieren sehr kleiner Listen
quelle
Sort3
wäre schneller (auf den meisten Architekturen jedenfalls), wenn Sie feststellen würden, dass dies(a+b+c)-(min+max)
die zentrale Nummer ist.#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
. Hier verwende ich nicht ?: Für d [y], weil es etwas schlechtere Leistung gibt, aber es ist fast im Rauschen.Da es sich um Ganzzahlen handelt und Vergleiche schnell sind, können Sie die Rangfolge der einzelnen Zahlen direkt berechnen:
quelle
0+1+2+3+4+5=15
Da einer von ihnen fehlt, ergibt 15 minus der Summe der restlichen einen fehlendenSieht so aus, als wäre ich ein Jahr zu spät zur Party gekommen, aber los geht's ...
Bei der Betrachtung der von gcc 4.5.2 generierten Baugruppe habe ich festgestellt, dass für jeden Austausch Ladevorgänge und Speicher ausgeführt werden, was wirklich nicht erforderlich ist. Es ist besser, die 6 Werte in Register zu laden, diese zu sortieren und wieder im Speicher zu speichern. Ich habe angeordnet, dass die Ladungen in den Geschäften so nah wie möglich an den Registern sind, die zuerst benötigt und zuletzt verwendet werden. Ich habe auch das SWAP-Makro von Steinar H. Gunderson verwendet. Update: Ich habe zu Paolo Bonzinis SWAP-Makro gewechselt, das gcc in etwas Ähnliches wie Gundersons konvertiert, aber gcc kann die Anweisungen besser ordnen, da sie nicht als explizite Assembly angegeben werden.
Ich habe die gleiche Swap-Reihenfolge verwendet wie das neu geordnete Swap-Netzwerk, das als die beste Leistung angegeben wurde, obwohl es möglicherweise eine bessere Reihenfolge gibt. Wenn ich mehr Zeit finde, werde ich eine Reihe von Permutationen generieren und testen.
Ich habe den Testcode geändert, um über 4000 Arrays zu berücksichtigen und die durchschnittliche Anzahl von Zyklen anzuzeigen, die zum Sortieren der einzelnen Arrays erforderlich sind. Auf einem i5-650 erhalte ich ~ 34,1 Zyklen / Sortierung (mit -O3), verglichen mit dem ursprünglich neu geordneten Sortiernetzwerk mit ~ 65,3 Zyklen / Sortierung (mit -O1, Beats -O2 und -O3).
Ich habe die Testsuite geändert, um auch Uhren pro Sortierung zu melden und weitere Tests auszuführen (die cmp-Funktion wurde aktualisiert, um auch den Ganzzahlüberlauf zu verarbeiten). Hier sind die Ergebnisse für einige verschiedene Architekturen. Ich habe versucht, auf einer AMD-CPU zu testen, aber rdtsc ist auf dem verfügbaren X6 1100T nicht zuverlässig.
quelle
-O3
Optimierung möglicherweise nicht kontraproduktiv.#define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }
.Ich bin vor einigen Tagen auf diese Frage von Google gestoßen, weil ich auch schnell ein Array mit fester Länge von 6 Ganzzahlen sortieren musste. In meinem Fall sind meine ganzen Zahlen jedoch nur 8 Bit (statt 32) und ich habe nicht die strikte Anforderung, nur C zu verwenden. Ich dachte, ich würde meine Ergebnisse trotzdem teilen, falls sie für jemanden hilfreich sein könnten ...
Ich habe eine Variante einer Netzwerksortierung in Assembly implementiert, die SSE verwendet, um die Vergleichs- und Auslagerungsoperationen so weit wie möglich zu vektorisieren. Es dauert sechs "Durchgänge", um das Array vollständig zu sortieren. Ich habe einen neuartigen Mechanismus verwendet, um die Ergebnisse von PCMPGTB (vektorisierter Vergleich) direkt in Shuffle-Parameter für PSHUFB (vektorisierter Swap) umzuwandeln, wobei ich nur einen PADDB-Befehl (vektorisierter Zusatz) und in einigen Fällen auch einen PAND-Befehl (bitweises UND) verwendete.
Dieser Ansatz hatte auch den Nebeneffekt, a zu ergeben wahres verzweigungslose Funktion erhalten wurde. Es gibt keinerlei Sprunganweisungen.
Es scheint, dass diese Implementierung etwa 38% schneller ist als die Implementierung, die derzeit als die schnellste Option in der Frage markiert ist ("Sortieren von Netzwerken 12 mit einfachem Austausch"). Ich habe diese Implementierung geändert, um sie zu verwenden
char
während meiner Tests Array-Elemente verwendet werden, um den Vergleich fair zu gestalten.Ich sollte beachten, dass dieser Ansatz auf jede Arraygröße mit bis zu 16 Elementen angewendet werden kann. Ich erwarte, dass der relative Geschwindigkeitsvorteil gegenüber den Alternativen für die größeren Arrays größer wird.
Der Code ist in MASM für x86_64-Prozessoren mit SSSE3 geschrieben. Die Funktion verwendet die "neue" Windows x64-Aufrufkonvention. Hier ist es...
Sie können dies mit einem ausführbaren Objekt kompilieren und mit Ihrem C-Projekt verknüpfen. Anweisungen dazu in Visual Studio finden Sie in diesem Artikel . Sie können den folgenden C-Prototyp verwenden, um die Funktion aus Ihrem C-Code aufzurufen:
quelle
pxor / pinsrd xmm4, mem, 0
Verwendenmovd
Sie stattdessen einfach !Der Testcode ist ziemlich schlecht; es läuft über das anfängliche Array (lesen die Leute hier keine Compiler-Warnungen?), das printf druckt die falschen Elemente aus, es verwendet .byte für rdtsc ohne guten Grund, es gibt nur einen Lauf (!), es gibt nichts, was das überprüft Die Endergebnisse sind tatsächlich korrekt (es ist also sehr einfach, sie auf subtile Weise zu „optimieren“), die enthaltenen Tests sind sehr rudimentär (keine negativen Zahlen?) und nichts hindert den Compiler daran, die gesamte Funktion als toten Code zu verwerfen.
Abgesehen davon ist es auch ziemlich einfach, die bitonische Netzwerklösung zu verbessern. Ändern Sie einfach das min / max / SWAP-Zeug in
und es kommt für mich ungefähr 65% schneller heraus (Debian gcc 4.4.5 mit -O2, amd64, Core i7).
quelle
Während ich das Swap-Makro wirklich mag:
Ich sehe eine Verbesserung (die ein guter Compiler machen könnte):
Wir nehmen zur Kenntnis, wie min und max funktionieren, und ziehen den gemeinsamen Unterausdruck explizit. Dadurch werden die Min- und Max-Makros vollständig eliminiert.
quelle
d[x]
anstattx
(gleich füry
), undd[y] < d[x]
für die Ungleichung hier (yep, anders als der Min / Max-Code).Optimieren Sie niemals Min / Max, ohne ein Benchmarking durchzuführen und die tatsächlich vom Compiler generierte Assembly zu betrachten. Wenn ich GCC min mit Anweisungen für bedingte Bewegungen optimieren lasse, erhalte ich eine Beschleunigung von 33%:
(280 vs. 420 Zyklen im Testcode). Max tun mit ?: Ist mehr oder weniger gleich, fast verloren im Rauschen, aber das oben genannte ist etwas schneller. Dieser SWAP ist sowohl mit GCC als auch mit Clang schneller.
Compiler leisten auch hervorragende Arbeit bei der Registerzuweisung und Alias-Analyse, indem sie d [x] im Voraus effektiv in lokale Variablen verschieben und erst am Ende wieder in den Speicher kopieren. In der Tat tun sie dies sogar noch besser, als wenn Sie vollständig mit lokalen Variablen (wie z
d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]
) gearbeitet hätten. Ich schreibe dies, weil Sie von einer starken Optimierung ausgehen und dennoch versuchen, den Compiler auf min / max zu überlisten. :) :)Übrigens habe ich Clang und GCC ausprobiert. Sie führen die gleiche Optimierung durch, aber aufgrund von Planungsunterschieden variieren die Ergebnisse der beiden. Sie können nicht wirklich sagen, was schneller oder langsamer ist. GCC ist in den Sortiernetzwerken schneller, Clang in den quadratischen Sortierungen.
Der Vollständigkeit halber sind auch Abroll- und Einfügesortierungen möglich. Hier ist die Blasensorte:
und hier ist die Einfügungssorte:
Diese Einfügungssortierung ist schneller als die von Daniel Stutzbach und eignet sich besonders für eine GPU oder einen Computer mit Prädikation, da ITER mit nur 3 Anweisungen ausgeführt werden kann (gegenüber 4 für SWAP). Zum Beispiel ist hier die
t = d[2]; ITER(1); ITER(0);
Zeile in der ARM-Assembly:Für sechs Elemente ist die Einfügesortierung mit dem Sortiernetzwerk konkurrenzfähig (12 Swaps vs. 15 Iterationen gleichen 4 Anweisungen / Swap vs. 3 Anweisungen / Iteration aus); Blase Art ist natürlich langsamer. Aber es wird nicht wahr sein, wenn die Größe wächst, da die Einfügesortierung O (n ^ 2) ist, während die Sortiernetzwerke O (n log n) sind.
quelle
Ich habe die Testsuite auf einen Computer mit PPC-Architektur portiert, den ich nicht identifizieren kann (ich musste keinen Code berühren, nur die Iterationen des Tests erhöhen, 8 Testfälle verwenden, um zu vermeiden, dass die Ergebnisse durch Mods verschmutzt werden, und den x86-spezifischen rdtsc ersetzen):
Direkter Aufruf der qsort-Bibliotheksfunktion : 101
Naive Implementierung (Einfügesortierung) : 299
Einfügungssortierung (Daniel Stutzbach) : 108
Insertion Sort Unrolled : 51
Sortieren von Netzwerken (Daniel Stutzbach) : 26
Sortieren von Netzwerken (Paul R) : 85
Sortieren von Netzwerken 12 mit Fast Swap : 117
Sorting Networks 12 neu geordnet Swap : 116
Rangfolge : 56
quelle
subfc r5,r4,r3; subfe r6,r6,r6; andc r6,r5,r6; add r4,r6,r4; subf r3,r6,r3
. r3 / r4 sind Eingänge, r5 / r6 sind Scratch-Register, am Ausgang erhält r3 die min und r4 die max. Es sollte anständig von Hand planbar sein. Ich fand es mit dem GNU-Superoptimierer, beginnend mit Min- und Max-Sequenzen mit 4 Anweisungen und manuell manuell nach zwei, die kombiniert werden konnten. Bei signierten Eingaben können Sie natürlich allen Elementen am Anfang 0x80000000 hinzufügen und am Ende erneut subtrahieren und dann so arbeiten, als wären sie nicht signiert.Ein XOR-Swap kann bei Ihren Swap-Funktionen hilfreich sein.
Das if kann zu großen Abweichungen in Ihrem Code führen. Wenn Sie jedoch die Garantie haben, dass alle Ihre Ints eindeutig sind, kann dies nützlich sein.
quelle
x
undy
zeigen Sie auf den gleichen Ort.Ich freue mich darauf, mich daran zu versuchen und aus diesen Beispielen zu lernen, aber zuerst einige Timings von meinem 1,5-GHz-PPC-Powerbook G4 mit 1 GB DDR-RAM. (Ich habe mir einen ähnlichen rdtsc-ähnlichen Timer für PPC von ausgeliehen http://www.mcs.anl.gov/~kazutomo/rdtsc.html für die Timings ausgeliehen.) Ich habe das Programm einige Male ausgeführt und die absoluten Ergebnisse waren unterschiedlich, aber die konsistent Der schnellste Test war "Insertion Sort (Daniel Stutzbach)", gefolgt von "Insertion Sort Unrolled".
Hier ist die letzte Zeit:
quelle
Hier ist mein Beitrag zu diesem Thread: Eine optimierte Shellsortierung mit 1,4 Lücken für einen 6-gliedrigen int-Vektor (valp) mit eindeutigen Werten.
Auf meinem HP dv7-3010so Laptop mit einem Dual-Core Athlon M300 @ 2 Ghz (DDR2-Speicher) wird er in 165 Taktzyklen ausgeführt. Dies ist ein Durchschnitt, der aus dem Timing jeder einzelnen Sequenz berechnet wird (insgesamt 6! / 720). Mit OpenWatcom 1.8 zu Win32 kompiliert. Die Schleife ist im Wesentlichen eine Einfügesortierung und ist 16 Anweisungen / 37 Bytes lang.
Ich habe keine 64-Bit-Umgebung zum Kompilieren.
quelle
Wenn die Einfügungssortierung hier einigermaßen wettbewerbsfähig ist, würde ich empfehlen, eine Shellsortierung zu versuchen. Ich fürchte, 6 Elemente sind wahrscheinlich zu wenig, um zu den besten zu gehören, aber es könnte einen Versuch wert sein.
Beispielcode, ungetestet, nicht debuggt usw. Sie möchten die Sequenzen inc = 4 und inc - = 3 optimieren, um das Optimum zu finden (versuchen Sie beispielsweise inc = 2, inc - = 1).
Ich denke nicht, dass dies gewinnen wird, aber wenn jemand eine Frage zum Sortieren von 10 Elementen stellt, wer weiß ...
Laut Wikipedia kann dies sogar mit Sortiernetzwerken kombiniert werden: Pratt, V (1979). Shellsort- und Sortiernetzwerke (Hervorragende Dissertationen in den Informatikwissenschaften). Girlande. ISBN 0-824-04406-1
quelle
Ich weiß, dass ich sehr spät dran bin, aber ich war daran interessiert, mit verschiedenen Lösungen zu experimentieren. Zuerst habe ich diese Paste bereinigt, kompiliert und in ein Repository gestellt. Ich habe einige unerwünschte Lösungen als Sackgassen beibehalten, damit andere es nicht versuchen. Darunter war meine erste Lösung, die versuchte sicherzustellen, dass x1> x2 einmal berechnet wurde. Nach der Optimierung ist es nicht schneller als die anderen einfachen Versionen.
Ich habe eine Schleifenversion der Sortierung nach Rangfolge hinzugefügt, da meine eigene Anwendung dieser Studie das Sortieren von 2-8 Elementen ist. Da es also eine variable Anzahl von Argumenten gibt, ist eine Schleife erforderlich. Aus diesem Grund habe ich auch die Sortiernetzwerklösungen ignoriert.
Der Testcode hat nicht getestet, ob Duplikate korrekt behandelt wurden. Obwohl alle vorhandenen Lösungen korrekt waren, habe ich dem Testcode einen Sonderfall hinzugefügt, um sicherzustellen, dass Duplikate korrekt behandelt wurden.
Dann habe ich eine Einfügesortierung geschrieben, die vollständig in AVX-Registern enthalten ist. Auf meinem Computer ist es 25% schneller als die anderen Einfügungsarten, aber 100% langsamer als die Rangfolge. Ich habe dies nur zu Versuchszwecken gemacht und hatte keine Erwartung, dass dies aufgrund der Verzweigung in der Einfügesorte besser ist.
Dann habe ich mit AVX eine Rangfolge-Sortierung geschrieben. Dies entspricht der Geschwindigkeit der anderen Rangordnungslösungen, ist jedoch nicht schneller. Das Problem hierbei ist, dass ich die Indizes nur mit AVX berechnen kann und dann eine Tabelle mit Indizes erstellen muss. Dies liegt daran, dass die Berechnung eher zielbasiert als quellenbasiert ist. Siehe Konvertieren von quellenbasierten Indizes in zielbasierte Indizes
Das Repo finden Sie hier: https://github.com/eyepatchParrot/sort6/
quelle
vmovmskps
ganzzahlige Vektoren verwenden (mit einem Cast, um die Intrinsics zufrieden zu stellen), ohne dasffs
Ergebnis von bitscan ( ) nach rechts verschieben zu müssen .cmpgt
Ergebnis bedingt hinzufügen, indem Sie es subtrahieren , anstatt es mit zu maskierenset1(1)
. zBindex = _mm256_sub_epi32(index, gt)
tutindex -= -1 or 0;
eq = _mm256_insert_epi32(eq, 0, I)
ist keine effiziente Möglichkeit, ein Element auf Null zu setzen, wenn es wie geschrieben kompiliert wird (insbesondere für Elemente außerhalb der niedrigen 4, davpinsrd
es nur mit einem XMM-Ziel verfügbar ist; Indizes über 3 müssen emuliert werden). Stattdessen_mm256_blend_epi32
(vpblendd
) mit einem Nullvektor.vpblendd
ist ein Single-UOP-Befehl, der auf jedem Port ausgeführt wird, im Gegensatz zu einem Shuffle, der Port 5 auf Intel-CPUs benötigt. ( agner.org/optimize ).rot
Vektoren mit unterschiedlichen Mischvorgängen aus derselben Quelle zu generieren oder mindestens zwei Dep-Ketten parallel auszuführen, die Sie abwechselnd verwenden, anstatt einer einzelnen Dep-Kette durch ein Lane-Crossing-Shuffle (3-Zyklus-Latenz). Dadurch wird der ILP innerhalb einer einzigen Sorte erhöht. 2 dep-Ketten begrenzen die Anzahl der Vektorkonstanten auf eine vernünftige Anzahl, nur 2: 1 für eine Umdrehung und eine für 2 Umdrehungsschritte zusammen.Diese Frage wird ziemlich alt, aber ich musste heutzutage tatsächlich das gleiche Problem lösen: schnelle Agorithmen, um kleine Arrays zu sortieren. Ich dachte, es wäre eine gute Idee, mein Wissen zu teilen. Während ich anfing, Sortiernetzwerke zu verwenden, gelang es mir schließlich, andere Algorithmen zu finden, bei denen die Gesamtzahl der Vergleiche, die zum Sortieren jeder Permutation von 6 Werten durchgeführt wurden, geringer war als bei Sortiernetzwerken und kleiner als bei der Einfügungssortierung. Ich habe die Anzahl der Swaps nicht gezählt. Ich würde erwarten, dass es ungefähr gleichwertig ist (manchmal vielleicht etwas höher).
Der Algorithmus
sort6
verwendet den Algorithmus,sort4
der den Algorithmus verwendetsort3
. Hier ist die Implementierung in einer leichten C ++ - Form (das Original ist vorlagenlastig, sodass es mit jedem Iterator mit wahlfreiem Zugriff und jeder geeigneten Vergleichsfunktion funktionieren kann).3 Werte sortieren
Der folgende Algorithmus ist eine nicht gerollte Einfügesortierung. Wenn zwei Swaps (6 Zuweisungen) ausgeführt werden müssen, werden stattdessen 4 Zuweisungen verwendet:
Es sieht etwas komplex aus, da die Sortierung für jede mögliche Permutation des Arrays mehr oder weniger einen Zweig hat, wobei 2 bis 3 Vergleiche und höchstens 4 Zuweisungen zum Sortieren der drei Werte verwendet werden.
4 Werte sortieren
Dieser Aufruf
sort3
führt dann eine nicht gerollte Einfügesortierung mit dem letzten Element des Arrays durch:Dieser Algorithmus führt 3 bis 6 Vergleiche und höchstens 5 Swaps durch. Es ist einfach, eine Einfügesortierung abzuwickeln, aber wir werden einen anderen Algorithmus für die letzte Sortierung verwenden ...
6 Werte sortieren
Dieser verwendet eine ungerollte Version einer sogenannten doppelten Einfügungssortierung . Der Name ist nicht so toll, aber er ist ziemlich beschreibend. So funktioniert es:
Nach dem Tausch ist das erste Element immer kleiner als das letzte, was bedeutet, dass beim Einfügen in die sortierte Sequenz nicht mehr als N Vergleiche durchgeführt werden, um die beiden Elemente im schlimmsten Fall einzufügen: Zum Beispiel, wenn das Das erste Element wurde an der 3. Position eingefügt, das letzte kann nicht tiefer als an der 4. Position eingefügt werden.
Meine Tests für jede Permutation von 6 Werten zeigen jemals, dass dieser Algorithmus immer zwischen 6 und 13 Vergleiche durchführt. Ich habe die Anzahl der durchgeführten Swaps nicht berechnet, aber ich erwarte nicht, dass sie im schlimmsten Fall höher als 11 ist.
Ich hoffe, dass dies hilft, auch wenn diese Frage kein tatsächliches Problem mehr darstellt :)
BEARBEITEN: Nach dem Einfügen in den bereitgestellten Benchmark ist es deutlich langsamer als die meisten interessanten Alternativen. Es ist in der Regel etwas leistungsfähiger als das Abrollen, aber das war's auch schon. Grundsätzlich ist es nicht die beste Sortierung für Ganzzahlen, könnte aber für Typen mit einer teuren Vergleichsoperation interessant sein.
quelle
operator<
für den Vergleich verwende. Neben der objektiven Anzahl von Vergleichen und Swaps habe ich auch meine Algorithmen richtig zeitlich abgestimmt. Diese Lösung war die schnellste generische, aber ich habe tatsächlich die von @ RexKerr verpasst.-O3
. Ich denke, ich werde dann eine andere Strategie für meine Sortierbibliothek anwenden: Bereitstellung von drei Arten von Algorithmen, um entweder eine geringe Anzahl von Vergleichen, eine geringe Anzahl von Swaps oder möglicherweise die beste Leistung zu erzielen. Zumindest ist das, was passiert, für den Leser transparent. Vielen Dank für Ihre Erkenntnisse :)Ich glaube, Ihre Frage besteht aus zwei Teilen.
Ich würde mir keine Sorgen um das Entleeren von Pipelines machen (unter der Annahme von aktuellem x86): Die Vorhersage von Zweigen hat einen langen Weg zurückgelegt. Ich würde mir Sorgen machen, dass der Code und die Daten jeweils in eine Cache-Zeile passen (vielleicht zwei für den Code). Sobald die Abruflatenzen erreicht sind, sind sie erfrischend niedrig, wodurch ein Stillstand ausgeglichen wird. Dies bedeutet auch, dass Ihre innere Schleife möglicherweise aus zehn Anweisungen besteht, genau dort, wo sie sein sollte (in meinem Sortieralgorithmus gibt es zwei verschiedene innere Schleifen, sie sind 10 Anweisungen / 22 Bytes bzw. 9/22 lang). Angenommen, der Code enthält keine Divs, können Sie sicher sein, dass er unglaublich schnell ist.
quelle
Ich weiß, das ist eine alte Frage.
Aber ich habe gerade eine andere Art von Lösung geschrieben, die ich teilen möchte.
Verwenden Sie nur verschachtelten MIN MAX,
Es ist nicht schnell, da es jeweils 114 verwendet,
könnte es ganz einfach auf 75 reduzieren -> Pastebin
Aber dann ist es nicht mehr nur min max.
Was möglicherweise funktioniert, ist, mit AVX min / max für mehrere Ganzzahlen gleichzeitig auszuführen
PMINSW-Referenz
EDIT:
Rangordnungslösung, inspiriert von Rex Kerrs, viel schneller als das Chaos oben
quelle
int16_t
). Ihre C-Funktion behauptet jedoch, dass sie ein Array von sortiertint
(was in allen C-Implementierungen, die dieseasm
Syntax unterstützen, 32-Bit ist ). Haben Sie es mit nur kleinen positiven ganzen Zahlen getestet, die nur 0 in ihrer hohen Hälfte haben? Das wird funktionieren ... Fürint
Sie benötigen SSE4.1pmin/maxsd
(d = dword). felixcloutier.com/x86/pminsd:pminsq oderpminusd
füruint32_t
.Ich fand, dass zumindest auf meinem System die Funktionen
sort6_iterator()
undsort6_iterator_local()
unterhalb sowohl RAN definierte mindestens so schnell und häufig deutlich schneller, als der über die aktuellen Rekordhalter:Ich habe diese Funktion als
std::vector
Iterator in meinem Timing-Code übergeben.Ich vermute (aus Kommentaren wie diesem und anderswo), dass die Verwendung von Iteratoren g ++ bestimmte Zusicherungen darüber gibt, was mit dem Speicher, auf den sich der Iterator bezieht, geschehen kann und was nicht, und es sind diese Zusicherungen, die es g ++ ermöglichen Optimieren Sie den Sortiercode besser (z. B. bei Zeigern kann der Compiler nicht sicher sein, dass alle Zeiger auf unterschiedliche Speicherorte zeigen). Wenn ich mich richtig erinnere, ist dies auch einen Teil des Grundes , warum so viele STL - Algorithmen, wie zum Beispiel
std::sort()
, im Allgemeinen eine so obszön gute Leistung haben.Außerdem,
sort6_iterator()
wird einige Male (wiederum abhängig vom Kontext, in dem die Funktion aufgerufen wird) durch die folgende Sortierfunktion, die die Daten vor dem Sortieren in lokale Variablen kopiert, konsistent übertroffen. 1 Beachten Sie, dass, da nur 6 lokale Variablen definiert sind, diese lokalen Variablen, wenn sie Grundelemente sind, wahrscheinlich nie tatsächlich im RAM gespeichert werden und stattdessen immer nur bis zum Ende des Funktionsaufrufs in den Registern der CPU gespeichert werden, was diese Sortierung erleichtert Funktion schnell. (Es hilft auch, dass der Compiler weiß, dass bestimmte lokale Variablen unterschiedliche Speicherorte im Speicher haben.)Beachten Sie das Definieren
SWAP()
wie folgt einige Male ergibt eine etwas bessere Leistung , obwohl die meiste Zeit in etwas schlechter Leistung oder einen vernachlässigbaren Unterschied in der Leistung führt.Wenn Sie nur einen Sortieralgorithmus für primitive Datentypen wünschen, kann gcc -O3 durchweg gut optimieren, unabhängig davon, in welchem Kontext der Aufruf der Sortierfunktion angezeigt wird 1 wird. Je nachdem, wie Sie die Eingabe übergeben, versuchen Sie einen der folgenden beiden Algorithmen:
Oder wenn Sie die Variablen als Referenz übergeben möchten, verwenden Sie diese (die folgende Funktion unterscheidet sich von der obigen in den ersten 5 Zeilen):
Der Grund für die Verwendung der
register
Schlüsselworts liegt darin, dass Sie nur selten wissen, dass Sie diese Werte in Registern verwenden möchten. Ohneregister
wird der Compiler dies die meiste Zeit herausfinden, aber manchmal nicht. Verwendung derregister
Schlüsselworts hilft bei der Lösung dieses Problems. Normalerweise verwenden Sie dasregister
Schlüsselwort jedoch nicht, da es Ihren Code eher verlangsamt als beschleunigt.Beachten Sie auch die Verwendung von Vorlagen. Dies geschieht absichtlich, da auch mit dem
inline
Schlüsselwort Vorlagenfunktionen von gcc im Allgemeinen viel aggressiver optimiert werden als Vanille-C-Funktionen (dies hat damit zu tun, dass gcc Funktionszeiger für Vanille-C-Funktionen behandeln muss, jedoch nicht mit Vorlagenfunktionen).quelle
Versuchen Sie, die sortierte Liste zusammenzuführen. :) Verwenden Sie zwei Arrays. Am schnellsten für kleine und große Arrays.
Wenn Sie konzernieren, überprüfen Sie nur, wo einfügen. Andere größere Werte, die Sie nicht vergleichen müssen (cmp = ab> 0).
Für 4 Zahlen können Sie das System 4-5 cmp (~ 4,6) oder 3-6 cmp (~ 4,9) verwenden. Blasensortierung mit 6 cmp (6). Viel cmp für langsameren Code mit großen Zahlen.
Dieser Code verwendet 5 cmp (keine MSL-Sortierung):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}
Prinzipielle MSL
9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8
js Code
quelle
Sortieren Sie 4 Elemente mit der Verwendung cmp == 0. Die Anzahl der cmp beträgt ~ 4,34 (FF native hat ~ 4,52), dauert jedoch dreimal so lange wie das Zusammenführen von Listen. Aber besser weniger cmp-Operationen, wenn Sie große Zahlen oder großen Text haben. Bearbeiten: Fehler behoben
Online-Test http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm
quelle
Vielleicht bin ich zu der Party zu spät, aber zumindest mein Beitrag ist ein neuer Ansatz.
swap
höher wären (dh die Kosten fürcompare
).SWAP()
zwei Elemente zu verwenden, werden die Zyklen verfolgt, wobei nur eine Temperatur und ein (Register-> Register) Swap (neu <- alt) benötigt werden.Update: Der Code wurde ein wenig geändert, einige Leute verwenden C ++ - Compiler, um C-Code zu kompilieren ...
quelle
wsort6()
Funktion hat die richtige Schnittstelle.o1..o5
ist das zweite temporäree[6]
Array nicht erforderlich . Und: C-Code auf einem C ++ - Compiler kompilieren und den Code beschuldigen?#include
. Festequelle
Nun, wenn es nur 6 Elemente sind und Sie Parallelität nutzen können, bedingte Verzweigungen minimieren möchten usw. Warum generieren Sie nicht alle Kombinationen und testen auf Ordnung? Ich würde es wagen, dass es in einigen Architekturen ziemlich schnell gehen kann (solange Sie den Speicher vorbelegt haben)
quelle
Hier sind drei typische Sortiermethoden, die drei verschiedene Klassen von Sortieralgorithmen darstellen:
Aber schauen Sie sich die Diskussion von Stefan Nelsson über den schnellsten Sortieralgorithmus an? wo er eine Lösung bespricht, die bis hinunter geht
O(n log log n)
.. überprüfen Sie ihre Implementierung in C.Dieser semilineare Sortieralgorithmus wurde 1995 in einem Artikel vorgestellt:
A. Andersson, T. Hagerup, S. Nilsson und R. Raman. In linearer Zeit sortieren? In Proceedings of the 27. Annual ACM Symposium on the Theory of Computing, S. 427-436, 1995.
quelle