Pythonはなぜ遅いのか、をちゃんと言う

「Pythonは遅い」の中には、1演算あたりの手間・メモリの並び方・並列に回らないという別々の3つの話が混ざっています。オブジェクトと評価ループ、NumPyが速い本当の理由、GILが何を守っているのか、そしてPEP 703以降のfree-threadedビルドがどこまで解決するのかを、前提知識ゼロから積み上げます。

「遅い」を一言で片づけない

家具を組み立てる場面を想像してください。設計図どおりに部品を打ち込んでいくのがCやRustです。Pythonはそうではなく、一手ごとに係員へ「この部品は何ですか」「この工具で合っていますか」と確認しながら組み立てます。確認は一回あたりほんの一瞬ですが、一万手あれば一万回の確認が積み上がります。

ここまでは誰でも聞いたことのある比喩です。問題は、この比喩が「Pythonが遅い」と言われる場面の一部しか説明していないことです。現場で遅いと報告される処理を分解すると、たいてい次の三つが混ざっています。

1. 一回の演算あたりの手間が多い — インタプリタの実行方式と、すべての値がオブジェクトであること
2. データの置き方が悪い — メモリ上に散らばっていて、CPUが本気を出せない
3. 並列に回らない — GIL(グローバルインタプリタロック)があるので、CPUを使う処理は複数スレッドに分けても速くならない

原因が違えば効く手も違います。1に効くのはベクトル化やCへの移譲、2に効くのはデータ構造の入れ替え、3に効くのはプロセス分割やfree-threadedビルドです。どれが効いているのか分からないまま「Pythonだから遅い」で止めると、いちばん高くつく手(言語の移植)から手を出すことになります。この記事は、その三つを分けて言えるようになるための地図です。

a + b の一行で何が起きているか

CPython(公式のPython実装)は、ソースコードをまずバイトコードという中間の命令列に変換し、それを評価ループが一命令ずつ解釈して実行します。この流れ自体はコンパイラを1からで扱った前半の工程と同じで、違うのは最後に機械語を吐かず、命令の列をその場で読み上げていく点です。

足し算がどんな命令になるかは標準ライブラリの dis で覗けます。

>>> import dis
>>> dis.dis(lambda a, b: a + b)
  RESUME        0
  LOAD_FAST     0 (a)
  LOAD_FAST     1 (b)
  BINARY_OP     0 (+)
  RETURN_VALUE

四命令。これだけ見ると軽そうです。ところが BINARY_OP の一命令の中身が重い。Pythonではすべての値がヒープ上のオブジェクトで、どの値も先頭に「参照カウント」と「型オブジェクトへのポインタ」を抱えています。整数も例外ではなく、しかもPythonの int は桁数に上限がないので、内部には桁の配列が入っています。1 という値ですら、机の上に置かれた数字ではなく、箱に入って棚に置かれた数字なのです。

そのため a + b は、およそこう進みます。a の型を調べる。その型が持つ加算の関数を関数ポインタ経由で呼ぶ。両方の箱から中身を取り出す(アンボクシング)。足す。結果を入れる新しい箱をヒープに確保する(ボクシング)。使い終わった箱の参照カウントを減らし、ゼロなら解放する。そして次のバイトコードへ分岐する。

本命の足し算はCPUの命令一つです。残りは全部おまけです。

遅さを式で分ける

同じ足し算を $N$ 回繰り返すループを、PythonとCで比べてみます。

記号はそれぞれ、$c_{\text{op}}$ が本命の演算、$c_{\text{dispatch}}$ が「次はどの命令か」を判断して飛ぶ費用、$c_{\text{unbox}}$ が箱から中身を出す費用、$c_{\text{alloc}}$ が結果の箱を作る費用、$c_{\text{rc}}$ が参照カウントの上げ下げです。要するに、Cは本命だけを$N$回、Pythonは本命におまけを足したものを$N$回やっている、と言っているだけです。

この式から、よく誤解される点が二つ読み取れます。まず、比は $1 + (\text{おまけ})/c_{\text{op}}$ なので、本命が軽い演算ほど不利になります。整数の足し算は最悪の部類です。逆に、正規表現のマッチや巨大整数の乗算のように一回が重い処理では比が縮みます — 中身がCで書かれた一回の呼び出しに包まれていて、おまけを払うのが一回で済むからです。「Pythonは何倍遅い」という単一の数字が存在しないのは、この比が処理の中身で決まるからです。

もう一つ。式の右辺に $N$ が共通で掛かっています。Pythonの遅さは定数倍の話であって、$N$ の増え方そのものには手を触れていません。

定数倍と、オーダーの違い

ここが実務でいちばん効く但し書きです。仮にPythonの定数倍を50倍として、Pythonで $O(n \log n)$ のアルゴリズムを書いた場合と、Cで $O(n^2)$ を書いた場合を比べます。

$$50\,n\log_2 n < n^2 \iff n > 50\log_2 n$$

つまり、$n$ が数百を超えたあたりから、遅い言語の良いアルゴリズムが、速い言語の悪いアルゴリズムを追い抜きます。そして実務で扱う$n$は、たいていその閾値の向こう側にあります。

だから最初にやることは言語の乗り換えではなく、オーダーを下げることです。リストに対する in を set に替えるだけで $O(n)$ が $O(1)$ になる、といった修正が、C移植より先に来ます。

評価ループの中で起きている賭け

では、その定数倍はなぜ縮まないのか。中心にあるのは動的型付けです。

コンパイラなら「この足し算は常に64ビット整数どうし」と決め打ちして一命令に潰せます。CPythonにはそれができません。a に何が入るかは実行してみないと分からず、しかも実行の途中で型が変わることさえ許されているからです。だから毎回、型を調べるところからやり直します。