Python 高速化選手権

この記事は 筑波NSミライラボ Advent Calendar 2023 の 9 日目の記事です。

はじめに

Pythonの速度に関する批判には目を背けることなく、私たちは真正面から向き合いましょう。
こんにちは、筑波大学 情報学群 情報科学類 1年 の Nameless です。Pythonista の皆さんは、一度はこんな言葉を聞いたことがあるかもしれません。

「 Python は遅い😡」

はい、正しいです。しかし、負けた気がしませんか？確かに、C++ や Rust は速いですよね。そりゃ、コンパイルができて静的型付けや手動によるメモリ管理が使えれば速いだろうし、ワインとぶどうジュースを比べているようなものです。

でもPython は遅いからって他の言語に浮気するのは、ちょっと待ってください。柔軟性だってあるし、書きやすさだって最高ですよね。そんな風に考えたことないですか？

だからこそ、この選手権で Python が速さにおいても負けないことを証明しましょう。C++ や Rust のユーザーに速さだけがすべてじゃないこと見せつけながら、Python の可能性を広げてやりましょう。それでは、Python 高速化選手権、挑戦の幕開けです！

環境

デバイス

• CPU: AMD Ryzen™ 9 7940HS 8コア/16スレッド
• 動作周波数 (標準/最大)：4.0GHz/5.2GHz

システム

Docker 上で Ubuntu 22.04.3 LTS を使用しています。

terminal

root@8b4a616d82d7:~# cat /etc/os-release
PRETTY_NAME="Ubuntu 22.04.3 LTS"
NAME="Ubuntu"
VERSION_ID="22.04"
VERSION="22.04.3 LTS (Jammy Jellyfish)"
VERSION_CODENAME=jammy
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=jammy

Pythonやその他のバージョンについては、後述します。

ベンチマーク選定

速度比較のベンチマークとして、Ackermann 関数を使用します。

Ackermann 関数

A(m, n) = 
\begin{cases} 
n+1 & \text{if } m = 0 \\
A(m-1, 1) & \text{if } n = 0 \\
A(m-1, A(m, n-1)) & \text{otherwise}
\end{cases}

この関数は与える数が大きくなると爆発的に計算量が大きくなるという特徴があるため、プログラム言語の性能評価に使われることがあります (wikipedia) 。今回の選手権では A(3, 10) を計算し、その処理時間で勝負します。コンパイルに要した時間などは含めない事とします。
ちなみにこの関数はwhileや再帰を使わずfor文のみで計算することはできないと証明されているらしいです。

1. CPython

Python 3.8.13

エントリー No.1 は、言わずと知れた生粋の Python です。単に Python と言った場合、大抵はこの CPython を指します。しかしここでは区別のため、CPython と呼ぶことにします。CPython での Ackermann 関数の実装は以下です。

ack.py

import time
import sys

sys.setrecursionlimit(10**7)


def ack(m, n):
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))


start = time.time()

ans = ack(3, 10)

elapsed_time = time.time() - start

print(f'answer: {ans}')
print(f'time: {elapsed_time}')

CPythonでは再帰回数の上限 (デフォルトでは 1000 回) が設定されているため、上限を10^7に引き上げています。
実行結果は以下のようになりました。

terminal

root@8b4a616d82d7:/home/python# python3.8 ack.py
answer: 8189
time: 8.400058031082153

約 8.4 秒もかかりました。

このコードがなぜ遅いのか

以下の理由が考えられます。

• Pythonは動的型付け言語なので、変数の型は実行時に解決される
• いちいち + が使われるたびに演算子のオーバーロードのチェックが走る ( __add__ など)

かなり Python の悪いところですよね。

とりあえずここからは、この記録 (8.4 秒) を目安に見ていきます。

2. PyPy

Python 3.8.13 (7.3.9+dfsg-1, Apr 01 2022, 21:41:47)
[PyPy 7.3.9 with GCC 11.2.0]

エントリー No.2 は PyPy です。Python の高速化といったら真っ先に浮かぶのが PyPy でしょう。特徴として、以下のような点が挙げられます。

• JIT コンパイルに対応している
• CPython との互換性に重点が置かれており、ほとんどの場合は CPython のコードを変えることなく実行できる
• 再帰が遅いと言われている

PyPy の再帰は遅く、場合によってはCPythonより遅くなる場合があります。今回はまさにその再帰なのですが、どうなるでしょうか。コードは CPython のものを再利用します (とても便利！) 。

terminal

root@8b4a616d82d7:/home/python# pypy3 ack.py
answer: 8189
time: 2.082540273666382

