Michaël Defferrard, PhD student, EPFL LTS2
That is one of the most heard complain about Python. Because CPython, the Python reference implementation, interprets the language (i.e. it compiles Python code to intermediate bytecode which is then interpreted by a virtual machine), it is inherentably slower than compiled languages, especially for computation heavy tasks such as number crunching.
There are three ways around it that we'll explore in this exercise:
In this exercise we'll compare many possible implementations of a function. Our goal is to compare the execution time of our implementations and get a sense of the many ways to write efficient Python code. We test seven implementations:
Along the exercise we'll use the function $$accuracy(\hat{y}, y) = \frac1n \sum_{i=0}^{i=n-1} 1(\hat{y}_i = y_i),$$ where $1(x)$ is the indicator function and $n$ is the number of samples. This function computes the accuracy, i.e. the percentage of correct predictions, of a classifier. A pure Python implementation is given below.
def accuracy_python(y_pred, y_true):
"""Plain Python implementation."""
num_correct = 0
for y_pred_i, y_true_i in zip(y_pred, y_true):
if y_pred_i == y_true_i:
num_correct += 1
return num_correct / len(y_true)
Below we test and measure the execution time of the above implementation. The %timeit function provided by IPython is a useful helper to measure the execution time of a line of Python code. As we'll see, the above implementation is very inefficient compared to what we can achieve.
import numpy as np
c = 10 # Number of classes.
n = int(1e6) # Number of samples.
y_true = np.random.randint(0, c, size=n)
y_pred = np.random.randint(0, c, size=n)
print('Expected accuracy: {}'.format(1/c))
print('Empirical accuracy: {}'.format(accuracy_python(y_pred, y_true)))
%timeit accuracy_python(y_pred, y_true)
Expected accuracy: 0.1 Empirical accuracy: 0.100053 10 loops, best of 3: 141 ms per loop
Specialized libraries, which provide efficient compiled implementations of the heavy computations, is an easy way to solve the performance problem. That is for example NumPy, which uses efficient BLAS and LAPACK implementations as a backend. SciPy and scikit-learn fall in the same category.
Implement below the accuracy function using:
Then test that it provides the correct result and measure it's execution time. How much faster are they compared to the pure Python implementation ?
def accuracy_numpy(y_pred, y_true):
"""Numpy implementation."""
# Your code here.
return 0
def accuracy_sklearn(y_pred, y_true):
"""Scikit-learn implementation."""
# Your code here.
return 0
# assert np.allclose(accuracy_numpy(y_pred, y_true), accuracy_python(y_pred, y_true))
# assert np.allclose(accuracy_sklearn(y_pred, y_true), accuracy_python(y_pred, y_true))
# %timeit accuracy_numpy(y_pred, y_true)
# %timeit accuracy_sklearn(y_pred, y_true)
The second option of choice, when the algorirthm does not exist in our favorite libraries and we have to implement it, it to implement in Python and compile it to machine code.
Below you'll compile Python with two frameworks.
While these two approaches offer maximal compatibility with the CPython and NumPy ecosystems, another approach is to use another Python implementation such as PyPy, which features a just-in-time compiler and supports multiple back-ends (C, CLI, JVM). Alternatives are Jython, which runs Python on the Java platform, and IronPython / PythonNet for the .NET platform.
from numba import jit
@jit
def accuracy_numba(y_pred, y_true):
"""Plain Python implementation, compiled by LLVM through Numba."""
return 0
%load_ext Cython
/usr/lib/python3.5/site-packages/Cython/Distutils/old_build_ext.py:30: UserWarning: Cython.Distutils.old_build_ext does not properly handle dependencies and is deprecated. "Cython.Distutils.old_build_ext does not properly handle dependencies "
%%cython
cimport numpy as np
cimport cython
def accuracy_cython(np.ndarray[long, ndim=1] y_pred, np.ndarray[long, ndim=1] y_true):
"""Python implementation with type information, transpiled to C by Cython."""
return 0
Evaluate below the performance of those two implementations, while testing their correctness. How do they compare with plain Python and specialized libraries ?
# Your code here.
%%file function.c
// The content of this cell is written to the "function.c" file in the current directory.
double accuracy(long* y_pred, long* y_true, int n) {
// Your code here.
return 0;
}
Overwriting function.c
The below cell describe a shell script, which will be executed by IPython as if you typed the commands in your terminal. Those commands are compiling the above C program into a dynamic library with GCC. You can use any other compiler, text editor or IDE to produce the C library. Windows users, you may want to use Microsoft toolchain.
%%script sh
FILE=function
gcc -c -O3 -Wall -std=c11 -pedantic -fPIC -o $FILE.o $FILE.c
gcc -o lib$FILE.so -shared $FILE.o
file lib$FILE.so
libfunction.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=eed9b1a0543aa0dd93d1f53b12a2e62fc97d0293, not stripped
The below cell finally create a wrapper around our C library so that we can easily use it from Python.
import ctypes
libfunction = np.ctypeslib.load_library('libfunction', './')
libfunction.accuracy.restype = ctypes.c_double
libfunction.accuracy.argtypes = [
np.ctypeslib.ndpointer(dtype=np.int),
np.ctypeslib.ndpointer(dtype=np.int),
ctypes.c_int
]
def accuracy_c(y_pred, y_true):
n = y_pred.size
return libfunction.accuracy(y_pred, y_true, n)
Evaluate below the performance of your C implementation, and test its correctness. How does it compare with the others ?
# Your code here.
Same idea as before, with Fortran ! Fortran is an imperative programming language developed in the 50s, especially suited to numeric computation and scientific computing. While you probably won't write new code in Fortran, you may have to interface with legacy code (especially in large and old corporations). Here we'll resort to the f2py utility provided by the Numpy project for the (almost automatic) generation of a wrapper.
%%file function.f
! The content of this cell is written to the "function.f" file in the current directory.
SUBROUTINE DACCURACY(YPRED, YTRUE, ACC, N)
CF2PY INTENT(OUT) :: ACC
CF2PY INTENT(HIDE) :: N
INTEGER*4 YPRED(N)
INTEGER*4 YTRUE(N)
DOUBLE PRECISION ACC
INTEGER N, NCORRECT
! Your code here.
ACC = 0
END
Overwriting function.f
The below command compile the Fortran code and generate a Python wrapper.
!f2py -c -m function function.f # >> /dev/null
running build running config_cc unifing config_cc, config, build_clib, build_ext, build commands --compiler options running config_fc unifing config_fc, config, build_clib, build_ext, build commands --fcompiler options running build_src build_src building extension "function" sources f2py options: [] f2py:> /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/functionmodule.c creating /tmp/tmpkn97e3yu/src.linux-x86_64-3.5 Reading fortran codes... Reading file 'function.f' (format:fix,strict) Post-processing... Block: function Block: daccuracy Post-processing (stage 2)... Building modules... Building module "function"... Constructing wrapper function "daccuracy"... acc = daccuracy(ypred,ytrue) Wrote C/API module "function" to file "/tmp/tmpkn97e3yu/src.linux-x86_64-3.5/functionmodule.c" adding '/tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.c' to sources. adding '/tmp/tmpkn97e3yu/src.linux-x86_64-3.5' to include_dirs. copying /usr/lib/python3.5/site-packages/numpy/f2py/src/fortranobject.c -> /tmp/tmpkn97e3yu/src.linux-x86_64-3.5 copying /usr/lib/python3.5/site-packages/numpy/f2py/src/fortranobject.h -> /tmp/tmpkn97e3yu/src.linux-x86_64-3.5 build_src: building npy-pkg config files running build_ext customize UnixCCompiler customize UnixCCompiler using build_ext customize Gnu95FCompiler Found executable /usr/bin/gfortran customize Gnu95FCompiler customize Gnu95FCompiler using build_ext building 'function' extension compiling C sources C compiler: gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -march=x86-64 -mtune=generic -O2 -pipe -fstack-protector-strong -fPIC creating /tmp/tmpkn97e3yu/tmp creating /tmp/tmpkn97e3yu/tmp/tmpkn97e3yu creating /tmp/tmpkn97e3yu/tmp/tmpkn97e3yu/src.linux-x86_64-3.5 compile options: '-I/tmp/tmpkn97e3yu/src.linux-x86_64-3.5 -I/usr/lib/python3.5/site-packages/numpy/core/include -I/usr/include/python3.5m -c' gcc: /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.c In file included from /usr/lib/python3.5/site-packages/numpy/core/include/numpy/ndarraytypes.h:1777:0, from /usr/lib/python3.5/site-packages/numpy/core/include/numpy/ndarrayobject.h:18, from /usr/lib/python3.5/site-packages/numpy/core/include/numpy/arrayobject.h:4, from /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.h:13, from /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.c:2: /usr/lib/python3.5/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: #warning "Using deprecated NumPy API, disable it by " "#defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-Wcpp] #warning "Using deprecated NumPy API, disable it by " \ ^~~~~~~ /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.c: In function ‘format_def’: /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.c:139:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare] if (size < sizeof(notalloc)) { ^ gcc: /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/functionmodule.c In file included from /usr/lib/python3.5/site-packages/numpy/core/include/numpy/ndarraytypes.h:1777:0, from /usr/lib/python3.5/site-packages/numpy/core/include/numpy/ndarrayobject.h:18, from /usr/lib/python3.5/site-packages/numpy/core/include/numpy/arrayobject.h:4, from /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.h:13, from /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/functionmodule.c:19: /usr/lib/python3.5/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: #warning "Using deprecated NumPy API, disable it by " "#defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-Wcpp] #warning "Using deprecated NumPy API, disable it by " \ ^~~~~~~ /tmp/tmpkn97e3yu/src.linux-x86_64-3.5/functionmodule.c:112:12: warning: ‘f2py_size’ defined but not used [-Wunused-function] static int f2py_size(PyArrayObject* var, ...) ^~~~~~~~~ compiling Fortran sources Fortran f77 compiler: /usr/bin/gfortran -Wall -g -ffixed-form -fno-second-underscore -fPIC -O3 -funroll-loops Fortran f90 compiler: /usr/bin/gfortran -Wall -g -fno-second-underscore -fPIC -O3 -funroll-loops Fortran fix compiler: /usr/bin/gfortran -Wall -g -ffixed-form -fno-second-underscore -Wall -g -fno-second-underscore -fPIC -O3 -funroll-loops compile options: '-I/tmp/tmpkn97e3yu/src.linux-x86_64-3.5 -I/usr/lib/python3.5/site-packages/numpy/core/include -I/usr/include/python3.5m -c' gfortran:f77: function.f function.f:11:33: INTEGER N, NTOTAL, NCORRECT 1 Warning: Unused variable ‘ncorrect’ declared at (1) [-Wunused-variable] function.f:11:23: INTEGER N, NTOTAL, NCORRECT 1 Warning: Unused variable ‘ntotal’ declared at (1) [-Wunused-variable] function.f:4:32: SUBROUTINE DACCURACY(YPRED, YTRUE, ACC, N) 1 Warning: Unused dummy argument ‘ypred’ at (1) [-Wunused-dummy-argument] function.f:4:39: SUBROUTINE DACCURACY(YPRED, YTRUE, ACC, N) 1 Warning: Unused dummy argument ‘ytrue’ at (1) [-Wunused-dummy-argument] /usr/bin/gfortran -Wall -g -Wall -g -shared /tmp/tmpkn97e3yu/tmp/tmpkn97e3yu/src.linux-x86_64-3.5/functionmodule.o /tmp/tmpkn97e3yu/tmp/tmpkn97e3yu/src.linux-x86_64-3.5/fortranobject.o /tmp/tmpkn97e3yu/function.o -L/usr/lib -lpython3.5m -lgfortran -o ./function.cpython-35m-x86_64-linux-gnu.so Removing build directory /tmp/tmpkn97e3yu
import function
def accuracy_fortran(y_pred, y_true):
return function.daccuracy(y_pred, y_true)
Evaluate below the performance of your Fortran implementation, and test its correctness. How does it compare with the others ?
# Your code here.
Plot a graph with n
as the x-axis and the execution time of the various methods on the y-axis.
# Your code here.
To reflect on what we've done, answer the following questions: