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

Question

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

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

Sustancialmente observé que: {[13]]}

>>> 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 que la condición if se active o no.

Asumo que tiene tiene que ver con diferentes bytecode generados por los dos, pero ¿alguien es capaz de confirmar/explicar en detalle?

EDITAR: Parece que no todo el mundo es capaz de reproducir mis tiempos, así que pensé que podría ser útil para dar algo de información sobre mi sistema. Estoy ejecutando Ubuntu 11.10 de 64 bits con Python instalado por defecto. 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

Aquí están 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

158

python optimization python-2.7

Author: Community, 2011-11-25

Source

1 answers

score 347 · Accepted Answer

Esto es una suposición pura, y no he descubierto una manera fácil de comprobar si es correcto, pero tengo una teoría para usted.

Probé tu código y obtener los mismos resultados, without_else() repetidamente es ligeramente 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]

Considerando 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 conjetura es que without_else tiene una colisión hash con otra cosa en globals() por lo que la búsqueda de nombres globales es ligeramente más lenta.

Editar : Un diccionario con 7 u 8 teclas probablemente tiene 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 hashing:

__builtins__ hashes a -1196389688 que redujo modulo el tamaño de la tabla (32) significa que se almacena en la ranura #8 de la tabla.

without_else hashes a 505688136 que reducido módulo 32 es 8 so hay una colisión. Para resolver esto Python calcula:

Empezando por:

j = hash % 32
perturb = hash

Repita esto hasta que encontremos una ranura libre:

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

Lo que le da 17 para usar como el siguiente índice. Afortunadamente eso es gratis por lo que el bucle 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 el número de bits utilizados del valor hash j.

Cada sonda en la tabla puede encontrar uno de estos:

La ranura está vacío, en ese caso el sondeo se detiene y sabemos la el valor no está en la tabla.
La ranura no se utiliza, pero se utilizó en el pasado, en cuyo caso vamos a probar el siguiente valor calculado como arriba.
La ranura está llena, pero el valor hash completo almacenado en la tabla no lo está 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 de hash que queremos, entonces Python comprueba si la clave y el objeto que estamos buscando son los mismo objeto (que en este caso serán porque cadenas cortas que podrían ser identificadores se internan identificadores tan idénticos utilizan la misma cadena exacta).
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á comparándolos para la igualdad. Esto es comparativamente lento, pero en el en realidad, las búsquedas de nombres no deberían suceder.