結果は約 2.1 秒でした。4 倍ほど高速化できました。(再帰じゃなければもっと速いんですが...)

3. Cython

Cython version 3.0.6

エントリー No.3 は、 Cython です。こちらも有名なやつです。Cython は C 言語と CPython の中間みたいなやつです。特徴として、以下のようなものがあります。

• CPython -> C のトランスパイラを含む
• CPython とは別に Cython の文法がある
• 拡張子が .pyx
• Cython のコードと CPython のコードを混ぜて書ける
• 静的型付けを使える

つまり、C のコードを CPython っぽく書けるってことです。CPython から C で作ったライブラリを呼び出せる (かなり語弊がある) のですが、Cython はその CPython のコードの一部を C に簡単に置き換えられるようにしたものです。実際のコードは、以下のようになります。

ack_cython.pyx

def ack(int m, int n):
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))

ここで注意したいのは、Cython コードは一度コンパイルされる必要があるということです。以下のコードによってコンパイルします。一度 hogehoge.c を経由したのち、hogehoge.hugahuga.so が生成されます。これが CPython 用のライブラリになります。

setup.py

from setuptools import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize("ack_cython.pyx")
)

terminal

root@8b4a616d82d7:/home/python# python3.8 setup.py build_ext --inplace
running build_ext
copying build/lib.linux-x86_64-3.8/ack_cython.cpython-38-x86_64-linux-gnu.so ->

ここで生成された高速な ack_cython を、CPythonから呼び出します。

ack_cython.py

from ack_cython import ack as ack

import time

start = time.time()

ans = ack(3, 10)
elapsed_time = time.time() - start

print(f'ans: {ans}')
print(f'time: {elapsed_time}')

結果は以下のようになりました。

terminal

root@8b4a616d82d7:/home/python# python3.8 ack_cython.py
ans: 8189
time: 0.9635007381439209

結果は約 0.96 秒でした。CPythonから約 8.7 倍高速化できました。PyPy よりもかなり高速です。

さらに粘ってみる

Cython には通常の def とは別に cdef という、関数ごと C の関数として定義できるものがあります。cdef では、制約がより厳しくなる代わりに非常に高速な動作を実現できます。そこで、コードを以下のように書き換えます。

ack_cython_2.pyx

cdef ack_(int m, int n):
    if m == 0:
        return n + 1
    elif n == 0:
        return ack_(m - 1, 1)
    else:
        return ack_(m - 1, ack_(m, n - 1))


def ack(int m, int n):
    return ack_(m, n)

再帰のはじめの関数呼び出しのみ def にし、あとは cdef で再帰するようにしてみました。あとは同じようにコンパイルし、実行してみます。

terminal

root@8b4a616d82d7:/home/python# python3.8 ack_cython_2.py
ans: 8189
time: 0.3733248710632324

結果は約 0.37 秒で、コードの変更前から 2.6 倍、CPython から約 23 倍高速になりました。この変更はかなり効果的でした。

4. Numba

0.58.1

エントリー No.4 は Numba です。これも有名なやつです。特徴は以下のようなものがあります。

• JIT コンパイルに対応している
• @jit デコレータを書くだけで高速化できる
• nopython モードと object モードがある
  • object モードでは Python C API を使用するが、nopython モードは使用しないので高速

今回は、nopythonモードに強制するために @jit ではなく @njit を利用しました。

ack_numba.py

import time
from numba import njit


@njit()
def ack(m, n):
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))


start = time.time()

ans = ack(3, 10)

elapsed_time = time.time() - start

print(f'answer: {ans}')
print(f'time: {elapsed_time}')

Numbaでは CPython のような再帰回数の上限変更をせずに動きました。

terminal

root@8b4a616d82d7:/home/python# python3.8 ack_numba.py
answer: 8189
time: 0.42870473861694336

結果は約 0.43 秒で、CPythonより 約 20 倍高速でした。@jit と書くだけなのに、ほとんど Cython と変わらない速度です。素晴らしい。

さらに粘ってみる

Numba は必要になったときに必要なものをひとまとまり (例えば一つの関数など) でコンパイルします。ということは、時間計測の前に一度 ack()を実行しておけば事前にコンパイルすることができるため、先ほどの記録からコンパイルにかかった時間の分だけ引くことができます (そういうレギュレーションです) 。

ack_numba_2.py

import time
from numba import njit


@njit()
def ack(m, n):
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))

ack(0, 0)  # ここで一度実行しておく

start = time.time()

ans = ack(3, 10)

elapsed_time = time.time() - start

print(f'answer: {ans}')
print(f'time: {elapsed_time}')

