Type le plus rapide de tableau int 6 de longueur fixe

401

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

Comme la question est de très bas niveau:

  • nous ne pouvons pas supposer que les bibliothèques sont disponibles (et l'appel lui-même a son coût), seul C
  • pour éviter de vider le pipeline d'instructions (qui a un coût très élevé), nous devons probablement minimiser les branches, les sauts et tout autre type de rupture de flux de contrôle (comme ceux cachés derrière les points de séquence dans &&ou ||).
  • l'espace est limité et la minimisation des registres et de l'utilisation de la mémoire est un problème, idéalement en place, le tri 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 du livre Zen of Code Optimization de Michael Abrash et ses suites .

Quant à savoir pourquoi il est intéressant, il existe plusieurs couches:

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

Voici ma mise en œuvre de référence (naïve, non optimisée) et mon jeu de test.

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

Résultats bruts

Comme le nombre de variantes devient important, je les ai toutes rassemblées dans une suite de tests qui peut être trouvée ici . Les tests réels utilisés sont un peu moins naïfs que ceux montrés ci-dessus, grâce à Kevin Stock. Vous pouvez le compiler et l'exécuter dans votre propre environnement. Je suis assez intéressé par le comportement sur différentes architectures / compilateurs cibles. (OK les gars, mettez-le dans les réponses, je vais attribuer +1 à chaque contributeur d'un nouvel ensemble de résultats).

