Interning de strings no MicroPython

O MicroPython utiliza string interning para economizar RAM e ROM. Isto evita ter de armazenar cópias duplicadas da mesma string. Principalmente, isto aplica-se a identificadores no seu código, uma vez que algo como o nome de uma função ou variável é muito provável que apareça em múltiplos locais no código. No MicroPython, uma string interned é chamada de QSTR (uniQue STRing).

Um valor QSTR (do tipo qstr) é um índice numa lista ligada de pools de QSTR. Os QSTRs armazenam o seu comprimento e um hash do seu conteúdo para comparação rápida durante o processo de desduplicaçã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 devem ser internadas no firmware final são escritas como MP_QSTR_Foo. Em tempo de compilação, isto irá avaliar para um valor qstr que aponta para o índice de "Foo" no pool de QSTR.

Um processo de múltiplos passos no Makefile faz isto funcionar. Em resumo, este processo tem três partes:

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

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

  3. Substituir todos os MP_QSTR_Foo (via o pré-processador) pelos seus índices correspondentes.

Os tokens MP_QSTR_Foo são pesquisados em duas fontes:

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

  2. $(QSTR_GLOBAL_DEPENDENCIES) adicionais (que inclui mpconfig*.h).

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

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

O processamento ocorre nas seguintes fases:

  1. qstr.i.last é a concatenação de passar cada ficheiro de entrada pelo pré-processador C. Isto significa que qualquer código desativado condicionalmente será removido e as macros expandidas. Isto significa que não adicionamos strings ao pool que não serão usadas no firmware final. Porque nesta fase (graças à macro NO_QSTR adicionada por QSTR_GEN_CFLAGS) não há definição para MP_QSTR_Foo, ela passa por esta fase sem alterações. Este ficheiro também inclui comentários do pré-processador com informação de número de linha. Note que este passo usa apenas ficheiros que foram alterados, o que significa que qstr.i.last conterá apenas dados de ficheiros que foram alterados desde a última compilação.

  2. qstr.split é um ficheiro vazio criado após executar makeqstrdefs.py split em qstr.i.last. É usado apenas como dependência para indicar que o passo foi executado. Este script produz um ficheiro por ficheiro C de entrada, genhdr/qstr/...file.c.qstr, que contém apenas os QSTRs correspondentes. Cada QSTR é impresso como Q(Foo). Este passo é necessário para combinar os ficheiros 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. Este é agora o conjunto completo de MP_QSTR_Foo encontrados no código, agora formatados como Q(Foo), um por linha, com duplicados. Este ficheiro é atualizado apenas se o conjunto de qstrs tiver mudado. Um hash dos dados QSTR é escrito noutro ficheiro (qstrdefs.collected.h.hash) que permite rastrear alterações entre compilações.

  4. Gera uma enumeração, em que cada entrada mapeia um MP_QSTR_Foo para o seu índice correspondente. Concatena qstrdefs.collected.h com qstrdefs*.h, depois transforma cada linha de Q(Foo) para "Q(Foo)" para que passem pelo pré-processador sem alterações. Em seguida, o pré-processador é utilizado para lidar com qualquer compilação condicional em qstrdefs*.h. Depois a transformação é desfeita para Q(Foo) e guardada como qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h é a saída de makeqstrdata.py. Para cada Q(Foo) em qstrdefs.preprocessed.h (mais alguns adicionais programados fixamente), produz QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

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

  1. Em qstr.h, cada QDEF torna-se uma entrada numa enumeração, o que torna MP_QSTR_Foo disponível para o código e igual ao índice dessa string na tabela QSTR.

  2. Em qstr.c, a tabela de dados QSTR real é 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

Necessitará de criar um QSTR para o valor de x para que possa ser utilizado pelo bytecode «load attr».

Além disso, ao compilar código Python, identificadores e literais precisam de ter QSTRs criados. Nota: apenas literais com menos de 10 caracteres se tornam QSTRs. Isto deve-se ao facto de uma string regular no heap ocupar sempre um mínimo de 16 bytes (um bloco GC), enquanto os QSTRs permitem que sejam empacotadas de forma mais eficiente no pool.

Os pools de QSTR (e os «chunks» subjacentes que armazenam os dados de string) são alocados por demanda no heap com um tamanho mínimo.