python - color - plotly title

¿Por qué es 2*x*x más rápido que 2*(x*x) en Python 3.x, para enteros?

Question

La siguiente multiplicación de enteros de Python 3.x toma en promedio entre 1.66s y 1.77s:

import time
start_time = time.time()
num = 0
for x in range(0, 10000000):
    # num += 2 * (x * x)
    num += 2 * x * x
print("--- %s seconds ---" % (time.time() - start_time))

si sustituyo 2 * x * x por 2 *(x * x) , se tarda entre 2.04 y 2.25 . ¿Cómo?

Por otro lado, es lo contrario en Java: 2 * (x * x) es más rápido en Java. Enlace de prueba de Java: ¿Por qué es 2 * (i * i) más rápido que 2 * i * i en Java?

Ejecuté cada versión del programa 10 veces, aquí están los resultados.

   2 * x * x        |   2 * (x * x)
---------------------------------------
1.7717654705047607  | 2.0789272785186768
1.735931396484375   | 2.1166207790374756
1.7093875408172607  | 2.024367570877075
1.7004504203796387  | 2.047525405883789
1.6676218509674072  | 2.254328966140747
1.699510097503662   | 2.0949244499206543
1.6889283657073975  | 2.0841963291168213
1.7243537902832031  | 2.1290600299835205
1.712965488433838   | 2.1942825317382812
1.7622807025909424  | 2.1200053691864014

Answer 1

En primer lugar, tenga en cuenta que no vemos lo mismo en Python 2.x:

>>> timeit("for i in range(1000): 2*i*i")
51.00784397125244
>>> timeit("for i in range(1000): 2*(i*i)")
50.48330092430115

Así que esto nos lleva a creer que esto se debe a cómo los enteros cambiaron en Python 3: específicamente, Python 3 usa long (enteros arbitrariamente grandes) en todas partes.

Para los enteros lo suficientemente pequeños (incluidos los que estamos considerando aquí), CPython en realidad solo usa el algoritmo de multiplicación dígito a dígito de la escuela de grado O (MN) (para enteros más grandes cambia al algoritmo de Karatsuba ). Puedes ver esto tú mismo en la source .

El número de dígitos en x*x es aproximadamente el doble que 2*x x (ya que log (x ² ) = 2 log (x)). Tenga en cuenta que un "dígito" en este contexto no es un dígito de base 10, sino un valor de 30 bits (que se tratan como dígitos únicos en la implementación de CPython). Por lo tanto, 2 es un valor de un solo dígito, y x y 2*x son valores de un solo dígito para todas las iteraciones del bucle, pero x*x es de dos dígitos para x >= 2**15 . Por lo tanto, para x >= 2**15 , 2*x*x solo requiere multiplicaciones de un solo dígito, mientras que 2*(x*x) requiere una única por una y una simple por dos dígitos multiplicación (ya que x*x tiene 2 dígitos de 30 bits).

Aquí hay una forma directa de ver esto (Python 3):

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
5.796971936999967
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
4.3559221399999615

Nuevamente, compare esto con Python 2, que no usa enteros de longitud arbitraria en todas partes:

>>> timeit("a*b", "a,b = 2, 123456**2", number=100000000)
3.0912468433380127
>>> timeit("a*b", "a,b = 2*123456, 123456", number=100000000)
3.1120400428771973

(Una nota interesante: si miras la fuente, verás que el algoritmo en realidad tiene un caso especial para cuadrar números (lo que estamos haciendo aquí), pero aún así esto no es suficiente para superar el hecho de que 2*(x*x) solo requiere procesar más dígitos.)

Answer 2

La representación interna de enteros de Python es especial, utiliza ranuras de 30 bits:

In [6]: sys.getsizeof(2**30-1)
Out[6]: 28 # one slot + heading

In [7]: sys.getsizeof(2**30)
Out[7]: 32 # two slots 

Entonces todo sucede como si Python contara en la base B = 2**30 = 1 073 741 824 ~1 billion .

Para un humano que quiere calcular 2 * 4 * 4, de dos maneras:

• (2 * 4) * 4 = 8 * 4 = 32 = 30 + 2 es inmediato si conoce sus tablas adicionales.
• 2 * (4 * 4) = 2 * 16 = 2 * 10 + 2 * 6 = (2 * 10 + 10) + 2 = 30 + 2 ya que tenemos que cancelar la operación.

Python tiene el mismo problema. Si x es un número tal que 2x < B < x² , sea x² = aB+b , con a,b <B . x² se almacena en 2 ranuras, que observo (a|b) . Los cálculos conducen a (sin la gestión lleva aquí):

   (x*x)*2 =>  (a|b)*2 => (2*a|2*b)
   (2*x)*x =>  (2x)*x =>(2a|2b)

en el primer caso, la operación 2* se realiza dos veces, contra solo una en el primer caso. Eso explica la diferencia.

Answer 3

Por lo que puedo decir, se reduce a un poco más de acceso a la memoria en la versión usando 2 * (x * x) . Imprimí el bytecode desmontado y parece probar que:

Parte relevante de 2 * x * x :

7          28 LOAD_FAST                1 (num)
           30 LOAD_CONST               3 (2)
           32 LOAD_FAST                2 (x)
           34 BINARY_MULTIPLY
           36 LOAD_FAST                2 (x)
           38 BINARY_MULTIPLY
           40 INPLACE_ADD
           42 STORE_FAST               1 (num)
           44 JUMP_ABSOLUTE           24

Parte relevante de 2 * (x * x) :

  7          28 LOAD_FAST                1 (num)
             30 LOAD_CONST               3 (2)
             32 LOAD_FAST                2 (x)
             34 LOAD_FAST                2 (x)
             36 BINARY_MULTIPLY                 <=== 1st multiply x*x in a temp value
             38 BINARY_MULTIPLY                 <=== then multiply result with 2
             40 INPLACE_ADD
             42 STORE_FAST               1 (num)
             44 JUMP_ABSOLUTE           24

Answer 4

Si su punto de referencia es correcto (no se verificó), puede deberse al hecho de que los enteros de Python pueden ser dos cosas diferentes: enteros nativos cuando son pequeños (con un cálculo rápido) y enteros grandes cuando aumentan de tamaño (más lento cálculo). La primera sintaxis mantiene el tamaño más pequeño después de la primera operación, mientras que la segunda sintaxis puede llevar a dos operaciones con enteros grandes.