Прирост в производительности после переноса алгоритма с Python на C++/C?

Question

[shstkv_a]

Здравствуйте. В Пайтоне сейчас используются примерно такие блоки кода:
Для парсинга строк:

content = contents(rcsb)
    atoms = []
    for line in content:
        if line[0] == 'ATOM':
            atom = [list(map(int, line[1:2])), line[2], line[3], line[5], line[8],
                    list(map(float, line[10:13])), ]
            atoms.append(atom)
    return atoms

Для вычислений:

x2, y2, z2 = sympy.symbols('x y z', real=True)
            eq2 = sympy.Eq((x2 - x0) ** 2 + (y2 - y0) ** 2, atom00 ** 2 - (z2 - z0) ** 2)
            eq3 = sympy.Eq((x2 - x1) ** 2 + (y2 - y1) ** 2, atom11 ** 2 - (z2 - z1) ** 2)
            eq4 = sympy.Eq(z2, (z0 + z1) / 2)

            answer1 = sympy.solve([eq2, eq3, eq4])
            answer0 = []
            for q in answer1[1:2]:
                for k, i in q.items():
                    if k == x2:
                        answer0.append(i)

                    if k == y2:
                        answer0.append(i)

                    if k == z2:
                        answer0.append(i)

            V1 = sympy.Matrix([x1, y1, z1])
            E = sympy.Matrix([(x0 - x1) / length, (y0 - y1) / length, (z0 - z1) / length])
            if len(answer0) > 1:
                A = sympy.Matrix([answer0[0] - x1, answer0[1] - y1, answer0[2] - z1])
                x, y, z = E[0], E[1], E[2]
                coordinates = []
                i = 1
                while i <= precision: 
                    t = (2 * math.pi / precision) * i
                    M = sympy.Matrix(
                        [[(math.cos(t) + (1 - math.cos(t)) * x ** 2), ((1 - math.cos(t)) * x * y - math.sin(t) * z),
                          ((1 - math.cos(t)) * x * z + math.sin(t) * y)],
                         [((1 - math.cos(t)) * x * y + math.sin(t) * z), (math.cos(t) + (1 - math.cos(t)) * y ** 2),
                          ((1 - math.cos(t)) * y * z - math.sin(t) * x)],
                         [((1 - math.cos(t)) * x * z - math.sin(t) * y), ((1 - math.cos(t)) * y * z + math.sin(t) * x),
                          (math.cos(t) + (1 - math.cos(t)) * z ** 2)]])
                    coord_sympy = M * A + V1
                    xa, ya, za = float(coord_sympy[0]), float(coord_sympy[1]), float(coord_sympy[2])
                    coordinate = [xa, ya, za]
                    coordinates.append(coordinate)
                    i += 1

Еще есть перемножение матриц, умножение векторов, сложение и вычитание.
Код в вычислении матрицы поворота у меня занимает 0.6-0.9 секунд, а текст парсится практически мгновенно на пайтоне. Активно используется динамическая типизация, списки, словари и функции с 8-12 параметрами. Время работы алгоритма 26-28 минут. Хочется быстрее. С другими языками программирования (ЯП) не работал.
Вопросы:
Какой ЯП выбрать для изучения и на какие его разделы уделить внимание, чтобы перенести код программы как можно быстрее (в течение года)? Во сколько раз ожидать прироста в производительности работы алгоритма? Планируется, чтобы будущая приложение работало на сервере - ЯП важен? Или может библиотеку другую?
Спасибо за внимание.

Comments

[Viktor T2]

SymPy поддерживает кодогенерацию.
То есть с вашего пайтон кода сгенрит Си или плюсовую програмку.
Я правда не пробовал.
Языки: Си - простой язык, плюсы - сложный замороченый язык.
В зависимости от, выйгрыш в скорости может не стоить того,
чтоб так заморочиться.
https://www.google.com/search?q=sympy+code+generat...

[shstkv_a]

Viktor T2, Ну, если в плюсах матрица поворота выполняется в 10 раз быстрее, чем здесь, то я думаю стоит переносить алгоритм. Однако я не знаю быстрее или нет, а проверить пока не смог, хотя, думаю не так это и сложно.

[Viktor T2]

shstkv_a, С чего ей выполнятся быстрее...
Все уже давно заоптимизировано, переоптимизировано вплоть до машинных кодов.
Тем более в 10 раз.
Хех.

[Viktor T2]

