Schnellste Art von 6 int Array mit fester Länge

401

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?

kriss
quelle
2
Haben Sie einige Einschränkungen für die Ints? Können wir zum Beispiel annehmen, dass für 2 x, y x-yund x+ykein Unterlauf oder Überlauf verursacht wird?
Matthieu M.
3
Sie sollten versuchen, mein 12-Swap-Sortiernetzwerk mit Pauls branchless Swap-Funktion zu kombinieren. Seine Lösung übergibt alle Parameter als separate Elemente auf dem Stapel anstelle eines einzelnen Zeigers auf ein Array. Das könnte auch einen Unterschied machen.
Daniel Stutzbach
2
Beachten Sie, dass die korrekte Implementierung von rdtsc auf 64-Bit darin besteht, __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.
Paolo Bonzini
3
@ Tyler: Wie implementiert man es auf Assembly-Ebene ohne Verzweigung?
Loren Pechtel
4
@Loren: CMP EAX, EBX; SBB EAX, EAXsetzt entweder 0 oder 0xFFFFFFFF ein, EAXje nachdem, ob EAXes größer oder kleiner als EBXist. SBBist "mit leihen subtrahieren", das Gegenstück zu ADC("mit Carry addieren"); Das Statusbit, auf das Sie sich beziehen, ist das Übertragsbit. Andererseits erinnere ich mich daran ADCund SBBhatte eine schreckliche Latenz und einen schrecklichen Durchsatz auf dem Pentium 4 im Vergleich zu ADDund SUBund war auf Core-CPUs immer noch doppelt so langsam. Seit dem 80386 gibt es auch Anweisungen zum SETccbedingten Speichern und zum CMOVccbedingten Verschieben, aber sie sind auch langsam.
j_random_hacker

Antworten:

162

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:

static __inline__ int sort6(int *d){
        int i, j;
        for (i = 1; i < 6; i++) {
                int tmp = d[i];
                for (j = i; j >= 1 && tmp < d[j-1]; j--)
                        d[j] = d[j-1];
                d[j] = tmp;
        }
}

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:

static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}
Daniel Stutzbach
quelle
9
+1: Schön, Sie haben es mit 12 Austauschen gemacht, anstatt mit den 13 in meinem handcodierten und empirisch abgeleiteten Netzwerk oben. Ich würde Ihnen eine weitere +1 geben, wenn ich den Link zu der Site könnte, die Netzwerke für Sie generiert - jetzt mit einem Lesezeichen versehen.
Paul R
9
Dies ist eine fantastische Idee für eine allgemeine Sortierfunktion, wenn Sie erwarten, dass die meisten Anforderungen kleine Arrays sind. Verwenden Sie mit diesem Verfahren eine switch-Anweisung für die Fälle, die Sie optimieren möchten. Lassen Sie den Standardfall eine Bibliothekssortierfunktion verwenden.
Mark Ransom
5
@Mark Eine gute Funktion zum Sortieren von Bibliotheken verfügt bereits über einen schnellen Pfad für kleine Arrays. Viele moderne Bibliotheken verwenden einen rekursiven QuickSort oder MergeSort, der nach dem Rekursieren auf zu InsertionSort wechselt n < SMALL_CONSTANT.
Daniel Stutzbach
3
@Mark Nun, eine C-Bibliotheks-Sortierfunktion erfordert, dass Sie die Vergleichsoperation über einen Funktionsportier angeben. Der Aufwand für das Aufrufen einer Funktion für jeden Vergleich ist enorm. Normalerweise ist dies immer noch der sauberste Weg, da dies selten ein kritischer Pfad im Programm ist. Wenn es sich jedoch um den kritischen Pfad handelt, können wir wirklich viel schneller sortieren, wenn wir wissen, dass wir Ganzzahlen und genau 6 davon sortieren. :)
Daniel Stutzbach
7
@tgwh: XOR-Tausch ist fast immer eine schlechte Idee.
Paul R
63

Hier ist eine Implementierung mit Sortiernetzwerken :

inline void Sort2(int *p0, int *p1)
{
    const int temp = min(*p0, *p1);
    *p1 = max(*p0, *p1);
    *p0 = temp;
}

