String-interning in MicroPython

MicroPython gebruikt string interning om zowel RAM als ROM te besparen. Dit voorkomt dat dubbele kopieën van dezelfde string moeten worden opgeslagen. Dit geldt voornamelijk voor identifiers in je code, aangezien iets als een functie- of variabelenaam zeer waarschijnlijk op meerdere plaatsen in de code voorkomt. In MicroPython wordt een geïnternde string een QSTR (uniQue STRing) genoemd.

Een QSTR-waarde (met type qstr) is een index in een gekoppelde lijst van QSTR-pools. QSTR’s slaan hun lengte op en een hash van hun inhoud voor snelle vergelijking tijdens het ontdubbelingsproces. Alle bytecode-bewerkingen die met strings werken, gebruiken een QSTR-argument.

QSTR-generatie tijdens compileren

In de C-code van MicroPython worden alle strings die in de uiteindelijke firmware geïnternd moeten worden geschreven als MP_QSTR_Foo. Tijdens het compileren wordt dit geëvalueerd tot een qstr-waarde die verwijst naar de index van "Foo" in de QSTR-pool.

Een meerstapsproces in de Makefile zorgt ervoor dat dit werkt. Samengevat bestaat dit proces uit drie delen:

  1. Vind alle MP_QSTR_Foo-tokens in de code.

  2. Genereer een statische QSTR-pool die alle stringdata bevat (inclusief lengtes en hashes).

  3. Vervang alle MP_QSTR_Foo (via de preprocessor) door hun bijbehorende index.

MP_QSTR_Foo-tokens worden gezocht in twee bronnen:

  1. Alle bestanden waarnaar verwezen wordt in $(SRC_QSTR). Dit is alle C-code (d.w.z. py, extmod, ports/stm32) maar exclusief code van derden zoals lib.

  2. Aanvullende $(QSTR_GLOBAL_DEPENDENCIES) (die mpconfig*.h omvat).

Opmerking: frozen_mpy.c (gegenereerd door mpy-tool.py) heeft zijn eigen QSTR-generatie en -pool.

Enkele aanvullende strings die niet kunnen worden uitgedrukt met de MP_QSTR_Foo-syntaxis (bijvoorbeeld omdat ze niet-alfanumerieke tekens bevatten) worden expliciet opgegeven in qstrdefs.h en qstrdefsport.h via de variabele $(QSTR_DEFS).

De verwerking verloopt in de volgende fasen:

  1. qstr.i.last is de samenvoeging van elk afzonderlijk invoerbestand dat door de C-preprocessor wordt gehaald. Dit betekent dat alle voorwaardelijk uitgeschakelde code wordt verwijderd en macro’s worden geëxpandeerd. Dit betekent dat we geen strings aan de pool toevoegen die niet in de uiteindelijke firmware worden gebruikt. Omdat er in dit stadium (dankzij de NO_QSTR-macro die door QSTR_GEN_CFLAGS wordt toegevoegd) geen definitie is voor MP_QSTR_Foo, gaat dit ongewijzigd door deze fase. Dit bestand bevat ook commentaar van de preprocessor met informatie over regelnummers. Merk op dat deze stap alleen bestanden gebruikt die zijn gewijzigd, wat betekent dat qstr.i.last alleen data bevat van bestanden die sinds de laatste compilatie zijn gewijzigd.

  2. qstr.split is een leeg bestand dat wordt aangemaakt nadat makeqstrdefs.py split is uitgevoerd op qstr.i.last. Het wordt alleen gebruikt als een dependency om aan te geven dat de stap is uitgevoerd. Dit script genereert één bestand per invoer-C-bestand, genhdr/qstr/...file.c.qstr, dat alleen de overeenkomende QSTR’s bevat. Elke QSTR wordt afgedrukt als Q(Foo). Deze stap is nodig om de bestaande bestanden te combineren met de nieuwe data die is gegenereerd uit de incrementele update in qstr.i.last.

  3. qstrdefs.collected.h is het resultaat van het samenvoegen van genhdr/qstr/* met makeqstrdefs.py cat. Dit is nu de volledige set MP_QSTR_Foo‘s die in de code is gevonden, nu geformatteerd als Q(Foo), één per regel, met duplicaten. Dit bestand wordt alleen bijgewerkt als de set qstrs is gewijzigd. Een hash van de QSTR-data wordt naar een ander bestand geschreven (qstrdefs.collected.h.hash), waardoor wijzigingen tussen builds kunnen worden gevolgd.

  4. Genereer een enumeratie, waarvan elke vermelding een MP_QSTR_Foo koppelt aan de bijbehorende index. Het voegt qstrdefs.collected.h samen met qstrdefs*.h, en transformeert vervolgens elke regel van Q(Foo) naar "Q(Foo)" zodat ze ongewijzigd door de preprocessor gaan. Vervolgens wordt de preprocessor gebruikt om eventuele voorwaardelijke compilatie in qstrdefs*.h af te handelen. Daarna wordt de transformatie ongedaan gemaakt terug naar Q(Foo) en opgeslagen als qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h is het resultaat van makeqstrdata.py. Voor elke Q(Foo) in qstrdefs.preprocessed.h (plus enkele extra hardgecodeerde) genereert het QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

Vervolgens gebeuren er in de hoofdcompilatie twee dingen met qstrdefs.generated.h:

  1. In qstr.h wordt elke QDEF een vermelding in een enum, waardoor MP_QSTR_Foo beschikbaar wordt voor code en gelijk is aan de index van die string in de QSTR-tabel.

  2. In qstr.c wordt de daadwerkelijke QSTR-datatabel gegenereerd als elementen van de mp_qstr_const_pool->qstrs.

QSTR-generatie tijdens runtime

Er kunnen aanvullende QSTR-pools tijdens runtime worden aangemaakt zodat er strings aan kunnen worden toegevoegd. Bijvoorbeeld, de code:

foo[x] = 3

Zal een QSTR moeten aanmaken voor de waarde van x zodat deze kan worden gebruikt door de “load attr”-bytecode.

Ook moeten bij het compileren van Python-code QSTR’s worden aangemaakt voor identifiers en literals. Opmerking: alleen literals die korter zijn dan 10 tekens worden QSTR’s. Dit komt omdat een gewone string op de heap altijd minimaal 16 bytes inneemt (één GC-blok), terwijl QSTR’s het mogelijk maken om ze efficiënter in de pool te verpakken.

QSTR-pools (en de onderliggende “chunks” die de stringdata opslaan) worden on-demand op de heap toegewezen met een minimumgrootte.