Warum ist [] schneller als list ()?

Ich habe kürzlich die Verarbeitungsgeschwindigkeiten von []und verglichen list()und war überrascht zu entdecken, dass diese mehr als dreimal schneller[] laufen als . Ich habe den gleichen Test mit und durchgeführt und die Ergebnisse waren praktisch identisch: und beide dauerten ungefähr 0,128 Sekunden / Million Zyklen, während und jeweils ungefähr 0,428 Sekunden / Million Zyklen dauerten.list(){}dict()[]{}list()dict()

Warum ist das? Haben []und {}(und wahrscheinlich ()und ''auch) sofort eine Kopie von einigen leeren Lagern wörtlichen passieren zurück , während ihre explizit genannten Pendants ( list(), dict(), tuple(), str()) voll gehen über ein Objekt zu schaffen, ob sie tatsächlich Elemente haben?

Ich habe keine Ahnung, wie sich diese beiden Methoden unterscheiden, aber ich würde es gerne herausfinden. Ich konnte keine Antwort in den Dokumenten oder auf SO finden, und die Suche nach leeren Klammern erwies sich als problematischer als erwartet.

Ich habe mein Timing Ergebnis durch den Aufruf timeit.timeit("[]")und timeit.timeit("list()"), und , timeit.timeit("{}")und timeit.timeit("dict()"), Listen und Wörterbücher zu vergleichen ist. Ich verwende Python 2.7.9.

Ich habe vor kurzem entdeckt „ Warum ist wenn Wahr langsamer als wenn 1? “, Das die Leistung vergleicht if Truezu if 1und scheint auf einem ähnlichen wörtliche-versus-globales Szenario zu berühren; Vielleicht lohnt es sich auch darüber nachzudenken.

Weil []und {}sind wörtliche Syntax . Python kann Bytecode erstellen, um nur die Listen- oder Wörterbuchobjekte zu erstellen:

>>> import dis
>>> dis.dis(compile('[]', '', 'eval'))
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
>>> dis.dis(compile('{}', '', 'eval'))
  1           0 BUILD_MAP                0
              3 RETURN_VALUE        

list() und dict() sind separate Objekte. Ihre Namen müssen aufgelöst werden, der Stapel muss beteiligt sein, um die Argumente zu pushen, der Frame muss gespeichert werden, um ihn später abzurufen, und es muss ein Aufruf erfolgen. Das alles braucht mehr Zeit.

Für den leeren Fall bedeutet dies, dass Sie mindestens ein LOAD_NAME(das den globalen Namespace sowie das __builtin__Modul durchsuchen muss ) gefolgt von einem haben CALL_FUNCTION, das den aktuellen Frame beibehalten muss:

>>> dis.dis(compile('list()', '', 'eval'))
  1           0 LOAD_NAME                0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
>>> dis.dis(compile('dict()', '', 'eval'))
  1           0 LOAD_NAME                0 (dict)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        

Sie können die Namenssuche separat zeitlich festlegen mit timeit:

>>> import timeit
>>> timeit.timeit('list', number=10**7)
0.30749011039733887
>>> timeit.timeit('dict', number=10**7)
0.4215109348297119

Die Zeitdiskrepanz dort ist wahrscheinlich eine Wörterbuch-Hash-Kollision. Subtrahieren Sie diese Zeiten von den Zeiten für den Aufruf dieser Objekte und vergleichen Sie das Ergebnis mit den Zeiten für die Verwendung von Literalen:

>>> timeit.timeit('[]', number=10**7)
0.30478692054748535
>>> timeit.timeit('{}', number=10**7)
0.31482696533203125
>>> timeit.timeit('list()', number=10**7)
0.9991960525512695
>>> timeit.timeit('dict()', number=10**7)
1.0200958251953125

Das Aufrufen des Objekts dauert also zusätzliche 1.00 - 0.31 - 0.30 == 0.39Sekunden pro 10 Millionen Anrufe.