J'ai donné la réponse à Daniel Stutzbach (pour le golf) il y a un an car il était à l'origine de la solution la plus rapide à l'époque (réseaux de tri).

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 (tri par insertion): 285,70
  • Tri d'insertion (Daniel Stutzbach): 142,12
  • Tri par insertion déroulé: 125,47
  • Ordre de classement: 102,26
  • Ordre de classement avec registres: 58.03
  • Réseaux de tri (Daniel Stutzbach): 111,68
  • Réseaux de tri (Paul R): 66,36
  • Réseaux de tri 12 avec échange rapide: 58,86
  • Réseaux de tri 12 réorganisés Échange: 53,74
  • Réseaux de tri 12 échange simple réorganisé: 31,54
  • Réseau de tri réorganisé avec échange rapide: 31,54
  • Réseau de tri réorganisé avec échange rapide V2: 33,63
  • Tri des bulles en ligne (Paolo Bonzini): 48,85
  • Tri par insertion déroulée (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 (tri par insertion): 135.60
  • Tri d'insertion (Daniel Stutzbach): 142,11
  • Tri par insertion déroulé: 126,75
  • Ordre de classement: 46,42
  • Ordre de classement avec registres: 43,58
  • Réseaux de tri (Daniel Stutzbach): 115,57
  • Réseaux de tri (Paul R): 64,44
  • Réseaux de tri 12 avec échange rapide: 61,98
  • Réseaux de tri 12 réorganisés Échange: 54,67
  • Réseaux de tri 12 échange simple réorganisé: 31,54
  • Réseau de tri réorganisé avec échange rapide: 31,24
  • Réseau de tri réorganisé avec échange rapide V2: 33.07
  • Tri des bulles en ligne (Paolo Bonzini): 45,79
  • Tri par insertion déroulée (Paolo Bonzini): 80,15

J'ai inclus à la fois les résultats -O1 et -O2 car étonnamment 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 par insertion (Daniel Stutzbach)

Comme prévu, minimiser les branches est en effet une bonne idée.

Réseaux de tri (Daniel Stutzbach)

Mieux que le tri par insertion. Je me demandais si l'effet principal n'était pas obtenu en évitant la boucle externe. Je l'ai essayé par tri d'insertion déroulée pour vérifier et en effet nous obtenons à peu près les mêmes chiffres (le code est ici ).

Réseaux de tri (Paul R)

Le meilleur jusqu'ici. Le code réel que j'ai utilisé pour tester est ici . Je ne sais pas encore pourquoi elle est presque deux fois plus rapide que l'autre implémentation du réseau de tri. Passage de paramètre? Rapide max?

Réseaux de tri 12 SWAP avec échange rapide

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

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

Appeler la bibliothèque qsort

Pour donner un autre point de 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 cela est devenu évident avec la nouvelle suite de tests, le principal problème semble être la charge initiale de la bibliothèque après le premier appel, et elle ne se compare pas si mal aux autres version. C'est juste entre 3 et 20 fois plus lent sur mon Linux. Sur certaines architectures utilisées pour les tests par d'autres, cela semble même être plus rapide (je suis vraiment surpris par celle-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, calculer directement sa position finale. Ceci est efficace car le calcul de l'ordre de classement n'a pas besoin de branchement. L'inconvénient de cette méthode est qu'elle prend 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 OS 32 bits et Intel Core2 Quad E8300, le nombre de cycles était légèrement inférieur à 1000 (comme les réseaux de tri avec swap de branchement). Mais lorsqu'elle a été compilée et exécutée sur ma boîte 64 bits (Intel Core2 Duo), elle s'est beaucoup mieux comportée: elle est devenue la plus rapide jusqu'à présent. J'ai finalement découvert la vraie raison. Ma boîte 32 bits utilise gcc 4.4.1 et ma boîte 64 bits gcc 4.4.

mise à jour :

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

Réseaux de tri 12 avec échange réorganisé

L'incroyable efficacité 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 tri sans branche? Mon hypothèse était qu'il avait moins de dépendances du type lecture après écriture, permettant une meilleure utilisation du planificateur d'instructions superscalaire du x86. Cela m'a donné une idée: réorganiser les swaps pour minimiser les dépendances de lecture après écriture. Plus simplement: lorsque vous le faites, SWAP(1, 2); SWAP(0, 2);vous devez attendre la fin du premier échange avant d'effectuer le second car les deux ont accès à une cellule de mémoire commune. Lorsque vous le faites, 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 tri fonctionnent environ 10% plus rapidement.

Tri des réseaux 12 avec échange simple

Un an après la publication originale, Steinar H. Gunderson a suggéré de ne pas essayer de déjouer le compilateur et de 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 échange optimisé à la main en utilisant le code d'assemblage en ligne x86 qui peut encore épargner quelques cycles supplémentaires. Le plus surprenant (il dit des volumes sur la psychologie du programmeur) est qu'il y a un an, aucun des utilisateurs n'avait essayé cette version de swap. Le code que je testais est ici . D'autres ont suggéré d'autres façons d'écrire un échange rapide en C, mais il donne les mêmes performances que le simple avec un compilateur décent.

Le "meilleur" code est maintenant le suivant:

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 que notre ensemble de tests (et, oui, il est assez médiocre, son simple avantage est d'être court, simple et facile à comprendre ce que nous mesurons), le nombre moyen de cycles du code résultant pour une sorte est inférieur à 40 cycles ( 6 tests sont exécutés). Cela met chaque swap à une moyenne de 4 cycles. J'appelle ça incroyablement rapide. D'autres améliorations possibles?

kriss
la source
2
Avez-vous des contraintes sur les pouces? Par exemple, pouvons-nous supposer que pour tout 2 x, y x-yet x+yne provoquera pas de débordement ou de débordement?
Matthieu M.
3
Vous devriez essayer de combiner mon réseau de tri à 12 swaps avec la fonction de swap sans branche de Paul. Sa solution transmet tous les paramètres en tant qu'éléments séparés sur la pile au lieu d'un seul pointeur vers un tableau. Cela pourrait également faire une différence.
Daniel Stutzbach
2
Notez que l'implémentation correcte de rdtsc sur 64 bits est __asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");due au fait que rdtsc place la réponse dans EDX: EAX tandis que GCC l'attend dans un seul registre 64 bits. Vous pouvez voir le bogue en compilant à -O3. Voir également ci-dessous mon commentaire à Paul R sur un SWAP plus rapide.
Paolo Bonzini
3
@Tyler: Comment l'implémentez-vous au niveau de l'assemblage sans branche?
Loren Pechtel
4
@Loren: CMP EAX, EBX; SBB EAX, EAXmettra 0 ou 0xFFFFFFFF EAXselon qu'il EAXest respectivement plus grand ou plus petit que EBX. SBBest "soustraire avec emprunter", la contrepartie de ADC("ajouter avec reporter"); le bit d'état auquel vous faites référence est le bit de retenue. Là encore, je me souviens de cela ADCet SBBavait une latence et un débit terribles sur le Pentium 4 par rapport à ADDet SUB, et était encore deux fois plus lent sur les processeurs Core. Depuis le 80386, il existe également des instructions de SETccstockage CMOVccconditionnel et de déplacement conditionnel, mais elles sont également lentes.
j_random_hacker

Réponses:

162

Pour toute optimisation, il est toujours préférable de tester, tester, tester. J'essaierais au moins les réseaux de tri et le tri par insertion. Si je misais, je mettrais mon argent sur le tri par insertion en fonction de mon expérience passée.

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

L'algorithme que vous avez publié est similaire à un tri par insertion, mais il semble que vous ayez minimisé le nombre de swaps au prix de plus de comparaisons. Les comparaisons sont cependant beaucoup plus chères que les swaps, car les branches peuvent entraîner le blocage du pipeline d'instructions.

Voici une implémentation de tri 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 construisais un réseau de tri. 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
}
Daniel Stutzbach
la source
9
+1: sympa, vous l'avez fait avec 12 échanges plutôt que les 13 de mon réseau codé à la main et dérivé empiriquement ci-dessus. Je vous donnerais un autre +1 si je pouvais pour le lien vers le site qui génère des réseaux pour vous - maintenant mis en signet.
Paul R
9
C'est une idée fantastique pour une fonction de tri à usage général si vous vous attendez à ce que la majorité des demandes soient des tableaux de petite taille. Utilisez une instruction switch pour les cas que vous souhaitez optimiser, en utilisant cette procédure; laissez le cas par défaut utiliser une fonction de tri de bibliothèque.
Mark Ransom
5
@Mark Une bonne fonction de tri de bibliothèque aura déjà un chemin rapide pour les petits tableaux. De nombreuses bibliothèques modernes utiliseront un QuickSort récursif ou un MergeSort qui bascule vers InsertionSort après avoir recursé vers n < SMALL_CONSTANT.
Daniel Stutzbach
3
@Mark Eh bien, une fonction de tri de bibliothèque C nécessite que vous spécifiiez l'opération de comparaison via un porteur de fonction. La surcharge de l'appel d'une fonction pour chaque comparaison est énorme. Habituellement, c'est toujours la voie la plus propre, car il s'agit rarement d'un chemin critique dans le programme. Cependant, si c'est le chemin critique, nous pouvons vraiment trier beaucoup plus rapidement si nous savons que nous trions des entiers et exactement 6 d'entre eux. :)
Daniel Stutzbach
7
@tgwh: Le swap XOR est presque toujours une mauvaise idée.
Paul R
63

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

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

Vous avez vraiment besoin de branchements minet d' maximplémentations très efficaces pour cela, car c'est effectivement ce que ce code se résume à - une séquence minet des maxopérations (13 de chaque, 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 vectorielles min / max) et également aux implémentations GPU (par exemple CUDA - étant sans branche, il n'y a pas de problèmes de divergence de chaîne, etc.).

Voir aussi: Implémentation rapide d'un algorithme pour trier une très petite liste

Paul R
la source
1
Pour quelques hacks de bits pour min / max: graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax
Rubys
1
@Paul: dans le vrai contexte d'utilisation de CUDA, c'est certainement la meilleure réponse. Je vais vérifier si c'est aussi (et combien) dans le contexte du golf x64 et publier le résultat.
kriss
1
Sort3serait plus rapide (sur la plupart des architectures, de toute façon) si vous notiez que (a+b+c)-(min+max)c'est le numéro central.
Rex Kerr
1
@Rex: Je vois - ça a l'air bien. Pour les architectures SIMD comme AltiVec et SSE, ce serait le même nombre de cycles d'instructions (max et min sont des instructions à cycle unique comme ajouter / soustraire), mais pour un processeur scalaire normal, votre méthode semble meilleure.
Paul R
2
Si je laisse GCC optimize min avec instructions conditionnelles , je reçois 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; }. Ici, je n'utilise pas?: Pour d [y] car cela donne des performances légèrement pires, mais c'est presque dans le bruit.
Paolo Bonzini
45

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

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
la source
@Rex: avec gcc -O1, c'est en dessous de 1000 cycles, assez rapide mais plus lent que le réseau de tri. Une idée pour améliorer le code? Peut-être que si nous pouvions éviter la copie du tableau ...
kriss
@kriss: C'est plus rapide que le réseau de tri pour moi avec -O2. Y a-t-il une raison pour laquelle -O2 n'est pas correct, ou est-ce plus lent pour vous sur -O2 également? C'est peut-être une différence dans l'architecture de la machine?
Rex Kerr
1
@Rex: désolé, j'ai raté le schéma> vs> = à première vue. Cela fonctionne dans tous les cas.
kriss
3
@kriss: Aha. Ce n'est pas complètement surprenant - il y a beaucoup de variables qui flottent, et elles doivent être soigneusement ordonnées et mises en cache dans les registres et ainsi de suite.
Rex Kerr
2
@SSpoke 0+1+2+3+4+5=15Puisqu'un d'entre eux est manquant, 15 moins la somme du reste donne un manquant
Glenn Teitelbaum
35

On dirait que je suis arrivé à la fête un an en retard, mais c'est parti ...

En regardant l'assembly généré par gcc 4.5.2, j'ai observé que des chargements et des magasins sont effectué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 trier et de les stocker en mémoire. J'ai ordonné que les charges dans les magasins soient aussi proches que possible de là où les registres sont d'abord nécessaires et utilisés en dernier. 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 en mesure de mieux ordonner les instructions car elles ne sont pas données comme assemblage explicite.

J'ai utilisé le même ordre de swap que le réseau de swaps réorganisé donné comme le plus performant, bien qu'il puisse y avoir un meilleur ordre. Si je trouve encore du temps, je vais générer et tester un tas de permutations.

J'ai changé le code de test pour prendre en compte plus de 4000 tableaux et afficher le nombre moyen de cycles nécessaires pour trier chacun. Sur un i5-650, j'obtiens ~ 34,1 cycles / tri (en utilisant -O3), par rapport au réseau de tri réorganisé d'origine obtenant ~ 65,3 cycles / tri (en utilisant -O1, bat -O2 et -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;
}

