Type de tableau de longueur fixe 6 int le plus rapide

En répondant à une autre question de Stack Overflow ( celle-ci ), je suis tombé sur un sous-problème intéressant. Quel est le moyen le plus rapide de sortinger un tableau de 6 pouces?

Comme la question est très faible:

  • nous ne pouvons pas supposer que les bibliothèques sont disponibles (et que l’appel lui-même a son coût), uniquement en clair
  • pour éviter de vider le pipeline d’instructions (qui a un coût très élevé), nous devrions probablement minimiser les twigs, les sauts et tout autre type de stream de contrôle (comme ceux cachés derrière les points de séquence dans && ou || ).
  • l’espace est restreint et minimiser les registres et l’utilisation de la mémoire est un problème, idéalement le sorting en place est probablement le meilleur.

Vraiment, cette question est une sorte de golf où le but n’est pas de minimiser la longueur de la source mais le temps d’exécution. Je l’appelle le code ‘Zening’ tel qu’il est utilisé dans le titre de l’ouvrage Zen of Code optimisation de Michael Aarmh et ses suites .

Pour ce qui est de l’intérêt, il y a plusieurs couches:

  • l’exemple est simple et facile à comprendre et à mesurer, pas beaucoup de compétences
  • il montre les effets du choix d’un bon algorithme pour le problème, mais aussi des effets du compilateur et du matériel sous-jacent.

Voici mon implémentation de référence (naïf, non optimisé) et mon ensemble de tests.

 #include  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); } 

Résultats bruts

Au fur et à mesure que le nombre de variantes augmente, je les ai rassemblées dans une suite de tests disponible ici . Grâce à Kevin Stock, les tests utilisés sont un peu moins naïfs que ceux présentés ci-dessus. Vous pouvez le comstackr et l’exécuter dans votre propre environnement. Je suis très intéressé par le comportement sur différentes architectures / compilateurs cibles. (OK les gars, mettez-le dans les réponses, je vais +1 chaque consortingbuteur d’un nouveau jeu de résultats).

Il y a un an, j’ai répondu à Daniel Stutzbach (pour le golf), car il était à l’origine de la solution la plus rapide à l’époque (réseaux de sorting).

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O2

  • Appel direct à la fonction de bibliothèque qsort: 689.38
  • Implémentation naïve (sorting par insertion): 285,70
  • Tri d’insertion (Daniel Stutzbach): 142.12
  • Tri par insertion déroulé: 125.47
  • Classement: 102.26
  • Ordre de classement avec registres: 58.03
  • Réseaux de sorting (Daniel Stutzbach): 111,68
  • Réseaux de sorting (Paul R): 66,36
  • Tri des réseaux 12 avec échange rapide: 58,86
  • Réseaux de sorting 12 Echange réorganisé: 53,74
  • Réseaux de sorting 12 Échange simple réorganisé: 31,54
  • Réseau de sorting réorganisé avec échange rapide: 31.54
  • Réseau de sorting réorganisé avec échange rapide V2: 33.63
  • Tri en bulles incorporé (Paolo Bonzini): 48,85
  • Tri d’insertion déroulé (Paolo Bonzini): 75.30

Linux 64 bits, gcc 4.6.1 64 bits, Intel Core 2 Duo E8400, -O1

  • Appel direct à la fonction de bibliothèque qsort: 705.93
  • Implémentation naïve (sorting par insertion): 135.60
  • Tri d’insertion (Daniel Stutzbach): 142.11
  • Tri par insertion déroulé: 126,75
  • Classement: 46.42
  • Ordre de classement avec registres: 43,58
  • Réseaux de sorting (Daniel Stutzbach): 115,57
  • Réseaux de sorting (Paul R): 64,44
  • Tri des réseaux 12 avec échange rapide: 61,98
  • Réseaux de sorting 12 Echange réorganisé: 54,67
  • Réseaux de sorting 12 Échange simple réorganisé: 31,54
  • Réseau de sorting réorganisé avec échange rapide: 31,24
  • Réseau de sorting réorganisé avec échange rapide V2: 33.07
  • Tri en bulles incorporé (Paolo Bonzini): 45,79
  • Tri d’insertion déroulé (Paolo Bonzini): 80.15