かなり無理やりなんですが、記録を更新することができました。

root@8b4a616d82d7:/home/python# python3.8 ack_numba_2.py
answer: 8189
time: 0.154587984085083

結果は約 0.15 秒でした。CPython の約 54 倍高速で、Cython より 約 2.4 倍高速です。
(ちなみに Numba は AOT コンパイル (事前コンパイル) にも対応しているそうです。 )

5. Codon

0.16.3

エントリー No.5 は、Codon です。Codon は、今年の初めに発表されたばかりの新しいコンパイラです。Codon には、以下の特徴があります。

• ネイティブな機械語にコンパイルする
• 静的型付けである
• プログラムの実行前に型チェックをする
• Pythonが実行時にデータ型を処理する際に発生する全てのオーバーヘッドが回避される(らしい)

これは期待大です。早速試します。

実装は以下です。Codon では、元々の Python にもある型ヒントを使って型を指定する必要があります。

ack_codon.py

import time


def ack(m: int, n: int) -> int:
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))


start = time.time()

ans = ack(3, 10)

elapsed_time = time.time() - start

print(f'answer: {ans}')
print(f'time: {elapsed_time}')

-release オプションを付けることで最適化してコンパイルされます。

terminal

root@8b4a616d82d7:/home/python# codon run -release ack_codon.py
answer: 8189
time: 0.0280712

とんでもない速さです。結果は約 0.028 秒で、CPythonの約 300 倍高速で、Cython と比べても約 13 倍高速です。

6. Nim

Nim Compiler Version 2.0.0 [Linux: amd64]

エントリーNo.6 は Nim です。とうとう Python ですらなくなりました。Nim は Python ライクな文法なのに速度は C/C++ に匹敵すると言われている言語です。Python と文法が似ているため、Pythonista にとっては学習コストが低いと言えるでしょう。特徴として、以下のようなものがあります。

• 静的型付け
• コンパイル型言語
• 高性能なガベージコレクション
• メモリ安全
• 可読性が高い
• 色々な言語と連携ができる ( Python プログラムを Nim で利用する、C プログラムを Nim で利用する等々)
• C にコンパイルできる
• 効率的で、表現豊かで、エレガントである ( Nim の謳い文句です (参考) )

Nim での実装は、以下のようになります。

ack.nim

import times, os


proc ack(m, n: int): int =
  if m == 0:
    result = n + 1
  elif n == 0:
    result = ack(m - 1, 1)
  else:
    result = ack(m - 1, ack(m, n - 1))


let start = cpuTime()

let ans = ack(3, 10)

let elapsed_time = cpuTime() - start

echo "answer:", ans
echo "time:", elapsed_time

結構 Python ライクだと思います。実行結果は以下のようになりました。
-d:nimCallDepthLimit=32767 は再帰回数の上限を変更するもので、int16 でなければならないため最大値の 32767 を指定しています。-d:release は最適化オプションです。

terminal

root@8b4a616d82d7:/home/nim# nim c -d:nimCallDepthLimit=32767 -d:release  -r ack.nim
Hint: used config file '/root/.choosenim/toolchains/nim-2.0.0/config/nim.cfg' [Conf]
Hint: used config file '/root/.choosenim/toolchains/nim-2.0.0/config/config.nims' [Conf]
Hint: mm: orc; threads: on; opt: speed; options: -d:release
10086 lines; 0.015s; 10.492MiB peakmem; proj: /home/nim/ack.nim; out: /home/nim/ack [SuccessX]
Hint: /home/nim/ack [Exec]
answer:8189
time:0.0359406

結果は約 0.036 秒で、CPython の約 230 倍高速でした。Codon の記録には届きませんでしたが、それでも十分すぎる速さです。

7. Mojo🔥

mojo 0.5.0 (6e50a738)

エントリー No.7 は、Mojo🔥 (以降 Mojo) です。Mojo は今年5月に発表された、新しい言語です。"Python++" とも呼ばれることのあるこの言語は Python の拡張として開発されており、Python と Mojo は C と C++ の関係に似ています。Python.import_module を使って直接 Python 用のライブラリが使用できたりします。

• Python ライクな構文
• 動的型付けと静的型付けに対応
• コンパイル型言語
• 拡張子が .🔥 ( .mojo でもよい )
• Python の 35000 倍速い ( Mojo の謳い文句です )

拡張子が .🔥 なのは、かなり遊んでる感じがあって私は好きです(笑)
Python の 35000 倍速いというのは、Mojo の謳い文句です。実際はかなり Mojo に有利な状況での結果らしいのですが、それにしても 35000 倍というのはとんでもない数字です。