J'ai modifié la suite de tests pour signaler également les horloges par tri et exécuter plus de tests (la fonction cmp a également été mise à jour pour gérer le débordement d'entier), voici les résultats 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
Kevin Stock
la source
Votre idée de variables de registre devrait être appliquée à la solution "Classement par ordre" de Rex Kerr. Cela devrait être plus rapide et peut-être que l' -O3optimisation ne sera pas contre-productive.
cdunn2001
1
@ cdunn2001 Je viens de le tester, je ne vois pas d'amélioration (sauf quelques cycles à -O0 et -Os). En regardant l'asm, il semble que gcc ait déjà réussi à utiliser des registres et à éliminer l'appel à memcpy.
Kevin Stock
Pourriez-vous ajouter la version de swap simple à votre suite de tests, je suppose qu'il pourrait être intéressant de la comparer avec un swap rapide d'assemblage optimisé à la main.
kriss
1
Votre code utilise toujours le swap de Gunderson, le mien le serait #define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }.
Paolo Bonzini
@Paolo Bonzini: Oui, j'ai l'intention d'ajouter un cas de test avec le vôtre, mais je n'ai pas encore eu le temps. Mais j'éviterai l'assemblage en ligne.
kriss
15

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

J'ai implémenté une variante d'un tri réseau dans l'assembly qui utilise SSE pour vectoriser les opérations de comparaison et d'échange, dans la mesure du possible. Il faut six «passes» pour trier complètement le tableau. J'ai utilisé un nouveau mécanisme pour convertir directement les résultats de PCMPGTB (comparaison vectorisée) en paramètres de shuffle pour PSHUFB (échange vectorisé), en utilisant uniquement une PADDB (vectorized add) et dans certains cas également une instruction PAND (bitwise AND).

Cette approche a également eu pour effet secondaire de produire une fonction véritablement dépourvue de branches. Il n'y a aucune instruction de saut.

Il apparaît que cette implémentation est 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 charéléments de tableau lors de mes tests, afin de rendre la comparaison équitable.

Je dois noter que cette approche peut être appliquée à n'importe quelle taille de tableau jusqu'à 16 éléments. Je m'attends à ce que l'avantage de vitesse relative par rapport aux alternatives augmente pour les baies plus grandes.

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

Vous pouvez le compiler dans un objet 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);
Joe Crivello
la source
Il serait intéressant de comparer la vôtre avec d'autres propositions au niveau de l'assemblage. Les performances d'implémentation comparées ne les incluent pas. L'utilisation de SSE semble bonne de toute façon.
kriss
Un autre domaine de recherche future serait l'application des nouvelles instructions Intel AVX à ce problème. Les vecteurs 256 bits plus grands sont suffisamment grands pour contenir 8 DWORD.
Joe Crivello
1
Au lieu de pxor / pinsrd xmm4, mem, 0, utilisez simplement movd!
Peter Cordes du
14

