Type le plus rapide de tableau de longueur fixe 6 int

répondant à une autre question sur le débordement de la pile ( celle-ci ), je suis tombé sur un sous-problème intéressant. Quelle est la manière la plus rapide de trier un tableau de 6 ints?

Comme la question est de très bas niveau:

  • nous ne pouvons pas assumer les bibliothèques sont disponibles (et l'appel lui-même a de son coût), seulement de la plaine C
  • pour éviter de vider le pipeline d'instruction (qui a un très coûts élevés) nous devrions probablement réduire au minimum les branches, les sauts et tout autre type de bris du flux de contrôle (comme ceux qui sont cachés derrière les points de séquence dans && ou || ).
  • la salle est limitée et minimiser les registres et l'utilisation de la mémoire est un problème, idéalement en place tri est probablement mieux.

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 "Zening' code utilisé dans le titre du livre Zen d'optimisation de Code par Michael Abrash et ses Suites .

quant à savoir pourquoi c'est intéressant, il y a plusieurs couches:

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

Voici mon implémentation de référence (naïve, non optimisée) et mon test set.

#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 est de plus en plus grand, je les ai tous réunis dans une suite de test qui peut être trouvé ici . Les tests utilisés sont un peu moins naïfs que ceux présentés ci-dessus, grâce à Kevin Stock. Vous pouvez compiler et de l'exécuter dans votre propre environnement. Je suis assez intéressé par le comportement sur l'architecture cible/compilateurs différents. (OK les gars, mettez - le dans les réponses, je vais +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 à la source de la solution la plus rapide à cette époque (réseaux de tri).

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

  • appel Direct à la bibliothèque qsort fonction: 689,38
  • implémentation Naïve (le tri par insertion) : 285.70
  • Insertion Tri (Daniel Stutzbach): 142.12
  • Tri D'Insertion: 125,47
  • Rang Ordre: 102.26
  • Ordre de Classement avec les registres : 58.03
  • Réseaux De Tri (Daniel Stutzbach): 111,68
  • Réseaux De Tri (Paul R): 66.36
  • réseaux de tri 12 à échange rapide: 58,86
  • réseaux de tri 12 Swap réorganisé: 53.74
  • réseaux de tri 12 réordonné simple Swap: 31.54
  • réseau de tri réorganisé avec échange rapide: 31.54
  • réorganisé Réseau de tri avec échange rapide V2: 33.63
  • Inline Tri À Bulles (Paolo Bonzini) : 48.85
  • Insertion Triée (Paolo Bonzini): 75,30

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

  • appel Direct à la bibliothèque qsort fonction: 705.93
  • mise en œuvre naïve (insertion tri) : 135.60
  • Insertion Sort (Daniel Stutzbach): 142.11
  • Tri D'Insertion: 126,75
  • Rang Ordre: 46.42
  • Ordre de Classement avec les registres : 43.58
  • Réseaux De Tri (Daniel Stutzbach): 115.57
  • Réseaux De Tri (Paul R): 64.44
  • réseaux de tri 12 à échange rapide: 61,98
  • réseaux de tri 12 Swap réorganisé: 54.67
  • réseaux de tri 12 réordonné simple Swap: 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
  • Inline Tri À Bulles (Paolo Bonzini) : 45.79
  • non laminé Insertion Tri (Paolo Bonzini): 80.15

j'ai inclus les résultats-O1 et-O2 parce qu'é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

Insertion Tri (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 d'insertion. Je me suis demandé si l'effet principal n'était pas d'éviter la boucle externe. Je lui ai donné un essai par Tri d'insertion déroulés pour vérifier et en effet nous obtenons à peu près les mêmes chiffres (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 . Je ne sais pas encore pourquoi il est presque deux fois plus rapide que l'autre mise en œuvre de réseau de tri. Passage de paramètre ? Fast max ?

réseaux de tri 12 SWAP à échange rapide

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

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

appel à 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 (code est ici ). Comme prévu, il est beaucoup plus lent : 10 à 30 fois plus lent... comme il est devenu évident avec la nouvelle suite de test, le principal problème semble être la charge initiale de la bibliothèque après le premier appel, et il se compare pas si mal avec d'autres versions. Il est juste entre 3 et 20 fois plus lent sur mon Linux. Sur certaines architectures utilisées pour des tests par d'autres, cela semble même plus rapide (je suis vraiment surpris par celle-ci, car la bibliothèque qsort utilise une API plus complexe).

Rang

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 parce que l'ordre de rang de calcul n'a pas besoin de branche. 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 rang). Les résultats sont très surprenants (et intéressant). Sur mon architecture de référence avec 32 bits OS et Intel Core2 Quad E8300, le nombre de cycles était légèrement inférieur à 1000 (comme les réseaux de tri avec ramification swap). Mais lorsqu'il a été compilé et exécuté sur ma boîte 64 bits (Duo Intel Core2), il a donné de meilleurs résultats : il est devenu le plus rapide à ce jour. J'ai enfin trouvé la vraie raison. Ma boîte de 32 bits utilise gcc 4.4.1 et ma boîte de 64 bits gcc 4.4.3 et la dernière semble beaucoup mieux pour optimiser ce code particulier (il y avait très peu de différence pour les autres propositions).

mise à jour :

comme les chiffres publiés ci-dessus montre cet effet a été encore renforcée par les versions ultérieures de gcc et L'ordre de rang est devenu systématiquement deux fois plus rapide que toute autre alternative.

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

l'étonnante efficacité de la proposition de Rex Kerr avec gcc 4.4.3 m'a fait me demander : comment un programme avec 3 fois plus d'utilisation de mémoire pourrait-il être plus rapide que le tri sans branchement les réseaux? Mon hypothèse était qu'il avait moins de dépendances du genre lire après écrire, permettant une meilleure utilisation de l'ordonnanceur d'instruction 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: quand vous faites SWAP(1, 2); SWAP(0, 2); vous devez attendre que le premier swap soit terminé avant d'effectuer le second parce que les deux accèdent à une cellule mémoire commune. Quand vous faites SWAP(1, 2); SWAP(4, 5); le processeur peut exécuter les deux en parallèle. Je l'ai essayé et ça marche comme prévu, les réseaux de tri tournent environ 10% plus vite.

réseaux de tri 12 à simple échange

"

un an après le post original Steinar H. Gunderson a suggéré, que nous ne devrions pas essayer de déjouer le compilateur et garder le code de swap simple. C'est en effet une bonne idée car le code qui en résulte est environ 40% plus rapide! Il a également proposé un swap optimisé à la main en utilisant le code d'assemblage en ligne x86 qui peut encore gardez un peu plus de cycles. Le plus surprenant (il est dit des volumes sur la psychologie de programmeur) est qu'Il ya un an, aucun utilisé essayé cette version de swap. Le Code que j'ai utilisé pour tester est ici . D'autres ont suggéré d'autres façons d'écrire un C swap rapide, mais il donne les mêmes performances que le simple avec un bon compilateur.

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 notre jeu d'essai (et, oui, il est tout à fait pauvre, le simple avantage est d'être bref, 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 a mis chaque échange à une moyenne de 4 cycles. J'appelle ça incroyablement rapide. D'autres améliorations possibles ?

369
demandé sur kriss 2010-05-07 11:24:45
la source

23 ответов

Pour toute optimisation, il est toujours préférable de tester, tester, tester. J'essaierais au moins de trier les réseaux et de trier les insertions. Si je pariais, je mettrais mon argent sur une sorte d'insertion basée sur l'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, l'insertion sort donne de meilleurs résultats 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 à une sorte d'insertion, mais il semble que vous avez minimisé le nombre de swaps au prix de plus de comparaisons. Les comparaisons sont beaucoup plus coûteuses que les swaps, cependant, parce que les branches peuvent faire décrocher le pipeline d'instruction.

Voici une implémentation de tri d'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. Tout d'abord, utiliser ce site pour générer un ensemble minimal de macros de 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
}
153
répondu Daniel Stutzbach 2011-08-24 15:35:51
la source