J’ai inclus à la fois les résultats -O1 et -O2 car, de manière surprenante, pour plusieurs programmes, O2 est moins efficace que O1. Je me demande quelle optimisation spécifique a cet effet?

Commentaires sur les solutions proposées

Tri d’insertion (Daniel Stutzbach)

Comme prévu, réduire les twigs est une bonne idée.

Réseaux de sorting (Daniel Stutzbach)

Mieux que le sorting par insertion. Je me demandais si l’effet principal n’était pas d’éviter la boucle externe. Je me suis efforcé de faire un sorting par insertion pour vérifier et nous avons en gros les mêmes chiffres (le code est ici ).

Réseaux de sorting (Paul R)

Le meilleur jusqu’ici. Le code que j’ai utilisé pour tester est ici . Je ne sais pas encore pourquoi il est presque deux fois plus rapide que l’autre mise en œuvre du réseau de sorting. Paramètre en passant? Max rapide?

Tri des réseaux 12 SWAP avec échange rapide

Comme l’a suggéré Daniel Stutzbach, j’ai combiné son réseau de sorting de 12 swaps avec un swap rapide (le code est ici ). Il est en effet plus rapide, le meilleur jusqu’à présent avec une petite marge (environ 5%) comme on pouvait s’y attendre avec 1 swap de moins.

Il est également intéressant de noter que le swap sans twig semble être beaucoup (4 fois) moins efficace que le simple en utilisant l’architecture PPC.

Qsort de la bibliothèque appelante

Pour donner un autre sharepoint référence, j’ai également essayé, comme suggéré, d’appeler simplement la bibliothèque qsort (le code est ici ). Comme prévu, il est beaucoup plus lent: 10 à 30 fois plus lent … comme il est devenu évident avec la nouvelle suite de tests, le principal problème semble être le chargement initial de la bibliothèque après le premier appel, et version. Il est juste entre 3 et 20 fois plus lent sous Linux. Sur certaines architectures utilisées pour des tests par d’autres, cela semble même être plus rapide (je suis vraiment surpris par celui-ci, car la bibliothèque qsort utilise une API plus complexe).

Ordre de classement

Rex Kerr a proposé une autre méthode complètement différente: pour chaque élément du tableau, calculez directement sa position finale. Ceci est efficace car l’ordre de classement informatique n’a pas besoin de twig. L’inconvénient de cette méthode est qu’il faut trois fois la quantité de mémoire du tableau (une copie du tableau et des variables pour stocker les ordres de classement). Les résultats de performance sont très surprenants (et intéressants). Sur mon architecture de référence avec un système d’exploitation 32 bits et Intel Core2 Quad E8300, le nombre de cycles était légèrement inférieur à 1000 (comme le sorting des réseaux avec permutation de twigs). Mais, compilé et exécuté sur mon boîtier 64 bits (Intel Core2 Duo), il était beaucoup plus performant: il est devenu le plus rapide jusqu’à présent. J’ai finalement découvert la vraie raison. Ma boîte 32bits utilise gcc 4.4.1 et ma boite 64bits gcc 4.4.3 et la dernière semble beaucoup mieux optimiser ce code particulier (il y avait très peu de différence pour les autres propositions).

mise à jour :

Comme le montrent les chiffres publiés ci-dessus, cet effet était encore amélioré par les versions ultérieures de gcc et Rank Order est devenu deux fois plus rapide que toute autre alternative.

Tri des réseaux 12 avec échange réorganisé

L’efficacité étonnante de la proposition Rex Kerr avec gcc 4.4.3 m’a fait me demander: comment un programme avec 3 fois plus de mémoire peut-il être plus rapide que les réseaux de sorting à distance? Mon hypothèse était qu’il y avait moins de dépendances du genre read after write, permettant une meilleure utilisation du planificateur d’instruction superscalaire du x86. Cela m’a donné une idée: réorganiser les swaps pour minimiser les dépendances après lecture. Plus simplement: quand vous faites SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); vous devez attendre que le premier échange soit terminé avant d’effectuer le second, car tous deux accèdent à une cellule de mémoire commune. Lorsque vous faites SWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); le processeur peut exécuter les deux en parallèle. Je l’ai essayé et cela fonctionne comme prévu, les réseaux de sorting fonctionnent environ 10% plus rapidement.

Tri des réseaux 12 avec échange simple

