python - ¿Por qué el código usa variables intermedias más rápido que el código sin él?

python-3.x cpython

Question

Me he encontrado con este comportamiento extraño y no he podido explicarlo. Estos son los puntos de referencia:

py -3 -m timeit "tuple(range(2000)) == tuple(range(2000))"
10000 loops, best of 3: 97.7 usec per loop
py -3 -m timeit "a = tuple(range(2000));  b = tuple(range(2000)); a==b"
10000 loops, best of 3: 70.7 usec per loop

¿Cómo es que la comparación con la asignación de variables es más rápida que usar una línea con variables temporales en más del 27%?

Según los documentos de Python, la recolección de basura se deshabilita durante el tiempo, por lo que no puede ser eso. ¿Es algún tipo de optimización?

Los resultados también pueden reproducirse en Python 2.x, aunque en menor medida.

Ejecutando Windows 7, CPython 3.5.1, Intel i7 3.40 GHz, 64 bit tanto OS como Python. Parece que una máquina diferente que he intentado ejecutar en Intel i7 3.60 GHz con Python 3.5.0 no reproduce los resultados.

Ejecutar usando el mismo proceso de Python con timeit.timeit() @ 10000 bucles produjo 0.703 y 0.804 respectivamente. Todavía se muestra aunque en menor medida. (~ 12.5%)

Answer 1

La primera pregunta aquí tiene que ser, ¿es reproducible? Para algunos de nosotros, al menos definitivamente es así, aunque otras personas dicen que no están viendo el efecto. Esto en Fedora, con la prueba de igualdad cambiada, is que hacer una comparación parece irrelevante para el resultado, y el rango aumentó hasta 200,000, ya que parece maximizar el efecto:

$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.03 msec per loop
$ python3 -m timeit "a = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 9.99 msec per loop
$ python3 -m timeit "a = b = tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.2 msec per loop
$ python3 -m timeit "tuple(range(200000)) is tuple(range(200000))"
100 loops, best of 3: 10.1 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7 msec per loop
$ python3 -m timeit "a = tuple(range(200000));  b = tuple(range(200000)); a is b"
100 loops, best of 3: 7.02 msec per loop

Observo que las variaciones entre las ejecuciones y el orden en que se ejecutan las expresiones hacen muy poca diferencia en el resultado.

Agregar asignaciones a b en la versión lenta no lo acelera. De hecho, como podríamos esperar, la asignación a variables locales tiene un efecto insignificante. Lo único que lo acelera es dividir la expresión por completo en dos. La única diferencia que esto debería estar haciendo es que reduce la profundidad máxima de pila utilizada por Python al evaluar la expresión (de 4 a 3).

Eso nos da la pista de que el efecto está relacionado con la profundidad de la pila, tal vez el nivel adicional empuja la pila a otra página de memoria. Si es así, deberíamos ver que hacer otros cambios que afecten la pila cambiará (lo más probable es que elimine el efecto), y de hecho eso es lo que vemos:

$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   tuple(range(200000)) is tuple(range(200000))" "foo()"
100 loops, best of 3: 10 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 9.97 msec per loop
$ python3 -m timeit -s "def foo():
   a = tuple(range(200000));  b = tuple(range(200000)); a is b" "foo()"
100 loops, best of 3: 10 msec per loop

Entonces, creo que el efecto se debe completamente a la cantidad de Python stack que se consume durante el proceso de sincronización. Sin embargo, todavía es raro.

Answer 2

Mis resultados fueron similares a los suyos: el código que usaba variables intermedias era bastante consistente al menos 10-20% más rápido en Python 3.4. Sin embargo, cuando utilicé IPython en el mismo intérprete de Python 3.4, obtuve estos resultados:

In [1]: %timeit -n10000 -r20 tuple(range(2000)) == tuple(range(2000))
10000 loops, best of 20: 74.2 µs per loop

In [2]: %timeit -n10000 -r20 a = tuple(range(2000));  b = tuple(range(2000)); a==b
10000 loops, best of 20: 75.7 µs per loop

Notablemente, nunca logré acercarme siquiera a los 74.2 µs para el primero cuando usé -mtimeit desde la línea de comando.