Voici une implémentation utilisant 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 d'implémentations sans branchless très efficaces min et max pour cela, puisque c'est effectivement ce que ce code se résume à - une séquence 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 à vectorisation (par exemple SIMD - la plupart des simulateurs ont des instructions vectorielles min/max) et aussi à des implémentations GPU (par exemple CUDA - étant sans branchless il n'y a pas de problèmes avec la divergence de chaîne etc).

Voir aussi: Rapide de l'implémentation de l'algorithme de tri très petite liste

59
répondu Paul R 2017-05-23 15:18:22
la source

Puisqu'il s'agit d'entiers et les comparaisons sont rapides, pourquoi ne pas calculer l'ordre de rang de chacun directement:

inline void sort6(int *d) {
  int e[6];
  memcpy(e,d,6*sizeof(int));
  int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  int o5 = 15-(o0+o1+o2+o3+o4);
  d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}
40
répondu Rex Kerr 2010-05-08 03:19:00
la source

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

en regardant l'assemblage généré par gcc 4.5.2 j'ai observé que les charges et les magasins sont faits pour chaque swap, 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 commandé les charges aux magasins pour être aussi près que possible là-bas les registres sont d'abord nécessaires et dernier utilisé. J'ai aussi utilisé L'échange de Steinar H. Gunderson. macro. Maj: je suis passé à la macro SWAP de Paolo Bonzini que gcc convertit en quelque chose de similaire à Gunderson, mais gcc est capable de mieux commander les instructions puisqu'elles ne sont pas données comme assemblage explicite.

j'ai utilisé le même ordre de swap que le réseau de swap réorganisé donné comme le plus performant, bien qu'il puisse y avoir un meilleur ordre. Si je trouve plus de temps, je générerai et testerai un tas de permutations.

j'ai changé le code de test en examiner plus de 4000 tableaux et montrer le nombre moyen de cycles nécessaires pour trier chacun. Sur un i5-650, j'obtiens ~34.1 cycles / sort (en utilisant-O3), par rapport au réseau de tri modifié d'origine, j'obtiens ~65.3 cycles/sort (en utilisant-O1, beats-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 , %%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 de rapporter aussi des horloges pour les trier et de les exécuter plus de tests (le cmp fonction a été mise à jour pour gérer débordement d'entier), voici les résultats sur quelques architectures différentes. J'ai essayé de tester un processeur AMD mais le rdtsc n'est pas fiable sur le X6 1100T que j'ai disponible.

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
35
répondu Kevin Stock 2011-08-25 15:00:20
la source

le code de test est assez mauvais; il déborde le tableau initial (les gens ici ne lisent-ils pas les Avertissements des compilateurs?), le printf imprime les mauvais éléments, il utilise .octet pour rdtsc pour aucune bonne raison, il n'y a qu'un seul (!), il n'y a rien pour vérifier que les résultats finaux sont corrects (il est donc très facile de "Optimiser" en quelque chose de subtilement erroné), les tests inclus sont très rudimentaires (pas de nombres négatifs?) et il n'y a rien pour empêcher le compilateur de se fonction entière en code mort.

cela dit, il est aussi assez facile d'améliorer la solution de réseau bitonique; il suffit de changer le truc 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 vite pour moi (Debian gcc 4.4.5 avec-O2, amd64, Core i7).

14
répondu Steinar H. Gunderson 2011-08-24 20:10:21
la source

Je suis tombé sur cette question de Google Il ya quelques jours parce que j'avais également un besoin de trier rapidement un tableau de longueur fixe de 6 entiers. Dans mon cas cependant, mes entiers sont seulement 8 bits (au lieu de 32) et je n'ai pas une exigence stricte de l'utilisation seulement C. j'ai pensé que je partagerais mes conclusions de toute façon, au cas où ils pourraient être utiles à quelqu'un...

j'ai implémenté une variante d'une sorte de réseau dans l'assemblage qui utilise le SSE pour vectoriser les opérations de comparaison et de swap, 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 (vectorized comparent) en paramètres de mélange pour PSHUFB (vectorized swap), en utilisant seulement une PADDB (vectorized add) et dans certains cas aussi une pand (bitwise AND) instruction.

cette approche a aussi eu l'effet secondaire de donner une fonction véritablement sans branchless. Il n'y a pas des instructions de saut que ce soit.

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 ("réseaux de tri 12 avec simple Swap"). J'ai modifié cette implémentation pour utiliser des éléments de tableau char lors de mes tests, pour 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 à l'avantage relatif de la vitesse sur les solutions de rechange à croître plus pour les plus grands tableaux.

le code est écrit en MASM pour les processeurs x86_64 avec SSSE3. La fonction utilise la "nouvelle" convention D'appel Windows x64. Elle 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 compiler cela à un objet exécutable et le lier dans votre projet C. Pour des instructions sur la façon de le faire dans Visual Studio, vous pouvez lire cet article . Vous pouvez utiliser le prototype C suivant pour appeler le fonction à partir de votre code C:

void simd_sort_6(char *values);
14
répondu Joe Crivello 2015-09-01 22:31:19
la source

alors que j'aime vraiment la macro de swap fourni:

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

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

nous prenons note de la façon dont min et max fonctionnent et nous tirons explicitement la sous-expression commune. Ceci élimine complètement les macros min et max.

12
répondu phkahler 2017-10-25 17:09:34
la source

N'optimise jamais min / max sans benchmarking et en regardant l'assemblage généré par le compilateur. Si je laisse GCC optimiser min avec des instructions de déplacement conditionnel je reçois 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 contre 420 cycles dans le code d'essai). Maxi ? est plus ou moins la même chose, presque perdu dans le bruit, mais le dessus est un peu plus rapide. Ce SWAP est plus rapide avec GCC et Clang.

compilateurs font également un travail exceptionnel lors de l'allocation de registre et de l'analyse d'alias, déplacement efficace de d[x] dans les variables locales à l'avance, et copie seulement 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 forte optimisation et pourtant 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 avoir une certaine variation dans les résultats, ne peut pas dire vraiment qui est plus rapide ou plus lent. GCC est plus rapide sur les réseaux de tri, Clang sur les types quadratiques.

par souci d'exhaustivité, il est également possible d'effectuer des tris de bulles et des tris d'insertion. 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 d'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 fait avec seulement 3 instructions (contre 4 pour SWAP). Par exemple, voici la ligne t = d[2]; ITER(1); ITER(0); dans L'assemblage de bras:

    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 d'insertion est concurrentiel par rapport au réseau de tri (12 swaps contre 15 Soldes d'itérations, 4 instructions/swap contre 3 instructions/itération); le tri à bulles est évidemment plus lent. Mais ce ne sera pas vrai quand la taille augmentera, puisque le tri d'insertion est O (N^2) tout en Tri les réseaux sont en O(n log n).

11
répondu Paolo Bonzini 2011-08-25 11:17:11
la source

j'ai porté la suite de test sur une machine d'architecture PPC que je ne peux pas identifier (Je n'ai pas eu besoin de code tactile, j'ai juste augmenté les itérations du test, j'ai utilisé 8 cas de test pour éviter des résultats polluants avec des mods et j'ai remplacé le rdtsc spécifique à x86):

appel Direct à la fonction de bibliothèque qsort : 101

naïve implementation (insertion sort) : 299

Insertion Tri (Daniel Stutzbach) : 108

Insertion Triée : 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 triage 12 réorganisés Swap : 116

Ordre : 56

10
répondu jheriko 2011-08-24 17:15:06
la source

un swap 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 si peut causer trop de divergence dans votre code, mais si vous avez une garantie que tous vos ints sont uniques, cela pourrait être pratique.

7
répondu naj 2011-08-24 15:36:20
la source

J'ai hâte d'essayer ma main à ce sujet et d'apprendre à partir de ces exemples, mais tout d'abord quelques timings de mon Powerbook 1,5 GHz PPC G4 w/ 1 Go DDR RAM. (J'ai emprunté une minuterie de type rdtsc pour le PPC de http://www.mcs.anl.gov/~kazutomo/rdtsc.html pour les horaires.) J'ai lancé le programme à quelques reprises et les résultats absolus ont varié, mais le test le plus rapide a toujours été "Insertion Sort (Daniel Stutzbach)", avec "Insertion Sort déroulé" à une seconde près.

Voici la dernière série de temps:

**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
5
répondu Nico 2011-08-25 06:49:06
la source

voici ma contribution à ce thread: un gap shellsort 1, 4 optimisé pour un vecteur int de 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 portable HP dv7-3010so avec un double noyau Athlon M300 @ 2 Ghz (Mémoire DDR2) il exécute en 165 cycles d'horloge. Il s'agit d'une moyenne calculée à partir du timing de chaque séquence unique (6!/720). Compilé pour Win32 En utilisant OpenWatcom 1.8. La boucle est essentiellement un tri d'insertion et est de 16 instructions / 37 octets de long.

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

4
répondu Olof Forshell 2012-03-14 15:30:49
la source

si le tri d'insertion est raisonnablement compétitif ici, je recommande d'essayer un shellsort. J'ai bien peur que 6 elements soit juste trop peu pour être parmi les meilleurs, mais ça pourrait valoir le coup d'essayer.

exemple de code, non testé,non modifié, etc. Vous voulez régler l'inc = 4 et inc -= 3 séquence de 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 va gagner, mais si quelqu'un poste une question sur trier 10 éléments, qui sait...

selon Wikipedia cela peut même être combiné avec des réseaux de tri: Pratt, V (1979). Shellsort et les réseaux de tri (dissertations exceptionnelles dans les sciences informatiques). Guirlande. ISBN 0-824-04406-1

3
répondu gcp 2011-08-24 23:03:57
la source

cette question devient assez vieille, mais j'ai dû en fait résoudre le même problème ces jours - ci: agorithmes rapides pour trier de petits tableaux. Je pensais 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'attends à ce qu'il soit à peu près équivalent (peut-être un peu plus parfois).

L'algorithme sort6 utilise l'algorithme de sort4 , qui utilise l'algorithme de sort3 . Voici l'implémentation sous une forme c++ légère (l'original est template-heavy de sorte qu'il peut fonctionner avec n'importe quel itérateur à accès aléatoire et n'importe quelle fonction de comparaison appropriée).

Tri 3 valeurs

l'algorithme est une sorte d'insertion non contrôlée. Lorsque deux swaps (6 cessions) doivent être effectués, il utilise 4 cessions à la place:

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

il semble un peu complexe parce que le sort a plus ou moins une branche pour chaque permutation possible du tableau, en utilisant 2~3 comparaisons et au plus 4 assignations pour trier les trois valeurs.

tri de 4 valeurs

celui-ci appelle sort3 puis effectue un tri d'insertion Non déroulante 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 d'insertion, mais nous allons utiliser un autre algorithme pour le dernier tri...

tri des 6 valeurs

celui-ci utilise une version non laminée de ce que j'ai appelé un double insertion tri . Le nom n'est pas terrible, mais c'est assez descriptif, ici, est de savoir comment il fonctionne:

  • Trier tout sauf le premier et les derniers éléments du tableau.
  • Swap le premier et les éléments du tableau si le premier est plus grand que le dernier.
  • Insérez le premier élément dans la séquence triée de l'avant puis le dernier élément de l'arrière.

après le swap, le premier élément est toujours plus petit que le dernier, ce qui signifie que, en les insérant 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 premier élément a été inséré en 3ème position, alors le dernier ne peut pas être inséré en dessous de la 4ème 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 jamais montrent que ces algorithmes 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 cette aide, même si cette question ne peut représenter un réel problème de plus :)

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éroulante, mais c'est à peu près tout. Fondamentalement, il n'est pas le meilleur sort pour les entiers, mais pourrait être intéressant pour les types avec un cher opération de comparaison.

2
répondu Morwenn 2017-05-23 14:55:10
la source

je sais que je suis en retard, mais j'étais intéressé à expérimenter avec quelques solutions différentes. D'abord, j'ai nettoyé cette pâte, Je l'ai compilée, et je l'ai mise dans un dépôt. J'ai gardé des solutions indésirables comme impasses pour que d'autres n'essayent pas. Parmi ceux-ci était ma première solution, qui a tenté de s'assurer que x1>x2 a été calculé une fois. Après optimisation, il n'est pas plus rapide que les autres versions simples.

j'ai ajouté une version en boucle de tri d'ordre de rang, puisque ma propre application de cette étude est pour le tri 2-8 articles, donc puisqu'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 d'essai ne permettait pas de vérifier que les duplicata étaient manipulés correctement, alors bien que les solutions existantes étaient toutes correctes, j'ai ajouté un cas spécial au code d'essai pour m'assurer que les duplicata étaient manipulés correctement.

puis, 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. J'ai fait cela uniquement à titre expérimental et je ne m'attendais pas à ce que ce soit mieux en raison du type de ramification en 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
}

puis, j'ai écrit un classement par ordre d'importance 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, et ensuite je dois faire une table des indices. C'est parce que le calcul est basé sur la destination plutôt que sur la source. Voir conversion d'Indices fondés sur les sources en Indices fondés sur les destinations

"
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
répondu eyepatch 2017-05-23 15:34:50
la source

je crois qu'il y a deux parties à votre question.

  • la première consiste à déterminer l'algorithme optimal. Cela est fait - au moins dans ce cas - en bouclant à travers chaque ordre possible (il n'y en a pas tant que cela) qui vous permet de calculer exact min, max, moyenne et écart-type de comparaisons et de swaps. Ayez un ou deux dauphins à portée de main.
  • La seconde est d'optimiser l'algorithme. Beaucoup peut être fait pour convertir manuel d'exemples de code pour des algorithmes de moyenne et de lean real-life. Si vous vous rendez compte qu'un algorithme ne peut pas être optimisé dans la mesure nécessaire, essayez un dauphin.

