Internarea șirurilor în MicroPython

MicroPython folosește string interning pentru a economisi atât RAM, cât și ROM. Acest lucru evită stocarea unor copii duplicate ale aceluiași șir. În principal, acest lucru se aplică identificatorilor din codul tău, deoarece ceva precum un nume de funcție sau de variabilă este foarte probabil să apară în mai multe locuri din cod. În MicroPython, un șir internat se numește QSTR (uniQue STRing).

O valoare QSTR (cu tipul qstr) este un index într-o listă înlănțuită de bazine (pools) de QSTR-uri. QSTR-urile își stochează lungimea și un hash al conținutului pentru o comparație rapidă în timpul procesului de eliminare a duplicatelor. Toate operațiile bytecode care lucrează cu șiruri folosesc un argument QSTR.

Generarea QSTR-urilor la compilare

În codul C al MicroPython, orice șiruri care ar trebui internate în firmware-ul final sunt scrise sub forma MP_QSTR_Foo. La compilare, acest lucru va fi evaluat la o valoare qstr care indică spre indexul lui "Foo" din bazinul de QSTR-uri.

Un proces în mai mulți pași din Makefile face ca acest lucru să funcționeze. În rezumat, acest proces are trei părți:

  1. Găsirea tuturor token-urilor MP_QSTR_Foo din cod.

  2. Generarea unui bazin static de QSTR-uri care conține toate datele șirurilor (inclusiv lungimile și hash-urile).

  3. Înlocuirea tuturor MP_QSTR_Foo (prin intermediul preprocesorului) cu indexul lor corespunzător.

Token-urile MP_QSTR_Foo sunt căutate în două surse:

  1. Toate fișierele referite în $(SRC_QSTR). Acesta este întregul cod C (adică py, extmod, ports/stm32), dar fără a include cod terț precum lib.

  2. Suplimentar, $(QSTR_GLOBAL_DEPENDENCIES) (care include mpconfig*.h).

Notă: frozen_mpy.c (generat de mpy-tool.py) are propria sa generare de QSTR-uri și propriul bazin.

Unele șiruri suplimentare care nu pot fi exprimate folosind sintaxa MP_QSTR_Foo (de exemplu pentru că conțin caractere nealfanumerice) sunt furnizate explicit în qstrdefs.h și qstrdefsport.h prin variabila $(QSTR_DEFS).

Procesarea are loc în următoarele etape:

  1. qstr.i.last este rezultatul concatenării obținute prin trecerea fiecărui fișier de intrare prin preprocesorul C. Aceasta înseamnă că orice cod dezactivat condiționat va fi eliminat, iar macrourile vor fi expandate. Aceasta înseamnă că nu adăugăm în bazin șiruri care nu vor fi folosite în firmware-ul final. Deoarece în această etapă (datorită macroului NO_QSTR adăugat de QSTR_GEN_CFLAGS) nu există nicio definiție pentru MP_QSTR_Foo, acesta trece prin această etapă neafectat. Acest fișier include de asemenea comentarii de la preprocesor care conțin informații despre numărul liniei. De reținut că acest pas folosește doar fișierele care s-au modificat, ceea ce înseamnă că qstr.i.last va conține doar date din fișierele care s-au modificat de la ultima compilare.

  2. qstr.split este un fișier gol creat după rularea makeqstrdefs.py split asupra qstr.i.last. El este folosit doar ca dependență pentru a indica faptul că pasul a fost rulat. Acest script produce câte un fișier pentru fiecare fișier C de intrare, genhdr/qstr/...file.c.qstr, care conține doar QSTR-urile potrivite. Fiecare QSTR este afișat ca Q(Foo). Acest pas este necesar pentru a combina fișierele existente cu noile date generate din actualizarea incrementală din qstr.i.last.

  3. qstrdefs.collected.h este rezultatul concatenării genhdr/qstr/* folosind makeqstrdefs.py cat. Acesta este acum setul complet de MP_QSTR_Foo găsite în cod, formatate acum ca Q(Foo), câte unul pe linie, cu duplicate. Acest fișier este actualizat doar dacă setul de qstr-uri s-a modificat. Un hash al datelor QSTR este scris într-un alt fișier (qstrdefs.collected.h.hash), ceea ce permite urmărirea modificărilor de-a lungul build-urilor.

  4. Generarea unei enumerații, fiecare intrare a căreia mapează un MP_QSTR_Foo la indexul său corespunzător. Aceasta concatenează qstrdefs.collected.h cu qstrdefs*.h, apoi transformă fiecare linie din Q(Foo) în "Q(Foo)" astfel încât să treacă neschimbate prin preprocesor. Apoi preprocesorul este folosit pentru a trata orice compilare condiționată din qstrdefs*.h. Apoi transformarea este anulată înapoi la Q(Foo) și salvată ca qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h este rezultatul makeqstrdata.py. Pentru fiecare Q(Foo) din qstrdefs.preprocessed.h (plus câteva codificate suplimentar), acesta produce QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

Apoi, în compilarea principală, se întâmplă două lucruri cu qstrdefs.generated.h:

  1. În qstr.h, fiecare QDEF devine o intrare într-un enum, ceea ce face ca MP_QSTR_Foo să fie disponibil codului și egal cu indexul acelui șir din tabelul QSTR.

  2. În qstr.c, tabelul efectiv de date QSTR este generat ca elemente ale mp_qstr_const_pool->qstrs.

Generarea QSTR-urilor la execuție

Pot fi create bazine suplimentare de QSTR-uri la execuție astfel încât să li se poată adăuga șiruri. De exemplu, codul:

foo[x] = 3

Va trebui să creeze un QSTR pentru valoarea lui x astfel încât aceasta să poată fi folosită de bytecode-ul „load attr”.

De asemenea, la compilarea codului Python, trebuie create QSTR-uri pentru identificatori și literali. Notă: doar literalii mai scurți de 10 caractere devin QSTR-uri. Acest lucru se întâmplă deoarece un șir obișnuit din heap ocupă întotdeauna minimum 16 octeți (un bloc GC), în timp ce QSTR-urile permit împachetarea lor mai eficient în bazin.

Bazinele de QSTR-uri (și „chunk-urile” subiacente care stochează datele șirurilor) sunt alocate la cerere în heap, cu o dimensiune minimă.