¿Dos veces más rápido que el cambio de bits, para los enteros de Python 3.x?

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

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

Aquí la load es un 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 la multiplicación por un desplazamiento también? Yo comparé los siguientes casos:

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

y encontró 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 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)]) 

introduzca la descripción de la imagen aquí introduzca la descripción de la imagen aquí

La pregunta:

¿Mi examen es válido? 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 statement original de la pregunta. Dan Getz proporciona una excelente explicación en su respuesta.

En aras de la integridad, aquí hay ejemplos de ilustraciones para x más grandes cuando no se aplican optimizaciones de multiplicación.

introduzca la descripción de la imagen aquí introduzca la descripción de la imagen aquí

Esto parece ser porque la multiplicación de números pequeños está optimizada en CPython 3.5, de una manera que los desplazamientos a la izquierda por números pequeños no lo son. Los desplazamientos a la izquierda positivos 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 de enteros de Python .

Debido a que los enteros en Python tienen una 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 simples, 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 una plataforma de 64 bits, o 15 bits en caso contrario. (Llamaré a este 30 de aquí en adelante para simplificar la explicación. Pero tenga en cuenta que si estuviera usando Python comstackdo para 32 bits, el resultado de su prueba de rendimiento dependería de si x fuera menor que 32,768).

Cuando las entradas y salidas de una operación se mantienen dentro de este límite de 30 bits, la operación se puede manejar de una manera optimizada en lugar de la forma general. El comienzo de la implementación de la 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 encaja en un dígito de 30 bits, esto se realiza como una multiplicación directa por el intérprete CPython, en lugar de trabajar con los enteros como matrices. ( MEDIUM_VALUE() llamado en un objeto entero positivo simplemente obtiene su primer dígito de 30 bits.) Si el resultado encaja en un solo dígito de 30 bits, PyLong_FromLongLong() notará esto en un número relativamente pequeño de operaciones, y creará una única -digit objeto entero para almacenarlo.

En contraste, los desplazamientos a la izquierda no se optimizan de esta manera, y cada desplazamiento a la izquierda se ocupa del desplazamiento del entero como una matriz. En particular, si observa el código fuente de long_lshift() , en el caso de un pequeño pero positivo desplazamiento a la izquierda, siempre se crea un objeto entero de 2 dígitos, aunque solo sea para que su longitud se trunque 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 preguntaste sobre el peor desempeño de la división de piso entero en comparación con los turnos correctos, porque eso se ajusta a tus (y mis) expectativas. Pero la división de un pequeño número positivo por otro pequeño número positivo tampoco está tan optimizada como pequeñas multiplicaciones. Cada // calcula tanto el cociente como el rest mediante la función long_divrem() . Este rest se calcula para un pequeño divisor con una multiplicación , y se almacena en un objeto entero recién asignado , que en esta situación se descarta de inmediato.