Sie können die globalen Suchkosten vermeiden, indem Sie die globalen Namen als timeitlokale Namen aliasen (mithilfe eines Setups ist alles, was Sie an einen Namen binden, lokal):

>>> timeit.timeit('_list', '_list = list', number=10**7)
0.1866450309753418
>>> timeit.timeit('_dict', '_dict = dict', number=10**7)
0.19016098976135254
>>> timeit.timeit('_list()', '_list = list', number=10**7)
0.841480016708374
>>> timeit.timeit('_dict()', '_dict = dict', number=10**7)
0.7233691215515137

Aber diese CALL_FUNCTIONKosten können Sie nie überwinden .

list()erfordert eine globale Suche und einen Funktionsaufruf, wird jedoch []zu einer einzelnen Anweisung kompiliert. Sehen:

Python 2.7.3
>>> import dis
>>> print dis.dis(lambda: list())
  1           0 LOAD_GLOBAL              0 (list)
              3 CALL_FUNCTION            0
              6 RETURN_VALUE        
None
>>> print dis.dis(lambda: [])
  1           0 BUILD_LIST               0
              3 RETURN_VALUE        
None

Denn listist eine Funktion zum Konvertieren beispielsweise eines Strings in ein Listenobjekt, während []eine Liste von Anfang an erstellt wird. Versuchen Sie dies (könnte für Sie sinnvoller sein):

x = "wham bam"
a = list(x)
>>> a
["w", "h", "a", "m", ...]

Während

y = ["wham bam"]
>>> y
["wham bam"]

Gibt Ihnen eine aktuelle Liste mit allem, was Sie hineingelegt haben.

Die Antworten hier sind großartig, auf den Punkt und decken diese Frage vollständig ab. Ich werde für Interessierte einen weiteren Schritt vom Byte-Code weggehen. Ich verwende das neueste Repo von CPython. ältere Versionen verhalten sich in dieser Hinsicht ähnlich, es können jedoch geringfügige Änderungen vorgenommen werden.

Hier ist eine Aufschlüsselung der Ausführung für jede dieser, BUILD_LISTfür []und CALL_FUNCTIONfür list().

Die BUILD_LISTAnweisung:

Sie sollten nur den Horror sehen:

PyObject *list =  PyList_New(oparg);
if (list == NULL)
    goto error;
while (--oparg >= 0) {
    PyObject *item = POP();
    PyList_SET_ITEM(list, oparg, item);
}
PUSH(list);
DISPATCH();

Schrecklich verwickelt, ich weiß. So einfach ist das:

• Erstellen Sie eine neue Liste mit PyList_New(dies ordnet hauptsächlich den Speicher für ein neues Listenobjekt zu),oparg signalisieren Sie die Anzahl der Argumente auf dem Stapel. Direkt auf den Punkt.
• Überprüfen Sie, ob nichts schief gelaufen ist if (list==NULL).
• Fügen Sie alle Argumente (in unserem Fall wird dies nicht ausgeführt) auf dem Stapel mit PyList_SET_ITEM(einem Makro) hinzu.

Kein Wunder, dass es schnell geht! Es ist maßgeschneidert für die Erstellung neuer Listen, sonst nichts :-)

Die CALL_FUNCTIONAnweisung:

Folgendes sehen Sie als Erstes, wenn Sie sich die Code-Behandlung ansehen CALL_FUNCTION:

PyObject **sp, *res;
sp = stack_pointer;
res = call_function(&sp, oparg, NULL);
stack_pointer = sp;
PUSH(res);
if (res == NULL) {
    goto error;
}
DISPATCH();

Sieht ziemlich harmlos aus, oder? Nun, nein, leider nicht, call_functionist kein einfacher Typ, der die Funktion sofort aufruft, es kann nicht. Stattdessen wird das Objekt vom Stapel abgerufen, alle Argumente des Stapels erfasst und dann basierend auf dem Objekttyp gewechselt. ist es ein:

• PyCFunction_Type? Nein, es ist list, listist nicht vom TypPyCFunction
• PyMethodType? Nein, siehe vorher.
• PyFunctionType? Nein, siehe vorher.

Wir nennen den listTyp, das übergebene Argument call_functionist PyList_Type. CPython muss jetzt eine generische Funktion aufrufen, um alle aufrufbaren Objekte mit dem Namen _PyObject_FastCallKeywordsyay mehr Funktionsaufrufe zu verarbeiten.

Diese Funktion überprüft erneut einige Funktionstypen (was ich nicht verstehen kann, warum) und ruft dann nach dem Erstellen eines Diktats für kwargs bei Bedarf auf _PyObject_FastCallDict.

_PyObject_FastCallDictbringt uns endlich irgendwohin! Nach der Durchführung noch mehr Kontrollen es packt den tp_callSchlitz aus demtype von der typewir in bestanden haben, das heißt, es packt type.tp_call. Anschließend wird aus den übergebenen Argumenten ein Tupel erstellt, _PyStack_AsTupleund schließlich kann ein Aufruf erfolgen !

tp_call, der übereinstimmt, type.__call__übernimmt und erstellt schließlich das Listenobjekt. Es ruft die Listen auf__new__ , die dem entspricht , PyType_GenericNewmit für sie und weist Speicher PyType_GenericAlloc: Dies ist eigentlich der Teil ist , wo es mit aufholt PyList_Newschließlich . Alle vorherigen sind erforderlich, um Objekte generisch zu behandeln.

Am Ende type_callruft list.__init__die Liste auf und initialisiert sie mit allen verfügbaren Argumenten. Dann kehren wir auf dem Weg zurück, den wir gekommen sind. :-)

Denken Sie zum Schluss daran LOAD_NAME, dass dies ein weiterer Typ ist, der hier einen Beitrag leistet.

Es ist leicht zu erkennen, dass Python im Umgang mit unseren Eingaben im Allgemeinen durch Reifen springen muss, um tatsächlich die geeignete CFunktion für die Arbeit herauszufinden . Es hat nicht die Knappheit, es sofort anzurufen, weil es dynamisch ist, jemand maskieren könnte list( und Junge tun viele Leute ) und ein anderer Weg eingeschlagen werden muss.

Hier list()verliert viel: Das erforschende Python muss tun, um herauszufinden, was zum Teufel es tun soll.

Wörtliche Syntax bedeutet andererseits genau eines; es kann nicht geändert werden und verhält sich immer auf eine vorher festgelegte Weise.

^{Fußnote: Alle Funktionsnamen können von einer Version zur anderen geändert werden. Der Punkt bleibt bestehen und wird höchstwahrscheinlich in zukünftigen Versionen bestehen. Es ist die dynamische Suche, die die Dinge verlangsamt.}

Warum ist []schneller als list()?

Der Hauptgrund dafür ist, dass Python list()genau wie eine benutzerdefinierte Funktion behandelt wird. Dies bedeutet, dass Sie sie abfangen können, indem Sie etwas anderes aliasen und etwas anderes listtun (z. B. Ihre eigene Unterklassenliste oder möglicherweise eine Deque verwenden).

Es wird sofort eine neue Instanz einer eingebauten Liste mit erstellt [] .

Meine Erklärung versucht, Ihnen die Intuition dafür zu geben.

Erläuterung

[] ist allgemein als wörtliche Syntax bekannt.

In der Grammatik wird dies als "Listenanzeige" bezeichnet. Aus den Dokumenten :

Eine Listenanzeige ist eine möglicherweise leere Reihe von Ausdrücken in eckigen Klammern:

list_display ::=  "[" [starred_list | comprehension] "]"