Je ne m'inquiéterais pas trop de vider les pipelines (en supposant x86 actuel): la prédiction de branche a parcouru un long chemin. Ce qui m'inquiète, c'est de m'assurer que le code et les données correspondent à une ligne de cache (peut-être deux pour le code). Une fois là-bas, les latences de va-et-vient sont agréablement basses, ce qui compensera tout décrochage. Cela signifie également que votre boucle interne sera peut-être dix instructions ou ainsi ce qui est juste où il devrait être (il y a deux boucles internes différentes dans mon algorithme de tri, ils sont 10 instructions/22 octets et 9/22 de long respectivement). En supposant que le code ne contient pas de divs, vous pouvez être sûr qu'il sera aveuglément rapide.

1
répondu Olof Forshell 2012-03-06 14:33:07
la source

j'ai trouvé qu'au moins sur mon système, les fonctions sort6_iterator() et sort6_iterator_local() définies ci-dessous les deux ont couru au moins aussi rapide, et souvent sensiblement plus rapide, que le détenteur de 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 d'un itérateur de std::vector dans mon code de temps. Je soupçonne que l'utilisation d'itérateurs donne g++ certaines assurances sur ce qui peut et ne peut pas arriver à la mémoire que l'itérateur se réfère, il n'aurait pas autrement et il est-ce que ces assurances permettent à g++ de mieux optimiser le code de tri (qui, si je me souviens bien, est aussi partie de la raison pour laquelle tant d'algorithmes std , tels que std::sort() , ont généralement de telles performances obscènes)? Cependant, pendant que le timing je remarquais que le contexte (c.-à-d. entourant le code) dans lequel l'appel à la fonction de tri a été fait avait un impact significatif sur la performance, qui est probablement dû à la fonction étant inlined et puis optimisé. Par exemple, si le programme était suffisamment simple, alors il n'y avait généralement pas beaucoup de différence dans la performance entre passer la fonction de tri un pointeur par rapport à passer un itérateur; autrement, l'utilisation d'itérateurs a généralement abouti à une performance nettement meilleure et jamais (dans mon expérience au moins jusqu'à présent) une performance sensiblement pire. Je pense que c'est peut-être parce que g++ peut globalement optimiser suffisamment de code simple.

de plus, sort6_iterator() est certains les temps (encore une fois, selon le contexte dans lequel la fonction est appelée) dépasse régulièrement par la suite de fonction de tri:

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
}

