Одним тёплым холодным зимним вечером, хотелось согреться в офисе и проверить теорию одного коллеги, что 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
Есть идеи, что можно было бы улучшить в копараторе, чтобы это работало быстрее?
