Лекция 11: Быстрее Python, ещё быстрее
Сергей Лебедев
3 декабря 2014 г.
IPython
IPython за 5 минут
• IPython — более лучшая интерактивная оболочка для языка
Python.
• Она поддерживает:
• интроспекцию и дополнение имён модулей, классов,
методов, переменных,
• расширенную работу с историей,
• использование стандартных команд UNIX, например, ls,
• систему “магических” команд %%magic.
• Установить можно с помощью менеджера пакетов pip:
$ pip install "ipython[all]"
1 / 41
IPython: интроспекция и дополнение
In [1]: from collections import de<TAB>
defaultdict deque
In [2]: d = {"foo": "bar"}
In [3]: d.c<TAB>
d.clear d.copy
In [4]: def f():
...: "I do nothing and return 42."
...: return 42
...:
In [5]: f? # вывод ?? также содержит исходный код.
Type: function
String form: <function f at 0x103d68ae8>
File: ...
Definition: f()
Docstring: I do nothing and return 42.
2 / 41
IPython: расширенная работа с историей
# номер ячейки
# |
# v
In [1]: [1, 2, 3]
Out[1]: [1, 2, 3]
In [2]: _[:-1] # ссылка на предыдущую ячейку
Out[2]: [1, 2]
In [3]: __[:-1] # ссылка на две ячейки назад
Out[3]: [1, 2]
In [4]: _2 == _3 # ссылка на ячейку по номеру
Out[4]: True
In [5]: _ih[3:] # _ih --- список вычисленных выражений
Out[5]: ['__[:-1]', '_2 == _3']
3 / 41
IPython: стандартные команды UNIX
In [1]: pwd
Out[1]: './cscenter/python'
In [2]: ls lecture*.tex
lecture-base.tex lecture1.tex lecture11.tex
lecture2.tex lecture3.tex lecture4.tex
lecture5.tex lecture6.tex lecture7.tex
lecture8.tex lecture9.tex
In [3]: cd /tmp
/tmp
In [4]: !date
Tue 2 Dec 2014 14:39:04 MSK
In [5]: output = !date
In [6]: output
Out[6]: ['Tue 2 Dec 2014 14:39:26 MSK']
4 / 41
IPython: “магические” команды
• “Магические” команды отвечают за магию.
• Однострочные “магические” команды начинаются с символа
%, многострочные — с %%.
• Пример однострочной “магической” команды, которая
позволяет отредактировать и вычислить содержимое
ячейки с указанным номером:
In [1]: def f():
...: pass
...:
In [2]: %edit 1
IPython will make a temporary file named: [...]
done. Executing edited code...
Out[2]: 'def f():\n return 42\n'
In [3]: f()
Out[3]: 42
5 / 41
IPython: “магические” команды и автомагия
• По умолчанию IPython работает в режиме %automagic, то
есть префикс % у однострочных команд можно не писать.
• Команды UNIX, которыми мы уже пользовались, — это
“магические” команды IPython, вызванные без префикса %.
• Пример многострочной “магической” команды, которая
сохраняет содержимое ячейки в указанный файл:
In [1]: %%writefile /tmp/example.py
...: def f():
...: return 42
...:
Writing /tmp/example.py
In [2]: %load /tmp/example.py
In [4]: f()
Out[4]: 42
In [5]: %lsmagic # DIY.
6 / 41
IPython: резюме
• IPython — удобная и полезная альтернатива стандартной
интерактивной оболочке Python.
• Мы поговорили только про основы её использования.
Больше информации можно найти на сайте:
http://ipython.org.
• У IPython также есть веб-интерфейс, именуемый IPython
Notebook. Если вы никогда о нём не слышали, обязательно
попробуйте ipython notebook или посмотрите
мотивирующий пример по ссылке
http://bit.ly/ipnb-example.
7 / 41
[[4], [2]]
Пример: класс Matrix
В качестве примера для изучения производительности Python
будем использовать умножение матриц.
class Matrix(list):
@classmethod
def zeros(cls, shape):
rows, cols = shape
return cls([[0] * cols for i in range(rows)])
@classmethod
def random(cls, shape):
M, (rows, cols) = cls(), shape
for i in range(rows):
M.append([random.randint(-255, 255)
for j in range(cols)])
return M
@property
def shape(self):
return ((0, 0) if not self else
(len(self), len(self[0])))
8 / 41
Пример: функция dot_product
def dot_product(X, Y):
xrows, xcols = X.shape
yrows, ycols = Y.shape
# верим, что с размерностями всё хорошо
Z = Matrix.zeros((xrows, ycols))
for i in range(xrows):
for j in range(xcols):
for k in range(ycols):
Z[i][k] += X[i][j] * Y[j][k]
return Z
def test(): # <-- всегда проверяйте на корректность!
X = Matrix([[1], [2], [3]])
Y = Matrix([[4, 5, 6]])
assert dot_product(X, Y) == Matrix([
[4, 5, 6], [8, 10, 12], [12, 15, 18]
])
assert dot_product(Y, X) == Matrix([[32]])
9 / 41
Измерениевремени работы
Модуль timeit
• Модуль timeit реализует одноимённую функцию timeit,
которую можно использовать для измерения скорости
работы кода на Python:In [1]: import timeit
In [2]: setup = """
...: from faster_python_faster import Matrix, \
...: dot_product
...: shape = 64, 64
...: X = Matrix.random(shape)
...: Y = Matrix.random(shape)
...: """
In [3]: timeit.timeit("dot_product(X, Y)", setup,
...: number=10)
Out[3]: 2.048279687005561
• Функция timeit замеряет время с помощью функции
time.perf_counter. На время измерений отключается
сборщик мусора.
10 / 41
“Магическая” команда timeit
• В IPython есть “магическая” команда timeit, которая
упрощает работу с одноимённой функцией:
In [1]: %timeit <expr>
100 loops, best of 3: 2.73 ms per loop
• Команду timeit также можно использовать в
многострочном варианте:
In [2]: def setup():
...: from faster_python_faster import Matrix, \
...: dot_product
...: shape = 64, 64
...: X = Matrix.random(shape)
...: Y = Matrix.random(shape)
...: return dot_product, X, Y
...:
In [3]: %%timeit dot_product, X, Y = setup()
...: dot_product(X, Y)
...:
10 loops, best of 3: 205 ms per loop
11 / 41
Промежуточный итог 1
• Умножение двух случайных матриц из целых чисел размера
64x64 занимает чуть больше 200 миллисекунд.
• 5 умножений матриц в секунду. Подозрительно медленно.
• В чём может быть проблема?
def dot_product(X, Y):
xrows, xcols = X.shape
yrows, ycols = Y.shape
Z = Matrix.zeros((xrows, ycols))
for i in range(xrows):
for j in range(xcols):
for k in range(ycols):
Z[i][k] += X[i][j] * Y[j][k]
return Z
12 / 41
Функция bench
Опередлим вспомогательную функцию bench, которая
генерирует случайные матрицы указанного размера, а затем
n_iter раз умножает их в цикле.
def bench(shape=(64, 64), n_iter=16):
X = Matrix.random(shape)
Y = Matrix.random(shape)
for iter in range(n_iter):
dot_product(X, Y)
if __name__ == "__main__":
bench()
13 / 41
Модуль cProfile
Модуль cProfile позволяет профилировать код на Python с
точностью до вызова функции или метода:
In [1]: import cProfile
In [2]: source = open("faster_python_faster.py").read()
In [3]: cProfile.run(source, sort="tottime")
41380 function calls in 3.209 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall function
16 3.172 0.198 3.173 0.198 dot_product
# ...
Для наших целей выглядит довольно бесполезно. Что делать?
14 / 41
Модуль line_profiler
• В отличие от cProfile модуль line_profiler анализирует
время работы с точностью до строки в исходном коде.
$ pip install line_profiler
• Модуль расширяет систему “магических” команд IPython
командой lprun. Чтобы воспользоваться ей, сначала нужно
загрузить файл расширения:
In [1]: %load_ext line_profiler
In [2]: from faster_python_faster import dot_product, \
...: bench
In [3]: %lprun -f dot_product bench()
# ^ ^
# | |
# имя функции выражение
15 / 41
Промежуточный итог 2
In [1]: %lprun -f dot_product bench()
Timer unit: 1e-06 s
Total time: 9.08323 s
File: faster_python_faster.py
Function: dot_product at line 24
% Time Line Contents
====================================================
def dot_product(X, Y):
0.0 xrows, xcols = X.shape
0.0 yrows, ycols = Y.shape
0.0 Z = Matrix.zeros((xrows, ycols))
0.0 for i in range(xrows):
0.4 for j in range(xcols):
26.4 for k in range(ycols):
73.2 Z[i][k] += X[i][j] * Y[j][k]
0.0 return Z
16 / 41
Перестановки
Операция list.__getitem__ не бесплатна. Запомним значения
X[i] и Z[i] и переставим местами циклы for так, чтобы код
делал меньше обращений по индексу.
def dot_product(X, Y):
xrows, xcols = X.shape
yrows, ycols = Y.shape
Z = Matrix.zeros((xrows, ycols))
for i in range(xrows):
Xi, Zi = X[i], Z[i]
for k in range(ycols):
acc = 0
for j in range(xcols):
acc += Xi[j] * Y[j][k]
Zi[k] = acc
return Z
17 / 41
Промежуточный итог 3
In [1]: %lprun -f dot_product bench()
Timer unit: 1e-06 s
Total time: 7.74146 s
File: faster_python_faster.py
Function: dot_product at line 36
% Time Line Contents
==============================================
def dot_product(X, Y):
0.0 xrows, xcols = X.shape
0.0 yrows, ycols = Y.shape
0.0 Z = Matrix.zeros((xrows, ycols))
0.0 for i in range(xrows):
0.0 Xi, Zi = X[i], Z[i]
0.6 for k in range(ycols):
0.5 acc = 0
36.2 for j in range(xcols):
61.7 acc += Xi[j] * Y[j][k]
0.8 Zi[k] = acc
0.0 return Z
18 / 41
Долой цикл for!
Больше 30% времени уходит на работу внутренней машинерии
цикла for. В данном случае цикл for можно заменить на
выражение-генератор.
def dot_product(X, Y):
xrows, xcols = X.shape
yrows, ycols = Y.shape
Z = Matrix.zeros((xrows, ycols))
for i in range(xrows):
Xi, Zi = X[i], Z[i]
for k in range(ycols):
Zi[k] = sum(Xi[j] * Y[j][k]
for j in range(xcols))
return Z
19 / 41
Промежуточный итог 4
In [1]: %lprun -f dot_product bench()
Timer unit: 1e-06 s
Total time: 3.59328 s
File: faster_python_faster.py
Function: dot_product at line 50
% Time Line Contents
=======================================================
def dot_product(X, Y):
0.0 xrows, xcols = X.shape
0.0 yrows, ycols = Y.shape
0.0 Z = Matrix.zeros((xrows, ycols))
0.0 for i in range(xrows):
0.0 Xi, Zi = X[i], Z[i]
2.0 for k in range(ycols):
97.9 Zi[k] = sum(Xi[j] * Y[j][k]
0.0 for j in range(xcols))
0.0 return Z
20 / 41
Снова перестановки
Почти всё время функция dot_product проводит в самом
внутреннем цикле. Попробуем убрать из него ещё одно
обращение по индексу, транспонировав матрицу Y.
def dot_product(X, Y):
xrows, xcols = X.shape
yrows, ycols = Y.shape
Z = Matrix.zeros((xrows, ycols))
Yt = Y.transpose() # <--
for i, (Xi, Zi) in enumerate(zip(X, Z)):
for k, Ytk in enumerate(Yt):
Zi[k] = sum(Xi[j] * Ytk[j]
for j in range(xcols))
return Z
21 / 41
Промежуточный итог 5
In [1]: %lprun -f dot_product bench()
Timer unit: 1e-06 s
Total time: 2.54586 s
File: faster_python_faster.py
Function: dot_product at line 76
% Time Line Contents
=======================================================
def dot_product(X, Y):
0.0 xrows, xcols = X.shape
0.0 yrows, ycols = Y.shape
0.0 Z = Matrix.zeros((xrows, ycols))
0.0 Yt = Y.transpose()
0.0 for i, (Xi, Zi) in enumerate(zip(X, Z)):
2.9 for k, Ytk in enumerate(Yt):
97.0 Zi[k] = sum(Xi[j] * Ytk[j]
0.0 for j in range(xcols))
0.0 return Z
22 / 41
Измерение времени работы: резюме
• Измерить время работы функции можно с помощью
функции timeit из модуля timeit.
• Найти узкое место в программе — с помощью модуля
cProfile.
• Оценить вклад каждой строки кода в общее время работы
функции — с помощью модуля line_profiler.
• В IPython есть “магические” команды для всех трёх типовизмерений:
• %timeit,
• %prun,
• %lprun.
23 / 41
Заметка о демотивации: NumPy
• NumPy — библиотека для научных вычислений на Python.
• В основе библиотеки — ndarray — многомерный
типизированный массив.
• Сравним результаты наших стараний с ndarray :In [1]: %%timeit dot_product, X, Y = setup()
...: dot_product(X, Y)
...:
10 loops, best of 3: 56.1 ms per loop
In [2]: def np_setup():
...: import numpy as np
...: shape = 64, 64
...: return (np.random.randint(-255, 255, shape)
...: np.random.randint(-255, 255, shape))
...:
In [3]: %%timeit X, Y = np_setup()
...: X.dot(Y)
...:
1000 loops, best of 3: 325 µs per loop # :-(
24 / 41
AOT и JIT компиляция кода на Python
• Дальнейшие способы ускорения кода на Python
предполагают его преобразование в машинный код либо
до, либо в момент его исполнения.
• Ahead-of-time компиляция.
• Python C-API: пишем код на С и реализуем к нему интерфейс,
понятный интерпретатору CPython.
• Пишем код на подмножестве Python и преобразуем его в
код на C++ (Pythran) или C (Cython), использующий C-API
интепретатора CPython.
• Just-in-time компиляция: пишем код на Python и пытаемсясделать его быстрее в момент исполнения.
• PyPy: следим за исполнением программы и компилируем в
машинный код наиболее частые пути в ней.
• Транслируем специальным образом помеченный код на
Python в LLVM (Numba) или C++ (HOPE), а затем
компилируем в машинный код.
25 / 41
Numba
Numba и ndarray
• Поставить Numba с помощью pip может быть непросто.
Рекомендуемый способ установки описан по ссылке:
http://bit.ly/install-numba.
• На момент версии 0.15 Numba не работает со списками,
поэтому нам придётся переписать функцию dot_product с
использованием ndarray :
import numba
@numba.jit
def jit_dot_product(X, Y):
xrows, xcols = X.shape
yrows, ycols = Y.shape
Z = np.zeros((xrows, ycols), dtype=X.dtype)
for i in range(xrows):
for k in range(ycols):
for j in range(xcols):
Z[i, k] += X[i, j] * Y[j, k]
return Z
26 / 41
Numba и декоратор jit
• Для использования Numba достаточно декорировать
функцию с помощью numba.jit.
• В момент первого вызова функция будет транслирована в
LLVM и скомпилирована в машинный код:
In [1]: def jit_setup():
...: import numpy as np
...: shape = 64, 64
...: X = np.random.randint(-255, 255, shape)
...: Y = np.random.randint(-255, 255, shape)
...: return jit_dot_product, X, Y
...:
In [2]: %%timeit jit_dot_product, X, Y = jit_setup()
...: jit_dot_product(X, Y)
1000 loops, best of 3: 747 µs per loop
27 / 41
Numba и вывод типов
• Декоратор numba.jit пытается вывести типы аргументов и
возвращаемого значения декорируемой функции.
• На момент версии 0.15 процесс вывода типов довольно
хрупкий.
• Если Numba не удаётся вывести типы, то ускорение от
компиляции кода становится незначительным:In [1]: @numba.jit
...: def jit_dot_product(X, Y):
...: xrows, xcols = X.shape
...: yrows, ycols = Y.shape
...: Z = np.zeros((xrows, ycols))
...: for i in range(xrows):
...: for k in range(ycols):
...: Z[i, k] = np.sum(X[i, :] * Y[:, k])
...: return Z
...:
In [2]: %%timeit jit_dot_product, X, Y = jit_setup()
...: jit_dot_product(X, Y)
10 loops, best of 3: 65 ms per loop # :-(28 / 41
Numba: резюме
• Numba — это JIT компилятор для Python кода, основанный
на трансляции в LLVM.
• В теории Numba не требует никаких изменений в коде,
кроме использования декоратора numba.jit.
• На практике механизм вывода типов, который используется
на этапе трансляции, далёк от совершенства, поэтому код
нужно писать специальным образом, чтобы Numba его
поняла.
• Мы не поговорили о:
• явной аннотации типов,
• автоматической векторизации,
• AOT компиляции кода, использующего Numba.
• Почитать об этом можно в документации проекта:
http://numba.pydata.org.
29 / 41
Cython
Что такое Cython?
• Cython — это:
• типизированное расширение1 языка Python,
• оптимизирующий компилятор Python и Cython в код на C,
использующий C-API интерпретатора CPython.
• Для простоты мы будем работать с Cython из IPython:
In [1]: %load_ext cython
In [2]: %%cython
...: print("Hello, world!")
...:
Hello, world!
Out[2]: {}
• Узнать подробности о взаимодействии Cython с системой
импортов и библиотекой setuptools можно на сайте
проекта: http://bit.ly/compile-cython.
1Любой код на Python — это корректный код на Cython.30 / 41
“Магическая” команда cython
“Магическая” команда cython компилирует содержимое ячейки с
помощью Cython, а затем загружает все имена из
скомпилированного модуля в глобальное пространство имён.
In [1]: %%cython
...: def f():
...: return 42
...: def g():
...: return []
...:
In [2]: f
Out[2]: <function _cython_magic_[...].f>
In [3]: g
Out[3]: <function _cython_magic_[...].g>
In [4]: f(), g()
Out[4]: (42, [])
31 / 41
Cython и умножение матриц
Попробуем скомпилировать функцию cy_dot_product с
помощью Cython и замерять её производительность.
In [1]: %%cython
...: def cy_dot_product(X, Y):
...: xrows, xcols = X.shape
...: yrows, ycols = Y.shape
...: Z = Matrix.zeros((xrows, ycols))
...: Yt = Y.transpose()
...: for i, (Xi, Zi) in enumerate(zip(X, Z)):
...: for k, Ytk in enumerate(Yt):
...: Zi[k] = sum(Xi[j] * Ytk[j]
...: for j in range(xcols))
...: return Z
...:
In [2]: %%timeit cy_dot_product, X, Y = cy_setup()
...: cy_dot_product(X, Y)
...:
10 loops, best of 3: 34.5 ms per loop
32 / 41
Cython и режим аннотации
• Компилятор Cython поддерживает опциональную
типизацию.
• Посмотрим, что происходит в функции cy_dot_product:
In [1]: %%cython -a
...: def cy_dot_product(X, Y):
...: xrows, xcols = X.shape
...: yrows, ycols = Y.shape
...: Z = Matrix.zeros((xrows, ycols))
...: Yt = Y.transpose()
...: for i, Xi, Zi in enumerate(zip(X, Z)):
...: for k, Ytk in enumerate(Yt):
...: Zi[k] = sum(Xi[j] * Ytk[j]
...: for j in range(xcols))
...: return Z
Out[2]: <IPython.core.display.HTML at 0x108ebac18>
33 / 41
Результат аннотации функции cy_dot_product
• Чем интенсивнее цвет, тем менее специфичен тип
выражения и тем медленней выполняется фрагмент кода.
• Обилие желтого цвета намекает, что результат компиляции
функции cy_dot_product мало чем отличается от её версии
на Python, потому что все объекты имеют тип PyObject.
34 / 41
Cython и NumPy
К сожалению, списки в Python гетерогенны, поэтому, как и в
случае с Numba, мы вынуждены перейти к использованию
ndarray :
In [1]: %%cython -a
...: import numpy as np
...: def cy_dot_product(X, Y):
...: xrows, xcols = X.shape
...: yrows, ycols = Y.shape
...: Z = np.zeros((xrows, ycols), dtype=X.dtype)
...: for i in range(xrows):
...: for k in range(ycols):
...: for j in range(xcols):
...: Z[i, k] += X[i, j] * Y[j, k]
...: return Z
...:
In [2]: %%timeit cy_dot_product, X, Y = cy_setup()
...: cy_dot_product(X, Y)
...:
10 loops, best of 3: 178 ms per loop
35 / 41
Cython и типизация
In [1]: %%cython -a
...: import numpy as np
...: cimport numpy as np
...: def cy_dot_product(np.ndarray X, np.ndarray Y):
...: cdef int xrows = X.shape[0]
...: cdef int xcols = X.shape[1]
...: cdef int yrows = Y.shape[0]
...: cdef int ycols = Y.shape[1]
...: cdef np.ndarray Z
...: Z = np.zeros((xrows, ycols), dtype=X.dtype)
...: for i in range(xrows):
...: for k in range(ycols):
...: for j in range(xcols):
...: Z[i, k] += X[i, j] * Y[j, k]
...: return Z
...:
In [2]: %%timeit cy_dot_product, X, Y = cy_setup()
...: cy_dot_product(X, Y)
...:
10 loops, best of 3: 177 ms per loop # :-(
36 / 41
Cython и NumPy: приближение 1
Несмотря на то что все переменные имеют явный тип, тип
элемента ndarray всё ещё не определён, поэтому тело самого
вложенного цикла ярко-жёлтое.
37 / 41
Cython и типизация элемента ndarray
In [1]: %%cython -a
...: import numpy as np
...: cimport numpy as np
...: def cy_dot_product(np.ndarray[np.int64_t, ndim=2] X,
...: np.ndarray[np.int64_t, ndim=2] Y):
...: # ...
...: cdef np.ndarray[np.int64_t, ndim=2] Z = \
...: np.zeros((xrows, ycols), dtype=X.dtype)
...: for i in range(xrows):
...: for k in range(ycols):
...: for j in range(xcols):
...: Z[i, k] += X[i, j] * Y[j, k]
...: return Z
...:
In [2]: %%timeit cy_dot_product, X, Y = cy_setup()
...: cy_dot_product(X, Y)
...:
1000 loops, best of 3: 869 µs per loop # O_O
38 / 41
Cython и NumPy: приближение 2
Всё прекрасно, но иногда хочется большего ;)
39 / 41
Cython и небезопасный код
Cython позволяет пожертвовать безопасностью в пользу
производительности, отключив проверки выхода за границы
массива и проверки переполнения в целочисленных операциях.
In [1]: %%cython -a
...: import numpy as np
...: cimport numpy as np
...: cimport cython
...: @cython.boundscheck(False)
...: @cython.overflowcheck(False)
...: def cy_dot_product(np.ndarray[np.int64_t, ndim=2] X,
...: np.ndarray[np.int64_t, ndim=2] Y):
...: # ...
...:
In [2]: %%timeit cy_dot_product, X, Y = cy_setup()
...: cy_dot_product(X, Y)
...:
10 loops, best of 3: 667 µs per loop
40 / 41
Cython: резюме
• Cython — удобный инструмент для написания критичного по
производительности кода на Python-подобном синтаксисе.
• Мы обсудили только самые основы использования Cython, вчастности, мы не коснулись:
• нюансов языка (C-функций и типов расширения),
• взаимодействия Cython с кодом на C и C++,
• многопоточности,
• профилирования и отладки.
• Обо всём этом и многом другом можно узнать из
документации: http://docs.cython.org.
41 / 41
P.S.In [3]: %%timeit X, Y = np_setup()
...: X.dot(Y)
...:
1000 loops, best of 3: 325 µs per loop