inline void Sort3(int *p0, int *p1, int *p2)
{
    Sort2(p0, p1);
    Sort2(p1, p2);
    Sort2(p0, p1);
}

inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  
}

inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
    Sort3(p0, p1, p2);
    Sort3(p3, p4, p5);
    Sort2(p0, p3);  
    Sort2(p2, p5);  
    Sort4(p1, p2, p3, p4);  
}

Sie benötigen dafür wirklich sehr effiziente Verzweigungs- minund maxImplementierungen, da dies genau das ist, worauf sich dieser Code beschränkt - eine Folge von minund maxOperationen (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

Paul R.
quelle
1
Für ein paar
kleine
1
@Paul: Im realen CUDA-Nutzungskontext ist es sicherlich die beste Antwort. Ich werde prüfen, ob es auch (und wie viel) im Golf x64-Kontext ist und das Ergebnis veröffentlichen.
Kriss
1
Sort3wäre schneller (auf den meisten Architekturen jedenfalls), wenn Sie feststellen würden, dass dies (a+b+c)-(min+max)die zentrale Nummer ist.
Rex Kerr
1
@ Rex: Ich verstehe - das sieht gut aus. Für SIMD-Architekturen wie AltiVec und SSE wäre es die gleiche Anzahl von Befehlszyklen (max und min sind Einzelzyklusbefehle wie Addieren / Subtrahieren), aber für eine normale skalare CPU sieht Ihre Methode besser aus.
Paul R
2
Wenn ich GCC min mit Anweisungen für bedingte Bewegungen optimieren lasse, erhalte ich eine Beschleunigung von 33% : #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.
Paolo Bonzini
45

Da es sich um Ganzzahlen handelt und Vergleiche schnell sind, können Sie die Rangfolge der einzelnen Zahlen direkt berechnen:

inline void sort6(int *d) {
  int e[6];
  memcpy(e,d,6*sizeof(int));
  int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  int o5 = 15-(o0+o1+o2+o3+o4);
  d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}
Rex Kerr
quelle
@ Rex: mit gcc -O1 sind es weniger als 1000 Zyklen, ziemlich schnell, aber langsamer als das Sortieren des Netzwerks. Irgendeine Idee, Code zu verbessern? Vielleicht, wenn wir Array-Kopie vermeiden könnten ...
kriss
@kriss: Mit -O2 ist es für mich schneller als das Sortiernetzwerk. Gibt es einen Grund, warum -O2 nicht in Ordnung ist, oder ist es für Sie auf -O2 auch langsamer? Vielleicht ist es ein Unterschied in der Maschinenarchitektur?
Rex Kerr
1
@ Rex: Entschuldigung, ich habe das Muster> vs> = auf den ersten Blick verpasst. Es funktioniert in jedem Fall.
kriss
3
@kriss: Aha. Das ist nicht ganz überraschend - es gibt viele Variablen, die herumschweben, und sie müssen sorgfältig geordnet und in Registern usw. zwischengespeichert werden.
Rex Kerr
2
@SSpoke 0+1+2+3+4+5=15Da einer von ihnen fehlt, ergibt 15 minus der Summe der restlichen einen fehlenden
Glenn Teitelbaum
35

Sieht 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).

#include <stdio.h>

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}

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.

Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02
Kevin Stock
quelle
Ihre Idee von Registervariablen sollte auf Rex Kerrs "Rank Order" -Lösung angewendet werden. Das sollte am schnellsten sein, und dann ist die -O3Optimierung möglicherweise nicht kontraproduktiv.
cdunn2001
1
@ cdunn2001 Ich habe es gerade getestet, ich sehe keine Verbesserung (außer ein paar Zyklen bei -O0 und -Os). Wenn man sich den asm ansieht, scheint es gcc bereits gelungen zu sein, Register zu verwenden und den Aufruf von memcpy zu eliminieren.
Kevin Stock
Würde es Ihnen etwas ausmachen, die einfache Swap-Version zu Ihrer Testsuite hinzuzufügen, könnte es interessant sein, sie mit dem von Hand optimierten schnellen Swap für die Montage zu vergleichen.
kriss
1
Ihr Code verwendet immer noch Gundersons Tausch, meiner wäre #define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }.
Paolo Bonzini
@Paolo Bonzini: Ja, ich beabsichtige, einen Testfall mit Ihrem hinzuzufügen, hatte aber noch keine Zeit. Aber ich werde Inline-Montage vermeiden.
Kriss
15

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 verwendenchar 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...

PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END

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:

void simd_sort_6(char *values);
Joe Crivello
quelle
Es wäre interessant, Ihre mit anderen Vorschlägen auf Versammlungsebene zu vergleichen. Die verglichenen Implementierungsleistungen schließen sie nicht ein. Die Verwendung von SSE klingt trotzdem gut.
Kriss
Ein weiterer Bereich zukünftiger Forschung wäre die Anwendung der neuen Intel AVX-Anweisungen auf dieses Problem. Die größeren 256-Bit-Vektoren sind groß genug, um 8 DWORDs aufzunehmen.
Joe Crivello
1
pxor / pinsrd xmm4, mem, 0Verwenden movdSie stattdessen einfach !
Peter Cordes
14

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

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

und es kommt für mich ungefähr 65% schneller heraus (Debian gcc 4.4.5 mit -O2, amd64, Core i7).

Steinar H. Gunderson
quelle
OK, der Testcode ist schlecht. Fühlen Sie sich frei, es zu verbessern. Und ja, Sie können Assembler-Code verwenden. Warum nicht den ganzen Weg gehen und es mit dem x86-Assembler vollständig codieren? Es ist vielleicht etwas weniger tragbar, aber warum sollte man sich die Mühe machen?
Kriss
Vielen Dank, dass Sie den Array-Überlauf bemerkt haben. Ich habe ihn korrigiert. Andere Leute haben es möglicherweise nicht bemerkt, weil sie auf den Link zum Kopieren / Einfügen von Code geklickt haben, wo es keinen Überlauf gibt.
Kriss
4
Sie brauchen eigentlich gar keinen Assembler. Wenn Sie nur alle cleveren Tricks fallen lassen, erkennt GCC die Sequenz und fügt die bedingten Bewegungen für Sie ein: #define min (a, b) ((a <b)? a: b) #define max (a, b) ( (a <b)? b: a) # SWAP definieren (x, y) {int a = min (d [x], d [y]); int b = max (d [x], d [y]); d [x] = a; d [y] = b; } Es kommt vielleicht ein paar Prozent langsamer heraus als die Inline-Asm-Variante, aber das ist schwer zu sagen, da es an richtigem Benchmarking mangelt.
Steinar H. Gunderson
3
… Und schließlich, wenn Ihre Zahlen Floats sind und Sie sich keine Sorgen um NaN usw. machen müssen, kann GCC dies in minss / maxss SSE-Anweisungen konvertieren, was noch ~ 25% schneller ist. Moral: Lassen Sie die cleveren Bitfiddling-Tricks fallen und lassen Sie den Compiler seinen Job machen. :-)
Steinar H. Gunderson
13

Während ich das Swap-Makro wirklich mag:

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

Ich sehe eine Verbesserung (die ein guter Compiler machen könnte):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

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.

phkahler
quelle
Das bringt sie rückwärts, beachte, dass d [y] das Maximum bekommt, das x ^ ist (allgemeiner Unterausdruck).
Kevin Stock
Ich bemerkte das Gleiche; Ich denke, dass Ihre Implementierung korrekt ist, d[x]anstatt x(gleich für y), und d[y] < d[x]für die Ungleichung hier (yep, anders als der Min / Max-Code).
Tyler
Ich habe es mit Ihrem Swap versucht, aber die lokale Optimierung hat negative Auswirkungen auf größerer Ebene (ich denke, sie führt zu Abhängigkeiten). Und das Ergebnis ist langsamer als der andere Swap. Wie Sie jedoch bei der vorgeschlagenen neuen Lösung sehen können, gab es tatsächlich viel Leistung, um den Swap zu optimieren.
Kriss
12

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%:

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(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 zd0 = 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:

SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);

und hier ist die Einfügungssorte:

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

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 diet = d[2]; ITER(1); ITER(0); Zeile in der ARM-Assembly:

    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6

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.

Paolo Bonzini
quelle
1
Mehr oder weniger verwandt: Ich habe einen Bericht an GCC gesendet, damit die Optimierung direkt im Compiler implementiert werden kann. Ich bin mir nicht sicher, ob es gemacht wird, aber zumindest können Sie verfolgen, wie es sich entwickelt.
Morwenn
11

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

