Stränginternering i MicroPython

MicroPython använder string interning för att spara både RAM och ROM. Detta undviker att behöva lagra dubbletter av samma sträng. I första hand gäller detta identifierare i din kod, eftersom något i stil med ett funktions- eller variabelnamn med stor sannolikhet förekommer på flera ställen i koden. I MicroPython kallas en internerad sträng för en QSTR (uniQue STRing).

Ett QSTR-värde (av typen qstr) är ett index i en länkad lista av QSTR-pooler. QSTR:er lagrar sin längd och en hash av sitt innehåll för snabb jämförelse under avdupliceringsprocessen. Alla bytekodsoperationer som arbetar med strängar använder ett QSTR-argument.

QSTR-generering vid kompileringstid

I MicroPythons C-kod skrivs alla strängar som ska interneras i den slutliga fasta programvaran som MP_QSTR_Foo. Vid kompileringstid kommer detta att utvärderas till ett qstr-värde som pekar på indexet för "Foo" i QSTR-poolen.

En flerstegsprocess i Makefile får detta att fungera. Sammanfattningsvis har denna process tre delar:

  1. Hitta alla MP_QSTR_Foo-token i koden.

  2. Generera en statisk QSTR-pool som innehåller all strängdata (inklusive längder och hashvärden).

  3. Ersätt alla MP_QSTR_Foo (via preprocessorn) med deras motsvarande index.

MP_QSTR_Foo-token söks efter i två källor:

  1. Alla filer som refereras i $(SRC_QSTR). Detta är all C-kod (dvs. py, extmod, ports/stm32) men inte tredjepartskod såsom lib.

  2. Ytterligare $(QSTR_GLOBAL_DEPENDENCIES) (som inkluderar mpconfig*.h).

Obs: frozen_mpy.c (genererad av mpy-tool.py) har sin egen QSTR-generering och pool.

Vissa ytterligare strängar som inte kan uttryckas med syntaxen MP_QSTR_Foo (t.ex. för att de innehåller icke-alfanumeriska tecken) anges explicit i qstrdefs.h och qstrdefsport.h via variabeln $(QSTR_DEFS).

Bearbetningen sker i följande steg:

  1. qstr.i.last är sammanfogningen av att köra varenda indatafil genom C-preprocessorn. Detta innebär att all villkorligt inaktiverad kod tas bort och att makron expanderas. Det innebär att vi inte lägger till strängar i poolen som inte kommer att användas i den slutliga fasta programvaran. Eftersom det i detta skede (tack vare makrot NO_QSTR som läggs till av QSTR_GEN_CFLAGS) inte finns någon definition för MP_QSTR_Foo passerar det detta skede oförändrat. Denna fil inkluderar även kommentarer från preprocessorn som innehåller radnummerinformation. Observera att detta steg endast använder filer som har ändrats, vilket innebär att qstr.i.last endast kommer att innehålla data från filer som har ändrats sedan den senaste kompileringen.

  2. qstr.split är en tom fil som skapas efter att makeqstrdefs.py split har körts på qstr.i.last. Den används bara som ett beroende för att indikera att steget kördes. Detta skript matar ut en fil per indata-C-fil, genhdr/qstr/...file.c.qstr, som endast innehåller de matchade QSTR:erna. Varje QSTR skrivs ut som Q(Foo). Detta steg är nödvändigt för att kombinera de befintliga filerna med den nya data som genererats från den inkrementella uppdateringen i qstr.i.last.

  3. qstrdefs.collected.h är resultatet av att sammanfoga genhdr/qstr/* med makeqstrdefs.py cat. Detta är nu den fullständiga uppsättningen av MP_QSTR_Foo:er som hittats i koden, nu formaterade som Q(Foo), en per rad, med dubbletter. Denna fil uppdateras endast om uppsättningen qstr:er har ändrats. En hash av QSTR-datan skrivs till en annan fil (qstrdefs.collected.h.hash) vilket gör det möjligt att spåra ändringar mellan byggen.

  4. Generera en uppräkning (enum), där varje post mappar en MP_QSTR_Foo till dess motsvarande index. Den sammanfogar qstrdefs.collected.h med qstrdefs*.h, och transformerar sedan varje rad från Q(Foo) till "Q(Foo)" så att de passerar oförändrade genom preprocessorn. Sedan används preprocessorn för att hantera eventuell villkorlig kompilering i qstrdefs*.h. Därefter ångras transformationen tillbaka till Q(Foo) och sparas som qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h är resultatet av makeqstrdata.py. För varje Q(Foo) i qstrdefs.preprocessed.h (plus några extra hårdkodade) matar den ut QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

Sedan, i huvudkompileringen, händer två saker med qstrdefs.generated.h:

  1. I qstr.h blir varje QDEF en post i en enum, vilket gör MP_QSTR_Foo tillgänglig för koden och lika med indexet för den strängen i QSTR-tabellen.

  2. I qstr.c genereras den faktiska QSTR-datatabellen som element i mp_qstr_const_pool->qstrs.

QSTR-generering vid körningstid

Ytterligare QSTR-pooler kan skapas vid körningstid så att strängar kan läggas till i dem. Till exempel kommer koden:

foo[x] = 3

att behöva skapa en QSTR för värdet på x så att den kan användas av bytekoden ”load attr”.

Vid kompilering av Python-kod behöver dessutom identifierare och literaler få QSTR:er skapade. Obs: endast literaler som är kortare än 10 tecken blir QSTR:er. Detta beror på att en vanlig sträng på heapen alltid tar upp minst 16 byte (ett GC-block), medan QSTR:er gör att de kan packas mer effektivt i poolen.

QSTR-pooler (och de underliggande ”chunks” som lagrar strängdatan) allokeras vid behov på heapen med en minsta storlek.