En quoi la fonction "min" de deux entiers est-elle aussi rapide que le "bit hacking" ?

Question

Je regardais un série de conférences sur "Bit Hacking" et je suis tombé sur l'optimisation suivante pour trouver le minimum de deux entiers :

return x ^ ((y ^ x) & -(x > y))

Qui dit être plus rapide que :

if x < y:
    return x
else:
    return y

Depuis le min peut traiter plus que deux entiers (des flottants, des chaînes de caractères, des listes et même des objets personnalisés), j'ai supposé que l'appel à la fonction min(x, y) prendrait plus de temps que le hack optimisé ci-dessus. À ma grande surprise, ils étaient presque identiques :

>>> python -m timeit "min(4, 5)"
1000000 loops, best of 3: 0.203 usec per loop

>>> python -m timeit "4 ^ ((5 ^ 4) & -(4 > 5))"
10000000 loops, best of 3: 0.19 usec per loop

Ceci est vrai même pour les nombres supérieurs à 255 (objets entiers python pré-alloués)

>>> python -m timeit "min(15456, 54657)"
10000000 loops, best of 3: 0.191 usec per loop

python -m timeit "15456 ^ ((54657 ^ 15456) & -(54657 > 15456))"
10000000 loops, best of 3: 0.18 usec per loop

Comment se fait-il qu'une fonction aussi polyvalente que min peut toujours être aussi rapide et optimisé ?

Note : J'ai exécuté le code ci-dessus en utilisant Python 3.5. Je suppose que c'est la même chose pour Python 2.7+ mais je n'ai pas testé.

---

J'ai créé le module c suivant :

#include <Python.h>

static PyObject * my_min(PyObject *self, PyObject *args){
    const long x;
    const long y;

    if (!PyArg_ParseTuple(args, "ll", &x, &y))
        return NULL;

    return PyLong_FromLong(x ^ ((y ^ x) & -(x > y)));
}

static PyMethodDef MyMinMethods[] = 
{
    { "my_min", my_min, METH_VARARGS, "bit hack min"
    },
    {NULL, NULL, 0, NULL}
};

PyMODINIT_FUNC
initmymin(void)
{
    PyObject *m;

    m = Py_InitModule("mymin", MyMinMethods);
    if (m == NULL)
        return;

}

Je l'ai compilé et installé sur mon système (une machine VM ubuntu). J'ai ensuite exécuté ce qui suit :

>>> python -m timeit 'min(4, 5)'
10000000 loops, best of 3: 0.11 usec per loop

>>> python -m timeit -s 'import mymin' 'mymin.my_min(4,5)'
10000000 loops, best of 3: 0.129 usec per loop

Bien que je comprenne qu'il s'agisse d'une machine virtuelle, ne devrait-il pas y avoir un écart plus important dans le temps d'exécution avec le "piratage de bits" qui est déchargé dans le langage c natif ?

Answer 1

Cela est probablement dû à la façon dont le min est implémentée en python.

De nombreux buildins python sont en fait implémentés dans des langages de bas niveau tels que le C ou l'assembleur et utilisent les apis python afin d'être appelables en python.

Votre technique de manipulation des bits est probablement très rapide en C, mais en Python, le coût d'interprétation de l'instruction dépassera de loin le coût d'appel d'une fonction, même complexe, implémentée dans un langage de bas niveau.

Si vous voulez vraiment un test équitable, comparez un programme C, ou une extension C python implémentant cette technique à votre appel python de min et voir comment il se compare, je pense que cela expliquera le résultat que vous voyez.

EDITAR:

Grâce à @Two-BitAlchemist, je peux maintenant donner quelques détails supplémentaires sur les raisons additionnelles pour lesquelles ce bidouillage de bits ne fonctionnera pas bien en python. Il apparaît que les nombres entiers ne sont pas stockés de la manière évidente mais sont en fait un objet d'expansion assez complexe conçu pour stocker des nombres potentiellement très grands.

