Making Python Fast
==================

Python is an expressive language that is well-suited for many of the
problems we typically solve. However, sometimes Python is just `too
slow`_. This page discusses some ways to speed up your Python code.

*Note: Using the correct data structures and algorithms is far more
important than what language you use! Moving from an* :math:`O(n^2)`
*implementation to a* :math:`O(n)` *implementation is a much larger
speedup than you can get by switching languages. Check your algorithms
and data structures first.*

.. _too slow: https://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=python3&lang2=gpp

The following sections are roughly ordered by ease-of-use, starting
with faster libraries and ending with foreign language bindings.


Faster libraries: Numpy
-----------------------

The easiest way to speed up your code is to properly utilize the
``numpy`` library. ``numpy`` offers high-dimensional arrays and
matrices that are *fast*. The library implements its core operations
and data structures in C or Fortran, avoiding the overhead of Python.

As an example, let's compute matrix powers. Specifically, we compute
:math:`A^{16}` where :math:`A` is a :math:`100 \times 100` matrix. Our
plain Python solution takes 11.77 seconds to run, while using Numpy to
perform the multiplications and generate the matrices takes 0.0097
seconds to run. Additionally, if we use the Numpy function ``power``
instead, we cut the runtime to 0.00065 seconds.

We could, of course, speed up our Python solution by more carefully
constructing the matrix. However even using Numpy to create the
matrices doesn't get us all the way to (or even close to) the Numpy
solution.

As an additional benefit, starting in Python 3.5 matrix multiplication
in libraries such as Numpy can be written as

.. code-block:: python

   A @ B @ C

using the new ``@`` binary operator.


Writing some code in C(++)
--------------------------

Sometimes Numpy (or other libraries) don't have exactly what you need,
but your code is still slow. If this is the case you could consider
writing the most time-consuming routines in C++, and using Python for
everything else.


Brief note on Python
--------------------

So far we've just referred to Python as Python, but 'Python' is
actually just the name of the language and does not necessarily imply
a specific implementation. The standard reference implementation is
called cpython and is written in C. There are other implementations
such as IronPython (for the .NET platform), Jython (for the Java
Virtual Machine) and PyPy (a just-in-time compiler for Python written
in Python; surprisingly fast). We will be focusing on cpython, which
is what you are using unless you have made a conscious choice not
to. In the following sections 'Python' will refer to cpython.


First-class extensions
----------------------

Python supports extensions to the language that directly add new
functions to Python. However writing these extensions is non-trivial;
you must use the Python header files and adhere to a strict interface
as well as deal with Python's memory model. This would be the approach
you'd want to take if you were publishing a library that you want many
people to use and to be fully integrated with Python.


Using the ``ctypes`` module
---------------------------

Fortunately there is a very simple alternative to writing a
first-class Python extension, which is using the ``ctypes``
module. The ``ctypes`` module lets you call any function defined in a
shared library (DLL on Windows). The upside is that you don't need to
change your C++ code at all. The downside is that your Python code
needs to wrangle with C's type system to call the functions.

As an example, consider the following C++ code.

Head file:

.. literalinclude:: c_add.hh
   :language: C++

Source file:

.. literalinclude:: c_add.cc
   :language: C++

We can compile a shared library called ``libexample.so`` via

.. code-block:: shell

   g++ -o c_add.os -c -fPIC -Wall -Werror -std=c++11 c_add.cc
   g++ -o libexample.so -shared c_add.os
              
We can use the following Python code to call into the shared library.

.. literalinclude:: c_add.py
   :language: python

When run, this Python file outputs

.. code-block:: shell

   $ python3 c_add.py
   5.5
   4.1 6.1