Moyen le plus rapide de trouver le minimum de 3 nombres ?

Question

Dans un programme que j'ai écrit, 20 % du temps est passé à trouver le minimum de 3 nombres dans une boucle interne, dans cette routine :

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    unsigned int m = a;
    if (m > b) m = b;
    if (m > c) m = c;
    return m;
}

Y a-t-il un moyen d'accélérer cela ? Je suis d'accord avec du code en langage d'assemblage pour x86/x86_64.

Éditer : En réponse à certains commentaires :
* Le compilateur utilisé est gcc 4.3.3
* En ce qui concerne l'assemblage, je suis seulement un débutant. J'ai demandé de l'assemblage ici, pour apprendre comment faire. :)
* J'ai un Intel 64 quad-core, donc les MMX/SSE etc. sont supportés.
* Il est difficile de poster la boucle ici, mais je peux vous dire que c'est une implémentation très optimisée de l'algorithme de Levenshtein.

Voici ce que le compilateur me donne pour la version non inlinée de min :

.globl min
    .type   min, @function
min:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %eax
    movl    16(%ebp), %ecx
    cmpl    %edx, %eax
    jbe .L2
    movl    %edx, %eax
.L2:
    cmpl    %ecx, %eax
    jbe .L3
    movl    %ecx, %eax
.L3:
    popl    %ebp
    ret
    .size   min, .-min
    .ident  "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
    .section    .note.GNU-stack,"",@progbits

La version inline est incluse dans le code optimisé -O2 (même mes marqueurs mrk = 0xfefefefe, avant et après l'appel à min()) sont optimisés par gcc, donc je n'ai pas pu y accéder.

Mise à jour : J'ai testé les changements suggérés par Nils, ephemient, cependant il n'y a pas de gain de performance perceptible en utilisant les versions en langage d'assemblage de min(). Cependant, j'obtiens un gain de performance de 12,5 % en compilant le programme avec -march=i686, ce qui je suppose est dû au fait que l'ensemble du programme bénéficie des nouvelles instructions plus rapides que gcc génère avec cette option. Merci pour votre aide.

Remarque - J'ai utilisé le profileur ruby pour mesurer les performances (mon programme C est une bibliothèque partagée chargée par un programme ruby), donc je pouvais obtenir le temps passé uniquement pour la fonction C de niveau supérieur appelée par le programme ruby, qui finit par appeler min() dans la pile. Veuillez consulter cette question.

Answer 1

En supposant que votre compilateur ne soit pas absent, cela devrait se compiler en deux comparaisons et deux mouvements conditionnels. Il n'est pas possible de faire beaucoup mieux que ça.

Si vous postez l'assemblage que votre compilateur génère réellement, nous pouvons voir s'il y a quelque chose d'inutile qui ralentit le tout.

La première chose à vérifier est que la routine est effectivement en ligne. Le compilateur n'est pas obligé de le faire, et s'il génère un appel de fonction, cela coûtera énormément pour une opération aussi simple.

Si l'appel est vraiment en ligne, alors le déroulement de la boucle peut être bénéfique, comme l'a dit DigitalRoss, ou la vectorisation peut être possible.

Modifier: Si vous voulez vectoriser le code, et utilisez un processeur x86 récent, vous voudrez utiliser l'instruction SSE4.1 pminud (intrinsèque : _mm_min_epu32), qui prend deux vecteurs de quatre unsigned ints chacun, et produit un vecteur de quatre unsigned ints. Chaque élément du résultat est le minimum des éléments correspondants dans les deux entrées.

Je constate également que votre compilateur utilise des branches au lieu de mouvements conditionnels ; vous devriez probablement essayer une version qui utilise d'abord des mouvements conditionnels et voir si cela vous donne une accélération avant de passer à une implémentation vectorielle.

Answer 2

Assurez-vous d'utiliser un -march approprié, tout d'abord. Par défaut, GCC n'utilise aucune instruction qui n'étaient pas supportées sur l'i386 original - permettant l'utilisation de nouveaux jeux d'instructions peut parfois faire une GRANDE différence! Avec -march=core2 -O2, j'obtiens :

min :
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %edx
    movl    12(%ebp), %ecx
    movl    16(%ebp), %eax
    cmpl    %edx, %ecx
    leave
    cmovbe  %ecx, %edx
    cmpl    %eax, %edx
    cmovbe  %edx, %eax
    ret

L'utilisation de cmov ici peut vous aider à éviter les retards de branchement - et vous l'obtenez sans asm en ligne juste en passant par -march. Lorsqu'il est intégré dans une fonction plus importante, cela est susceptible d'être encore plus efficace, peut-être juste quatre opérations en assembly. Si vous avez besoin de quelque chose de plus rapide que cela, voyez si vous pouvez faire fonctionner les opérations vectorielles SSE dans le contexte de votre algorithme global.

Answer 3

Ma version d'une implémentation d'assemblage x86, syntaxe GCC. Devrait être trivial à traduire dans une autre syntaxe d'assembleur en ligne :

int inline least (int a, int b, int c)
{
  int result;
  __asm__ ("mov     %1, %0\n\t"
           "cmp     %0, %2\n\t" 
           "cmovle  %2, %0\n\t"
           "cmp     %0, %3\n\t"
           "cmovle  %3, %0\n\t" 
          : "=r"(result) : 
            "r"(a), "r"(b), "r"(c)
          );
  return result;
}

---

Nouvelle version améliorée :

int inline least (int a, int b, int c)
{
  __asm__ (
           "cmp     %0, %1\n\t" 
           "cmovle  %1, %0\n\t"
           "cmp     %0, %2\n\t"
           "cmovle  %2, %0\n\t" 
          : "+r"(a) : 
            "%r"(b), "r"(c)
          );
  return a;
}

---

REMARQUE : Il peut être plus ou moins rapide que le code C.

Cela dépend de beaucoup de facteurs. En général, cmov l'emporte si les branchements ne sont pas prédictibles (sur certaines architectures x86) D'un autre côté, l'assembleur en ligne est toujours un problème pour l'optimiseur, donc le coût d'optimisation pour le code environnant peut surclasser tous les gains.

À propos, Sudhanshu, il serait intéressant de savoir comment ce code se comporte avec vos données de test.

Answer 4

Ce remplacement instantané affiche environ 1,5% de plus de performances sur mon AMD Phenom :

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{
    asm("cmp   %1,%0\n"
        "cmova %1,%0\n"
        "cmp   %2,%0\n"
        "cmova %2,%0\n"
        : "+r" (a) : "r" (b), "r" (c));
    return a;
}

Les résultats peuvent varier ; certains processeurs x86 ne gèrent pas très bien CMOV.

Answer 5

Les extensions d'instruction SSE2 contiennent une instruction entière min qui peut choisir 8 minimums à la fois. Voir _mm_mulhi_epu16 dans http://www.intel.com/software/products/compilers/clin/docs/ug_cpp/comm1046.htm