¿Por qué es mucho más lento copiar una lista aleatoria?

89

Copiar una range(10**6)lista aleatoria diez veces me lleva alrededor de 0.18 segundos: (estas son cinco ejecuciones)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

Copiar la lista sin mezclar diez veces me lleva alrededor de 0.05 segundos:

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

Aquí está mi código de prueba:

from timeit import timeit
import random

a = range(10**6)
random.shuffle(a)    # Remove this for the second test.
a = list(a)          # Just an attempt to "normalize" the list.
for _ in range(5):
    print timeit(lambda: list(a), number=10)

También intenté copiar con a[:], los resultados fueron similares (es decir, gran diferencia de velocidad)

¿Por qué la gran diferencia de velocidad? Conozco y entiendo la diferencia de velocidad en el famoso ¿Por qué es más rápido procesar una matriz ordenada que una matriz no ordenada? ejemplo, pero aquí mi procesamiento no tiene decisiones. Es simplemente copiar ciegamente las referencias dentro de la lista, ¿no?

Estoy usando Python 2.7.12 en Windows 10.

Editar: Probé Python 3.5.2 también ahora, los resultados fueron casi los mismos (mezclados consistentemente alrededor de 0.17 segundos, sin mezclar constantemente alrededor de 0.05 segundos). Aquí está el código para eso:

a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
    print(timeit(lambda: list(a), number=10))
python python-internals Stefan Pochmann
fuente
22
Por qué ordenar una matriz hace que un bucle de Python sea más rápido
vaultah
5
Por favor, no me grites, ¡estaba tratando de ayudarte! Después de cambiar el orden, obtengo aproximadamente 0.25en cada iteración de cada una de las pruebas. Entonces, en mi plataforma, el orden sí importa.
barak manos
1
@vaultah Gracias, pero lo he leído ahora y no estoy de acuerdo. Cuando vi el código allí, inmediatamente pensé en los aciertos / errores de caché de los ints, que también es la conclusión del autor. Pero su código agrega los números, lo que requiere mirarlos. Mi código no lo hace. El mío solo necesita copiar las referencias, no acceder a través de ellas.
Stefan Pochmann
2
Hay una respuesta completa en un enlace de @vaultah (ya veo que estás un poco en desacuerdo). Pero de todos modos, sigo pensando que no deberíamos usar Python para funciones de bajo nivel y, por lo tanto, preocuparnos. Pero ese tema es interesante de todos modos, gracias.
Nikolay Prokopyev
1
@NikolayProkopyev Sí, no estoy preocupado por eso, solo me di cuenta de esto mientras hacía otra cosa, no podía explicarlo y sentí curiosidad. Y me alegro de haber preguntado y tener una respuesta ahora :-)
Stefan Pochmann

Respuestas:

100

Lo interesante es que depende del orden en el que se creen primero los números enteros . Por ejemplo, en lugar de shufflecrear una secuencia aleatoria con random.randint:

from timeit import timeit
import random

a = [random.randint(0, 10**6) for _ in range(10**6)]
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

Esto es tan rápido como copiar su list(range(10**6))(primer y rápido ejemplo).

Sin embargo, cuando barajas, tus enteros ya no están en el orden en que fueron creados, eso es lo que lo hace lento.

Un intermezzo rápido:

  • Todos los objetos de Python están en el montón, por lo que cada objeto es un puntero.
  • Copiar una lista es una operación superficial.
  • Sin embargo, Python usa el recuento de referencias, por lo que cuando un objeto se coloca en un nuevo contenedor, su recuento de referencias debe incrementarse ( Py_INCREFenlist_slice ), por lo que Python realmente necesita ir a donde está el objeto. No puede simplemente copiar la referencia.

Entonces, cuando copia su lista, obtiene cada elemento de esa lista y lo coloca "como está" en la nueva lista. Cuando su siguiente elemento se creó poco después del actual, hay una buena posibilidad (¡no hay garantía!) De que se guarde junto a él en el montón.

Supongamos que cada vez que su computadora carga un elemento en la caché, también carga los elementos xsiguientes en la memoria (localidad de la caché). ¡Entonces su computadora puede realizar el incremento de recuento de referencias para x+1elementos en el mismo caché!

Con la secuencia barajada, todavía carga los elementos siguientes en la memoria, pero estos no son los siguientes en la lista. Por lo tanto, no puede realizar el incremento del recuento de referencias sin buscar "realmente" el siguiente elemento.

TL; DR: La velocidad real depende de lo que sucedió antes de la copia: en qué orden se crearon estos elementos y en qué orden están en la lista.

Puede verificar esto mirando el id:

Detalle de implementación de CPython: esta es la dirección del objeto en la memoria.

a = list(range(10**6, 10**6+100))
for item in a:
    print(id(item))

Solo para mostrar un breve extracto:

1496489995888
1496489995920  # +32
1496489995952  # +32
1496489995984  # +32
1496489996016  # +32
1496489996048  # +32
1496489996080  # +32
1496489996112
1496489996144
1496489996176
1496489996208
1496489996240
1496507297840
1496507297872
1496507297904
1496507297936
1496507297968
1496507298000
1496507298032
1496507298064
1496507298096
1496507298128
1496507298160
1496507298192

Entonces, estos objetos están realmente "uno al lado del otro en el montón". Con shuffleellos no son:

import random
a = list(range(10**6, 100+10**6))
random.shuffle(a)
last = None
for item in a:
    if last is not None:
        print('diff', id(item) - id(last))
    last = item

Lo que muestra que estos no están realmente uno al lado del otro en la memoria:

