python - ¿Por qué el retorno temprano es más lento que el resto?

optimization python-2.7

Question

Esta es una pregunta de seguimiento a una respuesta que di hace unos días . Editar: parece que el PO de esa pregunta ya usó el código que le envié para hacer la misma pregunta , pero no lo sabía. Disculpas ¡Las respuestas proporcionadas son diferentes!

Sustancialmente, observé que:

>>> def without_else(param=False):
... if param:
... return 1
... return 0
>>> def with_else(param=False):
... if param:
... return 1
... else:
... return 0
>>> from timeit import Timer as T
>>> T(lambda : without_else()).repeat()
[0.3011460304260254, 0.2866089344024658, 0.2871549129486084]
>>> T(lambda : with_else()).repeat()
[0.27536892890930176, 0.2693932056427002, 0.27011704444885254]
>>> T(lambda : without_else(True)).repeat()
[0.3383951187133789, 0.32756996154785156, 0.3279120922088623]
>>> T(lambda : with_else(True)).repeat()
[0.3305950164794922, 0.32186388969421387, 0.3209099769592285]

... o en otras palabras: tener la cláusula else es más rápido independientemente de if condición if se desencadena o no.

Supongo que tiene que ver con diferentes códigos de bytes generados por los dos, pero ¿alguien puede confirmar / explicar en detalle?

EDITAR: Parece que no todos pueden reproducir mis tiempos, así que pensé que podría ser útil dar algo de información sobre mi sistema. Estoy ejecutando Ubuntu 11.10 de 64 bits con el pitón predeterminado instalado. python genera la siguiente información de versión:

Python 2.7.2+ (default, Oct 4 2011, 20:06:09)
[GCC 4.6.1] on linux2

Estos son los resultados del desmontaje en Python 2.7:

>>> dis.dis(without_else)
2 0 LOAD_FAST 0 (param)
3 POP_JUMP_IF_FALSE 10
3 6 LOAD_CONST 1 (1)
9 RETURN_VALUE
4 >> 10 LOAD_CONST 2 (0)
13 RETURN_VALUE
>>> dis.dis(with_else)
2 0 LOAD_FAST 0 (param)
3 POP_JUMP_IF_FALSE 10
3 6 LOAD_CONST 1 (1)
9 RETURN_VALUE
5 >> 10 LOAD_CONST 2 (0)
13 RETURN_VALUE
14 LOAD_CONST 0 (None)
17 RETURN_VALUE

Answer 1

Esta es una pura suposición, y no he encontrado una manera fácil de verificar si está bien, pero tengo una teoría para ti.

without_else() tu código y without_else() los mismos resultados, without_else() es repetidamente un poco más lento que with_else() :

>>> T(lambda : without_else()).repeat()
[0.42015745017874906, 0.3188967452567226, 0.31984281521812363]
>>> T(lambda : with_else()).repeat()
[0.36009842032996175, 0.28962249392031936, 0.2927151355828528]
>>> T(lambda : without_else(True)).repeat()
[0.31709728471076915, 0.3172671387005721, 0.3285821242644147]
>>> T(lambda : with_else(True)).repeat()
[0.30939889008243426, 0.3035132258429485, 0.3046679117038593]

Teniendo en cuenta que el bytecode es idéntico, la única diferencia es el nombre de la función. En particular, la prueba de tiempo hace una búsqueda en el nombre global. Intenta renombrar without_else() y la diferencia desaparece:

>>> def no_else(param=False):
if param:
return 1
return 0
>>> T(lambda : no_else()).repeat()
[0.3359846013948413, 0.29025818923918223, 0.2921801513879245]
>>> T(lambda : no_else(True)).repeat()
[0.3810395594970828, 0.2969634408842694, 0.2960104566362247]

Mi suposición es que without_else tiene una colisión hash con algo más en globals() por lo que la búsqueda de nombres global es un poco más lenta.

Editar : Un diccionario con 7 u 8 teclas probablemente tenga 32 ranuras, por lo que sobre esa base without_else tiene una colisión hash con __builtins__ :

>>> [(k, hash(k) % 32) for k in globals().keys() ]
[(''__builtins__'', 8), (''with_else'', 9), (''__package__'', 15), (''without_else'', 8), (''T'', 21), (''__name__'', 25), (''no_else'', 28), (''__doc__'', 29)]

Para aclarar cómo funciona el hash:

__builtins__ hashes a -1196389688 que reducen el módulo el tamaño de la tabla (32) significa que está almacenado en el n. ° 8 de la mesa.

without_else hashes to 505688136 que redujo el módulo 32 es 8 por lo que hay una colisión. Para resolver esto, Python calcula:

Empezando con:

j = hash % 32
perturb = hash

Repite esto hasta que encontremos un espacio libre:

j = (5*j) + 1 + perturb;
perturb >>= 5;
use j % 2**i as the next table index;

que le da 17 para usar como el siguiente índice. Afortunadamente, eso es gratis, por lo que el ciclo solo se repite una vez. El tamaño de la tabla hash es una potencia de 2, por lo que 2**i es el tamaño de la tabla hash, i es la cantidad de bits utilizados a partir del valor hash j .

Cada sonda en la tabla puede encontrar uno de estos:

• La ranura está vacía, en ese caso el sondeo se detiene y sabemos que el valor no está en la tabla.

• La ranura no se usó pero se usó en el pasado, en cuyo caso vamos a probar el siguiente valor calculado como se indicó anteriormente.

• La ranura está llena, pero el valor hash completo almacenado en la tabla no es lo mismo que el hash de la clave que estamos buscando (eso es lo que sucede en el caso de __builtins__ vs without_else ).

• La ranura está llena y tiene exactamente el valor hash que queremos, Python verifica si la clave y el objeto que estamos buscando son el mismo objeto (que en este caso lo serán porque las cadenas cortas que podrían ser identificadores están intercaladas de manera identificadores idénticos usan exactamente la misma cadena).

• Finalmente, cuando la ranura está llena, el hash coincide exactamente, pero las teclas no son el objeto idéntico, entonces, y solo entonces, Python intentará compararlas para obtener igualdad. Esto es comparativamente lento, pero en el caso de las búsquedas de nombres no debería suceder realmente.