noter que la définition de SWAP() comme suit: quelques fois donne une performance légèrement meilleure, bien que la plupart du temps elle donne une performance légèrement moins bonne ou une différence de performance négligeable.

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

si vous vous voulez juste un algorithme de tri que gcc-O3 est toujours bon à optimiser alors, selon la façon dont vous passez l'entrée, essayez l'un des deux algorithmes suivants:

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

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 mot-clé register est parce que c'est l'une des rares fois que vous savez que vous voulez ces valeurs dans les registres. Sans register , le compilateur trouvera cela la plupart du temps, mais ce n'est pas toujours le cas. L'utilisation du mot-clé register aide à résoudre ce problème. Normalement, toutefois, n'utilisez pas le "1519120920 mot clé" car il est plus susceptible de ralentir votre code que de l'accélérer.

aussi, notez l'utilisation de gabarits. Ceci est fait exprès car, même avec le mot-clé inline , les fonctions de modèle sont généralement optimisées de manière beaucoup plus agressive par gcc que les fonctions de type C (cela a à voir avec gcc qui doit traiter les pointeurs de fonction pour les fonctions de type C mais pas avec le modèle des fonctions).

1
répondu Matthew K. 2017-07-18 19:50:20
la source

je sais que c'est une vieille question.

mais je viens d'écrire un autre type de solution que je veux partager.

En utilisant rien mais imbriquées MIN MAX,

ce n'est pas rapide car il utilise 114 de chaque,

pourrait le réduire à 75 assez simplement comme ainsi - > pastebin

mais ce n'est plus seulement min max.

ce qui pourrait marcher est faire min / max sur plusieurs entiers à la fois avec AVX

PMINSW reference

#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 inspirée du modèle de Rex Kerr, Beaucoup plus rapide que le mess 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;
}
1
répondu PrincePolka 2017-10-03 16:59:11
la source

Essayer " fusion liste triée de tri. :) L'utilisation du tableau deux. Plus rapide pour les petits et grand tableau.

Si vous concez, vous cochez seulement où insérer. D'autres valeurs plus grandes que vous n'avez pas besoin de comparer (cmp = a-b>0).

Pour 4 Nombres, vous pouvez utiliser le système 4-5 cmp (~4.6) ou 3-6 cmp (~4.9). Utiliser 6 cmp (6). Beaucoup de code cmp pour les grands nombres plus lent.

Ce code utilise 5 cmp (pas de 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);}

principal 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;
	}
}
0
répondu peter 2017-01-12 17:26:11
la source

Trier 4 articles avec usage cmp= = 0. Le nombre de cmp est d'environ 4.34 (FF native a ~ 4.52), mais prend 3 fois plus de temps que la fusion des listes. Mais mieux vaut moins d'opérations cmp, si vous avez de grands nombres ou de gros textes. Modifier: bogue 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;
}
0
répondu peter 2017-01-13 12:49:29
la source