Le code de test est assez mauvais; il déborde du tableau initial (les gens ici ne lisent 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 de «l'optimiser» en 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 rejeter la fonction entière en tant que code mort.

Cela étant dit, il est également assez facile d'améliorer la solution de réseau bitonique; changez simplement les trucs 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 sort environ 65% plus rapidement pour moi (Debian gcc 4.4.5 avec -O2, amd64, Core i7).

Steinar H. Gunderson
la source
OK, le code de test est médiocre. N'hésitez pas à l'améliorer. Et oui, vous pouvez utiliser le code assembleur. Pourquoi ne pas aller jusqu'au bout et le coder entièrement en utilisant l'assembleur x86? C'est peut-être un peu moins portable, mais pourquoi s'embêter?
kriss
Merci d'avoir remarqué le débordement de la baie, je l'ai corrigé. D'autres personnes ne l'ont peut-être pas remarqué car elles ont cliqué sur le lien pour copier / coller du code, où il n'y a pas de débordement.
kriss
4
Vous n'avez même pas besoin d'assembleur, en fait; si vous déposez simplement toutes les astuces intelligentes, GCC reconnaîtra la séquence et insérera les mouvements conditionnels pour vous: #define min (a, b) ((a <b)? a: b) #define max (a, b) ( (a <b)? b: a) #define SWAP (x, y) {int a = min (d [x], d [y]); int b = max (d [x], d [y]); d [x] = a; d [y] = b; } Il sort peut-être quelques pour cent plus lentement que la variante asm en ligne, mais c'est difficile à dire étant donné le manque de benchmarking approprié.
Steinar H. Gunderson
3
… Et enfin, si vos nombres sont flottants, et que vous n'avez pas à vous soucier de NaN, etc., GCC peut le convertir en instructions SSE min / maxss, ce qui est pourtant ~ 25% plus rapide. Moral: abandonnez les astuces astucieuses et laissez le compilateur faire son travail. :-)
Steinar H. Gunderson
13

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

Je vois une amélioration (qu'un bon compilateur pourrait apporter):

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

Nous prenons note du fonctionnement de min et max et tirons explicitement la sous-expression commune. Cela élimine complètement les macros min et max.

phkahler
la source
Cela les fait reculer, notez que d [y] obtient le max, qui est x ^ (sous-expression commune).
Kevin Stock
J'ai remarqué la même chose; Je pense que pour que votre implémentation soit correcte, vous voulez d[x]au lieu de x(même pour y), et d[y] < d[x]pour l'inégalité ici (oui, différent du code min / max).
Tyler
J'ai essayé avec votre swap, mais l'optimisation locale a des effets négatifs à un niveau plus important (je suppose que cela introduit des dépendances). Et le résultat est plus lent que l'autre échange. Mais comme vous pouvez le voir avec la nouvelle solution proposée, il y avait en effet beaucoup de performances pour gagner en optimisant le swap.
kriss
12

N'optimisez jamais les valeurs min / max sans analyse comparative et sans regarder l'assemblage généré par le compilateur. Si je laisse GCC optimiser le min avec des instructions de déplacement conditionnel, j'obtiens une accélération de 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 cycles dans le code de test). Faire max avec?: Est plus ou moins le même, presque perdu dans le bruit, mais ce qui précède est un peu plus rapide. Ce SWAP est plus rapide avec GCC et Clang.

Les compilateurs font également un travail exceptionnel en matière d'allocation de registres et d'analyse d'alias, déplaçant efficacement d [x] dans les variables locales à l'avance, et ne recopiant qu'en mémoire à la fin. En fait, ils le font encore mieux que si vous travailliez entièrement avec des variables locales (comme d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]). J'écris ceci parce que vous supposez une optimisation forte et que vous essayez de déjouer le compilateur sur min / max. :)

Au fait, j'ai essayé Clang et GCC. Ils font la même optimisation, mais en raison de différences de programmation, les deux ont une certaine variation dans les résultats, ne peuvent pas vraiment dire ce qui est plus rapide ou plus lent. GCC est plus rapide sur les réseaux de tri, Clang sur les tris quadratiques.

Par souci d'exhaustivité, le tri à bulles déroulées et les tri par insertion sont également possibles. Voici la sorte de bulle:

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

et voici le tri par insertion:

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

Ce type d'insertion est plus rapide que celui de Daniel Stutzbach, et est particulièrement bon sur un GPU ou un ordinateur avec prédication car ITER peut être effectué avec seulement 3 instructions (contre 4 pour SWAP). Par exemple, voici la t = d[2]; ITER(1); ITER(0);ligne dans l'assemblage ARM:

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

Pour six éléments, le tri par insertion est compétitif avec le réseau de tri (12 swaps vs 15 itérations équilibre 4 instructions / swap vs 3 instructions / itération); sorte de bulle est bien sûr plus lent. Mais cela ne sera pas vrai lorsque la taille augmentera, car le tri par insertion est O (n ^ 2) tandis que les réseaux de tri sont O (n log n).

Paolo Bonzini
la source
1
Plus ou moins liés: j'ai soumis un rapport à GCC afin qu'il puisse implémenter l'optimisation directement dans le compilateur. Pas sûr que ce sera fait, mais au moins vous pouvez suivre son évolution.
Morwenn
11

J'ai porté la suite de tests sur une machine d'architecture PPC que je ne peux pas identifier (je n'ai pas eu à toucher au code, juste augmenter les itérations du test, utiliser 8 cas de test pour éviter de polluer les résultats avec des mods et remplacer le rdtsc spécifique x86):

Appel direct à la fonction de bibliothèque qsort : 101

Implémentation naïve (tri par insertion) : 299

Tri d'insertion (Daniel Stutzbach) : 108

Tri par insertion déroulé : 51

Réseaux de tri (Daniel Stutzbach) : 26

Réseaux de tri (Paul R) : 85

Réseaux de tri 12 avec échange rapide : 117

Réseaux de tri 12 réorganisés Échange : 116

Ordre de classement : 56

jheriko
la source
1
Vraiment intéressant. Il semble que le swap sans branche soit une mauvaise idée sur PPC. Il peut également s'agir d'un effet lié au compilateur. Lequel a été utilisé?
kriss
C'est une branche du compilateur gcc - la logique min, max n'est probablement pas sans branche - je vais inspecter le démontage et vous le faire savoir, mais à moins que le compilateur soit assez intelligent, y compris quelque chose comme x <y sans si devient toujours une branche - sur x86 / x64, l'instruction CMOV pourrait éviter cela, mais il n'existe aucune instruction de ce type pour les valeurs à virgule fixe sur PPC, uniquement des flottants. Je pourrais essayer cela demain et vous le faire savoir - je me souviens qu'il y avait un min / max sans branche beaucoup plus simple dans la source Winamp AVS, mais iirc c'était uniquement pour les flotteurs - mais cela pourrait être un bon début vers une approche vraiment sans branche.
jheriko
4
Voici un min sans agence / max pour PPC avec des entrées non signées: subfc r5,r4,r3; subfe r6,r6,r6; andc r6,r5,r6; add r4,r6,r4; subf r3,r6,r3. r3 / r4 sont des entrées, r5 / r6 sont des registres à gratter, sur la sortie r3 obtient le minimum et r4 obtient le maximum. Il devrait être décemment programmable à la main. Je l'ai trouvé avec le superoptimiseur GNU, à partir de séquences min et max de 4 instructions et en recherchant manuellement deux qui pourraient être combinées. Pour les entrées signées, vous pouvez bien sûr ajouter 0x80000000 à tous les éléments au début et le soustraire à nouveau à la fin, puis travailler comme s'ils n'étaient pas signés.
Paolo Bonzini
7

Un échange XOR peut être utile dans vos fonctions d'échange.

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

Le if peut causer trop de divergence dans votre code, mais si vous avez la garantie que toutes vos entrées sont uniques, cela pourrait être pratique.

naj
la source
1
xor swap fonctionne également pour des valeurs égales ... x ^ = y définit x à 0, y ^ = x laisse y comme y (== x), x ^ = y définit x à y
jheriko
11
Quand cela ne fonctionne pas , c'est quand xet ypointez au même endroit.
hobbs
Quoi qu'il en soit, lorsqu'il est utilisé avec des réseaux de tri, nous n'appelons jamais avec x et y pointant vers le même emplacement. Il reste à trouver un moyen d'éviter les tests qui sont plus importants pour obtenir le même effet que le swap sans branche. J'ai une idée pour y arriver.
kriss
5

J'ai hâte de m'essayer à cela et d'apprendre de ces exemples, mais d'abord quelques timings de mon Powerbook G4 PPC à 1,5 GHz avec 1 Go de RAM DDR. (J'ai emprunté une minuterie similaire à rdtsc pour PPC à http://www.mcs.anl.gov/~kazutomo/rdtsc.html pour les horaires.) J'ai exécuté le programme plusieurs fois et les résultats absolus variaient mais la cohérence le test le plus rapide a été "Insertion Sort (Daniel Stutzbach)", avec "Insertion Sort Unrolled" juste derrière.

Voici le dernier ensemble de fois:

**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
la source
4

Voici ma contribution à ce fil: un shortsort optimisé à 1, 4 espaces pour un vecteur int à 6 membres (valp) contenant des valeurs uniques.

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

Sur mon ordinateur portable HP dv7-3010so avec un Athlon M300 à 2 GHz à double cœur (mémoire DDR2), il s'exécute en 165 cycles d'horloge. Il s'agit d'une moyenne calculée à partir du chronométrage de chaque séquence unique (6! / 720 en tout). Compilé sur Win32 à l'aide d'OpenWatcom 1.8. La boucle est essentiellement un tri par insertion et comporte 16 instructions / 37 octets.

Je n'ai pas d'environnement 64 bits pour compiler.

Olof Forshell
la source
agréable. Je vais l'ajouter à la suite de tests plus longue
kriss
3

Si le tri par insertion est raisonnablement compétitif ici, je recommanderais d'essayer un shellsort. Je crains que 6 éléments ne soient probablement pas assez pour être parmi les meilleurs, mais cela pourrait valoir la peine d'être essayé.

Exemple de code, non testé, non débogué, etc. Vous voulez régler la séquence inc = 4 et inc - = 3 pour trouver l'optimum (essayez inc = 2, inc - = 1 par exemple).

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

Je ne pense pas que cela gagnera, mais si quelqu'un poste une question sur le tri de 10 éléments, qui sait ...

Selon Wikipedia, cela peut même être combiné avec des réseaux de tri: Pratt, V (1979). Shellsort and sorting networks (Thèses exceptionnelles en informatique). Guirlande. ISBN 0-824-04406-1

gcp
la source
n'hésitez pas à proposer une implémentation :-)
kriss
Proposition ajoutée. Profitez des bugs.
gcp
3

Je sais que je suis super en retard, mais j'étais intéressé à expérimenter différentes solutions. Tout d'abord, j'ai nettoyé cette pâte, je l'ai compilée et placée dans un référentiel. J'ai gardé des solutions indésirables comme des impasses afin que d'autres ne l'essaient pas. Parmi celles-ci figurait ma première solution, qui tentait de s'assurer que x1> x2 était calculé une fois. Après optimisation, elle n'est pas plus rapide que les autres versions simples.

J'ai ajouté une version en boucle du tri par ordre de classement, car ma propre application de cette étude est de trier 2 à 8 éléments, donc comme il y a un nombre variable d'arguments, une boucle est nécessaire. C'est aussi pourquoi j'ai ignoré les solutions de réseau de tri.

Le code de test n'a pas testé que les doublons étaient traités correctement, donc bien que les solutions existantes soient toutes correctes, j'ai ajouté un cas spécial au code de test pour m'assurer que les doublons ont été traités correctement.

Ensuite, j'ai écrit une sorte d'insertion qui est entièrement dans les registres AVX. Sur ma machine, il est 25% plus rapide que les autres types d'insertion, mais 100% plus lent que l'ordre de classement. Je l'ai fait uniquement pour l'expérience et je ne m'attendais pas à ce que cela soit mieux en raison de la ramification en tri par insertion.

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
}

Ensuite, j'ai écrit un tri par ordre de classement en utilisant AVX. Cela correspond à la vitesse des autres solutions de classement, mais n'est pas plus rapide. Le problème ici est que je ne peux calculer les indices qu'avec AVX, puis je dois faire un tableau des indices. En effet, le calcul est basé sur la destination plutôt que sur la source. Voir Conversion d'indices basés sur la source en indices basés sur la destination

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

Le repo peut être trouvé ici: https://github.com/eyepatchParrot/sort6/

2 tours
la source
1
Vous pouvez utiliser vmovmskpssur des vecteurs entiers (avec un cast pour garder les intrinsèques heureux), en évitant d'avoir à déplacer à droite le résultat bitscan ( ffs).
Peter Cordes
1
Vous pouvez ajouter conditionnellement 1 en fonction d'un cmpgtrésultat en le soustrayant , au lieu de le masquer avec set1(1). par exemple , index = _mm256_sub_epi32(index, gt)faitindex -= -1 or 0;
Peter Cordes
1
eq = _mm256_insert_epi32(eq, 0, I)n'est pas un moyen efficace de mettre à zéro un élément s'il se compile tel qu'il est écrit (en particulier pour les éléments en dehors du 4 bas, car il vpinsrdn'est disponible qu'avec une destination XMM; les indices supérieurs à 3 doivent être émulés). Au lieu de cela, _mm256_blend_epi32( vpblendd) avec un vecteur mis à zéro. vpblenddest une instruction simple uop qui s'exécute sur n'importe quel port, par rapport à un shuffle qui a besoin du port 5 sur les processeurs Intel. ( agner.org/optimize ).
Peter Cordes
1
En outre, vous pouvez envisager de générer des rotvecteurs avec des shuffles différents à partir de la même source, ou au moins exécuter 2 chaînes dep en parallèle que vous utilisez alternativement, au lieu d'une seule chaîne dep via un shuffle de franchissement de voie (latence de 3 cycles). Cela augmentera l'ILP dans un seul type. 2 chaînes dep limitent le nombre de constantes vectorielles à un nombre raisonnable, juste 2: 1 pour une rotation et une pour 2 étapes de rotation combinées.
Peter Cordes
2

Cette question devient assez ancienne, mais j'ai dû résoudre le même problème de nos jours: des agorithmes rapides pour trier les petits tableaux. J'ai pensé que ce serait une bonne idée de partager mes connaissances. Alors que j'ai commencé par utiliser des réseaux de tri, j'ai finalement réussi à trouver d'autres algorithmes pour lesquels le nombre total de comparaisons effectuées pour trier chaque permutation de 6 valeurs était plus petit qu'avec les réseaux de tri, et plus petit qu'avec le tri par insertion. Je n'ai pas compté le nombre de swaps; Je m'attendrais à ce qu'il soit à peu près équivalent (peut-être un peu plus élevé parfois).

L'algorithme sort6utilise l'algorithme sort4qui utilise l'algorithme sort3. Voici l'implémentation sous une forme C ++ légère (l'original est lourd de modèles afin qu'il puisse fonctionner avec n'importe quel itérateur à accès aléatoire et toute fonction de comparaison appropriée).

Tri de 3 valeurs

L'algorithme suivant est un tri par insertion non déroulé. Lorsque deux swaps (6 affectations) doivent être effectués, il utilise à la place 4 affectations:

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

Cela semble un peu complexe car le tri a plus ou moins une branche pour chaque permutation possible du tableau, en utilisant 2 à 3 comparaisons et au plus 4 affectations pour trier les trois valeurs.

Tri de 4 valeurs

Celui-ci appelle sort3ensuite effectue un tri par insertion non déroulé avec le dernier élément du tableau:

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

Cet algorithme effectue 3 à 6 comparaisons et au plus 5 swaps. Il est facile de dérouler un tri par insertion, mais nous utiliserons un autre algorithme pour le dernier tri ...

Tri de 6 valeurs

Celui-ci utilise une version déroulée de ce que j'ai appelé un tri à double insertion . Le nom n'est pas génial, mais il est assez descriptif, voici comment cela fonctionne:

  • Triez tout sauf les premier et dernier éléments du tableau.
  • Échangez le premier et les éléments du tableau si le premier est supérieur au dernier.
  • Insérez le premier élément dans la séquence triée par l'avant puis le dernier élément par l'arrière.

Après l'échange, le premier élément est toujours plus petit que le dernier, ce qui signifie que, lors de leur insertion dans la séquence triée, il n'y aura pas plus de N comparaisons pour insérer les deux éléments dans le pire des cas: par exemple, si le le premier élément a été inséré en 3e position, puis le dernier ne peut pas être inséré plus bas que la 4e 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]);
                }
            }
        }
    }
}

