String-Interning in MicroPython

MicroPython verwendet string interning, um sowohl RAM als auch ROM zu sparen. Dadurch wird vermieden, dass doppelte Kopien desselben Strings gespeichert werden müssen. Dies betrifft in erster Linie Bezeichner in Ihrem Code, da etwas wie ein Funktions- oder Variablenname sehr wahrscheinlich an mehreren Stellen im Code vorkommt. In MicroPython wird ein internierter String als QSTR (uniQue STRing) bezeichnet.

Ein QSTR-Wert (mit Typ qstr) ist ein Index in eine verkettete Liste von QSTR-Pools. QSTRs speichern ihre Länge und einen Hash ihres Inhalts für einen schnellen Vergleich während des Deduplizierungsprozesses. Alle Bytecode-Operationen, die mit Strings arbeiten, verwenden ein QSTR-Argument.

QSTR-Generierung zur Kompilierzeit

Im C-Code von MicroPython werden alle Strings, die in der endgültigen Firmware interniert werden sollen, als MP_QSTR_Foo geschrieben. Zur Kompilierzeit wird dies zu einem qstr-Wert ausgewertet, der auf den Index von "Foo" im QSTR-Pool zeigt.

Ein mehrstufiger Prozess im Makefile lässt dies funktionieren. Zusammengefasst besteht dieser Prozess aus drei Teilen:

  1. Alle MP_QSTR_Foo-Token im Code finden.

  2. Einen statischen QSTR-Pool generieren, der alle String-Daten (einschließlich Längen und Hashes) enthält.

  3. Alle MP_QSTR_Foo (über den Präprozessor) durch ihren entsprechenden Index ersetzen.

Nach MP_QSTR_Foo-Token wird in zwei Quellen gesucht:

  1. Alle in $(SRC_QSTR) referenzierten Dateien. Das ist der gesamte C-Code (d. h. py, extmod, ports/stm32), aber nicht Drittanbieter-Code wie lib.

  2. Zusätzliche $(QSTR_GLOBAL_DEPENDENCIES) (die mpconfig*.h umfassen).

Hinweis: frozen_mpy.c (generiert von mpy-tool.py) hat seine eigene QSTR-Generierung und seinen eigenen Pool.

Einige zusätzliche Strings, die sich nicht mit der MP_QSTR_Foo-Syntax ausdrücken lassen (z. B. weil sie nicht-alphanumerische Zeichen enthalten), werden explizit in qstrdefs.h und qstrdefsport.h über die Variable $(QSTR_DEFS) bereitgestellt.

Die Verarbeitung erfolgt in den folgenden Phasen:

  1. qstr.i.last ist die Verkettung des Durchlaufs jeder einzelnen Eingabedatei durch den C-Präprozessor. Das bedeutet, dass jeder bedingt deaktivierte Code entfernt und Makros expandiert werden. Dadurch fügen wir dem Pool keine Strings hinzu, die in der endgültigen Firmware nicht verwendet werden. Da es in dieser Phase (dank des durch QSTR_GEN_CFLAGS hinzugefügten Makros NO_QSTR) keine Definition für MP_QSTR_Foo gibt, passiert es diese Phase unverändert. Diese Datei enthält außerdem Kommentare des Präprozessors mit Zeilennummerninformationen. Beachten Sie, dass dieser Schritt nur Dateien verwendet, die sich geändert haben, was bedeutet, dass qstr.i.last nur Daten aus Dateien enthält, die sich seit der letzten Kompilierung geändert haben.

  2. qstr.split ist eine leere Datei, die nach dem Ausführen von makeqstrdefs.py split auf qstr.i.last erstellt wird. Sie wird lediglich als Abhängigkeit verwendet, um anzuzeigen, dass der Schritt ausgeführt wurde. Dieses Skript gibt eine Datei pro Eingabe-C-Datei aus, genhdr/qstr/...file.c.qstr, die nur die übereinstimmenden QSTRs enthält. Jeder QSTR wird als Q(Foo) ausgegeben. Dieser Schritt ist notwendig, um die vorhandenen Dateien mit den neuen Daten zu kombinieren, die aus der inkrementellen Aktualisierung in qstr.i.last generiert wurden.

  3. qstrdefs.collected.h ist die Ausgabe der Verkettung von genhdr/qstr/* mittels makeqstrdefs.py cat. Dies ist nun die vollständige Menge der im Code gefundenen MP_QSTR_Foo, nun als Q(Foo) formatiert, eines pro Zeile, mit Duplikaten. Diese Datei wird nur aktualisiert, wenn sich die Menge der QSTRs geändert hat. Ein Hash der QSTR-Daten wird in eine andere Datei (qstrdefs.collected.h.hash) geschrieben, was es ermöglicht, Änderungen über mehrere Builds hinweg zu verfolgen.

  4. Eine Aufzählung generieren, deren jeder Eintrag ein MP_QSTR_Foo auf seinen entsprechenden Index abbildet. Sie verkettet qstrdefs.collected.h mit qstrdefs*.h und transformiert dann jede Zeile von Q(Foo) zu "Q(Foo)", damit sie den Präprozessor unverändert passieren. Dann wird der Präprozessor verwendet, um jegliche bedingte Kompilierung in qstrdefs*.h zu behandeln. Anschließend wird die Transformation wieder zu Q(Foo) rückgängig gemacht und als qstrdefs.preprocessed.h gespeichert.

  5. qstrdefs.generated.h ist die Ausgabe von makeqstrdata.py. Für jedes Q(Foo) in qstrdefs.preprocessed.h (plus einige zusätzliche fest codierte) gibt es QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo") aus.

Dann geschehen in der Hauptkompilierung zwei Dinge mit qstrdefs.generated.h:

  1. In qstr.h wird jedes QDEF zu einem Eintrag in einem Enum, was MP_QSTR_Foo für den Code verfügbar und gleich dem Index dieses Strings in der QSTR-Tabelle macht.

  2. In qstr.c wird die eigentliche QSTR-Datentabelle als Elemente von mp_qstr_const_pool->qstrs generiert.

QSTR-Generierung zur Laufzeit

Zur Laufzeit können zusätzliche QSTR-Pools erstellt werden, sodass ihnen Strings hinzugefügt werden können. Zum Beispiel der Code:

foo[x] = 3

Es muss ein QSTR für den Wert von x erstellt werden, damit er vom Bytecode „load attr“ verwendet werden kann.

Außerdem müssen beim Kompilieren von Python-Code für Bezeichner und Literale QSTRs erstellt werden. Hinweis: Nur Literale, die kürzer als 10 Zeichen sind, werden zu QSTRs. Das liegt daran, dass ein regulärer String auf dem Heap immer mindestens 16 Byte (einen GC-Block) belegt, während QSTRs es ermöglichen, sie effizienter im Pool zu packen.

QSTR-Pools (und die zugrunde liegenden „Chunks“, die die String-Daten speichern) werden bei Bedarf auf dem Heap mit einer Mindestgröße alloziert.