Así que este Heisenbug resultó ser algo bastante interesante. Decidí ejecutar el comando con strace y de hecho hay algo sospechoso:

% strace -o withoutvars python3 -m timeit "tuple(range(2000)) == tuple(range(2000))"
10000 loops, best of 3: 134 usec per loop
% strace -o withvars python3 -mtimeit "a = tuple(range(2000));  b = tuple(range(2000)); a==b"
10000 loops, best of 3: 75.8 usec per loop
% grep mmap withvars|wc -l
46
% grep mmap withoutvars|wc -l
41149

Ahora esa es una buena razón para la diferencia. El código que no usa variables hace que la llamada al sistema mmap se llame casi 1000 veces más que la que usa variables intermedias.

El withoutvars está lleno de mmap / munmap para una región de 256k; Estas mismas líneas se repiten una y otra vez:

mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0
mmap(NULL, 262144, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f32e56de000
munmap(0x7f32e56de000, 262144)          = 0

La llamada mmap parece provenir de la función _PyObject_ArenaMmap de Objects/obmalloc.c ; el obmalloc.c también contiene la macro ARENA_SIZE , que es #define d to be (256 << 10) (es decir 262144 ); de manera similar, el munmap coincide con el _PyObject_ArenaMunmap de obmalloc.c .

obmalloc.c dice que

Antes de Python 2.5, las arenas nunca eran free() ''ed. Comenzando con Python 2.5, intentamos free() arenas, y usamos algunas estrategias heurísticas leves para aumentar la probabilidad de que las arenas eventualmente puedan liberarse.

Por lo tanto, estas heurísticas y el hecho de que el asignador de objetos Python libera estas arenas libres tan pronto como se vacían conducen a python3 -mtimeit ''tuple(range(2000)) == tuple(range(2000))'' desencadenando un comportamiento patológico donde uno 256 El área de memoria kiB se reasigna y se libera repetidamente; y esta asignación ocurre con mmap / munmap , que es relativamente costoso ya que son llamadas al sistema; además, mmap con MAP_ANONYMOUS requiere que las páginas recién mapeadas se MAP_ANONYMOUS cero, aunque a Python no le importe.

El comportamiento no está presente en el código que usa variables intermedias, porque está usando un poco más de memoria y no se puede liberar ningún espacio de memoria ya que algunos objetos todavía están asignados en él. Eso es porque el timeit lo convertirá en un bucle no muy diferente

for n in range(10000)
    a = tuple(range(2000))
    b = tuple(range(2000))
    a == b

Ahora el comportamiento es que tanto a como b permanecerán vinculados hasta que sean * reasignados, por lo que en la segunda iteración, tuple(range(2000)) asignará una tercera tupla, y la asignación a = tuple(...) disminuya el recuento de referencia de la antigua tupla, haciendo que se libere, y aumente el recuento de referencia de la nueva tupla; entonces lo mismo le sucede a b . Por lo tanto, después de la primera iteración siempre hay al menos 2 de estas tuplas, si no 3, por lo que no se produce la agitación.

En particular, no se puede garantizar que el código que usa variables intermedias sea siempre más rápido; de hecho, en algunas configuraciones puede ser que el uso de variables intermedias mmap llamadas adicionales de mmap , mientras que el código que compara los valores de retorno directamente podría estar bien.

Alguien preguntó por qué sucede esto, cuando timeit desactiva la recolección de basura. De hecho, es cierto que el timeit hace :

Nota

Por defecto, timeit() desactiva temporalmente la recolección de basura durante el tiempo. La ventaja de este enfoque es que hace que los tiempos independientes sean más comparables. Esta desventaja es que el GC puede ser un componente importante del desempeño de la función que se está midiendo. Si es así, GC se puede volver a habilitar como la primera instrucción en la cadena de configuración. Por ejemplo:

Sin embargo, el recolector de basura de Python solo está allí para reclamar basura cíclica , es decir, colecciones de objetos cuyas referencias forman ciclos. No es el caso aquí; en cambio, estos objetos se liberan inmediatamente cuando el recuento de referencia cae a cero.