Mes tests sur chaque permutation de 6 valeurs montrent que cet algorithme effectue toujours entre 6 et 13 comparaisons. Je n'ai pas calculé le nombre de swaps effectués, mais je ne m'attends pas à ce qu'il soit supérieur à 11 dans le pire des cas.

J'espère que cela aide, même si cette question ne représente plus un problème réel :)

EDIT: après l'avoir mis dans le benchmark fourni, il est clairement plus lent que la plupart des alternatives intéressantes. Il a tendance à fonctionner un peu mieux que le type d'insertion déroulée, mais c'est à peu près tout. Fondamentalement, ce n'est pas le meilleur tri pour les entiers mais pourrait être intéressant pour les types avec une opération de comparaison coûteuse.

Morwenn
la source
Ce sont bien. Comme le problème résolu est vieux de plusieurs décennies, probablement aussi ancien qu'une programmation C, la question qui a maintenant près de 5 ans ne semble pas très pertinente.
kriss
Vous devriez voir comment les autres réponses sont chronométrées. Le fait est qu'avec un si petit ensemble de données, les comparaisons de comptage ou même les comparaisons et les échanges ne disent pas vraiment à quelle vitesse un algorithme (en gros, trier 6 entrées est toujours O (1) parce que O (6 * 6) est O (1)). La solution la plus rapide actuellement proposée consiste à trouver immédiatement la position de chaque valeur à l'aide d'une grande comparaison (par RexKerr).
kriss
@kriss Est-ce le plus rapide maintenant? De ma lecture des résultats, l'approche des réseaux de tri a été la plus rapide, ma mauvaise. Il est également vrai que ma solution provient de ma bibliothèque générique et que je ne compare pas toujours des entiers, ni que j'utilise toujours operator<pour la comparaison. Outre le nombre objectif de comparaisons et d'échanges, j'ai également correctement chronométré mes algorithmes; cette solution était la plus rapide générique, mais j'ai en effet raté celle de @ RexKerr. Je vais l'essayer :)
Morwenn
La solution de RexKerr (Order Rank) est devenue la plus rapide sur l'architecture X86 depuis le compilateur gcc 4.2.3 (et à partir de gcc 4.9 est devenue presque deux fois plus rapide que la deuxième meilleure). Mais cela dépend fortement des optimisations du compilateur et peut ne pas être vrai sur d'autres architectures.
kriss
@kriss C'est intéressant à savoir. Et je pourrais en effet encore plus de différences avec -O3. Je suppose que j'adopterai alors une autre stratégie pour ma bibliothèque de tri: fournir trois types d'algorithmes pour avoir soit un faible nombre de comparaisons, un faible nombre de swaps ou potentiellement les meilleures performances. Au moins, ce qui se passera sera transparent pour le lecteur. Merci pour vos idées :)
Morwenn
1

