Интернирование строк в MicroPython

MicroPython использует string interning для экономии как RAM, так и ROM. Это избавляет от необходимости хранить дублирующиеся копии одной и той же строки. В первую очередь это относится к идентификаторам в вашем коде, поскольку нечто вроде имени функции или переменной с большой вероятностью встречается в нескольких местах кода. В MicroPython интернированная строка называется QSTR (uniQue STRing).

Значение QSTR (с типом qstr) является индексом в связном списке пулов QSTR. QSTR хранят свою длину и хеш своего содержимого для быстрого сравнения в процессе дедупликации. Все операции байт-кода, работающие со строками, используют аргумент QSTR.

Генерация QSTR во время компиляции

В коде C MicroPython любые строки, которые должны быть интернированы в итоговой прошивке, записываются как MP_QSTR_Foo. Во время компиляции это вычисляется в значение qstr, указывающее на индекс "Foo" в пуле QSTR.

Это работает благодаря многоэтапному процессу в Makefile. В целом этот процесс состоит из трёх частей:

  1. Найти все токены MP_QSTR_Foo в коде.

  2. Сгенерировать статический пул QSTR, содержащий все строковые данные (включая длины и хеши).

  3. Заменить все MP_QSTR_Foo (с помощью препроцессора) их соответствующим индексом.

Токены MP_QSTR_Foo ищутся в двух источниках:

  1. Все файлы, на которые ссылается $(SRC_QSTR). Это весь код C (т. е. py, extmod, ports/stm32), но не включая сторонний код, такой как lib.

  2. Дополнительные $(QSTR_GLOBAL_DEPENDENCIES) (которые включают mpconfig*.h).

Примечание: frozen_mpy.c (генерируется mpy-tool.py) имеет собственную генерацию QSTR и собственный пул.

Некоторые дополнительные строки, которые не могут быть выражены с помощью синтаксиса MP_QSTR_Foo (например, они содержат не-алфавитно-цифровые символы), явно указываются в qstrdefs.h и qstrdefsport.h через переменную $(QSTR_DEFS).

Обработка происходит в следующих этапах:

  1. qstr.i.last представляет собой результат прогона каждого отдельного входного файла через препроцессор C. Это означает, что любой условно отключённый код будет удалён, а макросы развёрнуты. Это означает, что мы не добавляем в пул строки, которые не будут использованы в итоговой прошивке. Поскольку на этом этапе (благодаря макросу NO_QSTR, добавляемому через QSTR_GEN_CFLAGS) нет определения для MP_QSTR_Foo, оно проходит этот этап без изменений. Этот файл также включает комментарии препроцессора, содержащие информацию о номерах строк. Обратите внимание, что на этом шаге используются только изменившиеся файлы, что означает, что qstr.i.last будет содержать данные только из файлов, изменившихся с момента последней компиляции.

  2. qstr.split — это пустой файл, создаваемый после запуска makeqstrdefs.py split для qstr.i.last. Он используется лишь как зависимость, указывающая, что шаг был выполнен. Этот скрипт выводит по одному файлу на каждый входной файл C, genhdr/qstr/...file.c.qstr, который содержит только найденные QSTR. Каждый QSTR выводится как Q(Foo). Этот шаг необходим для объединения существующих файлов с новыми данными, сгенерированными в результате инкрементального обновления в qstr.i.last.

  3. qstrdefs.collected.h — это результат конкатенации genhdr/qstr/* с помощью makeqstrdefs.py cat. Теперь это полный набор MP_QSTR_Foo, найденных в коде, отформатированный как Q(Foo), по одному на строку, с дубликатами. Этот файл обновляется только в том случае, если набор qstr изменился. Хеш данных QSTR записывается в другой файл (qstrdefs.collected.h.hash), что позволяет отслеживать изменения между сборками.

  4. Сгенерировать перечисление, каждая запись которого сопоставляет MP_QSTR_Foo его соответствующему индексу. Оно конкатенирует qstrdefs.collected.h с qstrdefs*.h, затем преобразует каждую строку из Q(Foo) в "Q(Foo)", чтобы они проходили через препроцессор без изменений. Затем препроцессор используется для обработки условной компиляции в qstrdefs*.h. Затем преобразование отменяется обратно в Q(Foo) и сохраняется как qstrdefs.preprocessed.h.

  5. qstrdefs.generated.h — это результат работы makeqstrdata.py. Для каждого Q(Foo) в qstrdefs.preprocessed.h (плюс несколько дополнительных жёстко заданных) он выводит QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo").

Затем в основной компиляции с qstrdefs.generated.h происходят две вещи:

  1. В qstr.h каждый QDEF становится записью в перечислении, что делает MP_QSTR_Foo доступным для кода и равным индексу этой строки в таблице QSTR.

  2. В qstr.c генерируется собственно таблица данных QSTR в виде элементов mp_qstr_const_pool->qstrs.

Генерация QSTR во время выполнения

Дополнительные пулы QSTR могут создаваться во время выполнения, чтобы в них можно было добавлять строки. Например, код:

foo[x] = 3

Потребуется создать QSTR для значения x, чтобы оно могло использоваться байт-кодом «load attr».

Кроме того, при компиляции кода Python для идентификаторов и литералов необходимо создавать QSTR. Примечание: только литералы короче 10 символов становятся QSTR. Это связано с тем, что обычная строка в куче всегда занимает минимум 16 байт (один блок GC), тогда как QSTR позволяют упаковать их в пул более эффективно.

Пулы QSTR (и лежащие в их основе «чанки», хранящие строковые данные) выделяются в куче по мере необходимости с минимальным размером.