shstkv_a, Можно еще ChatGPT попытать,
только не в плане кода, а в плане алгоритма решения задачи.
Был один удачный случай, когда ChatGPT подсказал
не очевидный алгоритм.

[mayton2019]

Наблюдение. Я не использовал никогда sympy. Вот что пишут на сайте

SymPy is a Python library for symbolic mathematics.

Символические вычисления - это формульные вычисления. Тоесть вместо того чтобы 2/3 преобразовать
в вещесвтенное 0.6666666666666 такие библиотеки сохраняют семантику выражения и используют
ее до конца вычислений. Я считаю что это не самый быстрый способ считать и его имеет смысл
использовать лишь для доказательства теорем.

Поэтому для разгона я-бы первым делом отказался от Симпи и взять другую более близкую
к численным методам библиотеку.

Answer 1

[Everything_is_bad]

Хочется быстрее.

начни с поиска узких мест и их оптимизации, так же можно попробовать pypy, после этого стоит рассмотреть cython

Какой ЯП выбрать для изучения

любой популярный компилируемый

Во сколько раз ожидать прироста в производительности работы алгоритма

неизвестно, в активных вычислениях может быть на порядок, но так же всегда можно написать кривую реализацию и только всё замедлить

Comments

[Viktor T2]

shstkv_a, Everything_is_bad Вот соглашусь, что начать надо с профилирования
Статейка https://habr.com/ru/companies/ruvds/articles/757336/

Answer 2

[Vindicar]

У тебя вычисление повторяется для каждой строки? Посмотри, можно ли распараллелить код на несколько процессов (именно процессов, не потоков).
Также посмотри насчёт использования numpy/scipy и их численных солверов для систем уравнений вместо sympy. Может, используя sympy, получится сформулировать алгоритм расчёта, а уже его портировать на numpy?

Если надумаешь использовать numpy, держи в уме вот что: по возможности выполняй операции сразу над массивами значений. Упрощённо, вот это

a = numpy.array([3] * 1000000, dtype=numpy.float32)
b = 2 * a + 3

будет намного быстрее, чем это:

a = numpy.array([3] * 1000000, dtype=numpy.float32)
b = numpy.zeros_like(a)
for i in range(a.shape[0]):
    b[i] = 2 * a[i] + 3

Причина простая - операции над массивами реализуют перебор элементов массива нативно, т.е. с той же проивзодительностью, что и C/C++/Fortran. А вот сугубо питоньи циклы - штука медленная.

Comments

[shstkv_a]

Да, вычисление повторяется для каждой строки, только x, y, z разные. В NymPy не нашел способ решения для уравнений с тремя переменными. Примерно подсчитал, что решение уравнения занимает 0.06-0.09 секунд, основное время (0.5 секунд) уходит на циклы, количество которых зависит от precision. Спасибо. А как узнать: "можно распараллелить или нет?"

[Vindicar]

shstkv_a, если решение строки не зависит от решений других строк - то скорее всего можно.
Проще всего будет, если ты завернёшь решение в функцию, которая принимает простую структуру данных и возвращает простую структуру данных. Скажем, принимает строку из файла - возвращает кортеж чисел. Тогда через multiprocessing.Pool.map() можно будет достаточно просто распихать вызовы этой функции по процессам, а потом собрать обратно их результаты.

Насчёт солвера: numpy из коробки умеет только систему линейных уравнений решать, а у тебя, кажется, квадратичная, пусть и с двумя переменными (уравнение для z у тебя тривиальное, так что его значение ты вроде как знаешь). Свести к линейной системе через замену t = x^2 твои уравнения вроде не получится (хотя я могу быть и не прав).

А раз так, смотри в сторону пакета scipy, в частности, scipy.optimize.fsolve(). Проблема в том, что численным методам нужна какая-то "точка отсчёта" - начальное приближение для корней системы. Как его выбрать - смотри сам. Может, есть какое-то осмысленное значение, может, банальный 0;0 сойдёт.

Ещё один вариант - заменить на numpy расчёты с матрицами, уж с этим-то он справится. А вот поиск решения оставить на sympy. Но тут надо замерять, сколько времени уходит на эти шаги, и есть ли смысл в такой экономии.

[shstkv_a]

Vindicar, Это, надеюсь мне не кажется, исчерпывающий ответ о пайтоне. Спасибо! С использованием сразу С++ или других ЯП удастся ускорить, например на 1-2 порядка?) Может это риторический вопрос?