On peut trouver quelques détails à ce sujet aquí (Merci à Two-BitAlchemist) bien qu'il semble que cela ait quelque peu changé dans les nouvelles versions de python. Il n'en reste pas moins que nous ne manipulons certainement pas un simple ensemble de bits lorsque nous touchons un entier en python, mais un objet complexe où les manipulations de bits sont en fait des appels de méthodes virtuelles avec une surcharge énorme (par rapport à ce qu'elles font).

Answer 2

Le piratage des bits était peut-être plus rapide dans les années 90, mais il est deux fois plus lent sur les machines actuelles. Comparez par vous-même :

// gcc -Wall -Wextra -std=c11 ./min.c -D_POSIX_SOURCE -Os
// ./a.out 42

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define COUNT (1 << 28)

static int array[COUNT];

int main(int argc, char **argv) {
    (void) argc;
    unsigned seed = atoi(argv[1]);

    for (unsigned i = 0; i < COUNT; ++i) {
        array[i] = rand_r(&seed);
    }

    clock_t begin = clock();

    int x = array[0];
    for (unsigned i = 1; i < COUNT; ++i) {
        int y = array[i];
#if 1
        x = x ^ ((y ^ x) & -(x > y));
# else
        if (y < x) {
            x = y;
        }
#endif
    }

    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    printf("Minimum: %d (%.3f seconds)\n", x, time_spent);
    return 0;
}

En moyenne 0,277 secondes dans l'implémentation "naïve", mais 0,442 secondes pour l'implémentation "optimisée". Il faut toujours avoir un grain de doute dans les cours de CS. Au moins depuis le CMOVxx (ajoutée avec le Pentium Pro en 1995), il n'y a aucune chance que la solution du bit hacking ait pu être plus rapide.

Sur un i5-750 (gcc (Debian 5.2.1-23) 5.2.1 20151028) :

    optimized naïve
O0  1.367     0.781
O1  0.530     0.274
O2  0.444     0.271
O3  0.442     0.144
Os  0.446     0.273

Après coup : Les développeurs de compilateurs sont des personnes très intelligentes, qui passent leurs journées à trouver et à mettre en œuvre des optimisations. Si l'astuce du bit hacking était plus rapide, alors votre compilateur implémenterait min() de cette façon. Et vous pouvez supposer sans risque que le compilateur comprend ce que vous faites à l'intérieur de la boucle. Mais les personnes travaillant pour Intel, AMD, etc. sont également intelligentes et optimisent des opérations importantes telles que min() y max() s'ils voient que les hackers du compilateur font des hacks bizarres parce que la solution évidente est lente.

Pour les plus curieux : Voici le code généré pour l'implémentation "optimisée" avec -O3 :

    mov    $0x40600b00, %ebp     # int *e = &array[COUNT];
    mov    0x600b00, %ebx        # int x = array[0];
    mov    $0x600b04, %edx       # int *i = &array[1];
loop:
    mov    (%rdx), %eax          # int y = *i;
    xor    %ecx, %ecx            # int tmp = (
    cmp    %ebx, %eax            #     y < x
    setl   %cl                   #   ? 1 : 0 );
    xor    %ebx, %eax            # y ^= x;
    add    $0x4, %rdx            # ++i;
    neg    %ecx                  # tmp = -tmp;
    and    %ecx, %eax            # y &= tmp;
    xor    %eax, %ebx            # x ^= y;
    cmp    %rdx, %rbp            # if (i != e) {
    jne    loop                  #    goto loop; }

Et l'implémentation naïve avec -Os (-O3 est énorme et plein d'instructions SSE que je devrais chercher) :

    mov    600ac0, %ebx          # int x = array[0];
    mov    $0x40600abc,%ecx      # int *e = &array[COUNT];
    mov    $0x600ac0,%eax        # int *i = &array[0];
loop:
    mov    0x4(%rax),%edx        # int y = *(i + 1);
    cmp    %edx,%ebx             # if (x > y) {
    cmovg  %edx,%ebx             #    x = y; }
    add    $0x4,%rax             # ++i;
    cmp    %rcx,%rax             # if (i != e) {
    jne    loop                  #    goto loop; }

Answer 3

Plongeons un peu plus profondément pour découvrir la véritable raison de cette bizarrerie (si elle existe).

Créons 3 méthodes et regardons leur bytecode python et leur temps d'exécution...

import dis

