Python 3.12 から Unicode のサイズが小さくなります

Python 3.11 までは、空文字でも64バイトのメモリを使用していました。(64bitプラットフォームの場合)

Unicodeの内部表現のうち一番小さい PyASCIIObject 構造体が48バイトで、その構造体の後ろにASCII文字列が続きます。その文字列はNUL終端されているので、空文字列でも1バイト追加されて49バイトになります。

>>> sys.getsizeof("")
49

さらに小さいメモリブロックのアロケートをしているpymallocがメモリを(アライメントの関係で)16バイト単位で割り当てるので、49バイトのmallocでも64バイトが確保されてしまいます。

Python 3.12 からは、PyASCIIObject構造体から wchar_t* 表現をキャッシュするポインタが消え、40バイトになりました。それでASCIIで7文字までの文字列であれば48バイトに収まるようになりました。

>>> import sys
>>> for i in range(10):
...   print(i, sys.getsizeof("a"*i))
...
0 41
1 42
2 43
3 44
4 45
5 46
6 47
7 48
8 49
9 50

オブジェクトの名前として頻出する7文字以下のASCII文字列のメモリ消費量が、64バイトから48バイトへと、16バイト削減できました。

副作用として、同一の文字列を頻繁にWindowsAPIに渡す場合に、 wchar_t* 表現を毎回生成しないといけないのでオーバーヘッドが発生します。しかし Windows API に渡す文字列はごく一部しかないですし、Unixだとほぼ wchar_t* は出番がないので、ほとんどの場面ではメリットの方が圧倒的に大きいです。

この変更を実現するために、2年前に4000弱のPyPIのパッケージをダウンロードして deprecated な API の利用状況を調査した上でPEPを書いていました。3.11に入れられなかったのは、C APIレベルの非互換性のためにPEPで3.12をターゲットにしていたからです。

peps.python.org

methane.hatenablog.jp

まだ3.11がベータになったばかりですが、来年末の3.12にも期待してください。

Python 3.15からデフォルトのエンコーディングがUTF-8になります

Pythonがファイルを開くときなどに使われるエンコーディングロケールWindowsではANSIコードページ)依存でした。

Unixの世界ではどんどんUTF-8ロケールが一般的になっている一方、WindowsANSIコードページはなかなかUTF-8になりません。 そのために、Unixユーザーが open(filepath) のようにエンコーディングを指定しないままUTF-8を仮定するコードを気軽に書いてしまって、Windowsユーザーがエラーで困るといった問題が発生します。

また、Windowsでもメモ帳(Notepad.exe)やVSCodeはすでにUTF-8をデフォルトのエンコーディングで使用しています。ANSIコードページがUTF-8になるのを待っていたらどんどん周りの環境から置いていかれ、レガシー化してしまいます。

Pythonがデフォルトで利用するエンコーディングWindows上でもUTF-8にするために数年前から活動していたのですが、今回PEP 686がAcceptされ、Python 3.15 (2026年10月リリース予定)からUTF-8 Modeがデフォルトで有効になる予定になりました。(執筆時点ではまだ正式にAcceptはされてませんが、条件付きでAcceptされています)

なお、UTF-8 Mode自体はPython 3.7から利用できます。Windows上でPythonを使っている人は、2026年を待たずにUTF-8 Modeを使ってみて、フィードバックをもらえると嬉しいです。

UTF-8 Mode

UTF-8 Modeを有効にするには、 PYTHONUTF8=1 という環境変数を設定します。 -Xutf8 というコマンドラインオプションも利用できますが、PythonからサブプロセスとしてPythonを起動したときにUTF-8 Modeが引き継がれなくなるので、環境変数を使って設定する方をお勧めします。

UTF-8 Modeが有効になると、今までデフォルトでロケールエンコーディングを使用していたほとんどの場面でUTF-8がデフォルトに切り替わります。実際に影響が出る場面と、UTF-8 Modeでもロケールエンコーディングを使う方法を解説しておきます。

encoding オプション

open()pathlib.Path.read_text(), socket.makefile() など、 TextIOWrapper を利用している多くのAPIencoding オプションを持っていて、UTF-8 Modeが有効になると encoding を指定しなかった時のデフォルトが UTF-8 になります。

