Times-two plus rapide que bit-shift, pour les entiers de Python 3.x ?

Question

Je regardais la source de conteneurs_triés et a été surpris de voir cette ligne :

self._load, self._twice, self._half = load, load * 2, load >> 1

Aquí load est un nombre entier. Pourquoi utiliser le décalage de bits à un endroit, et la multiplication à un autre ? Il semble raisonnable que le décalage de bits puisse être plus rapide que la division intégrale par 2, mais pourquoi ne pas remplacer la multiplication par un décalage également ? J'ai testé les cas suivants :

1. (fois, diviser)
2. (shift, shift)
3. (temps, décalage)
4. (shift, divide)

et a constaté que le n°3 est toujours plus rapide que les autres alternatives :

# self._load, self._twice, self._half = load, load * 2, load >> 1

import random
import timeit
import pandas as pd

x = random.randint(10 ** 3, 10 ** 6)

def test_naive():
    a, b, c = x, 2 * x, x // 2

def test_shift():
    a, b, c = x, x << 1, x >> 1    

def test_mixed():
    a, b, c = x, x * 2, x >> 1    

def test_mixed_swapped():
    a, b, c = x, x << 1, x // 2

def observe(k):
    print(k)
    return {
        'naive': timeit.timeit(test_naive),
        'shift': timeit.timeit(test_shift),
        'mixed': timeit.timeit(test_mixed),
        'mixed_swapped': timeit.timeit(test_mixed_swapped),
    }

def get_observations():
    return pd.DataFrame([observe(k) for k in range(100)])

La question :

Mon test est-il valable ? Si oui, pourquoi (multiply, shift) est-il plus rapide que (shift, shift) ?

J'utilise Python 3.5 sur Ubuntu 14.04.

Modifier

Ci-dessus, l'énoncé original de la question. Dan Getz fournit une excellente explication dans sa réponse.

Dans un souci d'exhaustivité, voici des exemples d'illustrations de plus grande taille. x lorsque les optimisations de la multiplication ne s'appliquent pas.

Answer 1

Cela semble être dû au fait que la multiplication de petits nombres est optimisée dans CPython 3.5, d'une manière qui n'est pas le cas des décalages vers la gauche de petits nombres. Les décalages positifs à gauche créent toujours un objet entier plus grand pour stocker le résultat, dans le cadre du calcul, alors que pour les multiplications du type de celles que vous avez utilisées dans votre test, une optimisation spéciale évite cela et crée un objet entier de la taille correcte. Ceci peut être vu dans le code source de l'implémentation des nombres entiers de Python .

Les entiers en Python étant de précision arbitraire, ils sont stockés sous forme de tableaux de "chiffres" entiers, avec une limite sur le nombre de bits par chiffre entier. Ainsi, dans le cas général, les opérations impliquant des entiers ne sont pas des opérations simples, mais doivent gérer le cas de plusieurs "chiffres". Sur pyport.h cette limite de bit est défini comme suit 30 bits sur une plate-forme 64 bits, ou 15 bits sinon. (J'appellerai cela 30 à partir de maintenant pour simplifier l'explication. Mais notez que si vous utilisiez Python compilé pour 32 bits, le résultat de votre benchmark dépendrait de si x étaient inférieurs à 32 768 ou non).

Lorsque les entrées et les sorties d'une opération restent dans cette limite de 30 bits, l'opération peut être traitée de manière optimisée au lieu de la manière générale. Le début de l'opération Mise en œuvre de la multiplication des nombres entiers est le suivant :

static PyObject *
long_mul(PyLongObject *a, PyLongObject *b)
{
    PyLongObject *z;

    CHECK_BINOP(a, b);

    /* fast path for single-digit multiplication */
    if (Py_ABS(Py_SIZE(a)) <= 1 && Py_ABS(Py_SIZE(b)) <= 1) {
        stwodigits v = (stwodigits)(MEDIUM_VALUE(a)) * MEDIUM_VALUE(b);
#ifdef HAVE_LONG_LONG
        return PyLong_FromLongLong((PY_LONG_LONG)v);
#else
        /* if we don't have long long then we're almost certainly
           using 15-bit digits, so v will fit in a long.  In the
           unlikely event that we're using 30-bit digits on a platform
           without long long, a large v will just cause us to fall
           through to the general multiplication code below. */
        if (v >= LONG_MIN && v <= LONG_MAX)
            return PyLong_FromLong((long)v);
#endif
    }

Ainsi, lorsque l'on multiplie deux entiers dont chacun tient dans un chiffre de 30 bits, cela est effectué comme une multiplication directe par l'interprète CPython, au lieu de travailler avec les entiers comme des tableaux. ( MEDIUM_VALUE() appelé sur un objet entier positif obtient simplement son premier chiffre de 30 bits). Si le résultat tient dans un seul chiffre de 30 bits, PyLong_FromLongLong() le remarquera dans un nombre relativement faible d'opérations, et créera un objet entier à un chiffre pour le stocker.

En revanche, les décalages à gauche ne sont pas optimisés de cette façon, et chaque décalage à gauche traite l'entier décalé comme un tableau. En particulier, si vous regardez le code source de long_lshift() Dans le cas d'un décalage vers la gauche faible mais positif, un objet entier à 2 chiffres est toujours créé, ne serait-ce que pour que sa longueur soit tronquée à 1 par la suite : (mes commentaires dans /*** ***/ )

static PyObject *
long_lshift(PyObject *v, PyObject *w)
{
    /*** ... ***/

    wordshift = shiftby / PyLong_SHIFT;   /*** zero for small w ***/
    remshift  = shiftby - wordshift * PyLong_SHIFT;   /*** w for small w ***/

    oldsize = Py_ABS(Py_SIZE(a));   /*** 1 for small v > 0 ***/
    newsize = oldsize + wordshift;
    if (remshift)
        ++newsize;   /*** here newsize becomes at least 2 for w > 0, v > 0 ***/
    z = _PyLong_New(newsize);

    /*** ... ***/
}

---

Division de nombres entiers

Vous n'avez pas posé de question sur les moins bonnes performances de la division des étages entiers par rapport aux équipes de droite, car cela correspondait à vos (et à mes) attentes. Mais la division d'un petit nombre positif par un autre petit nombre positif n'est pas non plus aussi optimisée que les petites multiplications. Chaque // calcule à la fois le quotient y le reste en utilisant la fonction long_divrem() . Ce reste est calculé pour un petit diviseur avec une multiplication y est stocké dans un objet entier nouvellement alloué qui, dans cette situation, est immédiatement rejetée.