Magnus Lie Hetland [Magnus Lie Hetland] - Python Algorithms: Mastering Basic Algorithms in the Python Language, Second Edition

Make it work, make it right, make it fast.

Kent Beck

This appendix is a tiny peek at some of the options for tweaking the constant factors of your implementations. Although this kind of optimization in many cases wont take the place of proper algorithm designespecially if your problems can grow largemaking your program run ten times as fast can indeed be useful.

Before calling for external help, you should make sure youre using Pythons built-in tools to their full potential. Ive given you some pointers throughout the book, including the proper uses of list versus deque and how bisect and heapq can give you a great performance boost under the right circumstances. As a Python programmer, youre also lucky enough to have easy access to one of the most advanced and efficient (and efficiently implemented) sorting algorithms out there ( list.sort ), as well as a really versatile and fast hash table ( dict ). You might even find that itertools and functools can give your code a performance boost.

Also, when choosing your technology, make sure you optimize only what you must. Optimizations do tend to make either your code or your tool setup more complicated, so make sure its worth it. If your algorithm scales well enough and your code is fast enough, introducing the extension modules in another language such as C might not be worth it. What is enough is, of course, up to you to determine. (For some hints on timing and profiling your code, see .)

Note that the packages and extensions discussed in this appendix are mainly about optimizing single-processor code, either by providing efficiently implemented functionality, by letting you create or wrap extension modules, or by simply speeding up your Python interpreter. Distributing your processing to multiple cores and processors can certainly also be a big help. The multiprocessing module can be a place to start. If you want to explore this approach, you should be able to find a lot of third-party tools for distributed computing as well. For example, you could have a look at the Parallel Processing page in the Python Wiki.

In the following pages, I describe a selection of acceleration tools. There are several efforts in this area, and the landscape is of course a changing one: New projects appear from time to time, and some old ones fade and die. If you think one of these solutions sounds interesting, you should check out its web site and consider the size and activity of its communityas well, of course, as your own needs. For web site URLs, see later in the appendix.

NumPy, SciPy, Sage, and Pandas. NumPy is a package with a long lineage. It is based on older projects such as Numeric and numarray, and at its core it implements a multidimensional array of numbers. In addition to this data structure, NumPy has several efficiently implemented functions and operators that work on the entire array so that when you use them from Python, the number of function calls is minimized, letting you write highly efficient numeric computations without compiling any custom extensions. As a supplement to NumPy, Theano can optimize mathematical expressions on numeric arrays. SciPy and Sage are much more ambitious projects (although with NumPy as one of their building blocks), collecting several tools for scientific, mathematical, and high-performance computing (including some of the ones mentioned later in this appendix). Pandas is more geared toward data analysis, but if its data model fits your problem instances, it is both powerful and fast. A related toolkit is Blaze, which can help if youre working with large amounts of semistructured data.

PyPy, Pyston, Parakeet, Psyco, and Unladen Swallow. One of the least intrusive approaches to speeding up your code is to use a just-in-time (JIT) compiler. In the olden days, you could use Psyco together with your Python installation. After installing Psyco, you would simply import the psyco module and call psyco.full() to get a potentially quite noticeable speedup. Psyco would compile parts of your Python program into machine code while your program was running. Because it could watch what happens to your program at runtime, it could make optimizations that a static compiler could not. For example, a Python list can contain arbitrary values. If, however, Psyco noticed that a given list of yours only ever seems to contain integers, it could assume that this would be the case also in the future and compile that part of the code as if your list were an array of integers. Sadly, like several of the Python acceleration solutions, Psyco is, to quote its web site, unmaintained and dead. Its legacy lives on in PyPy, though.

PyPy is a more ambitious project: a reimplementation of Python in Python. This does not, of course, give a speedup directly, but the idea behind the platform is to put a lot of infrastructure in place for analyzing, optimizing, and translating code. Based on this framework, it is then possible to do JIT compilation (techniques used in Psyco are being ported to PyPy), or even translation to some high-performance language such as C. The core subset of Python used in implementing PyPy is called RPython (for restricted Python), and there are already tools for statically compiling this language into efficient machine code.

Unladen Swallow is also a JIT compiler for Python, in a way. More precisely, its a version of the Python interpreter that uses the so-called Low Level Virtual Machine (LLVM). The goal of the project has been a speedup factor of 5 compared to the standard interpreter. This target has not yet been reached, though, and the activity of the project seems to have stopped.

Pyston is a similar, more recent LLVM-based JIT compiler for Python being developed by Dropbox. At the time of writing, Pyston is still a young project, supporting only a subset of the language, and there is as yet no support for Python 3. However, it already beats the standard Python implementation in many cases and is under active development. Parakeet is also a rather young project, which, to quote the web page, uses type inference, data parallel array operators, and a lot of black magic to make your code run faster.

GPULib, PyStream, PyCUDA, and PyOpenCL. These four packages let you use graphics processing units (GPUs) to accelerate your code. They dont provide the kind of drop-in acceleration that a JIT compiler such as Psyco would, but if you have a powerful GPU, why not use it? Of the projects, PyStream is older, and the efforts of Tech-X Corporation have shifted to the newer GPULib project. It gives you a high-level interface for various forms of numeric computation using GPUs. If you want to use GPUs to speed up your code, you might also want to try PyCUDA or PyOpenCL.

Pyrex, Cython, Numba, and Shedskin. These four projects let you translate Python code into C, C++ or LLVM code. Shedskin compiles plain Python code into C++, while Pyrex and Cython (which is a fork of Pyrex) primarily target C. In Cython (and Pyrex, its predecessor), you can add optional type declarations to your code, stating that a variable is (and will always be) an integer, for example. In Cython, there is also interoperability support for NumPy arrays, letting you write low-level code that accesses the array contents efficiently. I have used this in my own code, achieving speedup factors of up to 300400 for suitable code. The code that is generated by Pyrex and Cython can be compiled directly to an extension module that can be imported into Python. If you want to generate C code from your Python, Cython is a safe bet. If youre just looking for the speedup, particularly for array-oriented and math-heavy code, you should look into Numba, which generates LLVM code at import time. With the premium features available in NumbaPro, theres even GPU support.