Jheriko
quelle
1
Wirklich interessant. Es sieht so aus, als wäre der branchless Swap eine schlechte Idee für PPC. Dies kann auch ein Compiler-Effekt sein. Welches wurde verwendet?
Kriss
Es ist ein Zweig des gcc-Compilers - die min, max-Logik ist wahrscheinlich nicht verzweigungslos - ich werde die Demontage überprüfen und Sie wissen lassen, aber es sei denn, der Compiler ist klug genug, etwas wie x <y einzuschließen, ohne dass ein if immer noch ein Zweig wird - auf x86 / x64 Der CMOV-Befehl könnte dies vermeiden, aber es gibt keinen solchen Befehl für Festpunktwerte auf PPC, sondern nur Floats. Ich könnte mich morgen damit beschäftigen und Sie wissen lassen - ich erinnere mich, dass es in der Winamp AVS-Quelle ein viel einfacheres verzweigungsloses Min / Max gab, aber es war nur für Floats - aber es könnte ein guter Anfang für einen wirklich verzweigungslosen Ansatz sein.
Jheriko
4
Hier ist ein branchless min / max für PPC mit vorzeichenlosen Eingängen : 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.
Paolo Bonzini
7

Ein XOR-Swap kann bei Ihren Swap-Funktionen hilfreich sein.

void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

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.

naj
quelle
1
xor swap funktioniert auch für gleiche Werte ... x ^ = y setzt x auf 0, y ^ = x lässt y als y (== x), x ^ = y setzt x auf y
jheriko
11
Wenn es nicht funktioniert, ist wann xund yzeigen Sie auf den gleichen Ort.
Hobbs
Bei der Verwendung mit Sortiernetzwerken rufen wir niemals an, wenn x und y auf denselben Ort zeigen. Es gibt noch einen Weg, um zu vermeiden, dass Tests durchgeführt werden, die größer sind, um den gleichen Effekt wie der branchless Swap zu erzielen. Ich habe eine Idee, um das zu erreichen.
Kriss
5

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:

**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116
Nico
quelle
4

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.

void shellsort (int *valp)
{      
  int c,a,*cp,*ip=valp,*ep=valp+5;

  c=*valp;    a=*(valp+4);if (c>a) {*valp=    a;*(valp+4)=c;}
  c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}

  cp=ip;    
  do
  {
    c=*cp;
    a=*(cp+1);
    do
    {
      if (c<a) break;

      *cp=a;
      *(cp+1)=c;
      cp-=1;
      c=*cp;
    } while (cp>=valp);
    ip+=1;
    cp=ip;
  } while (ip<ep);
}

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.

Olof Forshell
quelle
nett. Ich werde es der längeren Testsuite hinzufügen
kriss
3

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).

static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}

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

gcp
quelle
Fühlen Sie sich frei, eine Implementierung vorzuschlagen :-)
kriss
Vorschlag hinzugefügt. Genieße die Käfer.
GCP
3

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.

static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}

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

static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}

Das Repo finden Sie hier: https://github.com/eyepatchParrot/sort6/

Augenklappe
quelle
1
Sie können vmovmskpsganzzahlige Vektoren verwenden (mit einem Cast, um die Intrinsics zufrieden zu stellen), ohne das ffsErgebnis von bitscan ( ) nach rechts verschieben zu müssen .
Peter Cordes
1
Sie können 1 basierend auf einem cmpgtErgebnis bedingt hinzufügen, indem Sie es subtrahieren , anstatt es mit zu maskieren set1(1). zB index = _mm256_sub_epi32(index, gt)tutindex -= -1 or 0;
Peter Cordes
1
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, da vpinsrdes nur mit einem XMM-Ziel verfügbar ist; Indizes über 3 müssen emuliert werden). Stattdessen _mm256_blend_epi32( vpblendd) mit einem Nullvektor. vpblenddist 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 ).
Peter Cordes
1
Sie können auch in Betracht ziehen, die rotVektoren 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.
Peter Cordes
2

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 sort6verwendet den Algorithmus, sort4der den Algorithmus verwendet sort3. 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:

void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}

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 sort3führt dann eine nicht gerollte Einfügesortierung mit dem letzten Element des Arrays durch:

void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}

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:

  • Sortieren Sie alles außer dem ersten und dem letzten Element des Arrays.
  • Tauschen Sie das erste und die Elemente des Arrays aus, wenn das erste größer als das letzte ist.
  • Fügen Sie das erste Element von vorne in die sortierte Reihenfolge ein, dann das letzte Element von hinten.

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.

void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}

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.

Morwenn
quelle
Das sind nett. Da das gelöste Problem viele Jahrzehnte alt ist, wahrscheinlich so alt wie eine C-Programmierung, scheint die Frage, die jetzt fast 5 Jahre hat, nicht so relevant zu sein.
Kriss
Sie sollten sich ansehen, wie die anderen Antworten zeitlich festgelegt sind. Der Punkt ist, dass bei solch kleinen Datenmengen, die Vergleiche oder sogar Vergleiche und Swaps zählen, nicht wirklich sagt, wie schnell ein Algorithmus ist (im Grunde ist das Sortieren von 6 Zoll immer O (1), weil O (6 * 6) O (1) ist). Die derzeit schnellste der zuvor vorgeschlagenen Lösungen besteht darin, die Position jedes Werts anhand eines großen Vergleichs (von RexKerr) sofort zu ermitteln.
Kriss
@kriss Ist es jetzt das schnellste? Nach dem Lesen der Ergebnisse war der Ansatz der Sortiernetzwerke der schnellste, mein schlechter. Es ist auch wahr, dass meine Lösung aus meiner generischen Bibliothek stammt und dass ich nicht immer ganze Zahlen vergleiche oder immer 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.
Ich
Die Lösung von RexKerr (Order Rank) wurde die schnellste in der X86-Architektur seit gcc compiler 4.2.3 (und ab gcc 4.9 fast doppelt so schnell wie die zweitbeste). Es hängt jedoch stark von Compiler-Optimierungen ab und trifft möglicherweise nicht auf andere Architekturen zu.
Kriss
@kriss Das ist interessant zu wissen. Und ich könnte in der Tat wieder mehr Unterschiede mit -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 :)
Morwenn
1

Ich glaube, Ihre Frage besteht aus zwei Teilen.

  • Der erste besteht darin, den optimalen Algorithmus zu bestimmen. Dies geschieht - zumindest in diesem Fall - durch Durchlaufen jeder möglichen Reihenfolge (es gibt nicht so viele), mit der Sie die exakten Min-, Max-, Durchschnitts- und Standardabweichungen von Vergleichen und Swaps berechnen können. Halten Sie auch ein oder zwei Zweitplatzierte bereit.
  • Die zweite besteht darin, den Algorithmus zu optimieren. Es kann viel getan werden, um Lehrbuchcodebeispiele in gemeine und schlanke reale Algorithmen umzuwandeln. Wenn Sie feststellen, dass ein Algorithmus nicht im erforderlichen Umfang optimiert werden kann, versuchen Sie es mit einem zweiten Platz.

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.