Je pense que votre question comporte deux parties.

  • La première consiste à déterminer l'algorithme optimal. Cela se fait - au moins dans ce cas - en parcourant tous les ordres possibles (il n'y en a pas beaucoup), ce qui vous permet de calculer l'écart min, max, moyen et standard exact des comparaisons et des swaps. Ayez aussi un finaliste ou deux à portée de main.
  • La seconde consiste à optimiser l'algorithme. Beaucoup peut être fait pour convertir des exemples de code de manuel en algorithmes réels et simples. Si vous vous rendez compte qu'un algorithme ne peut pas être optimisé dans la mesure requise, essayez un finaliste.

Je ne m'inquiéterais pas trop de vider les pipelines (en supposant le x86 actuel): la prédiction de branche a parcouru un long chemin. Ce qui m'inquiéterait, c'est de m'assurer que le code et les données tiennent dans une ligne de cache chacun (peut-être deux pour le code). Une fois qu'il y a fetch, les latences sont rafraîchissantes, ce qui compensera tout blocage. Cela signifie également que votre boucle interne comportera peut-être une dizaine d'instructions, ce qui est exactement là où elle devrait être (il y a deux boucles internes différentes dans mon algorithme de tri, elles sont respectivement de 10 instructions / 22 octets et 9/22 de long). En supposant que le code ne contient pas de divs, vous pouvez être sûr qu'il sera incroyablement rapide.

Olof Forshell
la source
Je ne sais pas comment comprendre votre réponse. Tout d'abord, je ne comprends pas du tout quel algorithme vous proposez? Et comment cela pourrait être optimal si vous devez parcourir 720 commandes possibles (les réponses existantes prennent beaucoup moins de 720 cycles). Si vous avez une entrée aléatoire, je ne peux pas imaginer (même au niveau théorique) comment la prédiction de branche pourrait fonctionner mieux que 50-50, sauf si elle ne se soucie pas du tout des données d'entrée. De plus, la plupart des bonnes solutions déjà proposées sont déjà susceptibles de fonctionner avec les données et le code entièrement dans le cache. Mais j'ai peut-être complètement mal compris votre réponse. Vous voulez montrer du code?
kriss
Ce que je voulais dire, c'est qu'il n'y a que 720 (6!) Combinaisons différentes de 6 entiers et en les exécutant tous à travers les algorithmes candidats, vous pouvez déterminer beaucoup de choses comme je l'ai mentionné - c'est la partie théorique. La partie pratique consiste à affiner cet algorithme pour qu'il fonctionne le moins de cycles d'horloge possible. Mon point de départ pour trier 6 entiers est un shortsort de 1, 4 trous. L'écart 4 ouvre la voie à une bonne prédiction de branche dans l'écart 1.
Olof Forshell
Le shortsort 1, 4 écart pour 6! les combinaisons uniques (commençant par 012345 et se terminant par 543210) auront un meilleur cas de 7 comparaisons et 0 échanges et un pire de 14 comparaisons et 10 échanges. Le cas moyen est d'environ 11,14 comparaisons et 6 échanges.
Olof Forshell
1
Je ne reçois pas la "distribution aléatoire régulière" - ce que je fais, c'est tester toutes les combinaisons possibles et déterminer les statistiques min / moyenne / max. Shellsort est une série d'incréments décroissants d'insertion de sorte que l'incrément final - 1 - fait beaucoup moins de travail que s'il est effectué tout seul comme dans un tri par insertion pure. Quant au comptage d'horloge, mon algorithme nécessite 406 cycles d'horloge en moyenne, ce qui comprend la collecte de statistiques et deux appels à la routine de tri réelle - un pour chaque intervalle. C'est sur un Athlon M300 mobile, compilateur OpenWatcom.
Olof Forshell
1
"distribution aléatoire régulière" signifie que toutes les combinaisons de données réelles qui sont triées peuvent ne pas être de probabilité égale. Si toutes les combinaisons ne sont pas de probabilité égale, vos statistiques sont brisées car la moyenne doit prendre en compte le nombre de fois qu'une distribution donnée est susceptible de se produire. Pour le décompte d'horloge, si vous essayez une autre implémentation de ce type (liens fournis ci-dessus) et que vous l'exécutez sur votre système de test, nous aurons une base de comparaison et verrons dans quelle mesure celle que vous avez choisie fonctionne.
Kriss
1

