Beschleunigung von Methodenaufrufen

Yury Selivanov schrieb einen Patch zur Optimierung von Methodenaufrufen. Der Patch hängt von dem Patch „Implementierung eines pro-Opcode-Caches in ceval“ ab, der Dictionary-Versionen zur Invalidierung des Caches benötigt, falls das Globals-Dictionary oder das Builtins-Dictionary geändert wurde.

Der Cache erfordert auch, dass die Dictionary-Version global eindeutig ist. Es ist möglich, eine Funktion in einem Namespace zu definieren und sie in einem anderen Namespace aufzurufen, z.B. mit exec() mit dem globals-Parameter. In diesem Fall wurde das Globals-Dictionary ersetzt und der Cache muss ebenfalls invalidiert werden.

Spezialisierte Funktionen mit Guards

PEP 510 schlägt eine API zur Unterstützung spezialisierter Funktionen mit Guards vor. Sie ermöglicht die Implementierung statischer Optimierer für Python, ohne die Python-Semantik zu verletzen.

Der fatoptimizer des FAT Python-Projekts ist ein Beispiel für einen statischen Python-Optimierer. Er implementiert viele Optimierungen, die Guards für Namespaces erfordern.

• Aufruf reiner Builtins: Um len("abc") durch 3 zu ersetzen, sind Guards für builtins.__dict__['len'] und globals()['len'] erforderlich.
• Schleifenentrollung: Um die Schleife for i in range(...): ... zu entrollen, sind Guards für builtins.__dict__['range'] und globals()['range'] erforderlich.
• usw.

Pyjion

Laut Brett Cannon, einem der beiden Hauptentwickler von Pyjion, kann Pyjion von der Dictionary-Version profitieren, um Optimierungen zu implementieren.

Pyjion ist ein JIT-Compiler für Python, der auf CoreCLR (Microsoft .NET Core Runtime) basiert.

Cython

Cython kann von der Dictionary-Version profitieren, um Optimierungen zu implementieren.

Cython ist ein optimierender statischer Compiler sowohl für die Programmiersprache Python als auch für die erweiterte Cython-Programmiersprache.

Unladen Swallow

Auch wenn die Dictionary-Version nicht explizit erwähnt wurde, war die Optimierung von Globals- und Builtins-Lookups Teil des Unladen Swallow-Plans: "Implement one of the several proposed schemes for speeding lookups of globals and builtins." (Quelle: Unladen Swallow ProjectPlan).

Unladen Swallow ist ein Fork von CPython 2.6.1, der einen JIT-Compiler hinzufügt, der mit LLVM implementiert ist. Das Projekt wurde 2011 eingestellt: Unladen Swallow Retrospective.

Exponiere die Version auf Python-Ebene als schreibgeschütztes __version__ Property

Die erste Version des PEP schlug vor, die Dictionary-Version als schreibgeschütztes __version__-Property auf Python-Ebene zu exponieren und das Property auch zu collections.UserDict hinzuzufügen (da dieser Typ die dict-API nachahmen muss).

Es gibt mehrere Probleme:

• Um konsistent zu sein und böse Überraschungen zu vermeiden, muss die Version zu allen Mapping-Typen hinzugefügt werden. Die Implementierung eines neuen Mapping-Typs würde zusätzlichen Aufwand ohne Nutzen bedeuten, da die Version praktisch nur für den dict-Typ benötigt wird.
• Alle Python-Implementierungen müssten dieses neue Property implementieren, was anderen Implementierungen mehr Arbeit macht, obwohl sie die Dictionary-Version möglicherweise gar nicht nutzen.
• Die Exponierung der Dictionary-Version auf Python-Ebene kann zu falschen Annahmen über die Performance führen. Das Prüfen von dict.__version__ auf Python-Ebene ist nicht schneller als ein Dictionary-Lookup. Ein Dictionary-Lookup in Python kostet 48,7 ns und die Überprüfung der Version kostet 47,5 ns, der Unterschied beträgt nur 1,2 ns (3%).

  $ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd["33"] == 33'
  10000000 loops, best of 3: 0.0487 usec per loop
  $ python3.6 -m timeit -s 'd = {str(i):i for i in range(100)}' 'd.__version__ == 100'
  10000000 loops, best of 3: 0.0475 usec per loop
  

