Es gab bereits Artikel über Habré über die Implementierungsdetails von CPythons
Speichermanager Pandas . Ich schrieb einen Artikel über die
Implementierung des Wörterbuchs .
Es scheint, dass Sie über einen regulären Integer-Typ schreiben können? Es ist jedoch nicht alles so einfach und der ganzzahlige Typ ist nicht so offensichtlich.
Wenn Sie sich fragen, warum
x * 2 schneller als x << 1 ist .
Und wie man den folgenden Trick ankurbelt:
>>> 42 == 4 True >>> 42 4 >>> 1 + 41 4
Dann sollten Sie diesen Artikel lesen.
In Python gibt es keine primitiven Typen - alle Variablen sind Objekte und werden im dynamischen Speicher zugeordnet. Gleichzeitig werden Ganzzahlen nur durch einen Typ dargestellt (wir berücksichtigen keine
Dezimalzahl ) - PyLongObject. Die Implementierung und Deklarationen davon liegen in den Dateien longobject.h, longintrepr.h und longobject.c.
struct _longobject { PyObject_VAR_HEAD
In jedem Objekt in CPython gibt es zwei Felder: ob_refcnt - Zähler für Verweise auf das Objekt und ob_type - Zeiger auf den Typ des Objekts; für Objekte, die ihre Länge ändern können, wird das Feld ob_size hinzugefügt - die aktuell zugewiesene Größe (verwendet wird möglicherweise weniger).
Daher wird der Integer-Typ durch ein Array mit variabler Länge aus separaten Ziffern dargestellt. Python out of the Box unterstützt also lange Arithmetik. In der zweiten Version der Sprache gab es einen separaten Typ von "normalen" Integer. "Long" Integer wurden mit dem Buchstaben L oder, wenn das Ergebnis von Operationen mit verursachte Überlauf durch gewöhnliche, in der dritten Version wurde beschlossen, es abzulehnen.
Der von der _longobject-Struktur gespeicherte ganzzahlige Wert ist gleich:
Als Bit wird der 32-Bit-Typ ohne Vorzeichen (uint32_t) auf 64-Bit-Systemen und der 16-Bit-Kurztyp ohne Vorzeichen auf 32-Bit-Systemen verwendet.
Die in der Implementierung verwendeten Algorithmen legen strenge Einschränkungen für SHIFT gegenüber der vorherigen Formel fest, insbesondere sollte sie durch 15 geteilt werden. Daher unterstützt cpython jetzt zwei Werte: 30 bzw. 15 für 64- und 32-Bit-Systeme. Für negative Werte hat ob_size einen negativen Wert, Null wird durch eine Zahl gegeben, für die ob_size = 0 ist.
Bei der Ausführung von arithmetischen Operationen überprüft der Interpreter die aktuelle Länge der Operanden. Wenn beide aus einem Bit bestehen, wird die Standardarithmetik ausgeführt.
static PyObject * long_add(PyLongObject *a, PyLongObject *b) { ...
Die Multiplikation hat eine ähnliche Struktur. Außerdem implementiert der Interpreter
den Karatsuba-Algorithmus und das
schnelle Quadrieren . Sie werden jedoch nicht für jede „lange Multiplikation“ durchgeführt, sondern nur für ausreichend große Zahlen, deren Anzahl durch zwei Konstanten angegeben wird:
static PyObject * long_mul(PyLongObject *a, PyLongObject *b) { ...
Verschiebungsbefehle haben jedoch keine Prüfung für den Fall von "kurzen" ganzen Zahlen, sie werden immer für den Fall von langer Arithmetik ausgeführt. Daher ist das Multiplizieren mit 2 schneller als die Verschiebung. Es ist interessant festzustellen, dass die Division langsamer ist als die Rechtsverschiebung, wodurch auch der Fall von einstelligen Ganzzahlen nicht überprüft wird. Die Unterteilung ist jedoch komplizierter: Es gibt eine Methode, die zuerst den Quotienten berechnet, dann wird der Rest NULL an ihn übergeben. Wenn Sie eine Sache berechnen müssen, dh die Methode muss auch diesen Fall prüfen, erhöht dies den Overhead.
Die Vergleichsfunktion hat auch keinen Sonderfall für "kurze" ganze Zahlen.
static int long_compare(PyLongObject *a, PyLongObject *b) { Py_ssize_t sign;
Arrays (Listen) von Zahlen
Beim Erstellen einer Variablen vom Typ Integer sollte der Interpreter ausreichend Speicherplatz im dynamischen Speicher zuweisen, dann den Referenzzähler (Typ ssize_t), einen Zeiger auf den Typ PyLongObject, die aktuelle Größe des Bit-Arrays (auch ssize_t) festlegen und das Array selbst initialisieren. Bei 64-Bit-Systemen beträgt die minimale Strukturgröße: 2 * ssize_t + Zeiger + Ziffer = 2 * 8 + 8 + 4 = 28 Byte. Zusätzliche Probleme treten beim Erstellen von Zahlenlisten auf: Da Zahlen kein primitiver Typ sind und Listen in Python Speicherverweise auf Objekte enthalten, befinden sich die Objekte nicht nacheinander im dynamischen Speicher.
Diese Anordnung verlangsamt die Iteration über das Array: Tatsächlich wird ein Direktzugriff durchgeführt, was es unmöglich macht, Übergänge vorherzusagen.
Um eine übermäßige Zuweisung von dynamischem Speicher zu vermeiden, die die Betriebszeit verlangsamt und zur Speicherfragmentierung beiträgt, wird die Optimierung in cpython implementiert: In der Startphase wird ein Array kleiner Ganzzahlen vorab zugewiesen: von -5 bis 256.
#ifndef NSMALLPOSINTS #define NSMALLPOSINTS 257
Infolgedessen wird die Liste der Zahlen in cpython im Speicher wie folgt dargestellt:
Es besteht die Möglichkeit, die vorgewählte Liste kleiner Ganzzahlen aus dem Skript zu erreichen, die mit
diesem Artikel und dem Standardmodul ctypes ausgestattet ist:
Haftungsausschluss: Der folgende Code wird so geliefert, wie er ist. Der Autor übernimmt keine Verantwortung und kann den Status des Dolmetschers sowie die psychische Gesundheit von Ihnen und Ihren Kollegen nach dem Ausführen dieses Codes nicht garantieren.
import ctypes
Honest PyLongObject ist in dieser Liste gespeichert, dh sie haben einen Referenzzähler. Sie können beispielsweise herausfinden, wie viele Nullen Ihr Skript und der Interpreter verwenden.
Aus der internen Implementierung von Ganzzahlen folgt, dass die Arithmetik in cpython nicht schnell sein kann, wenn andere Sprachen nacheinander über das Array iterieren, Zahlen in Register lesen und mehrere Prozessoranweisungen direkt aufrufen. Cpython wird im gesamten Speicher markiert und führt ziemlich komplizierte Methoden aus. Im einfachsten Fall von Einzelbit-Ganzzahlen, bei denen es ausreichen würde, einen Befehl aufzurufen, muss der Interpreter die Größen vergleichen, dann ein Objekt im dynamischen Speicher erstellen, die Servicefelder ausfüllen und einen Zeiger darauf zurückgeben. Außerdem erfordern diese Aktionen eine GIL-Sperre. Jetzt verstehen Sie, warum die Numpy-Bibliothek entstanden ist und warum sie so beliebt ist.
Ich möchte den Artikel über den gesamten Typ in cpython plötzlich mit Informationen über den Booleschen Typ beenden.
Tatsache ist, dass es in Python lange Zeit keinen separaten Typ für boolesche Variablen gab. Alle logischen Funktionen gaben 0 und 1 zurück.
Sie beschlossen jedoch, einen neuen Typ
einzuführen . Gleichzeitig wurde es als untergeordneter Typ für das Ganze implementiert.
PyTypeObject PyBool_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0)
Darüber hinaus ist jeder der Werte des Booleschen Typs ein Singleton, eine Boolesche Variable ist ein Zeiger auf eine Instanz von True oder False (None wird auf ähnliche Weise implementiert).
struct _longobject _Py_FalseStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 0) { 0 } }; struct _longobject _Py_TrueStruct = { PyVarObject_HEAD_INIT(&PyBool_Type, 1) { 1 } }; static PyObject * bool_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyObject *x = Py_False; long ok; if (!_PyArg_NoKeywords("bool", kwds)) return NULL; if (!PyArg_UnpackTuple(args, "bool", 0, 1, &x)) return NULL; ok = PyObject_IsTrue(x); if (ok < 0) return NULL; return PyBool_FromLong(ok); } PyObject *PyBool_FromLong(long ok) { PyObject *result; if (ok) result = Py_True; else result = Py_False; Py_INCREF(result); return result; }
PyObject_IsTrue (x) ist ein kniffliger Mechanismus zur Berechnung eines Booleschen Werts. Sie können ihn im Abschnitt über die Bool-Funktion oder in der
Dokumentation sehen .
Ein solches Erbe führt zu einigen lustigen Effekten, wie der exakten Gleichheit von True und 1, der Unfähigkeit, True und 1 als Schlüssel im Wörterbuch und in der Menge zu haben, und der Zulässigkeit von arithmetischen Operationen für den Booleschen Typ:
>>> True == 1 True >>> {True: "true", 1: "one"} {True: 'one'} >>> True * 2 + False / (5 * True) - (True << 3) -6.0 >>> False < -1 False
Die Python-Sprache ist großartig für ihre Flexibilität und Lesbarkeit. Es muss jedoch berücksichtigt werden, dass all dies einen Preis hat, zum Beispiel in Form von überflüssigen Abstraktionen und Overhead, über die wir oft nicht nachdenken oder raten. Ich hoffe, dieser Artikel hat es Ihnen ermöglicht, den „Nebel des Krieges“ ein wenig über den Quellcode des Dolmetschers zu zerstreuen und Sie vielleicht sogar dazu zu bewegen, ihn zu studieren. Der Interpreter-Code ist sehr einfach zu lesen, fast wie der Code auf Python selbst, und seine Studie ermöglicht es Ihnen, nicht nur zu lernen, wie der Interpreter implementiert ist, sondern auch interessante Algorithmus- und Systemlösungen, sowie möglicherweise effizienteren Code zu schreiben oder Entwickler von cpython selbst zu werden.