Un an après le post initial proposé par Steinar H. Gunderson, nous ne devrions pas essayer de déjouer le compilateur et garder le code d’échange simple. C’est en effet une bonne idée car le code résultant est environ 40% plus rapide! Il a également proposé un swap optimisé à la main en utilisant le code assembleur en ligne x86 qui peut encore épargner davantage de cycles. Le plus surprenant (cela en dit long sur la psychologie du programmeur) est qu’il ya un an, aucun des utilisateurs n’a essayé cette version du swap. Le code que j’ai utilisé pour tester est ici . D’autres ont suggéré d’autres méthodes pour écrire un swap C rapide, mais cela donne les mêmes performances que le simple avec un compilateur correct.

Le “meilleur” code est maintenant comme suit:

 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 } 

Si nous croyons à notre ensemble de tests (et, oui, il est plutôt médiocre, le simple fait d’être court, simple et facile à comprendre), le nombre moyen de cycles du code résultant pour une sorte est inférieur à 40 cycles ( 6 tests sont exécutés). Cela a mis chaque échange à une moyenne de 4 cycles. Je l’appelle incroyablement vite. D’autres améliorations possibles?

Pour toute optimisation, il est toujours préférable de tester, tester, tester. Je voudrais essayer au moins de sortinger les réseaux et le sorting par insertion. Si je pariais, je mettrais mon argent sur un sorting par insertion basé sur mon expérience passée.

Savez-vous quelque chose sur les données d’entrée? Certains algorithmes fonctionneront mieux avec certains types de données. Par exemple, le sorting par insertion donne de meilleurs résultats avec les données sortingées ou presque sortingées, ce sera donc le meilleur choix s’il y a une chance supérieure à la moyenne de données presque sortingées.

L’algorithme que vous avez publié est similaire à un sorting par insertion, mais il semble que vous ayez minimisé le nombre de swaps au prix de plus de comparaisons. Les comparaisons sont beaucoup plus coûteuses que les swaps, car les twigs peuvent bloquer le pipeline d’instructions.

Voici une implémentation de sorting par insertion:

 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; } } 

Voici comment je construirais un réseau de sorting. Tout d'abord, utilisez ce site pour générer un ensemble minimal de macros SWAP pour un réseau de la longueur appropriée. Envelopper cela dans une fonction me donne:

 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 } 

Voici une implémentation utilisant des réseaux de sorting :

 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); } 

Pour cela, vous avez vraiment besoin d’implémentations très efficaces de min et max sans twig, car c’est bien ce à quoi ce code se résume – une séquence d’opérations min et max (13 au total). Je laisse cela comme un exercice pour le lecteur.

Notez que cette implémentation se prête facilement à la vectorisation (par exemple SIMD – la plupart des ISA SIMD ont des instructions min / max vectorielles) et aussi aux implémentations GPU (par exemple CUDA – sans dérive, il n’y a pas de problème de divergence de chaîne).

Voir aussi: Implémentation rapide de l’algorithme pour sortinger les très petites listes

Puisque ce sont des entiers et que les comparaisons sont rapides, pourquoi ne pas calculer l’ordre de classement de chacun directement:

 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]; } 

On dirait que je suis arrivé à la fête avec un an de retard, mais nous y voilà …

En regardant l’assemblage généré par gcc 4.5.2, j’ai observé que des charges et des magasins sont en train d’être réalisés pour chaque échange, ce qui n’est vraiment pas nécessaire. Il serait préférable de charger les 6 valeurs dans des registres, de les sortinger et de les stocker en mémoire. J’ai commandé les charges dans les magasins pour être aussi proche que possible des registres nécessaires et de la dernière utilisation. J’ai également utilisé la macro SWAP de Steinar H. Gunderson. Mise à jour: Je suis passé à la macro SWAP de Paolo Bonzini, que gcc convertit en quelque chose de similaire à Gunderson, mais gcc est capable de mieux ordonner les instructions car elles ne sont pas données comme un assemblage explicite.

J’ai utilisé le même ordre de swap que le réseau de swaps réordonné, considéré comme le plus performant, bien qu’il puisse y avoir une meilleure commande. Si je trouve plus de temps, je vais générer et tester un tas de permutations.