peut-être que je am en retard pour le parti, mais au moins ma contribution est une nouvelle approche.

  • le code really devrait être inliné
  • même s'il est inlined, Il ya trop de branches
  • la partie analytique est essentiellement O(N (N-1)) qui semble OK pour N = 6
  • le code pourrait être plus efficace si le coût de swap serait plus élevé (irt le coût de compare )
  • j'espère que les fonctions statiques seront abrégées.
  • la méthode est liée au classement
    • au lieu des grades, on utilise les grades relatifs (offsets).
    • la somme des rangs est zéro pour chaque cycle dans n'importe quel groupe de permutation.
    • au lieu de SWAP()

Maj: modification du code un peu, 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);
}
0
répondu wildplasser 2018-02-03 03:25:51
la source

bien, si ce n'est que 6 éléments et que vous pouvez tirer parti du parallélisme, vouloir minimiser la ramification conditionnelle, etc. Pourquoi ne pas générer toutes les combinaisons et tester pour l'ordre? Je crois que dans certaines architectures, il peut être assez rapide (tant que vous avez la mémoire préaffectés)

-1
répondu GClaramunt 2011-08-24 19:04:33
la source

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 vérifier Stefan nelsson discussion sur l'algorithme de tri le plus rapide? où il discute d'une solution qui descend à O(n log log n) .. vérifier les 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, and R. Raman. Tri linéaire de temps? Dans les actes de la 27e Annuel ACM Symposium sur la Théorie de la L'informatique, les pages 427-436, 1995.

-2
répondu Khaled A Khunaifer 2013-04-23 22:12:46
la source

Autres questions sur c algorithm sorting optimization gpgpu