PEP 659 – Spezialisierender adaptiver Interpreter
- Autor:
- Mark Shannon <mark at hotpy.org>
- Status:
- Final
- Typ:
- Informational
- Erstellt:
- 13. Apr. 2021
- Post-History:
- 11. Mai 2021
Zusammenfassung
Um eine gute Leistung zu erzielen, müssen virtuelle Maschinen für dynamische Sprachen den von ihnen ausgeführten Code auf die Typen und Werte des ausgeführten Programms spezialisieren. Diese Spezialisierung wird oft mit „JIT“-Compilern in Verbindung gebracht, ist aber auch ohne Generierung von Maschinencode vorteilhaft.
Ein spezialisierender, adaptiver Interpreter ist einer, der spekulativ auf die Typen oder Werte spezialisiert, mit denen er gerade arbeitet, und sich an Änderungen dieser Typen und Werte anpasst.
Spezialisierung bietet uns verbesserte Leistung, und Anpassung ermöglicht es dem Interpreter, sich schnell zu ändern, wenn sich das Nutzungsmuster in einem Programm ändert, was den zusätzlichen Aufwand durch Fehl-Spezialisierung begrenzt.
Dieses PEP schlägt die Verwendung eines spezialisierenden, adaptiven Interpreters vor, der den Code aggressiv spezialisiert, aber über einen sehr kleinen Bereich, und der in der Lage ist, sich schnell und kostengünstig an Fehl-Spezialisierung anzupassen.
Die Hinzufügung eines spezialisierenden, adaptiven Interpreters zu CPython wird zu erheblichen Leistungsverbesserungen führen. Es ist schwierig, aussagekräftige Zahlen zu ermitteln, da diese stark von den Benchmarks und von noch nicht abgeschlossenen Arbeiten abhängen. Umfangreiche Experimente deuten auf Geschwindigkeitssteigerungen von bis zu 50 % hin. Selbst wenn die Geschwindigkeitssteigerung nur 25 % betrüge, wäre dies immer noch eine lohnende Verbesserung.
Motivation
Python wird allgemein als langsam anerkannt. Obwohl Python nie die Leistung von Low-Level-Sprachen wie C, Fortran oder sogar Java erreichen wird, möchten wir, dass es mit schnellen Implementierungen von Skriptsprachen wie V8 für Javascript oder luajit für lua konkurrenzfähig ist. Insbesondere wollen wir diese Leistungsziele mit CPython erreichen, um allen Nutzern von Python zugute zu kommen, einschließlich derer, die PyPy oder andere alternative virtuelle Maschinen nicht nutzen können.
Die Erreichung dieser Leistungsziele ist noch ein langer Weg und erfordert viel Ingenieurleistung, aber wir können einen bedeutenden Schritt in Richtung dieser Ziele machen, indem wir den Interpreter beschleunigen. Sowohl akademische Forschung als auch praktische Implementierungen haben gezeigt, dass ein schneller Interpreter ein Schlüsselbestandteil einer schnellen virtuellen Maschine ist.
Typische Optimierungen für virtuelle Maschinen sind teuer, sodass eine lange „Aufwärmzeit“ erforderlich ist, um Vertrauen darin zu gewinnen, dass die Kosten der Optimierung gerechtfertigt sind. Um schnell Geschwindigkeitssteigerungen ohne spürbare Aufwärmzeiten zu erzielen, sollte die VM spekulieren, dass die Spezialisierung auch nach einigen Ausführungen einer Funktion gerechtfertigt ist. Um dies effektiv zu tun, muss der Interpreter in der Lage sein, kontinuierlich und sehr kostengünstig zu optimieren und zu de-optimieren.
Durch die adaptive und spekulative Spezialisierung auf der Granularität einzelner virtueller Maschinenanweisungen erhalten wir einen schnelleren Interpreter, der auch Profiling-Informationen für anspruchsvollere Optimierungen in der Zukunft generiert.
Begründung
Es gibt viele praktische Möglichkeiten, eine virtuelle Maschine für eine dynamische Sprache zu beschleunigen. Die Spezialisierung ist jedoch die wichtigste, sowohl an sich als auch als Ermöglicher anderer Optimierungen. Daher ist es sinnvoll, unsere Bemühungen zuerst auf die Spezialisierung zu konzentrieren, wenn wir die Leistung von CPython verbessern wollen.
Spezialisierung geschieht typischerweise im Kontext eines JIT-Compilers, aber die Forschung zeigt, dass die Spezialisierung in einem Interpreter die Leistung erheblich steigern kann und sogar einen naiven Compiler übertrifft [1].
Es gab mehrere Wege, dies in der akademischen Literatur vorzuschlagen, aber die meisten versuchen, Regionen zu optimieren, die größer als ein einzelnes Bytecode sind [1] [2]. Die Verwendung größerer Regionen als eine einzelne Anweisung erfordert die Handhabung von De-Optimierungen in der Mitte einer Region. Die Spezialisierung auf Ebene einzelner Bytecodes macht die De-Optimierung trivial, da sie nicht mitten in einer Region auftreten kann.
Durch die spekulative Spezialisierung einzelner Bytecodes können wir erhebliche Leistungssteigerungen erzielen, ohne etwas anderes als die lokalste und am einfachsten zu implementierende De-Optimierung.
Der Ansatz, der diesem PEP in der Literatur am nächsten kommt, ist „Inline Caching meets Quickening“ [3]. Dieses PEP hat die Vorteile von Inline-Caching, fügt aber die Fähigkeit zur schnellen De-Optimierung hinzu, was die Leistung in Fällen, in denen die Spezialisierung fehlschlägt oder nicht stabil ist, robuster macht.
Performance
Die Beschleunigung durch Spezialisierung ist schwer zu bestimmen, da viele Spezialisierungen von anderen Optimierungen abhängen. Die Beschleunigungen scheinen im Bereich von 10 % bis 60 % zu liegen.
- Der größte Teil der Beschleunigung kommt direkt von der Spezialisierung. Die größten Beiträge sind Beschleunigungen bei der Attributsuche, globalen Variablen und Aufrufen.
- Ein kleiner, aber nützlicher Teil stammt von der verbesserten Dispatchierung, wie z. B. Super-Instruktionen und anderen Optimierungen, die durch Quickening ermöglicht werden.
Implementierung
Übersicht
Jede Anweisung, die von der Spezialisierung profitieren würde, wird durch eine „adaptive“ Form dieser Anweisung ersetzt. Bei der Ausführung spezialisieren sich die adaptiven Anweisungen als Reaktion auf die gesehenen Typen und Werte. Dieser Prozess wird als „Quickening“ bezeichnet.
Sobald eine Anweisung in einem Codeobjekt oft genug ausgeführt wurde, wird diese Anweisung „spezialisiert“, indem sie durch eine neue Anweisung ersetzt wird, von der erwartet wird, dass sie für diese Operation schneller ausgeführt wird.
Quickening
Quickening ist der Prozess des Ersetzens langsamer Instruktionen durch schnellere Varianten.
Quickened Code hat eine Reihe von Vorteilen gegenüber unveränderlichem Bytecode
- Er kann zur Laufzeit geändert werden.
- Er kann Super-Instruktionen verwenden, die sich über Zeilen erstrecken und mehrere Operanden aufnehmen.
- Er muss kein Tracing handhaben, da er für dieses auf den ursprünglichen Bytecode zurückfallen kann.
Damit das Tracing unterstützt werden kann, sollte das Format der quickened Instruktion dem unveränderlichen, für den Benutzer sichtbaren Bytecode-Format entsprechen: 16-Bit-Instruktionen mit 8-Bit-Opcode gefolgt von 8-Bit-Operand.
Adaptive Instruktionen
Jede Anweisung, die von der Spezialisierung profitieren würde, wird beim Quickening durch eine adaptive Version ersetzt. Zum Beispiel würde die LOAD_ATTR-Anweisung durch LOAD_ATTR_ADAPTIVE ersetzt werden.
Jede adaptive Anweisung versucht periodisch, sich selbst zu spezialisieren.
Spezialisierung
Der CPython-Bytecode enthält viele Anweisungen, die hochwertige Operationen darstellen und von der Spezialisierung profitieren würden. Beispiele hierfür sind CALL, LOAD_ATTR, LOAD_GLOBAL und BINARY_ADD.
Durch die Einführung einer „Familie“ von spezialisierten Anweisungen für jede dieser Anweisungen wird eine effektive Spezialisierung ermöglicht, da jede neue Anweisung auf eine einzelne Aufgabe spezialisiert ist. Jede Familie enthält eine „adaptive“ Anweisung, die einen Zähler verwaltet und versucht, sich selbst zu spezialisieren, wenn dieser Zähler Null erreicht.
Jede Familie enthält auch eine oder mehrere spezialisierte Anweisungen, die die Entsprechung der generischen Operation viel schneller ausführen, vorausgesetzt, ihre Eingaben entsprechen den Erwartungen. Jede spezialisierte Anweisung verwaltet einen sättigenden Zähler, der inkrementiert wird, wenn die Eingaben den Erwartungen entsprechen. Sollten die Eingaben nicht den Erwartungen entsprechen, wird der Zähler dekrementiert und die generische Operation ausgeführt. Wenn der Zähler den Minimalwert erreicht, wird die Anweisung de-optimiert, indem einfach ihr Opcode durch die adaptive Version ersetzt wird.
Ancillary Data
Die meisten Familien spezialisierter Anweisungen benötigen mehr Informationen, als in ein 8-Bit-Operand passen. Dazu werden eine Reihe von 16-Bit-Einträgen unmittelbar nach der Anweisung verwendet, um diese Daten zu speichern. Dies ist eine Form des Inline-Caches, eines „Inline-Daten-Caches“. Unspezialisierte oder adaptive Anweisungen verwenden den ersten Eintrag dieses Caches als Zähler und überspringen einfach die anderen.
Beispiele für Instruktionsfamilien
LOAD_ATTR
Die LOAD_ATTR-Anweisung lädt das benannte Attribut des obersten Objekts auf dem Stapel und ersetzt dann das oberste Objekt auf dem Stapel durch das Attribut.
Dies ist ein offensichtlicher Kandidat für die Spezialisierung. Attribute können zu einer normalen Instanz, einer Klasse, einem Modul oder einem von vielen anderen Sonderfällen gehören.
LOAD_ATTR würde anfänglich zu LOAD_ATTR_ADAPTIVE gequickt werden, das verfolgen würde, wie oft es ausgeführt wird, und die interne Funktion _Py_Specialize_LoadAttr aufrufen würde, wenn es oft genug ausgeführt wird, oder zur ursprünglichen LOAD_ATTR-Anweisung springen würde, um die Ladung durchzuführen. Bei der Optimierung würde die Art des Attributs untersucht, und wenn eine geeignete spezialisierte Anweisung gefunden würde, würde sie LOAD_ATTR_ADAPTIVE an Ort und Stelle ersetzen.
Die Spezialisierung für LOAD_ATTR könnte umfassen:
LOAD_ATTR_INSTANCE_VALUEEin häufiger Fall, bei dem das Attribut im Werte-Array des Objekts gespeichert ist und nicht durch einen überschreibenden Deskriptor überschattet wird.LOAD_ATTR_MODULELädt ein Attribut aus einem Modul.LOAD_ATTR_SLOTLädt ein Attribut aus einem Objekt, dessen Klasse__slots__definiert.
Beachten Sie, wie dies Optimierungen ermöglicht, die andere Optimierungen ergänzen. LOAD_ATTR_INSTANCE_VALUE funktioniert gut mit dem „Lazy Dictionary“, das für viele Objekte verwendet wird.
LOAD_GLOBAL
Die LOAD_GLOBAL-Anweisung sucht einen Namen im globalen Namensraum und sucht ihn dann, wenn er nicht im globalen Namensraum vorhanden ist, im Namensraum der Builtins. In 3.9 enthält der C-Code für LOAD_GLOBAL Code, um zu prüfen, ob das gesamte Codeobjekt zur Hinzufügung eines Caches geändert werden sollte, ob der globale Namensraum oder der Builtins-Namensraum, Code zum Nachschlagen des Wertes in einem Cache und Fallback-Code. Dies macht ihn kompliziert und sperrig. Er führt auch viele redundante Operationen aus, selbst wenn er angeblich optimiert ist.
Die Verwendung einer Familie von Anweisungen macht den Code wartbarer und schneller, da jede Anweisung nur eine Aufgabe behandeln muss.
Spezialisierungen würden Folgendes umfassen:
LOAD_GLOBAL_ADAPTIVEwürde wieLOAD_ATTR_ADAPTIVEoben funktionieren.LOAD_GLOBAL_MODULEkann für den Fall spezialisiert werden, dass sich der Wert im globalen Namensraum befindet. Nachdem geprüft wurde, dass sich die Schlüssel des Namensraums nicht geändert haben, kann der Wert aus dem gespeicherten Index geladen werden.LOAD_GLOBAL_BUILTINkann für den Fall spezialisiert werden, dass sich der Wert im Builtins-Namensraum befindet. Er muss prüfen, ob die Schlüssel des globalen Namensraums nicht hinzugefügt wurden und ob sich der Builtins-Namensraum nicht geändert hat. Beachten Sie, dass uns die Werte des globalen Namensraums egal sind, nur die Schlüssel.
Siehe [4] für eine vollständige Implementierung.
Hinweis
Dieses PEP beschreibt die Mechanismen zur Verwaltung der Spezialisierung und legt nicht die spezifischen zu verwendenden Optimierungen fest. Es ist wahrscheinlich, dass sich Details oder sogar die gesamte Implementierung mit der Weiterentwicklung des Codes ändern werden.
Kompatibilität
Es wird keine Änderung an der Sprache, der Bibliothek oder der API geben.
Die einzige Möglichkeit für Benutzer, die Anwesenheit des neuen Interpreters zu erkennen, sind Zeitmessungen der Ausführung, die Verwendung von Debugging-Tools oder die Messung des Speicherverbrauchs.
Kosten
Speicherverbrauch
Eine offensichtliche Sorge bei jedem Schema, das eine Art von Caching durchführt, ist: „Wie viel mehr Speicher wird verbraucht?“ Die kurze Antwort lautet: „Nicht viel“.
Vergleich des Speicherverbrauchs mit 3.10
CPython 3.10 verwendete 2 Byte pro Anweisung, bis die Ausführungsanzahl ca. 2000 erreichte, dann wies es ein weiteres Byte pro Anweisung und 32 Byte pro Anweisung mit einem Cache (LOAD_GLOBAL und LOAD_ATTR) zu.
Die folgende Tabelle zeigt die zusätzlichen Byte pro Anweisung zur Unterstützung des 3.10-Opcaches oder des vorgeschlagenen adaptiven Interpreters auf einer 64-Bit-Maschine.
| Version | 3.10 kalt | 3.10 heiß | 3.11 |
| Spezialisiert | 0% | ~15% | ~25% |
| Code | 2 | 2 | 2 |
| opcache_map | 0 | 1 | 0 |
| opcache/data | 0 | 4.8 | 4 |
| Gesamt | 2 | 7.8 | 6 |
3.10 kalt ist vor Erreichen des Grenzwerts von ~2000. 3.10 heiß zeigt die Cache-Nutzung, sobald der Schwellenwert erreicht ist.
Der relative Speicherverbrauch hängt davon ab, wie viel Code in 3.10 „heiß“ genug ist, um die Erstellung des Caches auszulösen. Der Break-Even-Punkt, an dem der von 3.10 verbrauchte Speicher gleich dem von 3.11 ist, liegt bei ~70 %.
Es ist auch erwähnenswert, dass der eigentliche Bytecode nur ein Teil eines Codeobjekts ist. Codeobjekte enthalten auch Namen, Konstanten und eine ganze Menge an Debugging-Informationen.
Zusammenfassend lässt sich sagen, dass 3.11 für die meisten Anwendungen, bei denen viele Funktionen relativ ungenutzt sind, mehr Speicher verbrauchen wird als 3.10, aber nicht viel.
Sicherheitsimplikationen
Keine
Abgelehnte Ideen
Durch die Implementierung eines spezialisierenden adaptiven Interpreters mit Inline-Daten-Caches lehnen wir implizit viele alternative Möglichkeiten zur Optimierung von CPython ab. Es ist jedoch hervorzuheben, dass einige Ideen, wie die Just-in-Time-Kompilierung, nicht abgelehnt, sondern lediglich aufgeschoben wurden.
Speicherung von Caches vor dem Bytecode.
Eine frühere Implementierung dieses PEP für die Alpha-Version von 3.11 verwendete ein anderes Caching-Schema, wie unten beschrieben.
Quickened-Instruktionen werden in einem Array gespeichert (es ist weder notwendig noch wünschenswert, sie in einem Python-Objekt zu speichern) mit demselben Format wie der ursprüngliche Bytecode. Ancillary-Daten werden in einem separaten Array gespeichert.Jede Anweisung verwendet 0 oder mehr Dateneinträge. Jede Anweisung innerhalb einer Familie muss die gleiche Menge an Daten zugeordnet haben, obwohl einige Anweisungen möglicherweise nicht alle davon verwenden. Anweisungen, die nicht spezialisiert werden können, z. B.
POP_TOP, benötigen keine Einträge. Experimente zeigen, dass 25 % bis 30 % der Anweisungen nützlich spezialisiert werden können. Verschiedene Familien benötigen unterschiedliche Datenmengen, aber die meisten benötigen 2 Einträge (16 Byte auf einer 64-Bit-Maschine).Um größere Funktionen als 256 Anweisungen zu unterstützen, berechnen wir den Offset des ersten Dateneintrags für Anweisungen als
(instruction offset)//2 + (quickened operand).Verglichen mit dem Opcache in Python 3.10 ist dieses Design
- schneller; es erfordert keine Speicherlesevorgänge, um den Offset zu berechnen. 3.10 erfordert zwei abhängige Lesevorgänge.
- verbraucht deutlich weniger Speicher, da die Daten für verschiedene Instruktionsfamilien unterschiedliche Größen haben können und kein zusätzliches Array von Offsets benötigt wird. kann viel größere Funktionen unterstützen, bis zu etwa 5000 Anweisungen pro Funktion. 3.10 kann etwa 1000 unterstützen.
Wir haben dieses Schema verworfen, da der Inline-Cache-Ansatz sowohl schneller als auch einfacher ist.
Referenzen
Urheberrecht
Dieses Dokument wird in die Public Domain oder unter die CC0-1.0-Universal-Lizenz gestellt, je nachdem, welche Lizenz permissiver ist.
Quelle: https://github.com/python/peps/blob/main/peps/pep-0659.rst
Zuletzt geändert: 2024-10-29 10:45:35 GMT