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


Me he encontrado con este comportamiento extraño y no pude 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 variable es más rápida que usar un trazador de líneas único con variables temporales en más del 27%?

Según los documentos de Python, la recolección de basura está deshabilitada durante el tiempo, por lo que no puede ser así. ¿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 OS y Python. Parece una máquina diferente que he intentado ejecutar en Intel i7 3.60 GHz con Python 3.5.0 no reproduce los resultados.


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


75
2018-04-11 12:19


origen


Respuestas:


Mis resultados fueron similares a los tuyos: el código que usó variables intermedias fue bastante consistente al menos un 10-20% más rápido en el Python 3.4 que cansaba. 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 a los 74.2 μs de la primera cuando usaba -mtimeit desde la linea de comando

Entonces 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 causa mmap la llamada al sistema se llama casi 1000 veces más que la que usa variables intermedias.

los 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

los mmap la llamada parece provenir de la función _PyObject_ArenaMmap de Objects/obmalloc.c; el obmalloc.c también contiene la macro ARENA_SIZE, cual es #defined ser (256 << 10) (es decir 262144); del mismo modo el munmap coincide con el _PyObject_ArenaMunmap de obmalloc.c.

obmalloc.c dice que

Antes de Python 2.5, las arenas nunca fueron free()'ed. Comenzando con Python 2.5,   nosotros tratamos de free() arenas, y utilizan algunas estrategias heurísticas leves para aumentar   la probabilidad de que las arenas eventualmente puedan ser liberadas.

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

El comportamiento no está presente en el código que usa variables intermedias, porque está usando un poco Más la memoria y la arena sin memoria se pueden liberar ya que algunos objetos aún están asignados en ella. Eso es porque timeit lo convertirá en un ciclo no muy diferente

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

Ahora el comportamiento es que ambos ay 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(...) disminuirá el recuento de referencia de la antigua tupla, haciendo que se libere, y aumente el recuento de referencia de la nueva tupla; entonces pasa lo mismo 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 paliza.

Lo más notable es que no se puede garantizar que el código que utiliza variables intermedias siempre sea más rápido; de hecho, en algunas configuraciones podría ser que el uso de variables intermedias resulte en un extra mmap llamadas, mientras que el código que compara valores de retorno directamente podría estar bien.


Alguien preguntó por qué sucede esto, cuando timeit deshabilita la recolección de basura Es cierto que timeit lo 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 GC puede ser un componente importante del rendimiento de la función que se mide. Si es así, GC puede volver a habilitarse como la primera instrucción en la cadena de configuración. Por ejemplo:

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


101
2018-04-11 13:08



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 a is como en realidad hacer una comparación parece irrelevante para el resultado, y el rango empujó hasta 200,000 ya que eso 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

Noto 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 ay 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 completamente en dos. La única diferencia que 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 clave de que el efecto está relacionado con la profundidad de la pila, quizás el nivel extra empuje la pila hacia otra página de memoria. Si es así, deberíamos ver que cambiar otros cambios que afecten a la pila cambiará (lo más probable es que mate 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

Por lo tanto, creo que el efecto se debe completamente a cuánta pila de Python se consume durante el proceso de sincronización. Sin embargo, todavía es extraño.


7
2018-04-11 13:04