J’ai modifié le code de test pour prendre en compte plus de 4000 tableaux et indiquer le nombre moyen de cycles nécessaires pour sortinger chacun. Sur un i5-650, j’obtiens ~ 34.1 cycles / sort (en utilisant -O3), comparé au réseau de sorting original réordonné obtenant ~ 65.3 cycles / sorting (en utilisant -O1, battements -O2 et -O3).

 #include  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; } 

J’ai modifié la suite de tests pour signaler également les horloges par sorting et exécuter davantage de tests (la fonction cmp a également été mise à jour pour gérer également le débordement d’entiers), voici les résultats obtenus sur différentes architectures. J’ai essayé de tester sur un processeur AMD mais rdtsc n’est pas fiable sur le X6 1100T dont je dispose.

 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 

Le code de test est plutôt mauvais. il déborde le tableau initial (les gens ne lisent-ils pas les avertissements du compilateur?), le printf imprime les mauvais éléments, il utilise .byte pour rdtsc sans raison valable, il n’y a qu’une seule exécution (!), rien ne vérifie que le les résultats finaux sont en fait corrects (il est donc très facile d’optimiser quelque chose de subtilement faux), les tests inclus sont très rudimentaires (pas de nombres négatifs?) et rien n’empêche le compilateur de simplement supprimer la fonction

Cela étant dit, il est également très facile d’améliorer la solution réseau bitonique; changez simplement le contenu min / max / SWAP en

 #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"); } 

et il est environ 65% plus rapide pour moi (Debian gcc 4.4.5 avec -O2, amd64, Core i7).

Il y a quelques jours, je suis tombé sur cette question de Google, car j’avais également besoin de sortinger rapidement un tableau de longueur fixe de 6 nombres entiers. Dans mon cas cependant, mes entiers ne sont que de 8 bits (au lieu de 32) et je n’ai pas l’exigence ssortingcte d’utiliser uniquement C. Je pensais partager de toute façon mes découvertes, au cas où elles pourraient être utiles à quelqu’un …

J’ai implémenté une variante d’un sorting dans l’assemblage du réseau qui utilise SSE pour vectoriser les opérations de comparaison et d’échange, dans la mesure du possible. Il faut six “passes” pour sortinger complètement le tableau. J’ai utilisé un nouveau mécanisme pour convertir directement les résultats de PCMPGTB (comparaison vectorisée) en parameters de mélange pour PSHUFB (swap vectorisé), en utilisant uniquement une instruction PADDB (ajout vectorisé) et, dans certains cas, une instruction PAND (bitwise AND).

Cette approche a également eu pour effet secondaire de produire une fonction véritablement sans twig. Il n’y a aucune instruction de saut que ce soit.

Il semble que cette implémentation soit environ 38% plus rapide que l’implémentation qui est actuellement marquée comme l’option la plus rapide dans la question (“Tri des réseaux 12 avec échange simple”). J’ai modifié cette implémentation pour utiliser des éléments de tableau de caractères lors de mes tests, afin de rendre la comparaison équitable.

Je devrais noter que cette approche peut être appliquée à toute taille de tableau jusqu’à 16 éléments. Je m’attends à ce que l’avantage de la vitesse relative par rapport aux alternatives augmente pour les plus grands réseaux.

Le code est écrit en MASM pour les processeurs x86_64 avec SSSE3. La fonction utilise la “nouvelle” convention d’appel Windows x64. C’est ici…

 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 (eg 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 

Vous pouvez comstackr cela dans un object exécutable et le lier à votre projet C. Pour obtenir des instructions sur la façon de procéder dans Visual Studio, vous pouvez lire cet article . Vous pouvez utiliser le prototype C suivant pour appeler la fonction à partir de votre code C:

 void simd_sort_6(char *values); 

Bien que j’aime vraiment la macro d’échange fournie:

 #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; } 

I see an improvement (which a good comstackr might make):

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

We take note of how min and max work and pull the common sub-expression explicitly. This eliminates the min and max macros completely.

Never optimize min/max without benchmarking and looking at actual comstackr generated assembly. If I let GCC optimize min with conditional move instructions I get a 33% speedup:

 #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 cycles in the test code). Doing max with ?: is more or less the same, almost lost in the noise, but the above is a little bit faster. This SWAP is faster with both GCC and Clang.

Comstackrs are also doing an exceptional job at register allocation and alias analysis, effectively moving d[x] into local variables upfront, and only copying back to memory at the end. In fact, they do so even better than if you worked entirely with local variables (like d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5] ). I'm writing this because you are assuming strong optimization and yet trying to outsmart the comstackr on min/max. 🙂