Je sais que c'est une vieille question.

Mais je viens d'écrire un autre type de solution que je veux partager.
En n'utilisant que du MIN MAX imbriqué,

Ce n'est pas rapide car il utilise 114 de chacun,
pourrait le réduire à 75 tout simplement comme ça -> pastebin

Mais ce n'est plus purement min max.

Ce qui pourrait fonctionner, c'est de faire min / max sur plusieurs entiers à la fois avec AVX

Référence PMINSW

#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:
solution de classement basée sur Rex Kerr, beaucoup plus rapide que le gâchis ci-dessus

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
la source
1
toujours agréable de voir de nouvelles solutions. Il semble qu'une optimisation simple soit possible. En fin de compte, cela peut ne pas être si différent des réseaux de tri.
kriss
Oui, le nombre de MIN et MAX pourrait éventuellement être réduit, par exemple MIN (AB, CD) se répète plusieurs fois, mais les réduire beaucoup sera difficile je pense. J'ai ajouté vos cas de test.
PrincePolka
pmin / maxsw fonctionne sur des entiers signés 16 bits compressés ( int16_t). Mais votre fonction C prétend qu'elle trie un tableau de int(qui est de 32 bits dans toutes les implémentations C qui prennent en charge cette asmsyntaxe). L'avez-vous testé avec seulement de petits entiers positifs qui n'ont que 0 dans leurs moitiés hautes? Cela fonctionnera ... Pour intvous avez besoin de SSE4.1 pmin/maxsd(d = dword). felixcloutier.com/x86/pminsd:pminsq ou pminusdpour uint32_t.
Peter Cordes
1

J'ai constaté qu'au moins sur mon système, les fonctions sort6_iterator()et sort6_iterator_local()définies ci-dessous fonctionnaient toutes les deux au moins aussi rapidement, et souvent sensiblement plus vite, que le détenteur du record actuel ci-dessus:

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

J'ai passé cette fonction un std::vectoritérateur dans mon code temporel.

Je soupçonne (à partir de commentaires comme celui-ci et ailleurs) que l'utilisation d'itérateurs donne à g ++ certaines assurances sur ce qui peut et ne peut pas arriver à la mémoire à laquelle l'itérateur fait référence, ce qu'il n'aurait pas autrement et ce sont ces assurances qui permettent à g ++ de mieux optimiser le code de tri (par exemple avec des pointeurs, le compilateur ne peut pas être sûr que tous les pointeurs pointent vers des emplacements mémoire différents). Si je me souviens bien, cela fait également partie de la raison pour laquelle tant d'algorithmes STL, tels que std::sort(), ont généralement de si bonnes performances.

De plus, sort6_iterator()est quelques fois (encore une fois, en fonction du contexte dans lequel la fonction est appelée) surclassent par la fonction de tri suivant, qui copie les données dans les variables locales avant de les trier. 1 Notez que comme il n'y a que 6 variables locales définies, si ces variables locales sont des primitives, elles ne sont probablement jamais réellement stockées dans la RAM et ne sont plutôt stockées que dans les registres du CPU jusqu'à la fin de l'appel de fonction, ce qui aide à effectuer ce tri. fonctionner rapidement. (Cela aide également le compilateur à savoir que des variables locales distinctes ont des emplacements distincts en mémoire).

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
}

Notez que la définition SWAP()suit comme des résultats parfois dans des performances légèrement meilleures , bien que la plupart du temps , il en résulte un peu moins bonnes performances ou une différence négligeable dans la performance.

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

Si vous voulez juste un algorithme de tri qui sur les types de données primitifs, gcc -O3 est toujours bon pour optimiser quel que soit le contexte dans lequel l'appel à la fonction de tri apparaît en 1, puis, selon la façon dont vous passez l'entrée, essayez l'une des deux suivantes algorithmes:

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
}

Ou si vous souhaitez passer les variables par référence, utilisez-la (la fonction ci-dessous diffère de la précédente dans ses 5 premières lignes):

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
}

La raison de l'utilisation du registermot-clé est que c'est l'une des rares fois où vous savez que vous voulez ces valeurs dans les registres. Sans register, le compilateur trouvera cela la plupart du temps, mais parfois ce n'est pas le cas. L'utilisation du registermot clé permet de résoudre ce problème. Normalement, cependant, n'utilisez pas le registermot - clé car il est plus susceptible de ralentir votre code que de l'accélérer.

Notez également l'utilisation de modèles. Cela est fait exprès car, même avec le inlinemot - clé, les fonctions de modèle sont généralement beaucoup plus agressivement optimisées par gcc que les fonctions vanilla C (cela a à voir avec gcc devant traiter des pointeurs de fonction pour les fonctions vanilla C mais pas avec les fonctions de modèle).

  1. Lors du chronométrage de diverses fonctions de tri, j'ai remarqué que le contexte (c'est-à-dire le code environnant) dans lequel l'appel à la fonction de tri a été effectué a eu un impact significatif sur les performances, ce qui est probablement dû à la fonction en ligne puis optimisée. Par exemple, si le programme était suffisamment simple, il n'y avait généralement pas beaucoup de différence de performance entre passer la fonction de tri d'un pointeur et lui passer un itérateur; Sinon, l'utilisation d'itérateurs a généralement entraîné des performances sensiblement meilleures et jamais (du moins d'après mon expérience jusqu'à présent) des performances sensiblement inférieures. Je soupçonne que cela peut être dû au fait que g ++ peut globalement optimiser un code suffisamment simple.
Matthew K.
la source
0

