MicroPython の文字列インターニング

MicroPython は RAM と ROM の両方を節約するために string interning を使用します。これにより同じ文字列の重複コピーを保存する必要がなくなります。主にこれはコード内の識別子に適用されます。関数名や変数名のようなものはコード内の複数の場所に現れる可能性が非常に高いためです。MicroPython ではインターン化された文字列を QSTR (uniQue STRing) と呼びます。

QSTR 値 (型は qstr) は、QSTR プールの連結リストへのインデックスです。QSTR は重複排除処理中の高速比較のために、その長さと内容のハッシュを保存します。文字列を扱うすべてのバイトコード操作は QSTR 引数を使用します。

コンパイル時の QSTR 生成

MicroPython の C コードでは、最終ファームウェアでインターン化すべき文字列はすべて MP_QSTR_Foo として記述されます。コンパイル時に、これは QSTR プール内の "Foo" のインデックスを指す qstr 値に評価されます。

Makefile 内の複数ステップのプロセスによってこれが機能します。要約すると、このプロセスには 3 つの部分があります:

  1. コード内のすべての MP_QSTR_Foo トークンを見つけます。

  2. すべての文字列データ (長さとハッシュを含む) を含む静的 QSTR プールを生成します。

  3. すべての MP_QSTR_Foo を (プリプロセッサ経由で) 対応するインデックスに置き換えます。

MP_QSTR_Foo トークンは 2 つのソースから検索されます:

  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 構文では表現できない追加の文字列 (例: 英数字以外の文字を含むもの) は、$(QSTR_DEFS) 変数を介して qstrdefs.h と qstrdefsport.h で明示的に提供されます。

処理は以下の段階で行われます:

  1. qstr.i.last は、すべての入力ファイルを C プリプロセッサに通して連結したものです。これは、条件付きで無効化されたコードが削除され、マクロが展開されることを意味します。つまり、最終ファームウェアで使用されない文字列をプールに追加しません。この段階では (QSTR_GEN_CFLAGS によって追加される NO_QSTR マクロのおかげで) MP_QSTR_Foo の定義が存在しないため、この段階を影響を受けずに通過します。このファイルには、行番号情報を含むプリプロセッサからのコメントも含まれます。このステップは変更されたファイルのみを使用するため、qstr.i.last には前回のコンパイル以降に変更されたファイルのデータのみが含まれることに注意してください。

  2. qstr.split は、qstr.i.last に対して makeqstrdefs.py split を実行した後に作成される空ファイルです。これはステップが実行されたことを示す依存関係として使用されるだけです。このスクリプトは入力 C ファイルごとに 1 つのファイル genhdr/qstr/...file.c.qstr を出力し、これには一致した QSTR のみが含まれます。各 QSTR は Q(Foo) として出力されます。このステップは、既存のファイルと qstr.i.last のインクリメンタル更新から生成された新しいデータを結合するために必要です。

  3. qstrdefs.collected.h は、makeqstrdefs.py cat を使用して genhdr/qstr/* を連結した出力です。これは、コード内で見つかったすべての MP_QSTR_Foo の完全なセットであり、Q(Foo) として 1 行ずつ、重複ありでフォーマットされています。このファイルは 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 の出力です。qstrdefs.preprocessed.h 内の各 Q(Foo) (およびいくつかの追加のハードコードされたもの) に対して、QDEF(MP_QSTR_Foo, (const byte*)"hash" "Foo") を出力します。

次にメインのコンパイルで、qstrdefs.generated.h に対して 2 つのことが起こります:

  1. qstr.h では、各 QDEF が enum 内のエントリになり、これにより MP_QSTR_Foo がコードで利用可能になり、QSTR テーブル内のその文字列のインデックスと等しくなります。

  2. qstr.c では、実際の QSTR データテーブルが mp_qstr_const_pool->qstrs の要素として生成されます。

実行時の QSTR 生成

実行時に追加の QSTR プールを作成して、そこに文字列を追加できます。例えば、次のコード:

foo[x] = 3

は x の値に対する QSTR を作成する必要があり、それを "load attr" バイトコードで使用できるようにします。

また、Python コードをコンパイルする際、識別子とリテラルには QSTR を作成する必要があります。注意: 10 文字未満のリテラルのみが QSTR になります。これは、ヒープ上の通常の文字列が常に最低 16 バイト (1 つの GC ブロック) を占めるのに対し、QSTR ではそれらをプールにより効率的に詰め込めるためです。

QSTR プール (および文字列データを格納する基盤となる "チャンク") は、最小サイズでヒープ上にオンデマンドで割り当てられます。