明示的にロケールエンコーディングを使用するために encoding="locale" というオプションを Python 3.10 で追加していたのですが、これもUTF-8 ModeではUTF-8になってしまっていました。この問題は Python 3.11 で解決されます。

Windows専用のスクリプトであれば "mbcs" というコーデックが昔からあるので、Python 3.10以前でも encoding="mbcs" のように指定してロケールエンコーディングを利用できます。クロスプラットフォームスクリプトでは使えないので、UTF-8 Modeを使うのは Python 3.11 を待ってからの方が良いでしょう。

Standard I/O

Windowsで標準入出力がコンソールになっているときは、 (PYTHONLEGACYWINDOWSSTDIO という環境変数を設定しない限り)入出力はファイルAPIではなくUTF-16ベースのコンソールAPI (WriteConsoleW() など)を使うので UTF-8 Mode は影響ありません。

問題は標準入出力がファイルやパイプにリダイレクトされている場合です。今まではロケールエンコーディングが使われていましたが、UTF-8 ModeではUTF-8が使われます。

標準入出力がUTF-8になるのはnode.jsやGo、Rustなど、モダンな言語やランタイムの多くと共通した挙動です。なのでできれば MSYS を使うとか、PowerShellであれば [console]::OutputEncoding[console]::InputEncodingUTF-8 に設定するなど、周辺の環境もまとめてUTF-8に統一できればそれが一番いいと思います。

標準入出力をロケールエンコーディングのままにしたい場合は、 PYTHONIOENCODING 環境変数UTF-8 Mode よりも優先されるので、 set PYTHONIOENCODING=mbcs とか set PYTHONIOENCODING=cp932 のように設定できます。

これまでの経緯

2016年 UTF-8 Mode 誕生 (PEP 540)

Docker等で en_US.UTF-8 や C.UTF-8 などの UTF-8 localeを持たないミニマムな環境が使われることが増え、そういった環境でもUTF-8ロケールと同じように振る舞う設定が欲しいということでUTF-8 Modeが生まれました。

私はこのPEPをBDFL-DelegateとしてAcceptしましたが、この時はまだUnix環境のことしか考えていませんでした。

2019~ UTF-8デフォルト化を真剣に考え始める

Windows 10 の 2019 May Update で、Notepad.exeのデフォルトエンコーディングUTF-8に変更されました。

そのニュースがきっかけで、Pythonがテキストファイルを開く時のデフォルトエンコーディングWindowsを含めた全プラットフォームでUTF-8に統一するべきだと考え、本格的に議論や活動を開始しました。

このときにUTF-8 ModeがWindowsUTF-8をデフォルト化するのにも使えると気づき、UTF-8 Modeについての記事を書いたりもしていました。

このときに書いた提案が PEP 597ですが、最終的に PEP 597は大きく2回書き直しになりました。その中には、 PEP 686 と同じく(ただしWindowsでだけ) UTF-8 Mode を デフォルトで有効化する提案もありましたが、オプションで元に戻せるといっても後方互換性を大きく壊す変更に反対する意見が強く、このときには意見をまとめることができませんでした。

特に意見が分かれたのが、 encoding を指定していない open() 等の呼び出し全てを Deprecate して警告を出すべきかどうかです。どちらの意見とも強く主張するコア開発者が居て、僕の英語力とファシリテーション力ではとても議論をまとめることができませんでした。

最終的に、PEP 597を、 encoding を指定していない場合に EncodingWarning という警告を出すオプションを追加するという、両者の間を取った提案に書き直して、2021年にAcceptされ、Python 3.10 に実装されました。

2022年3月 JDK18リリース

2022年3月、JDK18がリリースされました。このJDKからJEP 400 が採用され、JavaUTF-8をデフォルトのテキストエンコーディングにするようになりました。

UTF-8デフォルト化の議論は今年後半まで休むつもりだったのですが、JEP 400に背中を押されて改めて議論を開始し、 PEP 686 を書きました。

JEP 400 では後方互換性のために -Dfile.encoding=COMPAT というオプションも追加されています。同じようにオプションで当面の後方互換性を確保するべきだと思い、しかし新たなオプションを追加したくはないので、すでにon/offをオプションで切り替えられるUTF-8 Modeをデフォルトで有効化する提案にしました。