Essayez de «fusionner la liste triée». :) Utilisez deux tableaux. Le plus rapide pour les petits et grands réseaux.
Si vous concédez, vous vérifiez seulement où insérer. D'autres valeurs plus importantes que vous n'avez pas besoin de comparer (cmp = ab> 0).
Pour 4 numéros, vous pouvez utiliser le système 4-5 cmp (~ 4,6) ou 3-6 cmp (~ 4,9). Le tri à bulles utilise 6 cmp (6). Beaucoup de cmp pour les grands nombres de code plus lent.
Ce code utilise 5 cmp (pas le tri MSL):
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

code js

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
la source
0

Triez 4 éléments avec l'utilisation cmp == 0. Le nombre de cmp est ~ 4.34 (FF native a ~ 4.52), mais prend 3 fois plus de temps que la fusion des listes. Mais il vaut mieux moins d'opérations cmp, si vous avez de gros nombres ou du gros texte. Edit: bug réparé

Test en ligne 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
la source
1
Le cas d'utilisation est légèrement différent du contexte initial de la question. Avec des tris de longueur fixe, les détails comptent et le calcul du nombre de swaps n'est pas suffisant. Je ne serais même pas surpris si ce n'était pas du tout le type réel qui consommerait du temps, mais quelque chose de complètement différent appelant la lumière typeof () dans l'init. Je ne sais pas comment effectuer la mesure réelle du temps d'horloge en utilisant Javascript. Peut-être avec noeud?
kriss
0

Je suis peut -être en retard à la fête, mais au moins ma contribution est une nouvelle approche.

  • Le code devrait vraiment être intégré
  • même en ligne, il y a trop de branches
  • la partie analysante est essentiellement O (N (N-1)) ce qui semble OK pour N = 6
  • le code pourrait être plus efficace si le coût deswap était plus élevé (irt le coût de compare)
  • J'espère que les fonctions statiques seront intégrées.
  • La méthode est liée au classement par rang
    • au lieu des classements, les classements relatifs (décalages) sont utilisés.
    • la somme des rangs est nulle pour chaque cycle dans n'importe quel groupe de permutation.
    • au lieu d' SWAP()ingérer deux éléments, les cycles sont poursuivis, ne nécessitant qu'un seul temp, et un swap (registre-> registre) (nouveau <- ancien).

Mise à jour: changé un peu le code, certaines personnes utilisent des compilateurs C ++ pour compiler du code C ...

#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
la source
ressemble à une sorte de bulle. Potentiellement un bon candidat pour l'implémentation la plus lente, mais il peut être toujours intéressant de savoir si le travail sur le code fait une telle différence. Veuillez mettre votre code au même format que les autres, afin que nous puissions exécuter le benchmark dessus.
kriss
@kriss en.wikipedia.org/wiki/Permutation_group Ce n'est certainement pas du type à bulles: le code détecte les cycles dans la permutation donnée, et parcourt ces cycles, en plaçant chaque élément à sa place finale. La wsort6()fonction finale a la bonne interface.
joop
@joop: mon mauvais, aucune sorte de bulle en effet. Cela étant dit dans le contexte, je m'attends toujours à ce que le code soit bien pire que toute autre implémentation actuelle. Par ailleurs, la solution Rank Order est optimale en ce qui concerne le nombre de swaps car elle trouve directement la position finale de chaque élément. Il est également difficile de savoir si la marche arrière fonctionne même lorsque nous supprimons l'hypothèse selon laquelle tous les numéros triés sont différents comme ici. Pour comparer le code, nous devons utiliser le code de trace. De plus, comme je compile généralement sur un compilateur C ++, le code ne fonctionnera pas parce que l'OP a appelé une variable "nouveau" (et cela rompt la mise en évidence de la syntaxe).
kriss
La méthode est très proche de l'ordre de classement, seules les affectations finales sont effectuées sur place . En dehors des rangs o1..o5, il n'est pas nécessaire d'avoir le deuxième e[6]tableau temporaire . Et: compiler du code C sur un compilateur C ++ et blâmer le code?
joop
@greybeard: merci, j'ai ajouté un espace avant #include. Corrigé
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
la source
Quelle que soit la vitesse, êtes-vous sûr que cela fonctionne? Dans le tri par bruteforce, vos boucles sont douteuses. Il me semble qu'ils ne fonctionneront pas si nous avons un zéro dans les valeurs triées.
kriss
1
Le tableau t [6] est initialisé à 0x0. Peu importe où et si une clé de valeur 0x0 sera écrite.
FranG
-1

Eh bien, si ce n'est que 6 éléments et que vous pouvez tirer parti du parallélisme, vous voulez minimiser la ramification conditionnelle, etc. Pourquoi ne générez-vous pas toutes les combinaisons et testez-vous l'ordre? Je m'aventurerais que dans certaines architectures, cela peut être assez rapide (tant que la mémoire est préallouée)

GClaramunt
la source
9
Il y a 720 commandes, et les versions rapides sont bien en dessous de 100 cycles. Même si un parallélisme massif pouvait être utilisé, à une si petite échelle de temps, le coût de création et de synchronisation des threads dépasserait probablement le coût du simple tri des tableaux sur un cœur.
Kevin Stock
-3

Voici trois méthodes de tri typiques qui représentent trois classes différentes d'algorithmes de tri:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

Mais consultez la discussion de Stefan Nelsson sur l'algorithme de tri le plus rapide? où il discute d'une solution qui descend jusqu'à O(n log log n).. vérifier sa mise en œuvre en C

Cet algorithme de tri semi-linéaire a été présenté par un article en 1995:

A. Andersson, T. Hagerup, S. Nilsson et R. Raman. Tri en temps linéaire? Dans Actes du 27e Symposium annuel ACM sur la théorie de l'informatique, pages 427-436, 1995.

Khaled A Khunaifer
la source
8
C'est intéressant mais hors de propos. Big-Θ est destiné à masquer les facteurs constants et à montrer la tendance lorsque la taille du problème (n) devient importante. Le problème ici concerne entièrement une taille de problème fixe (n = 6) et la prise en compte de facteurs constants.
kriss
@kriss vous avez raison, ma comparaison est asymptotique, donc la comparaison pratique montrera si c'est plus rapide ou non pour ce cas
Khaled.K
4
Vous ne pouvez pas conclure, car chaque algorithme différent cache une constante multiplicative K différente (et également une constante additive C). c'est-à-dire: k0, c0 pour le tri par insertion, k1, c1 pour le tri en tas et ainsi de suite. Toutes ces constantes étant en fait différentes (vous pourriez dire en termes physiques que chaque algorithme a son propre "coefficient de frottement"), vous ne pouvez pas conclure qu'un algorithme est en fait plus rapide dans ce cas (ou tout n fixe).
kriss