Speed Experiments in Python

Some time ago I wrote a post on calculating a selection of statistics from a list on numbers. I got some criticism from people saying that for some of the statistics I should have used Python built-in functions or functions from the Python Standard Library statistics module.

Doing so, however, would cause each of those functions to iterate over the entire dataset. If you want to calculate a number of different statistics in one go you can increase efficiency considerably with just one iteration.

I started writing a simple experiment to calculate the minimum, maximum, sum, mean and standard deviation of a list of numbers using Python's own functions, calculating them again using a single loop, and then comparing the performance.

I then decided to expand the experiment somewhat, firstly by running the plain Python code with PyPy instead of CPython, and then re-writing the Python as Cython. This article explores these experiments and presents the results.

CPython, PyPy and Cython

Python provides the following built-in functions for use with an iterable of numbers:

  • min
  • max
  • sum

and these functions (among others) in the statistics module

  • mean
  • pstdev (standard deviation of a population)

These are fine if you just need a single statistic from a relatively small data set. However, if you need more than one statistic you can avoid repeated iterations by calculating them during or after a single loop.

Furthermore you can speed up that loop itself using PyPy, or by re-writing the function as Cython.

The standard CPython implementation of Python is an interpreter and therefore inherently slow, whereas PyPy is a just-in-time (JIT) compiler which provides significant performance improvements just by using it instead of CPython with no changes to you code.

At the time of writing (February 2019) PyPy implements Python up to 3.5.3. I won't explore it in detail here but this is its website https://pypy.org/ and it is definitely worth installing and trying out.

If you are willing to do a bit more work in search of increased performance then Cython is really worth getting into. It is a superset of Python to which you can add strong typing, and which is transpiled to C and then compiled into extension modules for use by regular Python.

Perhaps a typical workflow would be to write everything in Python, identify any bottlenecks in the code, and split that code out to Cython.

The improvement in performance depends very much on what the code does and whether you add typing in appropriate places, but it can be startlingly. An ideal use for Cython would be code which iterates and crunches large amounts of numeric data, such as this project.

If you are interested in Cython I recommend this tutorial which will get you up and running in no time Optimizing with Cython Introduction - Cython Tutorial.

The Project

Below is an empty scoreboard listing the various environments and methods. During this project I will implement and time each combination, filling in the scoreboard along the way.

ImplementationFunctionTime(ms)Index
CPythonpython_functions
CPythonsingle_iteration
PyPypython_functions
PyPysingle_iteration
Cythonpython_functions
Cythonsingle_iteration

The project consists of the following files which you can download as a zip, or you can clone/download the Github repository if you prefer.

  • speedexperiments.py
  • functiontimer.py
  • statsfunctions.py
  • statsfunctionscython.pyx (note the .pyx extension)
  • setup.py

Source Code Links

ZIP File
GitHub

speedexperiments.py

import random
import sys
import os

import functiontimer
import statsfunctions
import statsfunctionscython


def main():

    print("--------------------")
    print("| codedrome.com    |")
    print("| SpeedExperiments |")
    print("--------------------\n")

    print("Using {}\n".format(os.path.basename(sys.executable)))

    print("Generating random data...\n")
    random.seed()
    data = [random.randint(1, 100) for i in range(1000000)]

    functiontimer.time_function(statsfunctions.python_functions,
                                data,
                                10)

    functiontimer.time_function(statsfunctions.single_iteration,
                                data,
                                10)

    # functiontimer.time_function(statsfunctionscython.python_functions,
    #                             data,
    #                             10)

    # functiontimer.time_function(statsfunctionscython.single_iteration,
    #                             data,
    #                             10)


main()

At the top of the main function the name of the currently running executable is displayed. In this project it will be some version of CPython or PyPy.

Next a list of a million random numbers is generated. We then call functiontimer.time_function twice with a different function each time, the random data and a count of 10. The two separate functions called here, as well as functiontimer.time_function, will be described later.

Finally there are two further calls, commented out for the time being, which carry out the same tasks as the first two but using Cython functions.

functiontimer.py

import time
import statistics