By the way, I sortinged Clang and GCC. They do the same optimization, but due to scheduling differences the two have some variation in the results, can't say really which is faster or slower. GCC is faster on the sorting networks, Clang on the quadratic sorts.

Just for completeness, unrolled bubble sort and insertion sorts are possible too. Here is the bubble sort:

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

and here is the insertion sort:

 //#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); 

This insertion sort is faster than Daniel Stutzbach's, and is especially good on a GPU or a computer with predication because ITER can be done with only 3 instructions (vs. 4 for SWAP). For example, here is the t = d[2]; ITER(1); ITER(0); line in ARM assembly:

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

For six elements the insertion sort is competitive with the sorting network (12 swaps vs. 15 iterations balances 4 instructions/swap vs. 3 instructions/iteration); bubble sort of course is slower. But it's not going to be true when the size grows, since insertion sort is O(n^2) while sorting networks are O(n log n).

I ported the test suite to a PPC architecture machine I can not identify (didn’t have to touch code, just increase the iterations of the test, use 8 test cases to avoid polluting results with mods and replace the x86 specific rdtsc):

Direct call to qsort library function : 101

Naive implementation (insertion sort) : 299

Insertion Sort (Daniel Stutzbach) : 108

Insertion Sort Unrolled : 51

Sorting Networks (Daniel Stutzbach) : 26

Sorting Networks (Paul R) : 85

Sorting Networks 12 with Fast Swap : 117

Sorting Networks 12 reordered Swap : 116

Rank Order : 56

An XOR swap may be useful in your swapping functions.

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

The if may cause too much divergence in your code, but if you have a guarantee that all your ints are unique this could be handy.

Looking forward to trying my hand at this and learning from these examples, but first some timings from my 1.5 GHz PPC Powerbook G4 w/ 1 GB DDR RAM. (I borrowed a similar rdtsc-like timer for PPC from http://www.mcs.anl.gov/~kazutomo/rdtsc.html for the timings.) I ran the program a few times and the absolute results varied but the consistently fastest test was “Insertion Sort (Daniel Stutzbach)”, with “Insertion Sort Unrolled” a close second.

Here’s the last set of times:

 **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 

Here is my consortingbution to this thread: an optimized 1, 4 gap shellsort for a 6-member int vector (valp) containing unique values.

 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=valp); ip+=1; cp=ip; } while (ip 

On my HP dv7-3010so laptop with a dual-core Athlon M300 @ 2 Ghz (DDR2 memory) it executes in 165 clock cycles. This is an average calculated from timing every unique sequence (6!/720 in all). Comstackd to Win32 using OpenWatcom 1.8. The loop is essentially an insertion sort and is 16 instructions/37 bytes long.

I do not have a 64-bit environment to comstack on.

If insertion sort is reasonably competitive here, I would recommend trying a shellsort. I’m afraid 6 elements is probably just too little for it to be among the best, but it might be worth a try.

Example code, untested, undebugged, etc. You want to tune the inc = 4 and inc -= 3 sequence to find the optimum (try inc = 2, inc -= 1 for example).

 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; } } } 

I don’t think this will win, but if someone posts a question about sorting 10 elements, who knows…

According to Wikipedia this can even be combined with sorting networks: Pratt, V (1979). Shellsort and sorting networks (Outstanding dissertations in the computer sciences). Garland. ISBN 0-824-04406-1

This question is becoming quite old, but I actually had to solve the same problem these days: fast agorithms to sort small arrays. I thought it would be a good idea to share my knowledge. While I first started by using sorting networks, I finally managed to find other algorithms for which the total number of comparisons performed to sort every permutation of 6 values was smaller than with sorting networks, and smaller than with insertion sort. I didn’t count the number of swaps; I would expect it to be roughly equivalent (maybe a bit higher sometimes).

The algorithm sort6 uses the algorithm sort4 which uses the algorithm sort3 . Here is the implementation in some light C++ form (the original is template-heavy so that it can work with any random-access iterator and any suitable comparison function).

Sorting 3 values

