Je regardais la source de sorted_containers et j'ai été surpris de voir cette ligne :

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

Voici loadun entier. Pourquoi utiliser le décalage de bits à un endroit et la multiplication à un autre? Il semble raisonnable que le décalage de bits soit plus rapide que la division intégrale par 2, mais pourquoi ne pas remplacer la multiplication par un décalage également? J'ai comparé les cas suivants:

1. (fois, diviser)
2. (shift, shift)
3. (horaires, décalage)
4. (déplacer, diviser)

et a constaté que le n ° 3 est systématiquement 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 valide? Si oui, pourquoi (multiplier, déplacer) est-il plus rapide que (décalage, décalage)?

J'exécute Python 3.5 sur Ubuntu 14.04.

Éditer

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

Par souci d'exhaustivité, voici des exemples d'illustrations plus grandes xlorsque les optimisations de multiplication ne s'appliquent pas.

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

Comme les entiers en Python sont 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 uniques, mais doivent à la place gérer le cas de plusieurs «chiffres». Dans pyport.h , cette limite de bits est définie comme 30 bits sur une plate-forme 64 bits, ou 15 bits dans le cas contraire. (J'appellerai simplement ce 30 à partir de maintenant pour garder l'explication simple. Mais notez que si vous utilisiez Python compilé pour 32 bits, le résultat de votre benchmark dépendrait de savoir s'il xétait inférieur à 32 768 ou non.)

Lorsque les entrées et sorties d'une opération restent dans cette limite de 30 bits, l'opération peut être gérée de manière optimisée au lieu de la manière générale. Le début de l' implémentation de la multiplication d'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, lors de la multiplication de deux entiers où chacun tient dans un chiffre de 30 bits, cela se fait comme une multiplication directe par l'interpréteur CPython, au lieu de travailler avec les entiers sous forme de 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 restreint d'opérations et créera un objet entier à un chiffre à stocker il.

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é sous forme de tableau. En particulier, si vous regardez le code source pour long_lshift(), dans le cas d'un décalage gauche petit mais positif, un objet entier à 2 chiffres est toujours créé, ne serait-ce que pour avoir sa longueur tronquée à 1 plus tard: (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 entière

Vous n'avez pas posé de questions sur les pires performances de la division des étages entiers par rapport aux bons changements, car cela correspond à vos (et mes) attentes. Mais diviser un petit nombre positif par un autre petit nombre positif n'est pas non plus aussi optimisé que de petites multiplications. Chacun //calcule à la fois le quotient et le reste en utilisant la fonction long_divrem(). Ce reste est calculé pour un petit diviseur avec une multiplication et est stocké dans un objet entier nouvellement alloué , qui dans cette situation est immédiatement ignoré.