Mojo での実装は以下のようになります。

ack.mojo

from time import now


fn ack(owned m: Int, owned n: Int) -> Int:
    if m == 0:
        return n + 1
    elif n == 0:
        return ack(m - 1, 1)
    else:
        return ack(m - 1, ack(m, n - 1))


fn main():
    let start = now()

    let ans = ack(3, 10)

    let elapsed_time = now() - start

    print('answer: ', ans)
    print('time: ', elapsed_time/1000000000)

文法に関しては、個人的には Nim に比べてより Python っぽく感じます。

ちょっと余談

現時点 (2023/12/1) で Qiita が mojo のシンタックスハイライトに対応してないので、Python として表示させています。こう見るとやっぱり、 Mojo ってほとんど Python の文法だなぁって感じます。

また、now() の返り値の単位がナノ秒なので出力の単位を秒に直すために 10^9 で割っています。
結果は以下のようになりました。

termial

root@8b4a616d82d7:/home/mojo# mojo ack.mojo
answer:  8189
time:  0.028863577000000001

結果は約 0.029 秒でした。CPython の 191 倍高速で、Codon の記録とほとんどタイです。Nim よりも速い結果となりました。

8. C++

gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04)

エントリーNo.8 、最後は C++ です。もはや Python と関係なくなりましたが、あれだけ高速、高速と言われるんならここで実力を見せてもらいましょう。

実装は以下のようになります。

ack.cpp

#include <iostream>
#include <time.h>

int ack(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ack(m - 1, 1);
    } else {
        return ack(m - 1, ack(m, n - 1));
    }
}

int main() {
    clock_t start = clock();

    int ans = ack(3, 10);

    clock_t end = clock();

    std::cout << "answer: " << ans << std::endl;
    std::cout << "time: " << (double)(end - start) / CLOCKS_PER_SEC << std::endl;

    return 0;
}

さっそく実行してみます。さて、Python は C++ に勝てるんでしょうか...！？

terminal

root@8b4a616d82d7:/home/cpp# g++ -o ack ack.cpp
root@8b4a616d82d7:/home/cpp# ./ack
answer: 8189
time: 0.138279

！？！？！？
記録は 約 0.14 秒でした。CPython の約 61 倍高速ですが、C++ より Mojo の方が約 4.8 倍高速です。まじですか？ C++ 意外と遅くてびっくり...私の実装が悪いのかな？

結果発表

全体の結果です。

名前	処理時間 (s)	速度 (CPython 比)	順位
Cpython	8.40	1.00	8
PyPy	2.08	4.03	7
Cython	0.373	22.5	6
Numba	0.155	54.3	5
Codon	0.0281	299	1
Nim	0.0359	234	3
Mojo🔥	0.0289	291	2
C++	0.138	60.7	4

まさかの結果です。 C++ が 4位になりました。

🥇🎉✨勝利✨🎊🏆

皆さん、Python ( 広義 ) は C++ に勝ちましたよ！！！！

まとめ

Python は遅い、それはもう時代遅れかもしれません。適切なコンパイラを選べば十分な速度を得られますし、Python でなくても特に Nim や Mojo なんかは Python ライクで手軽に高速な処理ができます。AtCoder (競技プログラミングのサイト) でも言語アップデートにより Nim が対応しましたし、C++ の独壇場とは言えなくなってきましたね。今後の言語のトレンドがどうなるのか楽しみです。

おまけ

ChatGPT (GPT-3.5) は Python と C++ で書かれているみたいですね。ちなみにこの記事の冒頭は ChatGPT に書いてもらったものです。Python 最高！

※追記

C++ に負けました()
私は C++ エアプなので知らなかったんですが、 C++er の友人に記事を見せたところ「最適化オプション -O3 が抜けている」とのことでした。
試してみます。

terminal

root@8b4a616d82d7:/home/cpp# g++ -o ack ack.cpp -O3
root@8b4a616d82d7:/home/cpp# ./ack
answer: 8189
time: 0.015174

結果は驚異の約 0.015 秒で、CPython の約 550 倍高速です。

もう一度結果を再集計します。

名前	処理時間 (s)	速度 (CPython 比)	順位
Cpython	8.40	1.00	8
PyPy	2.08	4.03	7
Cython	0.373	22.5	6
Numba	0.155	54.3	5
Codon	0.0281	299	2
Nim	0.0359	234	4
Mojo🔥	0.0289	291	3
C++	0.0152	554	1

やっぱり C++ には勝てないんですね(笑) いいいいイキってすみません...