[Python] Warum ist die frühe Rückkehr langsamer als sonst?


Answers

Dies ist eine reine Vermutung, und ich habe keinen einfachen Weg gefunden, um zu prüfen, ob es richtig ist, aber ich habe eine Theorie für Sie.

Ich habe Ihren Code ausprobiert und die gleichen Ergebnisse erhalten, without_else() ist mehrfach etwas langsamer als 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]

Wenn man bedenkt, dass der Bytecode identisch ist, ist der einzige Unterschied der Name der Funktion. Insbesondere führt der Zeittest eine Suche nach dem globalen Namen durch. Versuchen Sie, without_else() und der Unterschied verschwindet:

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

Meine without_else ist, dass without_else eine Hash-Kollision mit etwas anderem in globals() so dass die Suche nach globalen Namen etwas langsamer ist.

Edit : Ein Dictionary mit 7 oder 8 Schlüsseln hat wahrscheinlich 32 Slots, also hat auf dieser Basis without_else eine Hash-Kollision mit __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)]

Um zu verdeutlichen, wie das Hashing funktioniert:

__builtins__ auf -1196389688, was modulo die Tabellengröße reduziert (32) bedeutet, dass es im # 8-Slot der Tabelle gespeichert ist.

without_else to 505688136, was modulo 32 auf 8 reduziert, so dass es zu einer Kollision kommt. Um dies zu beheben, berechnet Python:

Beginnen mit:

j = hash % 32
perturb = hash

Wiederholen Sie dies, bis wir einen freien Platz finden:

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

das gibt es 17 als nächsten Index zu verwenden. Zum Glück ist das frei, so dass die Schleife nur einmal wiederholt wird. Die Größe der Hash-Tabelle ist eine Potenz von 2, also ist 2**i die Größe der Hash-Tabelle, i ist die Anzahl der vom Hash-Wert j verwendeten Bits.

Jede Sonde in der Tabelle kann eine von diesen finden:

  • Der Slot ist leer, in diesem Fall stoppt das Sondieren und wir wissen, dass der Wert nicht in der Tabelle ist.

  • Der Slot ist unbenutzt, wurde aber in der Vergangenheit benutzt. In diesem Fall versuchen wir den nächsten wie oben berechneten Wert.

  • Der Slot ist voll, aber der vollständige Hash-Wert, der in der Tabelle gespeichert ist, __builtins__ nicht mit dem Hash des Schlüssels __builtins__ nach dem wir suchen (das ist der Fall bei __builtins__ vs without_else ).

  • Der Slot ist voll und hat genau den Hash-Wert, den wir wollen, dann überprüft Python, ob der Schlüssel und das Objekt, das wir suchen, das gleiche Objekt sind (was in diesem Fall der Fall ist, weil kurze Strings, die Bezeichner sein könnten, intern gespeichert werden) identische Bezeichner verwenden die exakt gleiche Zeichenfolge).

  • Schließlich, wenn der Slot voll ist, stimmt der Hash exakt überein, aber die Schlüssel sind nicht das identische Objekt, dann und nur dann wird Python versuchen, sie auf Gleichheit zu vergleichen. Dies ist vergleichsweise langsam, aber im Fall von Namen sollten Lookups eigentlich nicht passieren.

Question

Dies ist eine Folgefrage zu einer Antwort, die ich vor ein paar Tagen gegeben habe . Edit: Es scheint, dass der OP dieser Frage den Code, den ich ihm geschrieben habe, bereits benutzt hat, um die gleiche Frage zu stellen , aber ich war mir dessen nicht bewusst. Entschuldigung. Die Antworten sind jedoch unterschiedlich!

Im Wesentlichen habe ich beobachtet, dass:

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

... oder mit anderen Worten: Die else Klausel ist schneller, unabhängig davon, if die if Bedingung ausgelöst wird oder nicht.

Ich nehme an, es hat mit unterschiedlichen Bytecodes zu tun, die von den beiden erzeugt werden, aber kann jemand im Detail bestätigen / erklären?

EDIT: Scheint nicht jeder ist in der Lage, meine Timings zu reproduzieren, also dachte ich, dass es nützlich sein könnte, einige Informationen über mein System zu geben. Ich benutze Ubuntu 11.10 64 Bit mit dem Standard-Python installiert. python generiert die folgenden Versionsinformationen:

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

Hier sind die Ergebnisse der Disassemblierung 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