pythonとPyPyの計算時間の違いに関して

Question

計算時間に関する質問になります.
Pop count (2進数表記におけるbitが1であるものの個数) を求める関数popcountと, 同様のことが可能な組み込み関数count('1')の実行時間をそれぞれ出力し, さらにその結果をpythonとPyPyで比較します.

def popcount(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c

検証方法としては, 恣意的に選んだ64bit以下の大きな数Nのpopcountを 30 ** 2 回計算し, 全体の時間を求めるということを行っております.

import time

N = 2 ** 63 + 5 ** 15
s = time.perf_counter()

for _ in range(3000):
    for _ in range(3000):
        a = popcount(N)

t = time.perf_counter()
print(t - s)

s = time.perf_counter()

for _ in range(3000):
    for _ in range(3000):
        a = bin(N).count('1')

t = time.perf_counter()
print(t - s)

これをpython3.9で実行すると

popcount関数→ 6.4915954秒
組み込み関数→ 3.3203775秒

という結果になり, またPyPy3.11で行ったときには

popcount関数→ 0.0214806秒
組み込み関数→ 1.3355724秒

という結果が得られました.

ここでご教授いただきたい質問とは, PyPy において popcount 関数が高速であることは分かったが, pythonでそれを行った場合に組み込み関数より遅くなってしまうのはどうしてか, ということです.

このpopcount関数はそれを求めるのに高速なアルゴリズムとして紹介されていた関数です.
一般に速いということは理解しております.
そうであるのにpythonで動作させると非常に遅くなってしまうのはなぜなのでしょうか.
count('1')の構造や, pythonとpypyの違い等について, 何かご存知の方がいらっしゃれば, この原因を推測していただきたいです.
拙い知識と説明になりますが, 何卒宜しくお願い致します.

Answer 1

提示コードでは値Nを整数として扱っていますが、ご存じの通りPythonの整数桁数は可変です。
そのうえで以下を読んでみます。

Bitwise Operators in Python - Arbitrary-Precision Integers

Such a representation eliminates integer overflow errors and gives the illusion of infinite bit-length, but it requires significantly more memory. Additionally, performing bignum arithmetic is slower than with fixed precision because it can’t run directly in hardware without an intermediate layer of emulation.

goole翻訳

このような表現は、整数のオーバーフローエラーを排除し、無限のビット長の錯覚を与えますが、かなり多くのメモリを必要とします。さらに、bignum演算の実行は、エミュレーションの中間層がないとハードウェアで直接実行できないため、固定精度よりも遅くなります。

すなわちこのエミュレーション動作が想像（期待）よりはるかに遅いのだと思われます。
なおbitarrayを使うと少しはマシになりました。

import time
from bitarray import bitarray

N = 2 ** 63 + 5 ** 15
N = bitarray(bin(N)[2:])

s = time.perf_counter()

for _ in range(3000):
    for _ in range(3000):
        a = N.count(1)

t = time.perf_counter()

print(t - s) # 1.4375530999999988

Comments

[Algeot]

ご回答ありがとうございます.
この文書は存じ上げず, 非常に参考になりました.
私はpythonしか扱うことができず, 他言語と比較できる知識がないのですが,
今回のように64bit以下の値のみを扱うように制限したとしても, pythonではそれ以上の大きさを想定して扱ってしまい, 結果として時間がかかってしまうということになるのでしょうか.

[8524ba23]

そのあたりはCPythonはじめとして各実装次第となるので何とも分かりません。
が、おそらくnumpyなど型をより意識した何らかのモジュールであれば高速で計算できるものがあるかもしれません。

[Algeot]

ご回答ありがとうございます.
参考にさせていただき, もう少し自分で考えることにします.
ありがとうございました.

Answer 2

pypyのpopcountはどこかの式の結果が保管され再利用されているかして、何かが短絡しています。

import time

N = 2 ** 63 + 5 ** 15
s = time.perf_counter()

for _ in range(3000):
    for _ in range(3000):
        N -= 1
        a = popcount(N)

t = time.perf_counter()
print(t - s)

N = 2 ** 63 + 5 ** 15
s = time.perf_counter()

for _ in range(3000):
    for _ in range(3000):
        N -= 1
        a = bin(N).count('1')

t = time.perf_counter()
print(t - s)

として同じ計算をさせないようにして計ってみてください。
pypyで誤差程度にしか違わなくなると思います。
CPythonでは組み込み関数の方が速いと思います。

---

CPythonで組み込み関数の方が速いのは、組み込み関数がCで実装されていて速いから、というだけの話でしょう。

---

(追記)
pypyでN = 2 ** 62 + 5 ** 15 にするとNを変化させても極端に速くなるようです。
2 ** 63 + 5 ** 15は64bit符号付き整数の範囲に収まってないですね。

Comments

[Algeot]

丁寧な回答ありがとうございます.
確かにNを変化させると, むしろ自作のpopcount関数の方が１秒ほど遅くなってしまいました.
結論としましては
1. pypyでは関数の値の保管があるので(特殊なケースにおいて)pythonより早くなる.
2. 自作関数が組み込み関数に比べてとても高速, ということではない(ほとんど性能に優劣はない).
3. 自作関数が少し遅いのは関数呼び出しに時間がかかるから.
ということになるのでしょうか.

[quickquip]

> 1.
pypyに詳しくないので保管されているのが関数の返り値なのかどうかは判断できないです。

> 3.
実装がわからないと簡単には言えないと思います。

[Algeot]

ご回答ありがとうございます.
64bitは63桁が最大なのですね, 存じ上げませんでした.
確かに, 2 ** 62 + 5 ** 15のケースで値を変化させてもpypyでは異様に速いことを確認しました.
自作関数が組み込み関数を上回るためには, 計算式で少しでもよいものを提供すればよいと短絡的に考えておりましたが, 前提としてpythonでは内部演算でCを使えるか使えないかという差があるので, 少しよいというだけでは自作関数の方が遅いのは当然ということなのですね.
大変参考になりました.