Internamento de strings no MicroPython

O MicroPython usa string interning para economizar tanto RAM quanto ROM. Isso evita ter que armazenar cópias duplicadas da mesma string. Principalmente, isso se aplica a identificadores no seu código, já que algo como o nome de uma função ou variável tem grande probabilidade de aparecer em vários lugares do código. No MicroPython, uma string internada é chamada de QSTR (uniQue STRing).

Um valor QSTR (com tipo qstr) é um índice em uma lista encadeada de pools de QSTR. As QSTRs armazenam seu comprimento e um hash de seu conteúdo para comparação rápida durante o processo de deduplicação. Todas as operações de bytecode que trabalham com strings usam um argumento QSTR.

Geração de QSTR em tempo de compilação

No código C do MicroPython, quaisquer strings que devam ser internadas no firmware final são escritas como MP_QSTR_Foo. Em tempo de compilação, isso será avaliado como um valor qstr que aponta para o índice de "Foo" no pool de QSTR.

Um processo de várias etapas no Makefile faz isso funcionar. Em resumo, esse processo tem três partes:

  1. Encontrar todos os tokens MP_QSTR_Foo no código.

  2. Gerar um pool estático de QSTR contendo todos os dados das strings (incluindo comprimentos e hashes).

  3. Substituir todos os MP_QSTR_Foo (via pré-processador) por seu índice correspondente.

Os tokens MP_QSTR_Foo são procurados em duas fontes:

  1. Todos os arquivos referenciados em $(SRC_QSTR). Isso inclui todo o código C (ou seja, py, extmod, ports/stm32), mas não código de terceiros como lib.

  2. Os $(QSTR_GLOBAL_DEPENDENCIES) adicionais (que incluem mpconfig*.h).

Nota: frozen_mpy.c (gerado por mpy-tool.py) tem sua própria geração e pool de QSTR.

Algumas strings adicionais que não podem ser expressas usando a sintaxe MP_QSTR_Foo (por exemplo, porque contêm caracteres não alfanuméricos) são fornecidas explicitamente em qstrdefs.h e qstrdefsport.h por meio da variável $(QSTR_DEFS).

O processamento ocorre nas seguintes etapas:

  1. qstr.i.last é a concatenação resultante de passar cada arquivo de entrada pelo pré-processador C. Isso significa que qualquer código desabilitado condicionalmente será removido, e as macros serão expandidas. Isso significa que não adicionamos ao pool strings que não serão usadas no firmware final. Como nesta etapa (graças à macro NO_QSTR adicionada por QSTR_GEN_CFLAGS) não há definição para MP_QSTR_Foo, ele passa por esta etapa sem ser afetado. Esse arquivo também inclui comentários do pré-processador que contêm informações de número de linha. Observe que esta etapa usa apenas arquivos que mudaram, o que significa que qstr.i.last conterá apenas dados de arquivos que mudaram desde a última compilação.

  2. qstr.split é um arquivo vazio criado após executar makeqstrdefs.py split em qstr.i.last. Ele é usado apenas como uma dependência para indicar que a etapa foi executada. Esse script gera um arquivo por arquivo C de entrada, genhdr/qstr/...file.c.qstr, que contém apenas as QSTRs correspondentes. Cada QSTR é impressa como Q(Foo). Esta etapa é necessária para combinar os arquivos existentes com os novos dados gerados pela atualização incremental em qstr.i.last.

  3. qstrdefs.collected.h é a saída da concatenação de genhdr/qstr/* usando makeqstrdefs.py cat. Esse é agora o conjunto completo dos MP_QSTR_Foo encontrados no código, agora formatados como Q(Foo), um por linha, com duplicatas. Esse arquivo só é atualizado se o conjunto de qstrs mudar. Um hash dos dados das QSTR é escrito em outro arquivo (qstrdefs.collected.h.hash), o que permite rastrear as mudanças entre builds.

  4. Gerar uma enumeração, na qual cada entrada mapeia um MP_QSTR_Foo ao seu índice correspondente. Ela concatena qstrdefs.collected.h com qstrdefs*.h, e então transforma cada linha de Q(Foo) em "Q(Foo)" para que passem inalteradas pelo pré-processador. Em seguida, o pré-processador é usado para lidar com qualquer compilação condicional em qstrdefs*.h. Depois, a transformação é desfeita de volta para Q(Foo) e salva como qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h é a saída de makeqstrdata.py. Para cada Q(Foo) em qstrdefs.preprocessed.h (mais alguns extras codificados manualmente), ele gera QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

Então, na compilação principal, duas coisas acontecem com qstrdefs.generated.h:

  1. Em qstr.h, cada QDEF se torna uma entrada em um enum, o que torna MP_QSTR_Foo disponível para o código e igual ao índice daquela string na tabela de QSTR.

  2. Em qstr.c, a tabela de dados QSTR propriamente dita é gerada como elementos de mp_qstr_const_pool->qstrs.

Geração de QSTR em tempo de execução

Pools de QSTR adicionais podem ser criados em tempo de execução para que strings possam ser adicionadas a eles. Por exemplo, o código:

foo[x] = 3

Será necessário criar uma QSTR para o valor de x para que ele possa ser usado pelo bytecode “load attr”.

Além disso, ao compilar código Python, identificadores e literais precisam ter QSTRs criadas. Nota: apenas literais com menos de 10 caracteres se tornam QSTRs. Isso porque uma string comum no heap sempre ocupa no mínimo 16 bytes (um bloco de GC), enquanto as QSTRs permitem que elas sejam empacotadas de forma mais eficiente no pool.

Os pools de QSTR (e os “chunks” subjacentes que armazenam os dados das strings) são alocados sob demanda no heap com um tamanho mínimo.