PyPy’s performances impress me

PyPy has been a project that I’ve heard about for a few years; a new implementation of the Python language. Because it was a young project and CPython worked for me, I never bothered to look at PyPy very closely. A couple weeks ago, I read a message that claimed that the performance of PyPy for CPU-bounded tasks was impressive compared to CPython’s.

Last week in my algorithms class, we learned about greedy algorithm. The first one we looked at was a program that made change. You give it an amount and a set of coins and it returns the smallest number of coins for amount. This is something we do every day without thinking about it. For fun, I wrote an implementation of the algorithm in Python:

from collections import defaultdict

def make_change1(amount, coins):
    total = 0
    solution = defaultdict(lambda: 0)
    current = 0

    while total != amount and current < len(coins):
        if total + coins[current] > amount:
            current += 1
        else:
            total += coins[current]
            solution[coins[current]] += 1

    return solution

Doing the change operation by successive subtraction is not terribly efficient, so I wrote another version that uses integer division instead:

def make_change2(amount, coins):
    solution = {}
    for coin in coins:
        count = amount / coin
        solution[coin] = count
        amount -= coin*count
    return solution

And then I created a small script to test them with a lot of amounts, using Canadian coins:

import sys

if sys.argv[1] == "1":
    make_change = make_change1
    n = 100000
else:
    make_change = make_change2
    n = 10000000

for i in xrange(n):
    make_change(i, [200, 100, 25, 10, 5, 1])

Here are the times of running this script on my Linux laptop:

$ python2 --version
Python 2.7.2

$ time python2 make_change.py 1
real    0m16.236s
user    0m16.236s
sys     0m0.000s

$ time python2 make_change.py 2
real    0m28.638s
user    0m28.491s
sys     0m0.057s

And now with PyPy:

$ pypy --version
Python 2.7.1 (?, Sep 04 2011, 13:10:48)
[PyPy 1.6.0 with GCC 4.6.1]

$ time pypy make_change.py 1
real    0m2.185s
user    0m2.157s
sys     0m0.023s

$ time pypy make_change.py 2
real    0m8.799s
user    0m8.769s
sys     0m0.023s

Clearly this is just one silly, unscientific micro-benchmark, but I plan on trying to use PyPy more in the future to see if it generally performs better than CPython.