この提案は基本的には一度あきらめた提案(WindowsUTF-8 Modeをデフォルトで有効にする)に近いものですが、今回はより多くの根拠を提示できました。

  • Javaが同等の変更を先に行った
    • PythonJavaで起こったインパクトを見ながら変更を実施できる
    • しかもJavaEncodingWarning のようなデフォルトエンコーディングを利用している場所を見つけるための機構を提供せずに行った
  • EncodingWarning をたくさん修正してきた結果
    • encoding を省略しているコードはほとんどが encoding="utf-8" に置き換えても問題ない。それで壊れることよりも、圧倒的にバグ修正になる方が多い。
    • ASCIIテキストを読み書きするのに encoding を指定するのは(やはり)大変な労力である。

また、UTF-8 Modeはロケールを無視してUTF-8を使う思想になっていたために、デフォルトで有効化すると今度は逆に本当にロケールエンコーディングを利用したいときに困ります。上で紹介した encoding="locale" の問題もこの一部です。こういった問題を洗い出して、Python 3.11からUTF-8 Modeをより広い人に試してもらえるように修正していきました。

最終的に、変更を実施するバージョンを3.15まで先延ばしする条件でPEP 686はAcceptされました。 デフォルトが変更されるのに2026年まで待たないといけないのは残念ですが、将来デフォルトになることが公式になれば、ユーザーは2026年を待たずともUTF-8 Modeを有効にしやすくなるはずです。 特に学生にPythonでプログラミングを教えている場合は、後方互換性を気にする必要がないので、最初に全員にUTF-8 Modeを有効化してもらうと良いと思います。テキストとバイナリの違いやエンコーディングについて教えなくても、VSCode等のエディタで読み書きするのと同じテキストファイルを open(filename)open(filename, "w") で読み書きできるようになるでしょう。

今回のPEPは、私にとってPython 3.6の Compact Ordered dict と同じくらい重要な Python の改善になりました。Pythonのコア開発者になって本当に良かったと思っています。 最後になりますが、今回の PEP を書く上で大きな力をくれた JEP 400 の作者の @naotoj さん、ありがとうございました。

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 はオプションで無効にできるので、メモリ使用量が重要な場面は試してみてください。

Swisstable Hash に使われているビット演算の魔術

Googleが開発したSwisstableと呼ばれるハッシュテーブル実装がAbseilとして公開されて、Rustの標準のHashMap実装にもその移植であるhashbrownが採用されました。

Swisstable の面白いところは、8または16要素をグループ化して、グループ内の各要素のハッシュ値のうち7bitをそれぞれ1byteに格納した8または16バイトの配列を作り、その配列に対して一気に並列でマッチングを行うことです。

この並列マッチングにはSSE2もしくはビット演算が使われます。この記事ではこの並列マッチング部分について解説します。

SSE2を使う場合

SSE2を使う場合は、グループのサイズは16になります。ハッシュ値を格納する配列のことを control と呼ぶことにすると、 control は char control[16] になります。control の各バイトの状態は次のようになります。

  • 0-127: 要素が入っているとき、そのハッシュ値のうち7bitを示します。
  • 0x80: 空 (EMPTY)
  • 0xFE: 削除済み (DELETED)

まず、要素を検索するときは、その要素のハッシュ値のうち7bit (上位か下位を切り取ることが多い) を char h2 = hash & 0x7f; のように切り出して、control の中で h2 に一致する要素を走査します。C言語擬似コードを書くと次のようになります。

for (uint64_t found = match(control, h2); found; next_pos(&found)) {
    int pos = first_pos(found);
    assert(control[pos] == h2);
    // 要素の配列の pos 番目と検索しているキーを比較する
}

match, first_pos, next_pos の実装を見ていきます。1行ずつコメントを入れたので読んでみてください。

uint64_t match(const char *control, char c) {
    // controlを __m128i に変換する. 16byte alignment に注意
    __m128i v = *(__m128i*)control;
    // c を16回繰り返した __m128i を作る
    __m128i w = _mm_set1_epi8(c);
    // vとwをバイトごとに比較し、一致したバイトを0xffに、しなかったバイトを0x00にする
    __m128i x = _mm_cmpeq_epi8(v, w);
    // 各バイトの符号ビット(最上位bit)を集めてint型にする
    return _mm_movemask_epi8(x);
}

int first_pos(uint64_t x) {
    // 最下位bitから、0のbitが何個あるか(=一番下の1のbitの位置)を返す。
    // 簡単のために gcc のビルトイン命令を使用してる。
    // MSVCなら _BitScanForward64() を使う
    return __builtin_ctzll(x);
}