The following algorithm is an unrolled insertion sort. When two swaps (6 assignments) have to be performed, it uses 4 assignments instead:

 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]); } } } } 

It looks a bit complex because the sort has more or less one branch for every possible permutation of the array, using 2~3 comparisons and at most 4 assignments to sort the three values.

Sorting 4 values

This one calls sort3 then performs an unrolled insertion sort with the last element of the array:

 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]); } } } } 

This algorithm performs 3 to 6 comparisons and at most 5 swaps. It is easy to unroll an insertion sort, but we will be using another algorithm for the last sort...

Sorting 6 values

This one uses an unrolled version of what I called a double insertion sort . The name isn't that great, but it's quite descriptive, here is how it works:

  • Sort everything but the first and the last elements of the array.
  • Swap the first and the elements of the array if the first is greater than the last.
  • Insert the first element into the sorted sequence from the front then the last element from the back.

After the swap, the first element is always smaller than the last, which means that, when inserting them into the sorted sequence, there won't be more than N comparisons to insert the two elements in the worst case: for example, if the first element has been insert in the 3rd position, then the last one can't be inserted lower than the 4th position.

 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]); } } } } } 

My tests on every permutation of 6 values ever show that this algorithms always performs between 6 and 13 comparisons. I didn't compute the number of swaps performed, but I don't expect it to be higher than 11 in the worst case.

I hope that this helps, even if this question may not represent an actual problem anymore 🙂

EDIT: after putting it in the provided benchmark, it is cleary slower than most of the interesting alternatives. It tends to perform a bit better than the unrolled insertion sort, but that's pretty much it. Basically, it isn't the best sort for integers but could be interesting for types with an expensive comparison operation.

I know I’m super-late, but I was interestd in experimenting with some different solutions. First, I cleaned up that paste, made it comstack, and put it into a repository. I kept some undesirable solutions as dead-ends so that others wouldn’t try it. Among this was my first solution, which attempted to ensure that x1>x2 was calculated once. After optimization, it is no faster than the other, simple versions.

I added a looping version of rank order sort, since my own application of this study is for sorting 2-8 items, so since there are a variable number of arguments, a loop is necessary. This is also why I ignored the sorting network solutions.

The test code didn’t test that duplicates were handled correctly, so while the existing solutions were all correct, I added a special case to the test code to ensure that duplicates were handled correctly.

Then, I wrote an insertion sort that is entirely in AVX registers. On my machine it is 25% faster than the other insertion sorts, but 100% slower than rank order. I did this purely for experiment and had no expectation of this being better due to the branching in insertion sort.

 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 } 

Then, I wrote a rank order sort using AVX. This matches the speed of the other rank-order solutions, but is no faster. The issue here is that I can only calculate the indices with AVX, and then I have to make a table of indices. This is because the calculation is destination-based rather than source-based. See Converting from Source-based Indices to Destination-based Indices

 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]; } 

The repo can be found here: https://github.com/eyepatchParrot/sort6/

I believe there are two parts to your question.

  • The first is to determine the optimal algorithm. This is done – at least in this case – by looping through every possible ordering (there aren’t that many) which allows you to compute exact min, max, average and standard deviation of compares and swaps. Have a runner-up or two handy as well.
  • The second is to optimize the algorithm. A lot can be done to convert textbook code examples to mean and lean real-life algorithms. If you realize that an algorithm can’t be optimized to the extent required, try a runner-up.

I wouldn’t worry too much about emptying pipelines (assuming current x86): branch prediction has come a long way. What I would worry about is making sure that the code and data fit in one cache line each (maybe two for the code). Once there fetch latencies are refreshingly low which will compensate for any stall. It also means that your inner loop will be maybe ten instructions or so which is right where it should be (there are two different inner loops in my sorting algorithm, they are 10 instructions/22 bytes and 9/22 long respectively). Assuming the code doesn’t contain any divs you can be sure it will be blindingly fast.

I found that at least on my system, the functions sort6_iterator() and sort6_iterator_local() defined below both ran at least as fast, and frequently noticeably faster, than the above current record holder:

 #define MIN(x, y) (x 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 } 

