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

Tout d'abord, regardez le désassemblage. Cela vous en dira beaucoup. Par exemple, tel qu'écrit, il y a 2 instructions if (ce qui signifie qu'il y a 2 prédictions de saut possibles), mais je suppose qu'un bon compilateur C moderne pourra faire cela sans branchement en utilisant une optimisation intelligente. J'aimerais bien le découvrir.

Ensuite, si votre libc a des fonctions min/max spéciales intégrées, utilisez-les. GNU libc a fmin/fmax pour les nombres flottants, par exemple, et ils affirment que "Sur certains processeurs, ces fonctions peuvent utiliser des instructions machine spéciales pour effectuer ces opérations plus rapidement que le code C équivalent". Peut-être qu'il y a quelque chose de similaire pour les uints.

Enfin, si vous faites cela sur un tas de nombres en parallèle, il existent probablement des instructions vectorielles pour le faire, ce qui pourrait fournir une accélération significative. Mais j'ai même vu du code non vectoriel être plus rapide lors de l'utilisation des unités vectorielles. Quelque chose comme "charger un uint dans un registre vectoriel, appeler la fonction min vectorielle, obtenir le résultat" semble idiot mais pourrait en fait être plus rapide.

Answer 2

Si vous ne faites qu'une seule comparaison, vous voudrez peut-être dérouler la boucle manuellement.

En premier lieu, essayez de voir si vous pouvez obtenir que le compilateur déroule la boucle pour vous, et si vous ne le pouvez pas, faites-le vous-même. Cela réduira au moins les frais de contrôle de la boucle...

Answer 3

Vous pourriez essayer quelque chose comme ceci pour économiser sur les déclarations et les comparaisons inutiles :

static inline unsigned int
min(unsigned int a, unsigned int b, unsigned int c)
{ 
    if (a < b)
    {
        if (a < c) 
             return a; 
        else 
             return c;
    }

    if (b < c)
        return b;
    else return c;
}

Answer 4

Ce sont toutes de bonnes réponses. Au risque d'être accusé de ne pas répondre à la question, je regarderais aussi les autres 80% du temps. Stackshots sont ma façon préférée de trouver du code qui vaut la peine d'être optimisé, surtout s'il s'agit d'appels de fonction dont vous découvrez que vous n'en avez pas absolument besoin.

Answer 5

Oui, poste d'assemblage, mais mon optimisation naïve est :

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) return c;
    return m;
}