Speicherverbrauch

Die Reduzierung des Speicherverbrauchs steht in direktem Zusammenhang mit der Anzahl der Dictionaries mit gemeinsam genutzten Schlüsseln, die zu einem bestimmten Zeitpunkt existieren. Diese Dictionaries sind typischerweise halb so groß wie die aktuelle Dictionary-Implementierung.

Benchmarking zeigt, dass der Speicherverbrauch für objektorientierte Programme um 10% bis 20% reduziert wird, ohne signifikante Änderungen des Speicherverbrauchs für andere Programme.

Geschwindigkeit

Die Leistung der neuen Implementierung wird von Speicherkolocationseffekten dominiert. Wenn Schlüssel nicht gemeinsam genutzt werden (z. B. in Modul-Dictionaries und Dictionaries, die explizit durch dict() oder {} erstellt werden), ändert sich die Leistung nicht (innerhalb eines oder zwei Prozent) im Vergleich zur aktuellen Implementierung.

Für den Fall gemeinsam genutzter Schlüssel trennt die neue Implementierung tendenziell die Schlüssel von den Werten, reduziert aber den gesamten Speicherverbrauch. Dies wird die Leistung in vielen Fällen verbessern, da die Auswirkungen des reduzierten Speicherverbrauchs die Verluste an Kolokation überwiegen, aber einige Programme können eine leichte Verlangsamung aufweisen.

Benchmarking zeigt bei den meisten Benchmarks keine signifikante Geschwindigkeitsänderung. Objektorientierte Benchmarks zeigen kleine Geschwindigkeitssteigerungen, wenn sie eine große Anzahl von Objekten derselben Klasse erstellen (der gcbench-Benchmark zeigt eine 10%ige Geschwindigkeitssteigerung; dies ist wahrscheinlich eine Obergrenze).

Split-Table-Dictionaries

Wenn Dictionaries erstellt werden, um den `__dict__`-Slot eines Objekts zu füllen, werden sie in aufgeteilter Form erstellt. Die Schlüssel-Tabelle wird im Typ gecacht, was potenziell ermöglicht, dass alle Attribut-Dictionaries von Instanzen einer Klasse Schlüssel gemeinsam nutzen. Sollten die Schlüssel dieser Dictionaries zu stark abweichen, werden einzelne Dictionaries verzögert in die kombinierte Tabellenform konvertiert. Dies gewährleistet einen guten Speicherverbrauch im häufigsten Fall und Korrektheit in allen Fällen.

Beim Ändern der Größe eines aufgeteilten Dictionaries wird es in eine kombinierte Tabelle konvertiert. Wenn die Größenänderung aufgrund des Speicherns eines Instanzattributs erfolgt und es nur eine Instanz einer Klasse gibt, wird das Dictionary sofort wieder aufgeteilt. Da die meisten OO-Codes Attribute in der `__init__`-Methode festlegen, werden alle Attribute gesetzt, bevor eine zweite Instanz erstellt wird, und es sind keine weiteren Größenänderungen erforderlich, da alle weiteren Instanz-Dictionaries die richtige Größe haben werden. Für komplexere Verwendungsmuster ist es unmöglich zu wissen, was der beste Ansatz ist, daher erlaubt die Implementierung zusätzliche Einfügungen bis zum Punkt einer Größenänderung, an dem sie zur kombinierten Tabelle (nicht gemeinsam genutzte Schlüssel) zurückkehrt.

Eine Löschung aus einem aufgeteilten Dictionary ändert die Schlüssel-Tabelle nicht, sie entfernt einfach den Wert aus dem Werte-Array.

Kombinierte-Table-Dictionaries

Explizite Dictionaries (dict() oder {}), Modul-Dictionaries und die meisten anderen Dictionaries werden als kombinierte Tabellen-Dictionaries erstellt. Ein kombiniertes Tabellen-Dictionary wird niemals zu einem aufgeteilten Tabellen-Dictionary. Kombinierte Tabellen sind weitgehend so aufgebaut wie die Tabellen im alten Dictionary, was zu einer sehr ähnlichen Leistung führt.

Vorteile

Signifikante Speicherersparnis für objektorientierte Anwendungen. Geringe Leistungssteigerung für Programme, die viele ähnliche Objekte erstellen.

Nachteile

Änderungen an Datenstrukturen: Drittanbieter-Module, die mit den Interna der Dictionary-Implementierung herumspielen, werden brechen.

Änderungen an der `repr()`-Ausgabe und der Iterationsreihenfolge: In den meisten Fällen bleibt dies unverändert. Bei einigen aufgeteilten Tabellen-Dictionaries ändert sich jedoch die Iterationsreihenfolge.

Keiner dieser Nachteile sollte ein Problem darstellen. Module, die mit den Interna der Dictionary-Implementierung herumspielen, sind bereits kaputt und sollten repariert werden, um die API zu verwenden. Die Iterationsreihenfolge von Dictionaries war nie definiert und war immer willkürlich; sie unterscheidet sich bei Jython und PyPy.

Alternative Implementierung

Eine alternative Implementierung für aufgeteilte Tabellen, die noch mehr Speicher sparen könnte, besteht darin, einen Index im Wertefeld der Schlüssel-Tabelle zu speichern (anstatt das Wertefeld zu ignorieren). Dieser Index würde explizit angeben, wo im Werte-Array gesucht werden soll. Das Werte-Array würde dann nur 1 Feld für jeden nutzbaren Slot in der Schlüssel-Tabelle benötigen, anstatt für jeden Slot in der Schlüssel-Tabelle.

Diese "indizierte" Version würde die Größe des Werte-Arrays um etwa ein Drittel reduzieren. Die Schlüssel-Tabelle würde ein zusätzliches "values_size"-Feld benötigen, wodurch die Größe kombinierter Dictionaries um ein Wort erhöht wird. Die zusätzliche Indirektion macht den Code komplexer und könnte die Leistung leicht reduzieren.

Die "indizierte" Version wird nicht in dieser Implementierung enthalten sein, sollte aber als aufgeschoben und nicht abgelehnt betrachtet werden, bis weitere Experimente durchgeführt wurden.