Cython для трейдинга – скорость имеет значение
Архивный пост
Python замечательный язык, де факто питон стал OpenSource альтернативой множеству дорогостоящих математических пакетов в научной среде, трейдинг здесь не является исплючением. Я считаю, что трейдинг – это больше наука, чем искусство. Весь прошлый месяц я делал инструмент, который выполняет тонны расчетов, при чем он это делает на питоне. А как любой интерпретируемый язык – питон достаточно медленный, и прожорливый по части памяти, но в умелых руках его скорости могут достигать скоростей C/C++ языков! Поделюсь небольшим опытом оптимизации расчетов на питоне, а также поделюсь single pass алгоритмом для расчета СКО на Питоне. Сразу скажу, для этого конкретного кода мне удалось добиться увеличения производительности кода в 30 (тридцать) раз!
Базовый код на Python
Вот тот самый код, который считает СКО, среднее и количество в online режиме, это позволяет получить большой выигрыш по производительности и по использованию памяти. Если кто не знает, обычный расчет СКО подразумевает 2 прохода по всем данным, сначала рассчитывается средняя, потом среднеквадратическое отклонение от нее. Более того большинство online алгоритмов расчета СКО не проходили проверку на стабильность, я тупо сравнивал с numpy.std(), и мой алгоритм имеет 100% сходимость с numpy. Хотя алгоритм конечно не мой, я откопал его где-то в интернетах и переписал на питон.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Stats_py:
k = 0.0
Mk = 0.0
Qk = 0.0
def __init__(self):
self.k = 0.0
def add(self, x):
self.k += 1
if self.k == 1.0:
self.Mk = x
self.Qk = 0.0
else:
d = x - self.Mk
self.Qk += (self.k-1.0)*d*d/self.k
self.Mk += d / self.k
def std(self):
return sqrt(self.Qk/self.k)
def mean(self):
return self.Mk
def count(self):
return self.k
Делаем простую проверку на скорость в IPython:
1
2
3
4
5
6
7
8
9
10
11
values = np.random.random(10000)
s = Stats_py()
for x in values:
s.add(x)
print np.std(values), s.std()
%timeit s.add(1)
------
0.289223020474 0.289223020474
100000 loops, best of 3: 2.93 µs per loop
Как вы видите цифры бьються до последнего знака, а выполнение одного вызова функции add() занимает 2.93 микросекунды = 2930 наносекунд. С одной стороны это очень мало, с другой стороны когда нужно совершить миллиарды итераций это время начинает уже сильно ощущаться.
Теперь давайте выжмем из этого кода все на что он способен! Для этого нам нужно взять в руки напильник Cython и научиться с ним работать. IPython Notebook предоставляет отличную возможность писать и отлаживать код Cython прямо в браузере! Для этого есть специальный %%cyton magiс, примеры работы с ним можно посмотреть в разделе Cython Magic Functions Extension.
Оптимизация cython
Для начала не будет мудрствовать и просто скопируем код из питона в Cython, переименуем класс в Stats_cy чтобы не запутаться, можно добавить ключ “–annotate” тогда у вас будет дополнительная возможность анализа кода:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
%%cython --annotate
import numpy as np
cimport numpy as np
cimport cython
from libc.math cimport sqrt
class Stats_cy:
k = 0.0
Mk = 0.0
Qk = 0.0
def __init__(self):
self.k = 0.0
def add(self, x):
self.k += 1.0
if self.k == 1.0:
self.Mk = x
self.Qk = 0.0
else:
d = x - self.Mk
self.Qk += (self.k-1.0)*d*d/self.k
self.Mk += d / self.k
def std(self):
return sqrt(self.Qk/self.k)
def mean(self):
return self.Mk
def count(self):
return self.k
Мы увидим примерно следующую картину, желтыми цветом выделен код который является не оптимиальным (т.е. вызовы Python), а если линия выделена белым – то код является чистым Си кодом, который компилируется и работает с такой же скоростью как любая другая программа на Си. Вы также можете щелкнуть на любую линию, чтобы развернуть Си код который сгенерировал и скомпилировал Cython. Он некрасивый, но с другой стороны его никто не читает :)
cython Делаем тестовый прогон кода, получаем следующие тайминги:
1
2
3
4
Stats_py time
100000 loops, best of 3: 2.93 µs per loop
Stats_cy time
100000 loops, best of 3: 2.62 µs per loop
Прирост производительности всего 11%, хотя для простого копи-паста уже недурно.
Cython – вторая космическая скорость
Приступим к оптимизации, необходимо для каждой переменной добавить тип, да динамическая типизация – один из плюсов Питона, но когда дело касается производительности об этом не может быть и речи. Просто добавляем типы ко всем переменным которы используют в нашем коде: поля класса, параметры функций, локальные переменные функций, все должно иметь свой тип переменных, в нашем случае это double.
Смотрим, результат, желтизны как не бывало! Пришлось добавить “cdef” перед именем класса, а также перенести инициацию глобальных переменных класса в метод init(). Обратите на листинг кода строки №17, это чистый Си код, теперь без того ужаса что быт тут раньше (см. первый рисунок строка 15)
Делаем тестовый прогон кода, получаем следующие тайминги:
1
2
3
4
Stats_py time
100000 loops, best of 3: 2.93 µs per loop
Stats_cy time
10000000 loops, best of 3: 94.6 ns per loop
Прирост скорости 30 раз!
Для перфекционистов, чтобы убрать желтый цвет со строк 24 и 25, нужно добавить в шапку функции следующую строку: “@cython.cdivision(True)” она запрещает проверки на деление на ноль и прочее, что делает питон. Сильно это производительность не повысит, это больше для успокоения души, что ваш код, бывший когда-то питоном, стал чистым Cи.
Прирост скорости на уровне статистической погрешности:
1
2
3
4
Stats_py time
100000 loops, best of 3: 2.98 µs per loop
Stats_cy time
10000000 loops, best of 3: 94.2 ns per loop
Встречайте, полностью оптимизированный код:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import numpy as np
cimport numpy as np
cimport cython
from libc.math cimport sqrt
cdef class Stats_cy:
cdef double k
cdef double Mk
cdef double Qk
def __init__(self):
self.k = 0.0
self.Mk = 0.0
self.Qk = 0.0
@cython.cdivision(True)
def add(self, double x):
self.k += 1.0
cdef double d
if self.k == 1.0:
self.Mk = x
self.Qk = 0.0
else:
d = x - self.Mk
self.Qk += (self.k-1.0)*d*d/self.k
self.Mk += d / self.k
def std(self):
return sqrt(self.Qk/self.k)
def mean(self):
return self.Mk
def count(self):
return self.k
Cython резюме
Трейдинг – та область, где очень важны математические вычисления, будь это скользящая средняя или формула Блэка-Шоулза, наши алгоритмы выполняют эти вычисления тысячи и миллионы раз за день. А ведь так, хочется чтобы это работало побыстрее. Cython – является прекрасным инструментом, который позволяет увеличить производительность расчетов в разы.
p.s. И конечно не нужно забывать про бритву Оккама, и делать оптимизации только для критически важных и нужных задач, только когда это необходимо.