• Das __version__ kann bei Integer-Überlauf „eingewickelt“ werden. Dies ist fehleranfällig: die Verwendung von dict.__version__ <= guard_version ist falsch, stattdessen muss dict.__version__ == guard_version verwendet werden, um das Fehlerrisiko bei Integer-Überlauf zu verringern (auch wenn der Integer-Überlauf in der Praxis unwahrscheinlich ist).

Obligatorisches „Bikeshedding“ auf dem Property-Namen

• __cache_token__: Name vorgeschlagen von Alyssa Coghlan, Name abgeleitet von abc.get_cache_token().
• __version__
• __version_tag__
• __timestamp__

Füge eine Version zu jedem dict-Eintrag hinzu

Eine einzige Version pro Dictionary erfordert das Beibehalten einer starken Referenz auf den Wert, was den Wert länger als erwartet lebendig halten kann. Wenn wir auch eine Version pro Dictionary-Eintrag hinzufügen, kann der Guard nur die Eintrag-Version (eine einfache Ganzzahl) speichern, um die starke Referenz auf den Wert zu vermeiden: nur starke Referenzen auf das Dictionary und den Schlüssel werden benötigt.

Änderungen: Füge ein Feld me_version_tag zur Struktur PyDictKeyEntry hinzu. Das Feld hat den C-Typ PY_UINT64_T. Wenn ein Schlüssel erstellt oder geändert wird, wird die Eintrag-Version auf die Dictionary-Version gesetzt, die bei jeder Änderung (Erstellung, Änderung, Löschung) inkrementiert wird.

Pseudocode eines schnellen Guards zur Überprüfung, ob ein Dictionary-Schlüssel geändert wurde, unter Verwendung hypothetischer Funktionen dict_get_version(dict) und dict_get_entry_version(dict)

UNSET = object()

class GuardDictKey:
    def __init__(self, dict, key):
        self.dict = dict
        self.key = key
        self.dict_version = dict_get_version(dict)
        self.entry_version = dict_get_entry_version(dict, key)

    def check(self):
        """Return True if the dictionary entry did not change
        and the dictionary was not replaced."""

        # read the version of the dictionary
        dict_version = dict_get_version(self.dict)
        if dict_version == self.version:
            # Fast-path: dictionary lookup avoided
            return True

        # lookup in the dictionary to read the entry version
        entry_version = get_dict_key_version(dict, key)
        if entry_version == self.entry_version:
            # another key was modified:
            # cache the new dictionary version
            self.dict_version = dict_version
            self.entry_version = entry_version
            return True

        # the key was modified
        return False

Der Hauptnachteil dieser Option ist die Auswirkung auf den Speicherbedarf. Sie erhöht die Größe jedes Dictionary-Eintrags, sodass die Überbelastung von der Anzahl der Buckets (Dictionary-Einträge, verwendet oder nicht verwendet) abhängt. Zum Beispiel erhöht sie die Größe jedes Dictionary-Eintrags um 8 Bytes auf 64-Bit-Systemen.

In Python ist der Speicherbedarf wichtig, und der Trend geht dahin, ihn zu reduzieren. Beispiele:

• PEP 393 – Flexible String Representation
• PEP 412 – Key-Sharing Dictionary

Füge einen neuen dict-Subtyp hinzu

Füge einen neuen Typ verdict hinzu, einen Subtyp von dict. Wenn Guards benötigt werden, verwende verdict für Namespaces (Modul-Namespace, Typ-Namespace, Instanz-Namespace usw.) anstelle von dict.

Lasse den Typ dict unverändert, um keinen Overhead (CPU, Speicherbedarf) hinzuzufügen, wenn Guards nicht verwendet werden.

Technisches Problem: Viel C-Code im Umlauf, einschließlich des CPython-Kerns, der den exakten Typ dict erwartet. Probleme:

• exec() benötigt ein dict für Globals und Locals. Viel Code verwendet globals={}. Es ist nicht möglich, das dict in einen dict-Subtyp umzuwandeln, da der Aufrufer erwartet, dass der Parameter globals geändert wird (dict ist veränderlich).
• C-Funktionen rufen direkt PyDict_xxx()-Funktionen auf, anstatt PyObject_xxx() aufzurufen, wenn das Objekt ein dict-Subtyp ist.
• Die Prüfung PyDict_CheckExact() schlägt bei dict-Subtypen fehl, während einige Funktionen den exakten Typ dict benötigen.
• Python/ceval.c unterstützt Dict-Subtypen für Namespaces nicht vollständig.

