L’interning delle stringhe in MicroPython

MicroPython utilizza l”string interning per risparmiare sia RAM che ROM. Questo evita di dover memorizzare copie duplicate della stessa stringa. Principalmente, ciò si applica agli identificatori nel tuo codice, dato che qualcosa come il nome di una funzione o di una variabile è molto probabile che compaia in più punti del codice. In MicroPython una stringa interned è chiamata QSTR (uniQue STRing).

Un valore QSTR (con tipo qstr) è un indice in una lista concatenata di pool di QSTR. I QSTR memorizzano la propria lunghezza e un hash del proprio contenuto per un confronto rapido durante il processo di de-duplicazione. Tutte le operazioni del bytecode che lavorano con le stringhe usano un argomento QSTR.

Generazione dei QSTR al momento della compilazione

Nel codice C di MicroPython, qualsiasi stringa che debba essere interned nel firmware finale viene scritta come MP_QSTR_Foo. Al momento della compilazione questo verrà valutato come un valore qstr che punta all’indice di "Foo" nel pool di QSTR.

Un processo a più fasi nel Makefile fa funzionare tutto questo. In sintesi questo processo è composto da tre parti:

  1. Trova tutti i token MP_QSTR_Foo nel codice.

  2. Genera un pool statico di QSTR contenente tutti i dati delle stringhe (incluse lunghezze e hash).

  3. Sostituisce tutti i MP_QSTR_Foo (tramite il preprocessore) con il loro indice corrispondente.

I token MP_QSTR_Foo vengono cercati in due sorgenti:

  1. Tutti i file referenziati in $(SRC_QSTR). Questo è tutto il codice C (cioè py, extmod, ports/stm32) ma non include il codice di terze parti come lib.

  2. Ulteriori $(QSTR_GLOBAL_DEPENDENCIES) (che includono mpconfig*.h).

Nota: frozen_mpy.c (generato da mpy-tool.py) ha la propria generazione e il proprio pool di QSTR.

Alcune stringhe aggiuntive che non possono essere espresse usando la sintassi MP_QSTR_Foo (ad esempio perché contengono caratteri non alfanumerici) vengono fornite esplicitamente in qstrdefs.h e qstrdefsport.h tramite la variabile $(QSTR_DEFS).

L’elaborazione avviene nelle seguenti fasi:

  1. qstr.i.last è la concatenazione del risultato del passaggio di ogni singolo file di input attraverso il preprocessore C. Questo significa che qualsiasi codice disabilitato condizionalmente verrà rimosso, e le macro espanse. Questo significa che non aggiungiamo al pool stringhe che non saranno usate nel firmware finale. Poiché in questa fase (grazie alla macro NO_QSTR aggiunta da QSTR_GEN_CFLAGS) non c’è alcuna definizione per MP_QSTR_Foo, esso attraversa questa fase senza essere modificato. Questo file include anche commenti dal preprocessore che contengono informazioni sui numeri di riga. Nota che questo passaggio usa solo i file che sono cambiati, il che significa che qstr.i.last conterrà solo dati provenienti dai file che sono cambiati dall’ultima compilazione.

  2. qstr.split è un file vuoto creato dopo l’esecuzione di makeqstrdefs.py split su qstr.i.last. Viene usato semplicemente come dipendenza per indicare che il passaggio è stato eseguito. Questo script produce un file per ciascun file C di input, genhdr/qstr/...file.c.qstr, che contiene solo i QSTR trovati. Ogni QSTR viene stampato come Q(Foo). Questo passaggio è necessario per combinare i file esistenti con i nuovi dati generati dall’aggiornamento incrementale in qstr.i.last.

  3. qstrdefs.collected.h è il risultato della concatenazione di genhdr/qstr/* usando makeqstrdefs.py cat. Questo è ora l’insieme completo dei MP_QSTR_Foo trovati nel codice, ora formattati come Q(Foo), uno per riga, con i duplicati. Questo file viene aggiornato solo se l’insieme dei qstr è cambiato. Un hash dei dati QSTR viene scritto in un altro file (qstrdefs.collected.h.hash) che consente di tracciare i cambiamenti tra le build.

  4. Genera un’enumerazione, ciascuna voce della quale mappa un MP_QSTR_Foo al suo indice corrispondente. Concatena qstrdefs.collected.h con qstrdefs*.h, poi trasforma ogni riga da Q(Foo) a "Q(Foo)" in modo che attraversino il preprocessore senza modifiche. Poi il preprocessore viene usato per gestire qualsiasi compilazione condizionale in qstrdefs*.h. Poi la trasformazione viene annullata tornando a Q(Foo), e salvata come qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h è il risultato di makeqstrdata.py. Per ogni Q(Foo) in qstrdefs.preprocessed.h (più alcuni hard-coded aggiuntivi), produce QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

Poi nella compilazione principale, accadono due cose con qstrdefs.generated.h:

  1. In qstr.h, ogni QDEF diventa una voce in un enum, il che rende MP_QSTR_Foo disponibile al codice e pari all’indice di quella stringa nella tabella QSTR.

  2. In qstr.c, l’effettiva tabella dei dati QSTR viene generata come elementi di mp_qstr_const_pool->qstrs.

Generazione dei QSTR a runtime

Pool di QSTR aggiuntivi possono essere creati a runtime in modo che vi si possano aggiungere stringhe. Per esempio, il codice:

foo[x] = 3

Dovrà creare un QSTR per il valore di x in modo che possa essere usato dal bytecode «load attr».

Inoltre, durante la compilazione del codice Python, è necessario creare QSTR per identificatori e letterali. Nota: solo i letterali più corti di 10 caratteri diventano QSTR. Questo perché una normale stringa nello heap occupa sempre un minimo di 16 byte (un blocco GC), mentre i QSTR consentono di impacchettarli in modo più efficiente nel pool.

I pool di QSTR (e i «chunk» sottostanti che memorizzano i dati delle stringhe) vengono allocati su richiesta nello heap con una dimensione minima.