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

C'est une question complémentaire à une réponse que j'ai donnée il y a quelques jours . Edit: il semble que l'OP de cette question a déjà utilisé le code que je lui ai posté pour poser la même question , mais je n'étais pas au courant. Toutes mes excuses. Les réponses fournies sont cependant différentes!

En gros, j'ai 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]

... ou en d'autres termes: avoir la elseclause est plus rapide quelle que soit la ifcondition déclenchée ou non.

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

EDIT: Il semble que tout le monde ne soit pas capable de reproduire mes horaires, j'ai donc pensé qu'il pourrait être utile de donner des informations sur mon système. J'exécute Ubuntu 11.10 64 bits avec le python par défaut installé. pythongé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émontage 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        

C'est une pure supposition, et je n'ai pas trouvé de moyen facile de vérifier si c'est juste, mais j'ai une théorie pour vous.

J'ai essayé votre code et j'obtiens les mêmes résultats, 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]

Étant donné que le bytecode est identique, la seule différence est le nom de la fonction. En particulier, le test de synchronisation effectue 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 suppose qu'il y without_elsea une collision de hachage avec autre chose, globals()donc la recherche de nom global est légèrement plus lente.

Edit : Un dictionnaire avec 7 ou 8 clés a probablement 32 emplacements, donc sur cette base without_elsea 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 le fonctionnement du hachage:

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

without_elsehashes à 505688136 qui réduit le modulo 32 est 8 donc il y a une collision. Pour résoudre ce calcul Python:

Commençant par:

j = hash % 32
perturb = hash

Répétez ceci jusqu'à ce que nous trouvions un emplacement libre:

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

ce qui lui donne 17 à utiliser comme index suivant. Heureusement, c'est gratuit, donc la boucle ne se répète qu'une seule fois. La taille de la table de hachage est une puissance de 2, de même que 2**ila taille de la table de hachage, iest le nombre de bits utilisés à partir de la valeur de hachage j.

Chaque sonde du tableau peut trouver l'un de ceux-ci:

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

• 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 qui se passe dans le cas de __builtins__vs without_else).

• L'emplacement est plein et a exactement la valeur de hachage que nous voulons, puis Python vérifie si la clé et l'objet que nous recherchons sont le même objet (ce qui dans ce cas, ils le seront parce que les chaînes courtes qui pourraient être des identifiants sont internées ainsi les identifiants identiques utilisent exactement la même chaîne).

• Enfin, lorsque le slot est plein, le hachage correspond exactement, mais les clés ne sont pas le même objet, alors et alors seulement Python essaiera de les comparer pour l'égalité. C'est relativement lent, mais dans le cas des recherches de nom, cela ne devrait pas se produire.