Mathieu’s log

The Python and C/C++ duo

Lately, Python and C/C++ are becoming my language combination of choice for my research. It’s a pragmatical choice.

Regarding Python:

- It has interesting packages for scientific computing such as NumPy (fast multi-dimensional arrays and vectorized code), SciPy (reusable scientific packages), Matplotlib (plotting), IPython (Matlab-like interactive environment).
- It has many libraries and many bindings/wrappers for C/C++ libraries, including in my fields of interest such as Machine Learning, Natural Language Processing and Image Processing.
- It has many users, meaning that more people can contribute to your projects.
- It’s a full-fledge language, with powerful features and a large standard library.

Regarding C/C++:

- They are the most commonly used languages to write native extensions for Python. Even though it’s possible to get huge speedups by vectorizing your code with NumPy (avoid for loops like the plague!), you can never get anywhere close to native programs speed.
- They are pretty much the fastest languages out there, although Fortran can be faster.

In a nutshell, I try to use Python and NumPy as much as possible and when necessary, I rewrite selected portions in C or C++.

Wrapping with SWIG

Wrappers/bindings need be created in order to be able to call C/C++ code from Python. Although it’s possible to write such bindings by hand, using the Python C API, it’s quite a tedious task and a lot of it can be automated.

SWIG is a tool that reads a .i interface file and can generate a wrapper automatically. The interface file defines the signature of the functions to wrap, together with hand-made rules to handle cases that SWIG cannot process automatically. SWIG can generate bindings for many languages besides Python.

SWIG can usually manage to generate bindings automatically for functions with simple types. However, when functions require arrays, pointers or structures, hand-made rules usually need be added to the interface file to tell SWIG how to process these types. In that case, SWIG becomes, in my opinion, a complicated tool and needs quite some time to master.

So far I never had to wrap existing third-party libraries and the only code I had to wrap is my own, to speed up selected portions of my Python code. In that case, my approach has been to specifically design my code to be easy to wrap by SWIG. Basically, the trick is to avoid all types that SWIG cannot handle directly and instead use C++ objects as a facade to your data. For example, to represent a handwritten stroke, instead of using a 2-dimensional array of integer coordinates (x, y), I can create a Stroke class, which defines a add_point(int x, int y) method.

C++ side:

void do_something (int **stroke); 
void do_something2 (Stroke *stroke);

Python side:

mydata = [(x1,y1), ..., (xn,yn)]
 
# won't work because need to instruct SWIG
# how to convert a list of int pairs to a int **
do_something(mydata)
 
# OK
stroke = Stroke()
for x,y in mydata:
    stroke.add_point(x, y)
do_something2(stroke)

As can be seen, this approach is far from ideal but at least, the code can be wrapped without adding any hand-made rules to SWIG’s interface file. However, it does require you to design your code specifically to make it easy to wrap for SWIG. The resulting Python code feels objected-oriented but not necessarily as pythonic as it could be.

Wrapping with Cython

Cython (not to be confused with CPython, the default implementation of the Python interpreter) is a tool which allows to compile Python into native Python extensions. It generates a C file which is then compiled to a Python extension with gcc. The compilation is completely transparent to the user thanks to the integration of Cython in distutils (you know, the module used by setup.py).

Compiling Python to native extension in itself won’t provide any speed up compared to purely interpreted code, although it does provide an effective way to do close-source in Python. However, Cython also provides additional features to the Python language such as static types that can give hints to the compiler to optimize the extension (Cython is therefore a new language, similar to Python). Concretely, Cython feels like Python with additional C-like features. The programmer can thus optimize selected portions of code by providing additional hints to the compiler, while still being able to use Python objects in other portions if willing to pay the speed cost.

Moreover, there are mechanisms in Cython to easily call external C/C++ functions. So with Cython, one can write extensions running at native speed either by writing them entirely in Cython, or, in a combination of C/C++ and Cython.

To try Cython, I’ve written a small extension to perform Dynamic Time Warping (see my recent post). Rather than writing my extension entirely in Cython, I’ve opted for the solution of writing it in C and wrapping it in Cython. There were several reasons for that:

- Cython is a language in its own right meaning that you need to learn it. Although Cython does seem easy to learn, I didn’t want to spend too much time for now.
- If I am to write C-style code, I prefer to write it in C directly. Mixing C-like code and Python-like code in the same functions seemed to be confusing me. I found it much easier to reason about my program if I split the C-like code and the Python-like code into two separate files.
- My editor doesn’t have Cython syntax highlighting ;-)

When wrapping C code with Cython, a useful trick is to leave memory allocation of both your input and output data to the Cython side. For example, my dtw C function takes a matrix as input and outputs a new matrix as result. Rather than allocating the output matrix on the C side, I allocate it from the Cython side and pass it as an additional argument to my function. It makes the C code clearer because it can focus on processing the data and you don’t need to care about memory de-allocation since objects are taken care of by the garbage collector just like other objects.

When using Numpy to allocate your arrays and matrices, it’s important to know the internal ndarray memory model: how elements are organized in memory. The Guide to Numpy has all the information you need for that.

This DTW implementation is trivial: it doesn’t support features commonly found in other implementations like window constraints. However, it was a nice way to try out Cython and I got a 100x speed-up compared to the pure Python and Numpy version. The problem of DTW and dynamic programming algorithms in general is that they are difficult to vectorize so writing a native extension makes a lot of sense here.

The source code is available here.

For completeness, finally let me mention ctypes and Weave, which are respectively a way to call C functions in pure Python and a way to inline C in your Python programs.

This entry was posted on Friday, November 27th, 2009 at 9:14 am and is filed under In English, Python. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.