Olof Forshell
quelle
Ich bin mir nicht sicher, wie ich deine Antwort verstehen soll. Zuerst verstehe ich überhaupt nicht, welchen Algorithmus Sie vorschlagen? Und wie könnte es optimal sein, wenn Sie 720 mögliche Ordnungen durchlaufen müssen (vorhandene Antworten dauern viel weniger als 720 Zyklen). Wenn Sie zufällige Eingaben haben, kann ich mir (selbst auf theoretischer Ebene) nicht vorstellen, wie die Verzweigungsvorhersage besser als 50-50 sein könnte, außer wenn es überhaupt nicht um Eingabedaten geht. Auch die meisten bereits vorgeschlagenen guten Lösungen funktionieren wahrscheinlich bereits mit Daten und Code vollständig im Cache. Aber vielleicht habe ich Ihre Antwort völlig falsch verstanden. Hast du etwas dagegen, Code zu zeigen?
Kriss
Was ich damit meinte war, dass es nur 720 (6!) Verschiedene Kombinationen von 6 ganzen Zahlen gibt und wenn Sie alle durch die Kandidatenalgorithmen laufen lassen, können Sie viele Dinge bestimmen, wie ich erwähnt habe - das ist der theoretische Teil. Der praktische Teil ist die Feinabstimmung dieses Algorithmus, um in so wenigen Taktzyklen wie möglich ausgeführt zu werden. Mein Ausgangspunkt für das Sortieren von 6 Ganzzahlen ist eine Shellsortierung mit 1, 4 Lücken. Die 4-Lücke ebnet den Weg für eine gute Verzweigungsvorhersage in der 1-Lücke.
Olof Forshell
Die 1, 4 Gap Shellsort für 6! Einzigartige Kombinationen (beginnend mit 012345 und endend mit 543210) haben den besten Fall von 7 Vergleichen und 0 Austauschen und den schlechtesten von 14 Vergleichen und 10 Austauschen. Der durchschnittliche Fall liegt bei 11,14 Vergleichen und 6 Börsen.
Olof Forshell
1
Ich bekomme keine "reguläre Zufallsverteilung" - ich teste jede mögliche Kombination und bestimme die Min / Average / Max-Statistiken. Shellsort ist eine Reihe von Einfügungsarten mit abnehmenden Inkrementen, so dass das letzte Inkrement - 1 - viel weniger Arbeit leistet, als wenn es allein wie bei einer reinen Einfügungssorte ausgeführt wird. Für die Taktzählung benötigt mein Algorithmus durchschnittlich 406 Taktzyklen. Dazu gehört das Sammeln von Statistiken und das Aufrufen der eigentlichen Sortierroutine durch zwei Aufrufe - einen für jede Lücke. Dies ist auf einem Athlon M300 Mobile, Compiler OpenWatcom.
Olof Forshell
1
"regelmäßige Zufallsverteilung" bedeutet, dass jede Kombination von tatsächlichen Daten, die sortiert wird, möglicherweise nicht die gleiche Wahrscheinlichkeit hat. Wenn nicht alle Kombinationen gleich wahrscheinlich sind, werden Ihre Statistiken gebrochen, da der Durchschnitt berücksichtigen muss, wie oft eine bestimmte Verteilung wahrscheinlich auftritt. Wenn Sie für die Uhrzeit eine andere Implementierung dieser Art ausprobieren (Links oben angegeben) und auf Ihrem Testsystem ausführen, haben wir eine Vergleichsbasis und sehen, wie gut Ihre ausgewählte Leistung ist.
kriss
1

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

#include <stdio.h>

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  int d[6][6] = {
    {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 (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}

EDIT:
Rangordnungslösung, inspiriert von Rex Kerrs, viel schneller als das Chaos oben

static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}
PrincePolka
quelle
1
immer schön neue lösungen zu sehen. Es sieht so aus, als ob eine einfache Optimierung möglich ist. Am Ende unterscheidet es sich möglicherweise nicht so sehr von Sorting Networks.
Kriss
Ja, die Anzahl von MIN und MAX könnte möglicherweise reduziert werden, zum Beispiel wiederholt sich MIN (AB, CD) einige Male, aber ich denke, es wird schwierig sein, sie stark zu reduzieren. Ich habe Ihre Testfälle hinzugefügt.
PrincePolka
pmin / maxsw arbeiten mit gepackten 16-Bit-Ganzzahlen mit Vorzeichen ( int16_t). Ihre C-Funktion behauptet jedoch, dass sie ein Array von sortiert int(was in allen C-Implementierungen, die diese asmSyntax 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ür intSie benötigen SSE4.1 pmin/maxsd(d = dword). felixcloutier.com/x86/pminsd:pminsq oder pminusdfür uint32_t.
Peter Cordes
1

Ich fand, dass zumindest auf meinem System die Funktionen sort6_iterator() und sort6_iterator_local()unterhalb sowohl RAN definierte mindestens so schnell und häufig deutlich schneller, als der über die aktuellen Rekordhalter:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + 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
}

Ich habe diese Funktion als std::vectorIterator 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 Beispielstd::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.)

template<class IterType> 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}

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.

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }

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:

template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

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):

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

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. Ohne registerwird der Compiler dies die meiste Zeit herausfinden, aber manchmal nicht. Verwendung derregister Schlüsselworts hilft bei der Lösung dieses Problems. Normalerweise verwenden Sie das registerSchlüsselwort jedoch nicht, da es Ihren Code eher verlangsamt als beschleunigt.

