Le tri le plus rapide d'un tableau de 6 int de longueur fixe

Question

Répondant à une autre question de Stack Overflow ( celui-ci ) Je suis tombé sur un sous-problème intéressant. Quel est le moyen le plus rapide de trier un tableau de 6 entiers ?

Comme la question est de très bas niveau :

• on ne peut pas supposer que les bibliothèques sont disponibles (et l'appel lui-même a un coût), seul le C simple est disponible.
• afin d'éviter de vider le pipeline d'instructions (qui possède un très coût élevé), nous devrions probablement minimiser les branches, les sauts et tout autre type de rupture du flux de contrôle (comme ceux qui se cachent derrière les points de séquence dans && ou ||).
• Si l'espace est limité et qu'il faut minimiser l'utilisation des registres et de la mémoire, l'idéal est probablement de trier sur place.

En réalité, 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. J'appelle cela le code "Zening", comme utilisé dans le titre du livre. Optimisation du code Zen par Michael Abrash et son séquelles .

Quant à savoir pourquoi c'est intéressant, il y a plusieurs niveaux :

• l'exemple est simple et facile à comprendre et à mesurer, il n'implique pas beaucoup de compétences C
• 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 mon implémentation 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 que l'on peut trouver à l'adresse suivante ici . Les tests réels utilisés sont un peu moins naïfs que ceux présenté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 cibles et compilateurs. (OK les gars, mettez-le dans les réponses, je vais +1 chaque contributeur d'un nouveau jeu 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 la bibliothèque qsort : 689.38
• Implémentation naïve (tri par insertion) : 285.70
• Tri d'insertion (Daniel Stutzbach) : 142.12
• Insertion Sort Unrolled : 125.47
• Ordre de classement : 102.26
• Ordre de classement avec les registres : 58.03
• Réseaux de tri (Daniel Stutzbach) : 111.68
• Réseaux de triage (Paul R) : 66.36
• Tri des réseaux 12 avec Fast Swap : 58.86
• Tri des réseaux 12 réordonnés Swap : 53.74
• Réseaux de triage 12 réordonnés Simple Swap : 31.54
• Réseau de triage réordonné avec échange rapide : 31.54
• Réseau de tri réordonné avec échange rapide V2 : 33.63
• Tri à bulles incluses (Paolo Bonzini) : 48.85
• Unrolled Insertion Sort (Paolo Bonzini) : 75.30

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

• Appel direct à la fonction de la bibliothèque qsort : 705.93
• Implémentation naïve (tri par insertion) : 135.60
• Tri d'insertion (Daniel Stutzbach) : 142.11
• Insertion Sort Unrolled : 126.75
• Ordre de classement : 46.42
• Ordre de classement avec les registres : 43.58
• Réseaux de tri (Daniel Stutzbach) : 115.57
• Réseaux de triage (Paul R) : 64.44
• Tri des réseaux 12 avec Fast Swap : 61.98
• Tri des réseaux 12 réordonnés Swap : 54.67
• Réseaux de triage 12 réordonnés Simple Swap : 31.54
• Réseau de triage réordonné avec échange rapide : 31.24
• Réseau de tri réordonné avec échange rapide V2 : 33.07
• Tri à bulles en ligne (Paolo Bonzini) : 45.79
• Unrolled Insertion Sort (Paolo Bonzini) : 80.15

J'ai inclus les résultats de -O1 et -O2 parce que, é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 suis demandé si l'effet principal n'était pas d'éviter la boucle externe. J'ai fait un essai en déroulant le tri d'insertion 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'à présent. Le code réel que j'ai utilisé pour tester est ici . Nous ne savons pas encore pourquoi il est presque deux fois plus rapide que l'autre mise en œuvre du réseau de tri. Passage de paramètres ? Maximisation rapide ?

Tri des réseaux 12 SWAP avec Fast Swap

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

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

Appel de la bibliothèque qsort

Pour donner un autre point de référence, j'ai également essayé, comme suggéré, d'appeler la bibliothèque qsort (le code est le suivant 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 problème principal semble être le chargement initial de la bibliothèque après le premier appel, et il ne se compare pas si mal avec les autres versions. Il est juste entre 3 et 20 fois plus lent sur mon Linux. Sur certaines architectures utilisées par d'autres pour les tests, il semble même être plus rapide (je suis vraiment surpris par cela, 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, on calcule directement sa position finale. Cette méthode est efficace car le calcul de l'ordre de classement ne nécessite pas de branche. L'inconvénient de cette méthode est qu'elle nécessite 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 des performances sont très surprenants (et intéressants). Sur mon architecture de référence avec un système d'exploitation 32 bits et un Intel Core2 Quad E8300, le nombre de cycles était légèrement inférieur à 1000 (comme des réseaux de tri avec swap de branchement). Mais lorsqu'il a été compilé et exécuté sur ma machine 64 bits (Intel Core2 Duo), il s'est beaucoup mieux comporté : il est devenu le plus rapide à ce jour. J'ai finalement trouvé la vraie raison. Ma boîte 32 bits utilise gcc 4.4.1 et ma boîte 64 bits gcc 4.4.3 et la dernière semble bien meilleure pour optimiser ce code particulier (il y avait très peu de différence pour les autres propositions).

Tri des réseaux 12 avec Swap réordonné

L'efficacité étonnante de la proposition de Rex Kerr avec gcc 4.4.3 m'a fait me demander : comment un programme utilisant 3 fois plus de mémoire pouvait-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, ce qui permettait une meilleure utilisation de l'ordonnanceur d'instructions superscalaires du x86. Cela m'a donné une idée : réorganiser les swaps pour minimiser les dépendances de type lecture après écriture. Plus simplement : lorsque vous faites 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 effectuez 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 s'exécutent environ 10% plus vite.

Tri des réseaux 12 avec Simple Swap

Un an après le post original, Steinar H. Gunderson a suggéré que nous ne devrions pas essayer d'être plus malins que le compilateur et garder le code swap 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 du code d'assemblage en ligne x86 qui peut encore épargner quelques cycles supplémentaires. Le plus surprenant (cela en dit long sur la psychologie des programmeurs) est qu'il y a un an, aucun d'entre nous n'a essayé cette version du swap. Le code que j'ai utilisé pour tester est ici . D'autres ont suggéré d'autres façons d'écrire un swap rapide en C, mais il donne les mêmes performances que le simple swap 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 l'on en croit notre jeu de tests (et, oui, il est assez pauvre, son seul avantage est d'être court, simple et facile à comprendre ce que nous mesurons), le nombre moyen de cycles du code résultant pour un tri est inférieur à 40 cycles (6 tests sont exécutés). Cela met chaque échange à une moyenne de 4 cycles. J'appelle cela incroyablement rapide. D'autres améliorations sont-elles possibles ?

Answer 1

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 devais parier, je miserais sur le tri par insertion, compte tenu de l'expérience passée.

Savez-vous quoi que ce soit sur les données d'entrée ? Certains algorithmes sont plus performants avec certains types de données. Par exemple, le tri par insertion est plus performant sur des données triées ou presque triées. Il sera donc le meilleur choix s'il y a une probabilité 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 d'un plus grand nombre de comparaisons. Les comparaisons sont cependant beaucoup plus coûteuses que les échanges, car les branches peuvent provoquer le blocage du pipeline d'instructions.

Voici une mise en œuvre du 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 construirais un réseau de tri. D'abord, utilisez ce site pour générer un ensemble minimal de macros SWAP pour un réseau de la longueur appropriée. Enrouler 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
}

Answer 2

Voici une mise en œuvre utilisant réseaux de triage :

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 d'un système sans branchements très efficace min et max Je ne connais pas d'implémentations pour cela, puisque c'est effectivement ce à quoi ce code se résume - une chaîne d'opérations min et max (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 (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 distorsion, etc.)

Voir aussi : http://stackoverflow.com/questions/2748749/fast-algorithm-implementation-to-sort-very-small-set/

Answer 3

Puisqu'il s'agit d'entiers et que les comparaisons sont rapides, pourquoi ne pas calculer directement l'ordre de classement de chacun d'entre eux ?

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

Answer 4

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

En regardant l'assemblage généré par gcc 4.5.2, j'ai observé que des chargements et des stockages sont effectués pour chaque swap, 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 à nouveau en mémoire. J'ai ordonné les chargements et les stockages pour qu'ils soient aussi proches que possible de l'endroit où les registres sont utilisés en premier et en dernier. J'ai également utilisé la macro SWAP de Steinar H. Gunderson. Mise à jour : J'ai changé pour la macro SWAP de Paolo Bonzini que gcc convertit en quelque chose de similaire à celle de Gunderson, mais gcc est capable de mieux ordonner les instructions puisqu'elles ne sont pas données en tant qu'assemblage explicite.

J'ai utilisé le même ordre d'échange que le réseau d'échange réordonné donné comme le plus performant, bien qu'il puisse y avoir un meilleur ordre. Si je trouve un peu plus de temps, je vais générer et tester un certain nombre de permutations.

J'ai modifié le code de test pour prendre en compte plus de 4000 tableaux et montrer le nombre moyen de cycles nécessaires pour trier chacun d'entre eux. Sur un i5-650, j'obtiens ~34,1 cycles/tri (en utilisant -O3), alors que le réseau de tri réordonné original obtient ~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 changé modifié la suite de tests pour rapporter également les horloges par tri et effectuer plus de tests (la fonction cmp a été mise à jour pour gérer les débordements d'entiers également), voici les résultats sur quelques architectures différentes. 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

Answer 5

J'ai trouvé cette question sur 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 l'obligation stricte d'utiliser uniquement le langage C. J'ai pensé que je partagerais quand même mes résultats, au cas où ils pourraient être utiles à quelqu'un...

J'ai implémenté une variante d'un tri réseau en assembleur 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 brassage pour PSHUFB (échange vectorisé), en utilisant seulement une instruction PADDB (addition vectorisée) et dans certains cas aussi une instruction PAND (ET bit à bit).

Cette approche a également eu pour effet secondaire d'aboutir à une vraiment fonction sans branchement. Il n'y a aucune instruction de saut.

Il semble que cette mise en œuvre est environ 38% plus rapide que l'implémentation qui est actuellement marquée comme l'option la plus rapide dans la question ("Sorting Networks 12 with Simple Swap"). J'ai modifié cette implémentation pour utiliser char éléments du tableau pendant mes tests, pour rendre la comparaison équitable.

Je dois noter que cette approche peut être appliquée à toute taille de tableau jusqu'à 16 éléments. Je m'attends à ce que l'avantage relatif en termes de vitesse par rapport aux autres solutions soit plus important pour les tableaux plus grands.

Le code est écrit en MASM pour les processeurs x86_64 avec SSE 4.1. La fonction utilise la "nouvelle" convention d'appel de Windows x64. Le voici...

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

    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
    pextrb byte ptr [rcx + 4], xmm4, 4
    pextrb byte ptr [rcx + 5], xmm4, 5

    ret

simd_sort_6 ENDP

END

Vous pouvez le compiler en un objet exécutable et le lier à votre projet C. Pour obtenir des instructions sur la manière 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);