def func1(x, y):
    return min(x, y)

def func2(x, y):
    if x < y:
        return x
    return y

def func3(x, y):
    return x ^ ((y ^ x) & -(x > y))

print "*" * 80
dis.dis(func1)
print "*" * 80
dis.dis(func2)
print "*" * 80
dis.dis(func3)

Le résultat de ce programme est...

*****************************************************
  4           0 LOAD_GLOBAL              0 (min)
              3 LOAD_FAST                0 (x)
              6 LOAD_FAST                1 (y)
              9 CALL_FUNCTION            2
             12 RETURN_VALUE        
*****************************************************
  7           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 COMPARE_OP               0 (<)
              9 POP_JUMP_IF_FALSE       16

  8          12 LOAD_FAST                0 (x)
             15 RETURN_VALUE        

  9     >>   16 LOAD_FAST                1 (y)
             19 RETURN_VALUE        
*****************************************************
 12           0 LOAD_FAST                0 (x)
              3 LOAD_FAST                1 (y)
              6 LOAD_FAST                0 (x)
              9 BINARY_XOR          
             10 LOAD_FAST                0 (x)
             13 LOAD_FAST                1 (y)
             16 COMPARE_OP               4 (>)
             19 UNARY_NEGATIVE      
             20 BINARY_AND          
             21 BINARY_XOR          
             22 RETURN_VALUE        

Voici les temps de fonctionnement de chacune de ces fonctions

%timeit func1(4343,434234)
1000000 loops, best of 3: 282 ns per loop

%timeit func2(23432, 3243424)
10000000 loops, best of 3: 137 ns per loop

%timeit func3(928473, 943294)
1000000 loops, best of 3: 246 ns per loop

func2 est le plus rapide car il a le moins de travail à faire dans l'interpréteur python. Comment ? En regardant le bytecode de func2, nous voyons que dans les deux cas de x > y o x < y l'interpréteur python exécutera 6 instructions.

func3 exécutera 11 instructions (et est donc presque deux fois plus lent que func2... en fait, il est extrêmement proche de 137.0 * 11 / 6 = 251 ns).

func1 a seulement 5 instructions python, et par la logique des 2 points précédents, nous pourrions penser que func1 devrait probablement être le plus rapide. Cependant, il existe une CALL_FUNCTION et les appels de fonction ont beaucoup de surcharge en Python (parce qu'ils créent un nouveau cadre d'évaluation pour l'appel de fonction - c'est ce que l'on voit dans le suivi de pile de Python - une pile de cadres d'évaluation).

Plus de détails : Parce que python est interprété, chaque instruction de bytecode python prend beaucoup plus de temps qu une seule instruction C/asm. En fait, vous pouvez jeter un coup d'oeil au code source de l'interpréteur python pour voir que chaque instruction a un surcoût d'une trentaine d'instructions C (ceci est tiré d'un examen très sommaire de la boucle principale de l'interpréteur python ceval.c). Le site for (;;) loop exécute une instruction python par cycle de boucle (en ignorant les optimisations).

https://github.com/python/cpython/blob/master/Python/ceval.c#L1221

Ainsi, avec une telle surcharge pour chaque instruction, il est inutile de comparer deux petits extraits de code C en python. L'un prendra 34 et l'autre 32 cycles de processeur, car l'interpréteur python ajoute 30 cycles de surcharge pour chaque instruction.

Dans le module C de OP, si nous bouclons à l'intérieur de la fonction C pour effectuer la comparaison un million de fois, cette boucle n'aura pas la surcharge de l'interpréteur python pour chaque instruction. Elle s'exécutera probablement 30 à 40 fois plus vite.

Conseils pour l'optimisation de python...

Profilez votre code pour trouver les points chauds, refactorez le code chaud dans sa propre fonction (écrivez des tests pour les points chauds avant cela pour vous assurer que le refactoring ne casse pas de choses), évitez les appels de fonction à partir du code chaud (fonctions en ligne si possible), utilisez la balise dis module sur une nouvelle fonction pour trouver des moyens de réduire le nombre d'instructions python ( if x est plus rapide que if x is True ... surpris ?), et enfin modifiez votre algorithme. Enfin, si le gain de vitesse de python n'est pas suffisant, réimplémentez votre nouvelle fonction en C.

