¿Por qué el retorno anticipado es más lento que otro?

Question

Esta es una pregunta de seguimiento al an answer I gave a few days back. Editar: parece que el OP de esa pregunta ya usó el código que le envié para preguntar the same question, pero no lo sabía. Disculpas ¡Las respuestas proporcionadas son diferentes!

Sustancialmente he observado 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: con la cláusula else es más rápida, independientemente de la condición if ser activado o no.

Supongo que tiene que ver con diferentes bytecode generados por los dos, pero ¿alguien puede confirmar/explicar en detalle?

EDIT: Parece que no todo el mundo puede 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 la versión:

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

Éstos 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

Ésta es una conjetura pura, y no me he dado cuenta de una manera fácil de comprobar si es correcto, pero tengo una teoría para ti.

me trataron su código y obtener los mismos de los resultados, es without_else() repetidamente 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] 

Teniendo en cuenta que el código de bytes es idéntica, la única diferencia es el nombre de la función. En particular, la prueba de tiempo hace una búsqueda en el nombre global. Trate de cambiar el nombre de 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 algo más en globals() por lo que la búsqueda de nombres global es ligeramente más lento.

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 hash:

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

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

A partir de:

j = hash % 32 
perturb = hash 

Repita esto hasta que nos encontramos con una ranura 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 desde el valor hash j.

Cada sonda en la tabla se puede encontrar uno de estos:

• La ranura está vacía, en ese caso las paradas de sondeo y sabemos el valor no está en la tabla.

• La ranura no se ha utilizado, pero se utilizó en el pasado, en cuyo caso vamos a intentar el siguiente valor calculado como se indicó anteriormente.

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

• La ranura está llena y tiene exactamente el valor hash que queremos, entonces Python comprueba si la clave y el objeto que buscamos arriba son el mismo objeto (que en este caso serán debido cadenas cortas que podrían ser identificadores están internados, por lo que los identificadores idénticos usan exactamente la misma cadena).

• Finalmente, cuando la ranura está llena, el hash coincide exactamente, pero las claves no son el objeto idéntico, entonces y sólo entonces Python tratar comparándolos por la igualdad. Esto es comparativamente lento, pero en el caso de búsqueda de nombres no debería suceder realmente.