manipulation - ¿Tiempos dos más rápidos que bit-shift para Python 3.x enteros?

python bit manipulation

Question

Estaba mirando la fuente de sorted_containers y me sorprendió ver esta línea :

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

Aquí load es un número entero. ¿Por qué usar bit shift en un lugar y multiplicación en otro? Parece razonable que el desplazamiento de bits sea más rápido que la división integral por 2, pero ¿por qué no reemplazar también la multiplicación por un desplazamiento? Comparé los siguientes casos:

1. (tiempos, dividir)
2. (turno, turno)
3. (tiempos, turno)
4. (cambio, división)

y descubrí que # 3 es consistentemente más rápido que otras alternativas:

# 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 pregunta:

¿Es válida mi prueba? Si es así, ¿por qué es (multiplicar, cambiar) más rápido que (cambiar, cambiar)?

Ejecuto Python 3.5 en Ubuntu 14.04.

Editar

Arriba está la declaración original de la pregunta. Dan Getz proporciona una excelente explicación en su respuesta.

En aras de la exhaustividad, aquí hay ilustraciones de muestra para x más grande cuando las optimizaciones de multiplicación no se aplican.

Answer 1

Esto parece deberse a que la multiplicación de números pequeños está optimizada en CPython 3.5, de una manera que los cambios a la izquierda por números pequeños no lo están. Los desplazamientos positivos a la izquierda siempre crean un objeto entero más grande para almacenar el resultado, como parte del cálculo, mientras que para las multiplicaciones del tipo que utilizó en su prueba, una optimización especial evita esto y crea un objeto entero del tamaño correcto. Esto se puede ver en el código fuente de la implementación entera de Python .

Debido a que los enteros en Python son de precisión arbitraria, se almacenan como matrices de "dígitos" enteros, con un límite en el número de bits por dígito entero. Entonces, en el caso general, las operaciones que involucran números enteros no son operaciones únicas, sino que necesitan manejar el caso de múltiples "dígitos". En pyport.h , este límite de bits se define como 30 bits en la plataforma de 64 bits, o 15 bits en caso contrario. (Solo llamaré a este 30 de aquí en adelante para que la explicación sea simple. Pero tenga en cuenta que si estuviera usando Python compilado para 32 bits, el resultado de su punto de referencia dependería de si x fuera menor que 32,768 o no).

Cuando las entradas y salidas de una operación permanecen dentro de este límite de 30 bits, la operación puede manejarse de manera optimizada en lugar de la forma general. El comienzo de la implementación de multiplicación de enteros es el siguiente:

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
    }

Entonces, al multiplicar dos enteros donde cada uno cabe en un dígito de 30 bits, esto se hace como una multiplicación directa por el intérprete CPython, en lugar de trabajar con los enteros como matrices. ( MEDIUM_VALUE() llamado a un objeto entero positivo simplemente obtiene su primer dígito de 30 bits). Si el resultado cabe en un solo dígito de 30 bits, PyLong_FromLongLong() lo notará en un número relativamente pequeño de operaciones y creará un solo objeto entero de dígitos para almacenarlo.

Por el contrario, los desplazamientos a la izquierda no están optimizados de esta manera, y cada desplazamiento a la izquierda trata con el número entero desplazado como una matriz. En particular, si observa el código fuente de long_lshift() , en el caso de un desplazamiento a la izquierda pequeño pero positivo, siempre se crea un objeto entero de 2 dígitos, aunque solo tenga su longitud truncada a 1 más tarde: (mis comentarios en /*** ***/ )

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);

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

División entera

No preguntó sobre el peor desempeño de la división de piso entero en comparación con los cambios correctos, porque eso se ajustaba a sus (y a mis) expectativas. Pero dividir un número positivo pequeño por otro número positivo pequeño tampoco es tan optimizado como las pequeñas multiplicaciones. Cada // calcula tanto el cociente como el resto utilizando la función long_divrem() . Este resto se calcula para un divisor pequeño con una multiplicación , y se almacena en un objeto entero recientemente asignado , que en esta situación se descarta inmediatamente.