Python 3.11のdictのメモリ消費削減

Pythonのdictのサイズをよりコンパクトにする改善をしました。今日リリースされたPython 3.11.0a6に含まれています。

bpo-46845: Reduce dict size when all keys are Unicode. by methane · Pull Request #31564 · python/cpython · GitHub

Pythonのdictで一番メモリを使っているのはエントリーの配列です。エントリーは次のような構造体です。

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;

このエントリー配列はハッシュテーブルのサイズの2/3だけ確保されています。ハッシュテーブルが最小の場合は8なので、エントリー配列のサイズは5になり、各エントリーが24バイトとすると120バイト必要になります。

ところで、Pythonでdictのキーに使われる型のダントツナンバーワンはstr型です。そしてstr型はハッシュ値のキャッシュを持っています。なのでdictのエントリーに格納されているハッシュ値と二重に保存されていることになります。そこで、全てのキーがstr型だった場合には、エントリーにハッシュ値を格納しないようにしてみました。

typedef struct {
    PyObject *me_key;   /* The key must be Unicode and have hash. */
    PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictUnicodeEntry;

これで、エントリーのサイズが24バイトから16バイトに削減できました。 {"foo":1} のような小さいdictの場合、メモリ使用量が232バイトから184バイトまで40バイト削減になります。

文字列キーを検索する場合、まずオブジェクトが同一かどうかを比較したあと、異なる場合はハッシュ値を比較し、ハッシュ値が一致した場合に文字列の長さと内容を比較します。この変更により、衝突が発生した時にハッシュ値を見るための間接参照が1つ増えてしまうので、若干のパフォーマンスの低下が懸念されます。しかし、Python 3.10, 3.11 と続いているPython高速化プロジェクトにより名前空間アクセス時にdictの探索を実際に実行する頻度がかなり下がりました。衝突時の間接参照が1つ増えるオーバーヘッドよりも、メモリ効率とキャッシュ効率が改善する効果の方が大きいと判断してこの変更に踏み切りました。

Python Insiderのリリースノートによると、Python 3.11は3.10に比べて幾何平均で19%の高速化がされています。楽しみにしてください。

メモリ使用量については、 PEP 657 の影響で増える分で、今回のdictによる改善は相殺されてしまうと思います。 PEP 657 はオプションで無効にできるので、メモリ使用量が重要な場面は試してみてください。