void next_found(uint64_t *x) {
    // 一番下の1のbitを0に反転させる。
    *x &= (*x - 1);
}

実際に試してみましょう。

#include <stdio.h>
#include <stdint.h>
#include <emmintrin.h>
#include <mmintrin.h>

uint64_t match(const char *control, char c) {
    // controlを __m128i に変換する. 16byte alignment に注意
    __m128i v = *(__m128i*)control;
    // c を16回繰り返した __m128i を作る
    __m128i w = _mm_set1_epi8(c);
    // vとwをバイトごとに比較し、一致したバイトを0xffに、しなかったバイトを0x00にする
    __m128i x = _mm_cmpeq_epi8(v, w);
    // 各バイトの符号ビット(最上位bit)を集めてint型にする
    return _mm_movemask_epi8(x);
}

int first_pos(uint64_t x) {
    // 最下位bitから、0のbitが何個あるか(=一番下の1のbitの位置)を返す。
    // 簡単のために gcc のビルトイン命令を使用してる。
    // MSVCなら _BitScanForward64() を使う
    return __builtin_ctzll(x);
}

void next_pos(uint64_t *x) {
    // 一番下の1のbitを0に反転させる。
    *x &= (*x - 1);
}

int main() {
    char control[16] = {
        0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
        0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17};

    for (uint64_t found = match(control, 0x13); found; next_pos(&found)) {
        printf("found = %lx\n", found);
        int pos = first_pos(found);
        printf("pos = %d\n", pos);
    }

    return 0;
}

出力:

found = 808
pos = 3
found = 800
pos = 11

配列の3番目と13番目に 0x13 が入っていることを見つけられました。

SSE2を使わない場合

今時SSE2が使えないCPU?と思われるかもしれませんが、ARMも広く使われています(NEONへの最適化は今のところうまくいっていないようです)し、今後はRISC-Vも重要になってくるでしょう。 なので、古典的なビット演算の魔術が現代でも重宝されるのです。面白いですね。

SSE2を使わない場合は、 __m128i の代わりに int64_t を使い、グループのサイズも8に減ります。 for 文の部分は同じなので、 match, first_pos, next_pos の実装がどうなるかをみていきましょう。

#include <stdio.h>
#include <stdint.h>

static const uint64_t LSB = 0x0101010101010101ul;
static const uint64_t MSB = 0x8080808080808080ul;

uint64_t match(const char *control, char c) {
    // controlを uint64_t に変換する. alignment に注意
    uint64_t v = *(uint64_t*)control;
    // c を8回繰り返した int64_t を作る
    uint64_t w = LSB * c;
    // vとwをbitごとに比較する。
    // バイト単位でみたとき、一致したら0に、一致しなかったら0以外になる
    uint64_t x = v ^ w;
    // 各バイトが0なら0x80に、それ以外なら0x00にする。
    return (x-LSB) & (~x & MSB);
}

int first_pos(uint64_t x) {
    // 最下位bitから、0のbitが何個あるか(=一番下の1のbitの位置)を返す。
    // 簡単のために gcc のビルトイン命令を使用してる。
    // MSVCなら _BitScanForward64() を使う
    //
    // x = 0x80 の場合、 __builtin_ctzll(x) は 7 になり、7>>3 = 1 になる.
    // x = 0x8000 の場合、 __builtin_ctzll(x) は 15 になり、15>>3 = 1 になる.
    return __builtin_ctzll(x) >> 3;
}

void next_pos(uint64_t *x) {
    // 一番下の1のbitを0に反転させる。
    *x &= (*x - 1);
}


int main() {
    char control[16] = {0x10, 0x11, 0x12, 0x13, 0x14, 0x13, 0x12, 0x11};

    for (uint64_t found = match(control, 0x13); found; next_pos(&found)) {
        printf("found = %lx\n", found);
        int pos = first_pos(found);
        printf("pos = %d\n", pos);
    }

    return 0;
}