diff 736
diff -64
diff -17291008
diff -128
diff 288
diff -224
diff 17292032
diff -1312
diff 1088
diff -17292384
diff 17291072
diff 608
diff -17290848
diff 17289856
diff 928
diff -672
diff 864
diff -17290816
diff -128
diff -96
diff 17291552
diff -192
diff 96
diff -17291904
diff 17291680
diff -1152
diff 896
diff -17290528
diff 17290816
diff -992
diff 448

Nota IMPORTANTE:

No lo he pensado yo mismo. La mayoría de la información se puede encontrar en la publicación del blog de Ricky Stewart .

Esta respuesta se basa en la implementación CPython "oficial" de Python. Los detalles en otras implementaciones (Jython, PyPy, IronPython, ...) pueden ser diferentes. Gracias @ JörgWMittag por señalar esto .

MSeifert
fuente
6
@augurar Copiar una referencia implica incrementar el contador de referencia que está en el objeto (por lo tanto, el acceso al objeto es inevitable)
León
1
@StefanPochmann La función que realiza la copia es list_slicey en la línea 453 puede ver la Py_INCREF(v);llamada que necesita para acceder al objeto asignado al montón.
MSeifert
1
@MSeifert Otro buen experimento es el uso a = [0] * 10**7(de 10 ** 6 porque era demasiado inestable), que es incluso más rápido que el uso a = range(10**7)(por un factor de aproximadamente 1,25). Claramente porque eso es incluso mejor para el almacenamiento en caché.
Stefan Pochmann
1
Me preguntaba por qué obtuve números enteros de 32 bits en una computadora de 64 bits con Python de 64 bits. Pero en realidad eso también es bueno para el almacenamiento en caché :-) Even [0,1,2,3]*((10**6) // 4)es tan rápido como a = [0] * 10**6. Sin embargo, con los números enteros del 0 al 255, hay otro hecho: estos están internos, por lo que el orden de creación (dentro de su secuencia de comandos) ya no es importante, porque se crean cuando inicia Python.
MSeifert
2
Tenga en cuenta que de las cuatro implementaciones de Python listas para producción que existen actualmente, solo una utiliza el recuento de referencias. Entonces, este análisis realmente solo se aplica a una sola implementación.
Jörg W Mittag
24

Cuando mezcla los elementos de la lista, tienen una localidad de referencia peor, lo que conduce a un peor rendimiento de la caché.

Podría pensar que copiar la lista solo copia las referencias, no los objetos, por lo que sus ubicaciones en el montón no deberían importar. Sin embargo, copiar aún implica acceder a cada objeto para modificar el recuento de referencias.

augurar
fuente
Esta podría ser una mejor respuesta para mí (al menos si tuviera un enlace a una "prueba" como la de MSeifert) ya que esto es todo lo que me faltaba y es muy conciso, pero creo que me quedaré con MSeifert como creo que podría ser mejor para los demás. Sin embargo, también voté a favor de esto, gracias.
Stefan Pochmann
También agregará que los pentioides, athlums, etc.tienen una lógica mística en ellos para detectar patrones de direcciones, y comenzarán a buscar datos previamente cuando vean un patrón. Lo que, en este caso, podría estar activando la captación previa de datos (reduciendo las pérdidas de caché) cuando los números están en orden. Este efecto se suma, por supuesto, al aumento del% de golpes desde la localidad.
Greggo
5

Como explicaron otros, no se trata solo de copiar las referencias, sino que también aumenta el recuento de referencias dentro de los objetos y, por lo tanto, se accede a los objetos y la caché juega un papel.

Aquí solo quiero agregar más experimentos. No tanto sobre barajado vs no barajado (donde acceder a un elemento puede perder el caché pero obtener los siguientes elementos en el caché para que sean golpeados). Pero sobre la repetición de elementos, donde los accesos posteriores del mismo elemento pueden afectar la caché porque el elemento todavía está en la caché.

Probando un rango normal:

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

Una lista del mismo tamaño pero con un solo elemento repetido una y otra vez es más rápida porque llega a la caché todo el tiempo:

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

Y no parece importar qué número sea:

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

Curiosamente, se vuelve aún más rápido cuando, en cambio, repito los mismos dos o cuatro elementos:

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

Supongo que a algo no le gusta que el mismo contador se incremente todo el tiempo. Tal vez alguna tubería se detenga porque cada aumento tiene que esperar el resultado del aumento anterior, pero esta es una suposición descabellada.

De todos modos, intente esto para un número aún mayor de elementos repetidos:

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

El resultado (la primera columna es el número de elementos diferentes, para cada uno pruebo tres veces y luego tomo el promedio):

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

Entonces, de aproximadamente 2.8 segundos para un solo elemento (repetido), cae a aproximadamente 2.2 segundos para 2, 4, 8, 16, ... elementos diferentes y permanece en aproximadamente 2.2 segundos hasta los cien mil. Creo que esto usa mi caché L2 (4 × 256 KB, tengo un i7-6700 ).

Luego, en unos pocos pasos, los tiempos suben a 3,5 segundos. Creo que esto usa una mezcla de mi caché L2 y mi caché L3 (8 MB) hasta que eso también se "agota".

Al final, se mantiene en unos 3,5 segundos, supongo que porque mis cachés ya no ayudan con los elementos repetidos.

Stefan Pochmann
fuente
0

Antes de la reproducción aleatoria, cuando se asignan en el montón, los objetos de índice adyacentes son adyacentes en la memoria y la tasa de aciertos de la memoria es alta cuando se accede a ellos; después de barajar, el objeto del índice adyacente de la nueva lista no está en la memoria. Adyacente, la tasa de aciertos es muy baja.

xws
fuente