Одним тёплым холодным зимним вечером, хотелось согреться в офисе и проверить теорию одного коллеги, что C++ vector мог бы быстрее справиться с задачей, чем CPython list.
В компании мы разрабатываем продукты на базе Django и случилось так, что нужно было обработать один большой массив словарей. Коллега предположил, что реализация на C++ была бы гораздо быстрее, а меня не покидало чувство, что Гвидо и сообщество наверное немного круче нас в Си и возможно уже решили и обошли все подводные камни, реализовав всё гораздо быстрее.
Для проверки теории, я решил написать небольшой тестовый файл, в котором решил прогнать в цикле вставку 1М словарей одинакового содержания в массив и в vector 100 раз подряд.
Результаты хоть и были ожидаемые, но так же и внезапные.
Так уж вышло, что мы активно используем Cython, поэтому в целом результаты будут отличаться на полностью CPython реализации.
Стенд
- Calculate Linux onegreyonewhite 4.18.14-calculate #1 SMP PREEMPT Sat Oct 13 21:03:27 UTC 2018 x86_64 Intel® Core(TM) i7-4770 CPU @ 3.40GHz GenuineIntel GNU/Linux
- Python 2.7 и 3.6
- Cython 0.28.3
- gcc (Gentoo 7.3.0-r3 p1.4)
Скрипт
К слову, здесь пришлось повозиться. Чтобы получить максимально реальные числа (т.е. не просто сделать супероптимизировано, но и так, что мы потом сможем это использовать без танцев с бубном), пришлось всё делать основном скрипте, а все дополнительные .h свести к минимуму.
Первая проблема заключалась в том, что обёртка Cython для vector не хочет работать в таком виде:
# Так не хотел
ctypedef vector[object] dict_vec
# И так не завелось (ошибка появлялась на vector.push_back(dict()))
ctypedef vector[PyObject*] dict_vec
# И даже так, что удивительно (просто говорит, что не может object привести к PyObject.)
ctypedef vector[PyObject] dict_vecПри всём при этом получали ошибку, что невозможно привести dict к PyObject. Конечно же это проблемы Cython, но так как мы его используем, нам нужно решить эту конкретную проблему.
Пришлось сделать маленький костылик в виде
#include "Python.h"
static PyObject * convert_to_pyobject(PyObject *obj)
{
return obj;
}Самое удивительное, что это заработало. Больше всего меня пугает, что я до конца не понимаю почему и какие последствия влечёт.
cython_experiments.h
#include "Python.h"
static PyObject * convert_to_pyobject(PyObject *obj)
{
return obj;
}cython_experiments.pyx
# -*- coding: utf-8 -*-
# distutils: language = c++
# distutils: include=['./']
# distutils: extra_compile_args=["-O1"]
from __future__ import unicode_literals
import time
from libc.stdlib cimport free
from cpython.dict cimport PyDict_New, PyDict_SetItemString
from cpython.ref cimport PyObject
from libcpp.string cimport string
from libcpp.vector cimport vector
cdef extern from "cython_experiments.h":
PyObject* convert_to_pyobject(object obj)
ctypedef vector[PyObject*] dict_vec
range_attempts = 10 ** 6
# Insert time
cdef test_list():
t_start = time.time()
data_list = list()
for i from 0 <= i < range_attempts:
data_list.append(dict(
name = 'test_{}'.format(i),
test_data = i,
test_data2 = str(i),
test_data3 = range(10),
))
del data_list
return time.time() - t_start
cdef test_vector():
t_start = time.time()
cdef dict_vec *data_list
data_list = new dict_vec()
data_list.resize(range_attempts)
for i from 0 <= i < range_attempts:
data = PyDict_New()
PyDict_SetItemString(data, 'name', 'test_{}'.format(i))
PyDict_SetItemString(data, 'test_data', i)
PyDict_SetItemString(data, 'test_data2', str(i))
PyDict_SetItemString(data, 'test_data3', range(10))
data_list.push_back(convert_to_pyobject(data))
free(data_list)
return time.time() - t_start
# Get statistic
times = dict(list=[], vector=[])
attempts = 100
for i from 0 <= i < attempts:
times['list'].append(test_list())
times['vector'].append(test_vector())
print('''
Attempt: {}
List time: {}
Vector time: {}
'''.format(i, times['list'][-1], times['vector'][-1]))
avg_list = sum(times['list']) / attempts
avg_vector = sum(times['vector']) / attempts
print('''
Statistics:
attempts: {}
list avg time: {}
vector avg time: {}
'''.format(attempts, avg_list, avg_vector))Попытка 1
Очень хочется, чтобы можно было собирать *.whl для проекта и чтобы это всё завелось на практически любой системе, поэтому сперва был выставлен флаг оптимизации в 0. Это привело к странному результату:
Python 2.7
Statistics:
attempts: 100
list avg time: 2.61709237576
vector avg time: 2.92562381506Немного поразмыслив, решил что мы всё равно используем флаг -O1, поэтому выставил всё же его и получил:
Python 2.7
Statistics:
attempts: 100
list avg time: 2.49274396896
vector avg time: 0.922211170197Как-то немного взгруснулось: всё же вера в профессионализм Гвидо и Ко меня подвела. Но потом, я заметил что как-то подозрительно жрёт память скрипт и к концу он подъедал примерно 20Гб ОЗУ. Проблема была в следующем: в итоговом скрипте, можно наблюдать функцию free, после прохода цикла. На этой итерации его ещё не было. Тогда я подумал...
А не отключить ли мне gc?
Между попытками я сделал gc.disable() и после попытки gc.enable(). Запускаю сборку и скрипт и получаю:
Python 2.7
Statistics:
attempts: 100
list avg time: 1.00309731514
vector avg time: 0.941153049469В целом, разница не большая, поэтому я подумал, что нет смысла переплачивать стараться как-то извратиться и просто использовать CPython, но собирать его по прежнему Cython'ом.
Наверное у многих возник вопрос: "А что там с памятью?" Самое удивительное (нет), что ничего. Она росла с такой же скоростью и в таком же количестве. На ум пришла статья, но лезть в исходники Python совсем не хотелось. Да и означало это лишь одно — проблема в реализации вектора.
Финал
После долгих мучений с приведением типов, а именно, чтобы вектор принимал в себя pointer на словарь, был получен тот самый итоговый скрипт и с включённым gc я получал в среднем разницу в 2.6 раза (вектор быстрее) и относительно хорошую работу с памятью.
Вдруг до меня дошло, что я собираю всё только под Py2.7 и даже не попробовал сделать что-либо с 3.6.
И вот тут я реально удивился (после предыдущих результатов, удивление было закономерным):
Python 3.6
Statistics:
attempts: 100
list avg time: 0.8771139788627624
vector avg time: 1.075702157020569
Python 2.7
Statistics:
attempts: 100
list avg time: 2.61709237576
vector avg time: 0.92562381506При всём при этом, gc по прежнему работал, память не отжиралась и это был один и тот же скрипт. Понимая, что через уже чуть больше года, нужно будет распрощаться с 2.7, мне всё равно не давало покоя, что между ними такая разница. Чаще всего, я слышал/читал/экспериментировал и Py3.6 был медленнее Py2.7. Однако ребята из Cython-разработчиков сделали что-то невероятное и поменяли ситуацию на корню.
Итог
После этого эксперимента, мы решили сильно не заморачиваться с поддержкой Python 2.7 и переделкой каких-либо частей приложений на C++, просто потому что оно того не стоит. Всё уже написали до нас, нам остаётся это лишь правильно применить для решения конкретной задачи.
UPD 24.12.2018:
По совету iCpu и после выпадов в сторону, что проверяется непонять что и как, постарался переписать C++ часть максимально удобным для разработки в дальнейшем способом, а так же минимизировать абстракции. Получилось ещё хуже:
cython_experiments.h
#include "Python.h"
#include <vector>
#include <algorithm>
#ifndef PyString_AsString
#define PyString_AsString PyUnicode_AsUTF8
#define PyString_FromString PyUnicode_FromString
#endif
typedef struct {
char* name;
bool reverse;
} sortFiled;
class cmpclass {
public:
cmpclass(std::vector<char*> fields) {
for (std::vector<char*>::iterator it = fields.begin() ; it < fields.end(); it++){
bool is_reverse = false;
char* name;
if (it[0] == "-"){
is_reverse = true;
for(int i=1; i<strlen(*it); ++i)
name[i] = *it[i];
}
else {
name = *it;
}
sortFiled field = {name, is_reverse};
this->fields_to_cmp.push_back(field);
}
}
~cmpclass() {
this->fields_to_cmp.clear();
this->fields_to_cmp.shrink_to_fit();
}
bool operator() (PyObject* left, PyObject* right) {
//
bool result = false;
for (std::vector<sortFiled>::iterator it = this->fields_to_cmp.begin() ; it < this->fields_to_cmp.end(); it++){
//
PyObject* str_name = PyString_FromString(it->name);
PyObject* right_value = PyDict_GetItem(right, str_name);
PyObject* left_value = PyDict_GetItem(left, str_name);
if(!it->reverse){
result = left_value < right_value;
} else {
result = (left_value > right_value);
}
PyObject_Free(str_name);
if(!result)
return false;
}
return true;
}
private:
std::vector<sortFiled> fields_to_cmp;
};
void vector_multikeysort(std::vector<PyObject *> items, PyObject* columns, bool reverse)
{
std::vector<char *> _columns;
for (int i=0; i<PyList_GET_SIZE(columns); ++i) {
PyObject* item = PyList_GetItem(columns, i);
char* item_str = PyString_AsString(item);
_columns.push_back(item_str);
}
cmpclass cmp_obj(_columns);
std::sort(items.begin(), items.end(), cmp_obj);
if(reverse)
std::reverse(items.begin(), items.end());
}
std::vector<PyObject *> _test_vector(PyObject* store_data_list, PyObject* columns, bool reverse = false)
{
int range_attempts = PyList_GET_SIZE(store_data_list);
std::vector<PyObject *> data_list;
for (int i=0; i<range_attempts; ++i) {
data_list.push_back(PyList_GetItem(store_data_list, i));
}
vector_multikeysort(data_list, columns, reverse);
return data_list;
}cython_experiments.pyx
# -*- coding: utf-8 -*-
# distutils: language = c++
# distutils: include=['./']
# distutils: extra_compile_args=["-O2", "-ftree-vectorize"]
from __future__ import unicode_literals
import time
from libc.stdlib cimport free
from cpython.dict cimport PyDict_New, PyDict_SetItemString
from cpython.ref cimport PyObject
from libcpp.string cimport string
from libcpp.vector cimport vector
import gc
cdef extern from "cython_experiments.h":
vector[PyObject*] _test_vector(object store_data_list, object columns, int reverse)
range_attempts = 10 ** 6
store_data_list = list()
for i from 0 <= i < range_attempts:
store_data_list.append(dict(
name = 'test_{}'.format(i),
test_data = i,
test_data2 = str(i),
test_data3 = range(10),
))
# Insert time
def multikeysort(items, columns, reverse=False):
items = list(items)
columns = list(columns)
columns.reverse()
for column in columns:
# pylint: disable=cell-var-from-loop
is_reverse = column.startswith('-')
if is_reverse:
column = column[1:]
items.sort(key=lambda row: row[column], reverse=is_reverse)
if reverse:
items.reverse()
return items
cdef test_list():
t_start = time.time()
data_list = list()
for i in store_data_list:
data_list.append(i)
data_list = multikeysort(data_list, ('name', '-test_data'), True)
for i in data_list:
i
del data_list
return time.time() - t_start
cdef test_vector():
t_start = time.time()
data_list = _test_vector(store_data_list, ['name', '-test_data'], 1)
for i in data_list:
i
return time.time() - t_start
# Get statistic
times = dict(list=[], vector=[])
attempts = 10
gc.disable()
for i from 0 <= i < attempts:
times['list'].append(test_list())
times['vector'].append(test_vector())
gc.collect()
print('''
Attempt: {}
List time: {}
Vector time: {}
'''.format(i, times['list'][-1], times['vector'][-1]))
del store_data_list
avg_list = sum(times['list']) / attempts
avg_vector = sum(times['vector']) / attempts
print('''
Statistics:
attempts: {}
list avg time: {}
vector avg time: {}
'''.format(attempts, avg_list, avg_vector))
Python 3.6
Statistics:
attempts: 10
list avg time: 0.2640914678573608
vector avg time: 2.5774293661117555 Есть идеи, что можно было бы улучшить в копараторе, чтобы это работало быстрее?
