Pypy vs cpython performance report

bench.py

import sys
from math import gcd


def mininum_number_of_item_needed_to_reach_gcd(xs: list[int]) -> int:
    g = gcd(*xs)
    cache: dict[tuple[int, int], int] = {}

    def rec(i: int, x: int) -> int:
        if x == g:
            return 0
        if len(xs) == i:
            return len(xs)
        key = (i, x)
        value = cache.get(key)
        if value is not None:
            return value
        y = xs[i] if x == 0 else gcd(x, xs[i])
        r = min(rec(i + 1, x), rec(i + 1, y) + 1)
        cache[key] = r
        return r

    return rec(0, 0)


if __name__ == "__main__":
    n = int(sys.argv[1])
    sys.setrecursionlimit(10000)
    xs = list(range(2, n))
    assert mininum_number_of_item_needed_to_reach_gcd(xs) == 2

bench2.py

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


def gcd_many(*args: int) -> int:
    result, *tail = args
    for x in tail:
        result = gcd(result, x)
    return result


def mininum_number_of_item_needed_to_reach_gcd(xs: list[int]) -> int:
    n = len(xs)
    g = gcd_many(*xs)
    n_bit_length = n.bit_length()
    cache_length = (max(xs) + 1) << n_bit_length
    cache = [-1] * cache_length

    def rec(i: int, x: int) -> int:
        if x == g:
            return 0
        if len(xs) == i:
            return n
        key = (x << n_bit_length) | i
        value = cache[key]
        if value >= 0:
            return value
        y = xs[i] if x == 0 else gcd(x, xs[i])
        r = min(rec(i + 1, x), rec(i + 1, y) + 1)
        cache[key] = r
        return r

    return rec(0, 0)


if __name__ == "__main__":
    import sys

    n = int(sys.argv[1])
    sys.setrecursionlimit(10000)
    xs = list(range(2, n))
    assert mininum_number_of_item_needed_to_reach_gcd(xs) == 2

plot.py

import time
from subprocess import run
import matplotlib.pyplot as plt

ns = range(1000, 10000, 500)
cpython_results = []
pypy_results = []

cpython = "python3"
pypy = "pypy3"
bench_script = "bench.py"

for n in ns:
    print(f"Running cpython for n = {n}")
    start = time.time()
    run([cpython, bench_script, str(n)], check=True)
    cpython_results.append(time.time() - start)
    print(f"-> CPython time: {cpython_results[-1]:.1f} seconds")

    print(f"Running pypy for n = {n}")
    start = time.time()
    run([pypy, bench_script, str(n)], check=True)
    pypy_results.append(time.time() - start)
    print(f"-> PyPy time: {pypy_results[-1]:.1f} seconds")

plt.plot(ns, cpython_results, label="CPython")
plt.plot(ns, pypy_results, label="PyPy")
plt.xlabel("n")
plt.ylabel("Time (seconds)")
plt.title("Performance Comparison: CPython vs PyPy")
plt.legend()
plt.grid(True)
plt.show()