Perché il ritorno anticipato è più lento di altri?

Question

Questa è una domanda successiva a an answer I gave a few days back. Modifica: sembra che l'OP di quella domanda abbia già utilizzato il codice che gli ho inviato per chiedere the same question, ma non ne ero a conoscenza. Scuse. Le risposte fornite sono diverse però!

Sostanzialmente ho osservato che:

>>> 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 in altre parole: avere la clausola else è più veloce indipendentemente dalla condizione if essere attivato o meno.

Suppongo che abbia a che fare con diversi bytecode generati dai due, ma qualcuno è in grado di confermare/spiegare in dettaglio?

EDIT: Sembra che non tutti siano in grado di riprodurre i tempi, quindi ho pensato che potrebbe essere utile fornire alcune informazioni sul mio sistema. Sto usando Ubuntu 11.10 64 bit con il python predefinito installato. python genera le seguenti informazioni di versione:

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

Ecco i risultati del disassemblaggio in 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

Si tratta di una congettura pura, e non ho capito un modo semplice per controllare se è giusto, ma ho una teoria per te.

Ho provato il codice e ottengono stesso dei risultati, without_else() è ripetutamente leggermente più lento 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 che il bytecode è identica, l'unica differenza è il nome della funzione. In particolare il test di temporizzazione fa una ricerca sul nome globale. Provare a rinominare without_else() e la differenza scompare:

>>> 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] 

mia ipotesi è che without_else ha una collisione hash con qualcos'altro in globals() quindi la ricerca del nome globale è leggermente più lento.

Edit: Un dizionario con 7 o 8 tasti probabilmente ha 32 slot, così su questa base without_else ha una collisione 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)] 

a chiarire come l'hashing:

__builtins__ hash a -1196389688 che ha ridotto modulo la dimensione della tabella (32) significa che è memorizzato nello slot # 8 della tabella.

without_else hash a 505688136 che ha ridotto modulo 32 è 8 quindi c'è una collisione.Per risolvere il Python calcola:

Inizia con:

j = hash % 32 
perturb = hash 

Ripetere questo fino a quando troviamo uno slot libero:

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

che gli conferisce 17 da utilizzare come l'indice successivo. Fortunatamente è gratis, quindi il ciclo si ripete solo una volta. La dimensione della tabella hash è una potenza di 2, quindi 2**i è la dimensione della tabella hash, i è il numero di bit utilizzati dal valore hash j.

Ogni sonda nella tabella può trovare uno di questi:

• Lo slot è vuoto, in questo caso le fermate di sondaggio e sappiamo il valore non è nella tabella.

• Lo slot non è utilizzato ma è stato utilizzato in passato, nel qual caso andiamo a provare il valore successivo calcolato come sopra.

• Lo slot è pieno, ma il valore hash completo memorizzato nella tabella non è lo stesso che l'hash della chiave che stiamo cercando (che è quello che accade nel caso di __builtins__ vs without_else).

• Lo slot è pieno e ha esattamente il valore di hash che vogliamo, poi Python controlli per vedere se la chiave e l'oggetto che stiamo cercando up sono lo stesso oggetto (che in questo caso saranno perché brevi stringhe che potrebbero essere identificatori internati in modo identico identificatori utilizzare la stessa stringa esatta).

• Infine quando lo slot è piena, l'hash corrisponde esattamente, ma le chiavi non sono oggetto identico, allora e solo allora Python provare confrontandoli per la parità. Questo è relativamente lento, ma nel caso di ricerche di nomi non dovrebbe effettivamente accadere.