История одного эксперимента с Cython и C++ vector

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