[Viktor T2]

shstkv_a, А можно в цифрах?
Размеры исходного массива,
количество итераций в цикле,
тогда очевидно можно оценить экономию в милисекундах

[U235U235]

shstkv_a, а вы сумеете написать символьный сольвер на С++? Это нетривиальная задача, как мне кажется...

[shstkv_a]

Viktor T2, массив в 500-1000 пар минимум, циклов 36. 36 циклов прогоняется за 0.6-0.9 секунд. То есть если решать это вычисление за мгновение, то 28 минут превратятся в 22 минуты. В алгоритме много еще условий и вложенных циклов, может поэтому тормозит. Выше посоветовали профилирование стэка, нужно взглянуть. Оптимизация пока не горит, но этот сценарий планируется использовать несколько десятков, может, сотен раз на одного пользователя, что превращается в 10 + часов. Не ладно. Поэтому хотелось бы ускорить, ну, на несколько порядков минимум. Возможно алгоритм не годный (ранняя разработка). Ниже пример разных вложений; похожее используется практически в каждой функции:

for i, p_atom0 in enumerate(p_atoms):
        for k0, v0 in c_a.items():
            if p_atom0[3] in k0:
                if p_atom0[2] in v0:
                    x0, y0, z0 = round(p_atom0[5][0], 1), round(p_atom0[5][1], 1), round(p_atom0[5][2], 1)
                    """Second loop"""
                    for p_atom1 in p_atoms_copy:
                        for k1, v1 in c_a.items():
                            if p_atom1[3] in k1:
                                if p_atom1[2] in v1:
                                    if p_atom1 != p_atom0:
                                        x1, y1, z1 = round(p_atom1[5][0], 1), round(p_atom1[5][1], 1), round(p_atom1[5][2], 1)

[shstkv_a]

U235U235, Суметь-то можно, вопрос во времени. Полагаю, для написания сольвера не достаточно знания структур данных и синтаксиса? Мне кажется, проблема даже не в сольвере.

[Vindicar]

shstkv_a, погоди-ка, а что ты этой конструкцией пытаешься добиться? Найти взаимодействующие пары атомов? или что? Объясни, пожалуйста, смысл данных в c_a.

Ну и до кучи, у тебя в M = sympy.Matrix(...) довольно брутальные вещи творятся. По стопицот раз вычисляешь синус и косинус одного и того же числа, а это небыстрая операция! Ну и опять же, там numpy вот прям напрашивается...

[shstkv_a]

Vindicar, Совершенно верно. Из словаря c_a извлекаются коэффициенты функциональных групп аминокислот. M - матрица поворота, другого не дано...
Спасибо за обратную связь.

[Vindicar]

shstkv_a, я просто задумался, не проще ли было бы пройтись по c_a один раз и составить список пар, кто с кем взаимодействует. А потом уже идти по этому списку. Ну да тебе виднее, будет ли от этого выигрыш.

[shstkv_a]

Vindicar, Спасибо! Обязательно попробую как начнется процесс оптимизации.

[shstkv_a]

Vindicar, Кстати насчет процессов. Никогда это не делал, но полагаю, что массив из 1000 возможно поделить на число ядер - то есть сделать 6 процессов и на первых пяти происходят вычисления для 199 пар, а на 6-м ядре для 5 пар. Вопрос (каюсь, нарушаю правила): сейчас 1 процесс загружает 4-6% проца, значит ли, что на шести процессах загрузка будет 24-30 % вместе с ростом производительности в 5 раз? Как возможно увеличить загрузку проца для одного процесса в пайтоне (если меньше ядер, но выше частота)? Спасибо.

[Vindicar]

shstkv_a, а тут всё очень сложно, увы. Число ядер необязательно равно числу одновременно работающих потоков. Процессорное время выделяется именно потокам, просто потоки в Питоне всё ещё... того. Неэффективны для вычислений. Приходится воевать с процессами.
Я бы просто поиграл числом одновременно работающих процессов-воркеров в поисках оптимума, каким бы он не оказался. А дальше уже совершенствовал бы сам воркер.
И да, посмотри в сторону ссылки на map() выше - незачем самому резать массив на дольки, если можно просто скармливать значения из коллекции воркерам. Ты вполне можешь итерироваться прямо по исходному файлу, отдавая воркеру строку - а дальше пусть он сам всё делает.

[shstkv_a]

Спасибо большое!