def time_function(function, arguments, runcount):

    """
    Runs the function with the arguments the
    specified number of times.
    Prints the minimum, maximum and mean
    durations in milliseconds.    
    """

    print("Running " + function.__name__ + "...")

    durations = []

    for r in range(0, runcount):
        start_time = time.time()
        function(arguments)
        end_time = time.time()
        duration_ms = (end_time - start_time) * 1000
        durations.append(duration_ms)

    print("min:  {:6.0f}ms".format(min(durations)))
    print("max:  {:6.0f}ms".format(max(durations)))
    print("mean: {:6.0f}ms".format(statistics.mean(durations)))

The Python Standard Library has a module called timeit which provides a function with the same name used to "time small bits of Python code". It is actually quite basic and doesn't do what I wanted to do here so I resorted to writing my own function.

It takes a function which it calls the specified number of times with the supplied arguments, and then prints out the shortest, longest and average times the individual runs took. The shortest times are the ones we are really interested in for benchmarking as they are the ones slowed down the least by the system doing other stuff at the same time, and they are the ones I shall use for filling in the scoreboard.

statsfunctions.py

import statistics


def python_functions(data):

    """
    Calculate a few statistics from
    the numeric list using Python functions.
    Inefficient due to repeated iteration.
    """

    stats = {}

    stats["len"] = len(data)
    stats["min"] = min(data)
    stats["max"] = max(data)
    stats["sum"] = sum(data)
    stats["mean"] = statistics.mean(data)
    stats["pstdev"] = statistics.pstdev(data)

    return stats


def single_iteration(data):

    """
    Calculate a few statistics from
    the numeric list using single iteration
    for increased efficiency.
    """

    sum_of_squares = 0

    stats = {}

    stats["len"] = len(data)
    stats["min"] = data[0]
    stats["max"] = data[0]
    stats["sum"] = 0

    for n in data:
        stats["min"] = min(stats["min"], n)
        stats["max"] = max(stats["max"], n)
        stats["sum"] += n
        sum_of_squares += n**2

    stats["mean"] = stats["sum"] / stats["len"]

    stats["pstdev"] = ((sum_of_squares / stats["len"]) - (stats["mean"]**2))**0.5

    return stats

The two functions in this file take a list of numeric values and create dictionaries containing a few statistics on this data. The first, python_functions, use Python functions of functions in the statistics module. As I mentioned above each of these (except len) need to iterate the entire data set.

The second function, single_iteration, iterates the data just once as its name suggests. Within the loop we pick up the minimum and maximum values as well as keeping running totals of the sum and sum of squares. The running totals are then used after the loop to calculate the mean and standard deviation.

statsfunctionscython.pyx

import statistics


def python_functions(list data):

    """
    Calculate a few statistics from
    the numeric list using Python functions.
    Inefficient due to repeated iteration.

    This Cython implementation is no more
    efficient than the Python version
    and is only included for demonstration.
    """

    cdef int length = len(data)
    cdef double minval = min(data)
    cdef double maxval = max(data)
    cdef double total = sum(data)
    cdef double mean = statistics.mean(data)
    cdef double std_dev = statistics.pstdev(data)

    stats = {}
    stats["len"] = length
    stats["min"] = minval
    stats["max"] = maxval
    stats["sum"] = total
    stats["mean"] = mean
    stats["pstdev"] = std_dev

    return stats


def single_iteration(list data):

    """
    Calculate a few statistics from
    the numeric list using single iteration
    for increased efficiency.

    Very significant improvement on Python
    version due to typing.
    """

    cdef int length = len(data)
    cdef double minval = data[0]
    cdef double maxval = data[0]
    cdef double total = 0
    cdef double sum_of_squares = 0
    cdef double mean = 0
    cdef double std_dev = 0

    cdef double n
    for n in data:
        minval = min(minval, n)
        maxval = max(maxval, n)
        total += n
        sum_of_squares += n**2

    mean = total / length
    std_dev = ((sum_of_squares / length) - (mean**2))**0.5

    stats = {}
    stats["len"] = length
    stats["min"] = minval
    stats["max"] = maxval
    stats["sum"] = total
    stats["mean"] = mean
    stats["pstdev"] = std_dev

    return stats

