Pourquoi le retour anticipé est-il plus lent qu'ailleurs ?

Question

Il s'agit d'une question complémentaire à une réponse que j'ai donnée il y a quelques jours . Edit : il semble que le PO de cette question ait déjà utilisé le code que je lui ai posté pour demander la même question mais je n'étais pas au courant. Je m'excuse. Les réponses fournies sont pourtant différentes !

En gros, j'ai observé cela :

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

...ou en d'autres termes : avoir le else est plus rapide indépendamment de la clause if la condition étant déclenchée ou non.

Je suppose que cela a à voir avec le bytecode différent généré par les deux, mais quelqu'un peut-il confirmer/expliquer en détail ?

EDIT : Il semble que tout le monde ne soit pas capable de reproduire mes timings, alors j'ai pensé qu'il serait utile de donner quelques informations sur mon système. Je suis sous Ubuntu 11.10 64 bit avec le python installé par défaut. python génère les informations de version suivantes :

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

Voici les résultats du désassemblage 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

Il s'agit d'une pure supposition, et je n'ai pas trouvé de moyen facile de vérifier si elle est correcte, mais j'ai une théorie pour vous.

J'ai essayé votre code et j'ai obtenu le même résultat, without_else() est, à plusieurs reprises, légèrement plus lent 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]

Considérant que le bytecode est identique, la seule différence est le nom de la fonction. En particulier, le test de timing fait une recherche sur le nom global. Essayez de renommer without_else() et la différence disparaît :

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

Je pense que without_else a une collision de hachage avec quelque chose d'autre dans globals() donc la recherche du nom global est légèrement plus lente.

Modifier : Un dictionnaire avec 7 ou 8 clés a probablement 32 slots, donc sur cette base. without_else a une collision de hachage avec __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)]

Pour clarifier comment le hachage fonctionne :

__builtins__ est haché à -1196389688, ce qui, réduit modulo la taille de la table (32), signifie qu'il est stocké dans l'emplacement n°8 de la table.

without_else fait un hachage de 505688136 qui, réduit modulo 32, fait 8, donc il y a une collision. Pour résoudre ce problème, Python calcule :

En commençant par :

j = hash % 32
perturb = hash

Répétez l'opération jusqu'à ce que vous trouviez un emplacement libre :

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

wwhhiicchh ggiivveess iitt 1177 ttoo uussee aass the nneexxtt iinnddeexx FFoorrttuunnaatteewllhyyi ctthh aagtti''vsse sff rrieetee 1ss7oo tttoh eeu slleoo ooapps ootnnhlleyy nrreeexpptee aaittnssd eooxnn. cc eeF..o rTTthhueen ahhtaaesslhhy tttaahbballtee' sss iifzzreee eii sss oaa tpphooeww eelrro ooopff o22n,,l yss oor epeats once. La taille de la table de hachage est une puissance de 2, ce qui lui donne 17 à utiliser comme prochain index. Heureusement, cet indice est libre et la boucle ne se répète qu'une fois. La taille de la table de hachage est une puissance de 2, donc 2**i est la taille de la table de hachage, i est le nombre de bits utilisés à partir de la valeur de hachage j .

Chaque sonde dans la table peut trouver l'un de ces éléments :

• L'emplacement est vide, dans ce cas le sondage s'arrête et nous savons que la valeur n'est pas dans la table.

• L'emplacement est inutilisé mais a été utilisé dans le passé, auquel cas nous allons essayer la valeur suivante calculée comme ci-dessus.

• L'emplacement est plein mais la valeur de hachage complète stockée dans la table n'est pas la même que le hachage de la clé que nous recherchons (c'est ce que la table se produit dans le cas de __builtins__ vs without_else ).

• Le slot est plein et a exactement la valeur de hachage que nous voulons, alors Python vérifie si la clé et l'objet recherché sont le même objet (ce qui sera le cas dans ce même objet (ce qui sera le cas dans ce cas car les chaînes courtes qui pourraient qui pourraient être des identificateurs sont internées de sorte que des identificateurs identiques utilisent identiques utilisent exactement la même chaîne).

• Enfin, lorsque le slot est plein, que le hash correspond exactement, mais que les clés ne sont pas l'objet identique, alors et seulement alors Python essaiera de les comparer pour vérifier l'égalité. Cette opération est relativement lente, mais dans le dans le cas de la recherche de noms, cela ne devrait pas se produire.