Beachten Sie auch die Verwendung von Vorlagen. Dies geschieht absichtlich, da auch mit deminline 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).

  1. Beim Timing verschiedener Sortierfunktionen stellte ich fest, dass der Kontext (dh der umgebende Code), in dem die Sortierfunktion aufgerufen wurde, einen erheblichen Einfluss auf die Leistung hatte, was wahrscheinlich darauf zurückzuführen ist, dass die Funktion eingebunden und dann optimiert wurde. Wenn das Programm beispielsweise ausreichend einfach war, gab es normalerweise keinen großen Leistungsunterschied zwischen der Übergabe der Zeigerfunktion an einen Zeiger und der Übergabe eines Iterators. Andernfalls führte die Verwendung von Iteratoren normalerweise zu einer merklich besseren Leistung und (zumindest nach meiner bisherigen Erfahrung) nie zu einer merklich schlechteren Leistung. Ich vermute, dass dies daran liegen könnte, dass g ++ global ausreichend einfachen Code global optimieren kann.
Matthew K.
quelle
0

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

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Peter
quelle
0

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

function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}
Peter
quelle
1
Der Anwendungsfall unterscheidet sich geringfügig vom ursprünglichen Kontext der Frage. Bei Sortierungen mit fester Länge spielen Details eine Rolle und das Zählen von cmp Swaps reicht nicht aus. Ich wäre nicht einmal überrascht, wenn es nicht die eigentliche Sorte wäre, die Zeit verbrauchen würde, sondern etwas völlig anderes Licht, das typeof () in der Init aufruft. Ich weiß nicht, wie ich mit Javascript die tatsächliche Uhrzeitmessung durchführen soll. Vielleicht mit Knoten?
kriss
0

Vielleicht bin ich zu der Party zu spät, aber zumindest mein Beitrag ist ein neuer Ansatz.

  • Der Code sollte wirklich inline sein
  • Auch wenn inline, gibt es zu viele Zweige
  • Der Analyseteil ist im Grunde O (N (N-1)), was für N = 6 in Ordnung zu sein scheint
  • Der Code könnte effektiver sein, wenn die Kosten fürswap höher wären (dh die Kosten für compare).
  • Ich vertraue darauf, dass statische Funktionen eingebunden werden.
  • Die Methode bezieht sich auf die Rangfolge
    • Anstelle von Rängen werden die relativen Ränge (Offsets) verwendet.
    • Die Summe der Ränge ist für jeden Zyklus in einer Permutationsgruppe Null .
    • Anstatt 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 ...

#include <stdio.h>

#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif

static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);

int wsort6(int *arr);

void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", *arr);
        }
fprintf(stderr,"\n");
}

void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", (int) *arr);
        }
fprintf(stderr,"\n");
}

static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;

for (top = 0; top < cnt; top++ ) {
        for (bot = 0; bot < top; bot++ ) {
                if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
                }
        }