Das exec()-Problem ist ein Blockierungsproblem.

Andere Probleme

• Der Garbage Collector hat speziellen Code, um dict-Instanzen zu „entfolgen“. Wenn ein dict-Subtyp für Namespaces verwendet wird, kann der Garbage Collector einige Referenzzyklen nicht brechen.
• Einige Funktionen haben einen Fast-Path für dict, der für dict-Subtypen nicht genommen würde, und dies würde Python ein wenig langsamer machen.

Methoden-Cache und Typ-Versions-Tag

Im Jahr 2007 schrieb Armin Rigo einen Patch zur Implementierung eines Methoden-Caches. Er wurde in Python 2.6 integriert. Der Patch fügt Typen (die Struktur PyTypeObject) einen „type attribute cache version tag“ (tp_version_tag) und ein Flag „valid version tag“ hinzu.

Der Typ-Versions-Tag wird nicht auf Python-Ebene exponiert.

Der Versionstag hat den C-Typ unsigned int. Der Cache ist eine globale Hash-Tabelle mit 4096 Einträgen, die von allen Typen gemeinsam genutzt wird. Der Cache ist global, um ihn „schnell, mit geringem Speicherbedarf und deterministisch zu machen und ihn einfach zu invalidieren“. Jeder Cache-Eintrag hat einen Versionstag. Ein globaler Versionstag wird verwendet, um den nächsten Versionstag zu erstellen; er hat ebenfalls den C-Typ unsigned int.

Standardmäßig ist das Flag „valid version tag“ eines Typs gelöscht, um anzuzeigen, dass der Versionstag ungültig ist. Wenn die erste Methode des Typs gecached wird, werden der Versionstag und das Flag „valid version tag“ gesetzt. Wenn ein Typ geändert wird, werden das Flag „valid version tag“ des Typs und seiner Unterklassen gelöscht. Später, wenn ein Cache-Eintrag dieser Typen verwendet wird, wird der Eintrag entfernt, da sein Versionstag veraltet ist.

Bei Integer-Überlauf wird der gesamte Cache gelöscht und der globale Versionstag wird auf 0 zurückgesetzt.

Siehe Method cache (issue #1685986) und Armin’s method cache optimization updated for Python 2.6 (issue #1700288).

Globale / Builtin-Cache

Im Jahr 2010 schlug Antoine Pitrou einen Globals / builtins cache (issue #10401) vor, der ein privates Feld ma_version zur Struktur PyDictObject (Typ dict) hinzufügt. Das Feld hat den C-Typ Py_ssize_t.

Der Patch fügt Funktionen und Frames einen „globalen und builtin-Cache hinzu und ändert die Instruktionen LOAD_GLOBAL und STORE_GLOBAL, um den Cache zu verwenden.

Die Änderung an der Struktur PyDictObject ist der dieses PEP sehr ähnlich.

Gecachter Globals+Builtins Lookup

Im Jahr 2006 schlug Andrea Griffini einen Patch zur Implementierung einer Cached globals+builtins lookup optimization vor. Der Patch fügt der Struktur PyDictObject (Typ dict) ein privates Feld timestamp hinzu. Das Feld hat den C-Typ size_t.

Thread auf python-dev: About dictionary lookup caching (Dezember 2006).

Guard gegen Änderung des dict während der Iteration

Im Jahr 2013 schlug Serhiy Storchaka Guard against changing dict during iteration (issue #19332) vor, der ein Feld ma_count zur Struktur PyDictObject (Typ dict) hinzufügt. Das Feld hat den C-Typ size_t. Dieses Feld wird inkrementiert, wenn das Dictionary geändert wird.

PySizer

PySizer: ein Speicherprofiler für Python, ein Google Summer of Code 2005 Projekt von Nick Smallbone.

Dieses Projekt hat einen Patch für CPython 2.4, der die Felder key_time und value_time zu Dictionary-Einträgen hinzufügt. Er verwendet einen globalen, prozessweiten Zähler für Dictionaries, der bei jeder Änderung eines Dictionaries inkrementiert wird. Die Zeiten werden verwendet, um zu entscheiden, wann Kindobjekte zum ersten Mal in ihren Elternobjekten erschienen sind.