I passed this function a std::vector ‘s iterator in my timing code. I suspect that using iterators gives g++ certain assurances about what can and can’t happen to the memory that the iterator refers to, which it otherwise wouldn’t have and it is these assurances that allow g++ to better optimize the sorting code (which if I remember correctly, is also part of the reason why so many std algorithms, such as std::sort() , generally have such obscenely good performance). However, while timing I noticed that the context (ie surrounding code) in which the call to the sorting function was made had a significant impact on performance, which is likely due to the function being inlined and then optimized. For instance, if the program was sufficiently simple then there usually wasn’t much of a difference in performance between passing the sorting function a pointer versus passing it an iterator; otherwise using iterators usually resulted in noticeably better performance and never (in my experience so far at least) any noticeably worse performance. I suspect that this may be because g++ can globally optimize sufficiently simple code.

Moreover, sort6_iterator() is some times (again, depending on the context in which the function is called) consistently outperformed by the following sorting function:

 template 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 } 

Note that defining SWAP() as follows some times results in slightly better performance although most of the time it results in slightly worse performance or a negligible difference in performance.

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

If you just want a sorting algorithm that gcc -O3 is consistently good at optimizing then, depending on how you pass the input, try one of the following two algorithms:

 template 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 } 

Ou

 template 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 } 

The reason for using the register keyword is because this is one of the few times that you know that you want these values in registers. Without register , the comstackr will figure this out most of the time but sometimes it doesn’t. Using the register keyword helps solve this issue. Normally, however, don’t use the register keyword since it’s more likely to slow your code than speed it up.

Also, note the use of templates. This is done on purpose since, even with the inline keyword, template functions are generally much more aggressively optimized by gcc than vanilla C functions (this has to do with gcc needing to deal with function pointers for vanilla C functions but not with template functions).

I know this is an old question.

But I just wrote a different kind of solution I want to share.
Using nothing but nested MIN MAX,

It’s not fast as it uses 114 of each,
could reduce it to 75 pretty simply like so -> pastebin

But then it’s not purely min max anymore.

What might work is doing min/max on multiple integers at once with AVX

PMINSW reference

 #include  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]); } } 

MODIFIER:
Rank order solution inspired by Rex Kerr's, Much faster than the mess above

 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-abcde]=F; } 

Maybe I am late to the party, but at least my consortingbution is a new approach.

  • The code really should be inlined
  • even if inlined, there are too many twigs
  • the analysing part is basically O(N(N-1)) which seems OK for N=6
  • the code could be more effective if the cost of swap would be higher (irt the cost of compare )
  • I trust on static functions being inlined.
  • The method is related to rank-sort
    • instead of ranks, the relative ranks (offsets) are used.
    • the sum of the ranks is zero for every cycle in any permutation group.
    • instead of SWAP() ing two elements, the cycles are chased, needing only one temp, and one (register->register) swap (new <- old).

Update: changed the code a bit, some people use C++ comstackrs to comstack C code …

 #include  #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); } 

Well, if it’s only 6 elements and you can leverage parallelism, want to minimize conditional branching, etc. Why you don’t generate all the combinations and test for order? I would venture that in some architectures, it can be pretty fast (as long as you have the memory preallocated)

Try ‘merging sorted list’ sort. 🙂 Use two array. Fastest for small and big array.
If you concating, you only check where insert. Other bigger values you not need compare (cmp = ab>0).
For 4 numbers, you can use system 4-5 cmp (~4.6) or 3-6 cmp (~4.9). Bubble sort use 6 cmp (6). Lots of cmp for big numbers slower code.
This code use 5 cmp (not MSL sort):
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);}

Principial 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;step0) {arr[n][k] = arr[m][j]; j++; k++;} else {arr[n][k] = arr[m][i]; i++; k++;} } while (i 

Sort 4 items with usage cmp==0. Numbers of cmp is ~4.34 (FF native have ~4.52), but take 3x time than merging lists. But better less cmp operations, if you have big numbers or big text. Edit: repaired bug

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; } 

Here are three typical sorting methods that represent three different classes of Sorting Algorithms:

 Insertion Sort: Θ(n^2) Heap Sort: Θ(n log n) Count Sort: Θ(3n) 

But check out Stefan Nelsson discussion on the fastest sorting algorithm? where he discuss a solution that goes down to O(n log log n) .. check out its implementation in C

This Semi-Linear Sorting algorithm was presented by a paper in 1995:

A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pages 427-436, 1995.