The Cython versions of the functions work in the same way as the Python versions but have additional typing information, removing the need for dynamic type checking.

I must stress that the first Cython function, python_functions, still uses the same Python functions as the non-Cython version so although I have added as much typing as possible it doesn't really help. As I stated in the docstring I have only included this function for demonstration and completeness.

The second Cython function, single_iteration, is however a huge improvement on the Python version. It doesn't rely on any Python functions so is free to use typing information to speed things up considerably.

setup.py

from distutils.core import setup
from Cython.Build import cythonize

setup(ext_modules = cythonize('statsfunctionscython.pyx'))

Cython requires the intermediate steps of converting .pyx files to C, and then compiling the C to an extension module. This file contains the code to do this, and can be used with any Cython project just by editing the argument to cythonize. In fact you could expand this file to take the filename as a command line argument to use it with any Cython source file.

Now the coding is finished we need to run it in three ways, starting with the functions in statsfunctions.py with CPython.

Run - CPython

python3.7 speedexperiments.py

After a rather boring wait we'll get something like this:

Program Output - CPython

--------------------
| codedrome.com    |
| SpeedExperiments |
--------------------

Using python3.7

Generating random data...

Running python_functions...
min:    5251ms
max:    5278ms
mean:   5260ms
Running single_iteration...
min:    1481ms
max:    1505ms
mean:   1492ms

Now lets run the statsfunctions.py code again, this time with PyPy.

Run - PyPy

pypy3 speedexperiments.py

A slightly shorter wait gives us:

Program Output - PyPy

---------------------
| codedrome.com     |
| Speed Experiments |
---------------------

Using pypy3

Generating random data...

Running python_functions...
min:    1631ms
max:    1654ms
mean:   1638ms
Running single_iteration...
min:      70ms
max:      75ms
mean:     71ms

Finally we'll run the Cython code. Comment out the first two function calls in main, uncomment the second two, and run these two commands.

Run - Cython

python3.7 setup.py build_ext --inplace
python3.7 speedexperiments.py

Another long wait for the first bit to run, and then a very short wait for the second bit:

Program Output - Cython

---------------------
| codedrome.com     |
| Speed Experiments |
---------------------

Using python3.7

Generating random data...

Running python_functions...
min:    5351ms
max:    5429ms
mean:   5393ms
Running single_iteration...
min:      23ms
max:      27ms
mean:     24ms

If you look in the folder where you have your source code you'll find two new files, statsfunctionscython.c and another with a name like statsfunctionscython.cpython-37m-x86_64-linux-gnu.so, depending on your version of Python, your architecture and your OS. (The C source code is theoretically human-readable...!)

Plugging the minimum times into the scoreboard gives us this.

ImplementationFunctionTime(ms)Index
CPythonpython_functions52511
CPythonsingle_iteration14813.55
PyPypython_functions16313.22
PyPysingle_iteration7075.01
Cythonpython_functions53510.98
Cythonsingle_iteration23228.30

The first row, python_functions on CPython, is used as a baseline with an index of 1. The other indexes show how many times faster (or slower in one case) the other runs are.

You can also carry out further comparisons if you wish, for example 1481 / 70 = 21, so just by using PyPy we speed up the exact same functions by a factor of 21 with this particular combination of code and data size.

The Magic Line of Code

The single_iteration function in statsfunctionscython.pyx includes this humble line of code:

cdef double n

It doesn't look much but it frees up the code from dynamically checking the type of the variable n on each iteration of the loop. With the test data I have used that's a million checks it doesn't have to do.

In the test runs I got a minimum time of 23ms for this function, but commenting out this line increases the minimum to 760ms. That's over 32 times longer! That's why I have dubbed it "The Magic Line of Code".

Thinking of Starting Your Own Blog?

If you are thinking of starting your own blog or looking to migrate to a better host check out BlueHost. Free domain name for 1 year, free SSL certificate and 1-Click WordPress Install.