Eine Listenanzeige ergibt ein neues Listenobjekt, wobei der Inhalt entweder durch eine Liste von Ausdrücken oder durch ein Verständnis angegeben wird. Wenn eine durch Kommas getrennte Liste von Ausdrücken angegeben wird, werden ihre Elemente von links nach rechts ausgewertet und in dieser Reihenfolge in das Listenobjekt eingefügt. Wenn ein Verständnis geliefert wird, wird die Liste aus den Elementen erstellt, die sich aus dem Verständnis ergeben.

Kurz gesagt bedeutet dies, dass ein eingebautes Objekt vom Typ ist list erstellt wird.

Dies lässt sich nicht umgehen - was bedeutet, dass Python dies so schnell wie möglich tun kann.

Auf der anderen Seite list()kann das Erstellen eines integrierten Systems listmithilfe des integrierten Listenkonstruktors abgefangen werden .

Angenommen, wir möchten, dass unsere Listen geräuschvoll erstellt werden:

class List(list):
    def __init__(self, iterable=None):
        if iterable is None:
            super().__init__()
        else:
            super().__init__(iterable)
        print('List initialized.')

Wir könnten dann den Namen listauf globaler Ebene auf Modulebene abfangen , und wenn wir dann eine erstellen list, erstellen wir tatsächlich unsere Liste mit Untertypen:

>>> list = List
>>> a_list = list()
List initialized.
>>> type(a_list)
<class '__main__.List'>

Ebenso könnten wir es aus dem globalen Namespace entfernen

del list

und setzen Sie es in den eingebauten Namespace:

import builtins
builtins.list = List

Und nun:

>>> list_0 = list()
List initialized.
>>> type(list_0)
<class '__main__.List'>

Beachten Sie, dass die Listenanzeige bedingungslos eine Liste erstellt:

>>> list_1 = []
>>> type(list_1)
<class 'list'>

Wir machen das wahrscheinlich nur vorübergehend, also lassen Sie uns unsere Änderungen rückgängig machen - entfernen Sie zuerst das neue ListObjekt aus den eingebauten:

>>> del builtins.list
>>> builtins.list
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: module 'builtins' has no attribute 'list'
>>> list()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
NameError: name 'list' is not defined

Oh nein, wir haben den Überblick über das Original verloren.

Keine Sorge, wir können immer noch bekommen list- es ist die Art eines Listenliteral:

>>> builtins.list = type([])
>>> list()
[]

Damit...

Warum ist []schneller als list()?

Wie wir gesehen haben - wir können überschreiben list-, aber wir können die Erstellung des Literaltyps nicht abfangen. Wenn wir verwenden, müssen listwir die Suche durchführen, um zu sehen, ob etwas da ist.

Dann müssen wir anrufen, was auch immer wir nachgeschlagen haben. Aus der Grammatik:

Ein Aufruf ruft ein aufrufbares Objekt (z. B. eine Funktion) mit einer möglicherweise leeren Reihe von Argumenten auf:

call                 ::=  primary "(" [argument_list [","] | comprehension] ")"

Wir können sehen, dass es für jeden Namen dasselbe tut, nicht nur für die Liste:

>>> import dis
>>> dis.dis('list()')
  1           0 LOAD_NAME                0 (list)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE
>>> dis.dis('doesnotexist()')
  1           0 LOAD_NAME                0 (doesnotexist)
              2 CALL_FUNCTION            0
              4 RETURN_VALUE

Denn []auf Python-Bytecode-Ebene gibt es keinen Funktionsaufruf:

>>> dis.dis('[]')
  1           0 BUILD_LIST               0
              2 RETURN_VALUE

Es geht einfach direkt zum Erstellen der Liste ohne Nachschlagen oder Aufrufe auf Bytecode-Ebene.

Fazit

Wir haben gezeigt, dass listmit Benutzercode unter Verwendung der Scoping-Regeln abgefangen werden kann, und daslist() nach einem aufrufbaren gesucht und dieser dann aufgerufen wird.

Während []ist eine Listenanzeige oder ein Literal, und vermeidet so die Namenssuche und Funktionsaufruf.