ps : L'explication ci-dessus est simplifiée pour garder la réponse dans une taille raisonnable. Par exemple, toutes les instructions python ne prennent pas le même temps, et il y a des optimisations, donc chaque instruction n'a pas la même surcharge... et beaucoup d'autres choses. Veuillez ignorer ces omissions dans un souci de concision.

Answer 4

J'ai fait quelque chose comme ça aquí il y a quelques jours. Il a suivi des exemples plus évidents où sauts (mal prédites) tuaient les performances.

Chaque opération [dans l'algorithme de Stein] est très simple : tester le bit de poids le plus faible, décaler d'un bit vers la droite, incrémenter un bit de poids fort. int . Mais le branche est un tueur !

Dans un noyau de traitement moderne superscalaire hautement pipeliné, une branche conditionnelle rompt le pipeline. Les processeurs x86 utilisent la prédiction de branchement et l'exécution spéculative pour atténuer ce problème, mais ici la décision de branchement est essentiellement aléatoire à chaque itération. Elle se trompe la moitié du temps.

⋮

Mais il me reste encore un tour à jouer. if (n>m) std::swap (n, m); est un point de branchement, et il prendra un chemin ou l'autre plusieurs fois en bouclant. C'est-à-dire que c'est une autre "mauvaise" branche.

Le remplacement d'un branchement conditionnel par des manipulations de bits sans branchement (expliqué dans l'article ; exemple plus clair que l'OP) a entraîné une accélération mesurable du code. Il s'agit d'un résultat différent de celui noté par une autre réponse, donc ma forme "moderne" pourrait mieux fonctionner, et ce n'est pas seulement un min mais le min et le max sont nécessaires simultanément, ce qui nécessite plus d'affectations même dans l'implémentation régulière.

Le résultat indique que tous ces calculs et l'utilisation de registres sont moins chers que le branchement : 44 devient 39 ou 37, 84 devient 75. Cela représente environ un 11% d'accélération de l'algorithme global .

Answer 5

Voici quelques timings sur Python 2.7 ( car j'ai mal supposé, je suis désolé) :

def mymin(x, y):
    if x < y:
        return x
    return y

10000000 loops, best of 3: 0.0897 usec per loop

---

def mymin(x, y):
    return y

10000000 loops, best of 3: 0.0738 usec per loop

---

mymin = min

10000000 loops, best of 3: 0.11 usec per loop

---

mymin = operator.add

10000000 loops, best of 3: 0.0657 usec per loop

Qu'est-ce que cela signifie ? Cela signifie presque tout le coût est dans l'appel de la fonction. Le plus rapide physiquement que CPython puisse faire ici est de 0.066 usec par boucle, ce qui add réalise.

Votre min en C va avoir

• moins de frais généraux parce qu'elle ne traite pas d'arguments arbitraires et de cmp mais

• plus de surcharge parce qu'il génère un nouvel entier, plutôt que de simplement retourner l'ancien. PyArg_ParseTuple n'est probablement pas rapide, non plus.

Les instructions C réelles pour la comparaison ou le coût du décalage des bits. effectivement rien . Ils sont gratuits. La loi d'Amdahl se moque de vous.

---

Pendant ce temps, PyPy prend environ 0,0003 usec par appel à min soit 200 fois moins de temps. De toute évidence, les instructions C sont au moins aussi bon marché, puisqu'elles se compilent en un bon code machine.

---

Je vais peut-être le dire autrement...

Qu'est-ce qui est plus cher qu'une branche ou une comparaison ?

• Allocation, que Python effectue pour allouer le cadre de la fonction et pour allouer le tuple dans lequel sont stockés les arguments.

• L'analyse syntaxique des chaînes de caractères, qui PyArg_ParseTuple fait.

• varargs, également utilisé par PyArg_ParseTuple .

• Les consultations de tableaux, qui PyLong_FromLong les performances.

• Calculé goto s, exécutés par la répartition interne du bytecode de CPython (et je crois que la version 2.7 utilise une fonction switch qui est encore plus lent).

Le corps de min implémenté en C, n'est pas le problème.