return ;
}
        /* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){

dif[0] =     (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}

static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;

Dif difs[cnt];

#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);

#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif

nswap = 0;
for (idx=0; idx < cnt; idx++) {
        int newval;
        int step,cyc;
        if ( !difs[idx] ) continue;
        newval = arr[idx];
        cyc = 0;
        src = idx;
        do      {
                int oldval;
                step = difs[src];
                difs[src] =0;
                dst = src + step;
                cyc += step ;
                if(dst == idx+1)idx=dst;
                oldval = arr[dst];
#if (DUMP_IT&1)
                fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d  Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
                        , nswap, cyc, step, idx, oldval, newval
                        , src, dst, difs[dst], arr[dst]
                        , newval  );
                do_print_a("Array ", arr, cnt);
                do_print_d("Steps ", difs, cnt);
#endif

                arr[dst] = newval;
                newval = oldval;
                nswap++;
                src = dst;
                } while( cyc);
        }

return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}
Wildplasser
quelle
sieht aus wie eine Blasensorte. Möglicherweise ein guter Anwärter auf die langsamste Implementierung, aber es kann immer noch von Interesse sein zu wissen, ob die Arbeit am Code so viel Unterschied macht. Bitte setzen Sie Ihren Code in das gleiche Format wie andere, damit wir den Benchmark darauf ausführen können.
Kriss
@kriss en.wikipedia.org/wiki/Permutation_group Es handelt sich sicherlich nicht um eine Blasensortierung : Der Code erkennt Zyklen in der angegebenen Permutation und geht diese Zyklen durch, wobei jedes Element an seiner endgültigen Stelle platziert wird. Die letzte wsort6()Funktion hat die richtige Schnittstelle.
Joop
@joop: meine schlechte, keine Blasensorte in der Tat. Abgesehen davon erwarte ich immer noch, dass der Code viel schlechter ist als jede andere aktuelle Implementierung. Übrigens ist die Rangordnungslösung hinsichtlich der Anzahl der Swaps optimal, da sie direkt die endgültige Position aller Elemente findet. Es ist auch unklar, ob Walksort überhaupt funktioniert, wenn wir die Hypothese entfernen, dass alle sortierten Zahlen wie hier unterschiedlich sind. Um den Code zu vergleichen, sollten wir den Trace-Code verwenden. Da ich normalerweise auf einem C ++ - Compiler kompiliere, funktioniert der Code nicht, da das OP eine Variable "new" nennt (und das die Syntaxhervorhebung unterbricht).
Kriss
Das Verfahren ist sehr nahe Rangordnung, nur die letzten Aufträge werden durchgeführt , an Ort und Stelle . Abgesehen von den Rängen o1..o5ist das zweite temporäre e[6]Array nicht erforderlich . Und: C-Code auf einem C ++ - Compiler kompilieren und den Code beschuldigen?
Joop
@ Greybeard: Danke, ich habe vorher ein Leerzeichen hinzugefügt #include. Feste
wildplasser
0
//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

    wire( 0, 1); wire( 2, 3); wire( 4, 5);
    wire( 3, 5); wire( 0, 2); wire( 1, 4);
    wire( 4, 5); wire( 2, 3); wire( 0, 1); 
    wire( 3, 4); wire( 1, 2); 
    wire( 2, 3);

    #undef wire
}
FrantzelasG
quelle
Sind Sie sicher, dass es funktioniert, unabhängig von der Geschwindigkeit? Bei der Bruteforce-Sortierung sind Ihre Loops zweifelhaft. Mir scheint, sie werden nicht funktionieren, wenn wir eine Null in sortierten Werten haben.
Kriss
1
Das Array t [6] wird auf 0x0 initialisiert. Es spielt also keine Rolle, wo und ob ein Schlüssel mit 0x0-Wert geschrieben wird.
FranG
-1

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)

GClaramunt
quelle
9
Es gibt 720 Bestellungen und die schnellen Versionen liegen weit unter 100 Zyklen. Selbst wenn eine massive Parallelität genutzt werden könnte, würden die Kosten für das Erstellen und Synchronisieren der Threads in einem so kleinen Zeitrahmen wahrscheinlich die Kosten für das einfache Sortieren der Arrays auf einem Kern übersteigen.
Kevin Stock
-3

Hier sind drei typische Sortiermethoden, die drei verschiedene Klassen von Sortieralgorithmen darstellen:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

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.

Khaled A Khunaifer
quelle
8
Das ist interessant, aber nebensächlich. Big-Θ soll konstante Faktoren verbergen und den Trend anzeigen, wenn die Problemgröße (n) groß wird. Das Problem besteht hier vollständig in einer festen Problemgröße (n = 6) und unter Berücksichtigung konstanter Faktoren.
kriss
@kriss Sie haben Recht, mein Vergleich ist asymptotisch, so dass der praktische Vergleich zeigt, ob es für diesen Fall schneller ist oder nicht
Khaled.K
4
Sie können nicht schließen, weil jeder unterschiedliche Algorithmus eine andere K-Multiplikationskonstante (und auch eine C-Additivkonstante) verbirgt. dh: k0, c0 für die Einfügesortierung, k1, c1 für die Heap-Sortierung und so weiter. Da all diese Konstanten tatsächlich unterschiedlich sind (man könnte in physikalischen Begriffen sagen, dass jeder Algorithmus seinen eigenen "Reibungskoeffizienten" hat), kann man nicht schließen, dass ein Algorithmus in diesem Fall (oder einem festen n-Fall) tatsächlich schneller ist.
Kriss