match() の最後の、 (x-LSB) & (~x & MSB) が難しいのでもう少し噛み砕きます。 各バイトに注目したとき、 LSB は 0x01 になっているので、 x が 0x00 なら 0xff になり、最上位bitが立ちます。しかし x が 0x81 以上の時も -1 しても最上位bitが立っているので、それだけでは判定できません。 右辺の (~x & MSB) で、MSBは0x80なので、xの最上位bit (0x80) が1のときは 0x00 になり、最上位ビットが0のときは0x80になります。 この左辺と右辺を & することで、各バイトが0のときだけ 0x80 になるのです。

さて、このプログラムを実行してみましょう。

found = 80800080000000
pos = 3
found = 80800000000000
pos = 5
found = 80000000000000
pos = 6

0x13 は 3, 5 番目だけなのに、 6 番目も検出されてしまっています!!!

これは、matchがSIMDでないために起こっています。pos=5,6がmatch()でどう処理されるかを見ていきましょう。

  1. control[6], control[5] は 0x1213 になっています(アドレスが低い方が低位バイトになってるので左右逆転します)
  2. 0x1213 ^ 0x1313 = 0x0100 になります。(一致している0x13の部分がちゃんと00になっている)
  3. 0x0100 - 0x0101 = 0xffff になります。 (0x01 の部分のbitが繰り下がりに消費されてしまっています。)
  4. ~0x0100 & 0x8080 = 0x8080
  5. 0x8080 & 0xffff = 0x8080

このように、bit演算は問題ないのですが、引き算によってバイト単位の処理が壊れてしまっていることがわかります。

この誤検出(false positive)が発生するのは、比較対象と最下位ビット (0x01) だけの違いしかなかくて、かつ隣の下位バイトでfalse positiveまたはtrue positiveが発生して繰り下がりが発生する場合に起こります。 (0x0200 - 0x0101 = 0x00ff; 0x00ff & 0x8080 = 0x0080)

ハッシュテーブルの探索でも1/128の確率でこの誤検出が発生しますが、これは大した問題ではありません。

通常のハッシュテーブルでは、大きさ8あたりハッシュ値の3bitを使いますが、Swisstable (SSEなし)の場合8要素のグループ内の検索に7bitを使っているので、そもそも衝突の頻度は4bit分少ないのです。 false positiveにより、true positiveの隣のバイト限定で1bitの違いが無視されますが、それでも6bit分は有効に照合されているので、古典的なハッシュテーブルよりはずっと「ハッシュ値の一部しか一致しない要素に対する比較」は減っているのです。

なお、EMPTY (0x80) と DELETED (0xFE) は両方とも最上位bitが立っているので、 false positive を起こしません。なので、EMPTYやDELETEDに該当する要素を見に行って、未初期化メモリやdangling pointerを参照することは避けられます。

Bit Twiddling Hacks

Swisstable実装で使われていたビット操作は、参考陸としてこのサイトが紹介されていました。

Bit Twiddling Hacks

x86以外でも速く動作するプログラムを書きたい場合は、どんなハックがあるのか目を通しておくのがいいかもしれません。

Python 3.11 からデフォルトの文字列ハッシュアルゴリズムが SipHash13 になります

Pythonの文字列やバイト列に対するハッシュアルゴリズムは、HashDoS対策としてPython 3.4から SipHash24が使われていました。

その後、ラウンド数を減らしたSipHash13でも十分に安全だとして2015年にRustが、2016年にRubyが、SipHash24からSipHash13への切り替えを行いました。

Python でもSipHash13に切り替えようという提案を2017年に行っていたのですが、実装した人がなかなかプルリクエストを作ってくれず、またPythonは文字列がimmutableでハッシュ値をキャッシュしているためにそこまで大きなインパクトがなかったこともあり、ずっと放置されていました。

Issue 29410: Moving to SipHash-1-3 - Python tracker

しかし、Python の高速化プロジェクト Faster CPython で、セキュリティをある程度犠牲にしても高速なハッシュアルゴリズムを使うことで起動速度を上げられないかという話題が持ち上がり、まずは SipHash13 の切り替えを前に進めることにしました。

Faster hash function · Issue #88 · faster-cpython/ideas · GitHub

ということで、 Rust や Ruby からは数年遅れましたが、Pythonもデフォルトの文字列ハッシュアルゴリズムがSipHash13に切り替わりました。

他のハッシュアルゴリズムを使いたいときは、 configure のオプションの --with-hash-algorithm=[fnv|siphash13|siphash24] で切り替えることができます。

このブログに乗せているコードは引用を除き CC0 1.0 で提供します。