Ускорьте Python до 150 раз с помощью C

Практическое руководство по переносу критически важного для производительности кода на язык C без отказа от Python.

Делиться

Если вы программируете на Python, рано или поздно вы столкнётесь с проблемой скорости выполнения кода. Если вы когда-либо писали сложные алгоритмы на Python, например, для вычисления расстояния между строками, для работы с матрицами или для криптографического хеширования, вы поймёте, о чём я.

Конечно, бывают случаи, когда внешние библиотеки, такие как NumPy, могут прийти на помощь, но что, если алгоритм изначально последовательный? Именно это и было моей проблемой, когда я хотел протестировать конкретный алгоритм, определяющий количество правок, необходимых для преобразования одной строки в другую.

Я попробовал Python. Попробовал NumPy. А потом обратился к C — языку, который я впервые изучил в колледже несколько десятилетий назад, но из-за злости не использовал его около 15 лет. Вот тут-то и началось самое интересное.

Сначала мне нужно было ответить на вопрос: «Можно ли вызвать C из Python?». После небольшого исследования быстро стало ясно, что ответ действительно «да ». На самом деле, оказывается, это можно сделать несколькими способами, и в этой статье я рассмотрю три наиболее распространённых.

От самого простого к самому сложному мы рассмотрим использование

• подпроцесс
• ctypes
• Расширения Python C

Алгоритм, который мы будем тестировать, называется алгоритмом расстояния Левенштейна (LD) . Расстояние Левенштейна между двумя словами — это минимальное количество односимвольных правок (вставок, удалений или замен), необходимых для преобразования одного слова в другое. Он назван в честь советского математика Владимира Левенштейна, который определил эту метрику в 1965 году. Она применяется в различных программах, таких как программы проверки орфографии и системы оптического распознавания символов.

Чтобы вы лучше поняли, о чем идет речь, приведем несколько примеров.

Рассчитайте LD между словами «книга» и «черный».

1. книга → баок (замена «о» на «а»),
2. baok → back (замена «o» на «c»)
3. назад → черный (добавьте букву «л»)

Таким образом, LD в данном случае равен трем.

Рассчитайте LD между словами «superb» и «super».

1. superb → super (убрать букву «b»)

В данном случае ЛД — просто единица.

Мы напишем код алгоритма LD на Python и C, а затем настроим тесты для проверки того, сколько времени потребуется для его запуска с использованием чистого кода Python по сравнению со временем, необходимым для его запуска с использованием кода C, вызванного из Python.

Предпосылки

Поскольку я работал в MS Windows, мне требовался способ компилировать программы на языке C. Проще всего было скачать инструменты сборки Visual Studio Build 2022. Они позволяют компилировать программы на языке C в командной строке.

Чтобы установить Visual Studio, сначала перейдите на главную страницу загрузок. На втором экране вы увидите строку поиска. Введите «Build Tools» в поле поиска и нажмите «Поиск». В результате поиска должен появиться следующий экран:

Нажмите кнопку «Загрузить» и следуйте инструкциям по установке. После установки в окне терминала DOS при нажатии на кнопку с маленьким плюсом для открытия нового терминала вы увидите опцию «Открыть командную строку разработчика для VS 2022».

Большая часть моего кода Python будет выполняться в Jupyter Notebook, поэтому вам следует настроить новую среду разработки и установить Jupyter. Сделайте это сейчас, если хотите продолжить. В этой части я использую инструмент UV, но вы можете использовать любой удобный для вас метод.

c:> uv init pythonc c:> cd pythonc c:> uv venv pythonc c:> source pythonc/bin/activate (pythonc) c:> uv pip install jupyter

Алгоритм LD на языке C

Нам нужны немного разные версии алгоритма LD на языке C, в зависимости от метода его вызова. Это версия для нашего первого примера, где мы используем подобработку для вызова исполняемого файла C.

1/ подобработка: lev_sub.c

#include #include #include static int levenshtein(const char* a, const char* b) { size_t n = strlen(a), m = strlen(b); if (n == 0) return (int)m; if (m == 0) return (int)n; int* prev = (int*)malloc((m + 1) * sizeof(int)); int* curr = (int*)malloc((m + 1) * sizeof(int)); if (!prev || !curr) { free(prev); free(curr); return -1; } for (size_t j = 0; j <= m; ++j) prev[j] = (int)j; for (size_t i = 1; i <= n; ++i) { curr[0] = (int)i; char ca = a[i - 1]; for (size_t j = 1; j <= m; ++j) { int cost = (ca == b[j - 1]) ? 0 : 1; int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + cost; int d = del < ins ? del : ins; curr[j] = d < sub ? d : sub; } int* tmp = prev; prev = curr; curr = tmp; } int ans = prev[m]; free(prev); free(curr); return ans; } int main(int argc, char** argv) { if (argc != 3) { fprintf(stderr, "usage: %s n», argv[0]); return 2; } int d = levenshtein(argv[1], argv[2]); if (d < 0) return 1; printf("%dn", d); return 0; }

Чтобы скомпилировать это, запустите новую командную строку разработчика для VS Code 2022 и введите следующее, чтобы убедиться, что мы оптимизируем компиляцию для 64-битной архитектуры.

(pythonc) c:> «%VSINSTALLDIR%VCAuxiliaryBuildvcvarsall.bat» x64

Далее мы можем скомпилировать наш код на языке C с помощью этой команды.

(pythonc) c:> cl /O2 /Fe:lev_sub.exe lev_sub.c

Это создаст исполняемый файл.

Сравнительный анализ кода подобработки

В блокноте Jupyter введите следующий код, который будет использоваться во всех наших тестах. Он генерирует случайные строки в нижнем регистре длиной N и вычисляет количество правок, необходимых для преобразования строки string1 в строку string2.

# Подпроцесс бенчмарка import time, random, string, subprocess import numpy as np EXE = r»lev_sub.exe» def rnd_ascii(n): return ''.join(random.choice(string.ascii_lowercase) for _ in range(n)) def lev_py(a: str, b: str) -> int: n, m = len(a), len(b) if n == 0: return m if m == 0: return n prev = list(range(m+1)) curr = [0]*(m+1) for i, ca in enumerate(a, 1): curr[0] = i for j, cb in enumerate(b, 1): cost = 0 if ca == cb else 1 curr[j] = min(prev[j] + 1, curr[j-1] + 1, prev[j-1] + cost) prev, curr = curr, prev return prev[m]

Далее следует сам код бенчмаркинга и результаты прогона. Для запуска части кода на языке C мы запускаем подпроцесс, который выполняет скомпилированный файл кода на языке C, созданный ранее, и измеряет время выполнения, сравнивая его с методом на чистом Python. Мы запускаем каждый метод на наборах из 2000 и 4000 случайных слов три раза и выбираем лучшее время.

def lev_subprocess(a: str, b: str) -> int: out = subprocess.check_output([EXE, a, b], text=True) return int(out.strip()) def bench(fn, *args, repeat=3, warmup=1): for _ in range(warmup): fn(*args) best = float(«inf»); out_best = None for _ in range(repeat): t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() — t0 if dt < best: best, out_best = dt, out return out_best, best if __name__ == "__main__": cases = [(2000,2000),(4000, 4000)] print("Тест производительности: Python против C (подпроцесс)n") for n, m in cases: a, b = rnd_ascii(n), rnd_ascii(m) py_out, py_t = bench(lev_py, a, b, repeat=3) sp_out, sp_t = bench(lev_subprocess, a, b, repeat=3) print(f"n={n} m={m}") print(f" Python : {py_t:.3f}s -> {py_out}») print(f» Подпроцесс : {sp_t:.3f}s -> {sp_out}n»)

Вот результаты.

Тест производительности: Python против C (подпроцесс) n=2000 m=2000 Python: 1,276 с -> 1768 Подпроцесс: 0,024 с -> 1768 n=4000 m=4000 Python: 5,015 с -> 3519 Подпроцесс: 0,050 с -> 3519

Это довольно существенное улучшение времени выполнения C по сравнению с Python.

2. ctypes: lev.c

ctypes — это библиотека интерфейса внешних функций (FFI) , встроенная непосредственно в стандартную библиотеку Python. Она позволяет загружать и вызывать функции из общих библиотек, написанных на C (DLL-библиотеки в Windows, файлы .so в Linux, .dylib в macOS), непосредственно из Python , без необходимости писать полноценный модуль расширения на C.

Во-первых, вот наша версия алгоритма LD на языке C, использующая ctypes. Она практически идентична нашей функции subprocess C, с добавлением строки, которая позволяет использовать Python для вызова DLL после её компиляции.

/* * lev.c */ #include #include /* строка ниже включает эту функцию в таблицу экспорта DLL, * чтобы другие программы могли ее использовать. */ __declspec(dllexport) int levenshtein(const char* a, const char* b) { size_t n = strlen(a), m = strlen(b); if (n == 0) return (int)m; if (m == 0) return (int)n; int* prev = (int*)malloc((m + 1) * sizeof(int)); int* curr = (int*)malloc((m + 1) * sizeof(int)); if (!prev || !curr) { free(prev); free(curr); return -1; } for (size_t j = 0; j <= m; ++j) prev[j] = (int)j; для (size_t i = 1; i <= n; ++i) { curr[0] = (int)i; char ca = a[i - 1]; для (size_t j = 1; j <= m; ++j) { int cost = (ca == b[j - 1]) ? 0 : 1; int del = prev[j] + 1; int ins = curr[j - 1] + 1; int sub = prev[j - 1] + cost; int d = del < ins ? del : ins; curr[j] = d < sub ? d : sub; } int* tmp = prev; prev = curr; curr = tmp; } int ans = prev[m]; free(prev); free(curr); return ans; }

При использовании ctypes для вызова C в Python нам необходимо преобразовать наш C-код в динамическую библиотеку (DLL), а не в исполняемый файл. Вот команда сборки, которая вам для этого нужна.

(pythonc) c:> cl /O2 /LD lev.c /Fe:lev.dll

Сравнительный анализ кода ctypes

В этом фрагменте кода я опускаю функции Python lev_py и rnd_ascii , поскольку они идентичны функциям в предыдущем примере. Перепишите это в свой блокнот.

#ctypes benchmark import time, random, string, ctypes import numpy as np DLL = r»lev.dll» levdll = ctypes.CDLL(DLL) levdll.levenshtein.argtypes = [ctypes.c_char_p, ctypes.c_char_p] levdll.levenshtein.restype = ctypes.c_int def lev_ctypes(a: str, b: str) -> int: return int(levdll.levenshtein(a.encode('utf-8'), b.encode('utf-8'))) def bench(fn, *args, repeat=3, warmup=1): for _ in range(warmup): fn(*args) best = float(«inf»); out_best = None for _ in range(repeat): t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() — t0 if dt < best: best, out_best = dt, out return out_best, best if __name__ == "__main__": cases = [(2000,2000),(4000, 4000)] print("Тест производительности: Python против NumPy против C (ctypes)n") for n, m in cases: a, b = rnd_ascii(n), rnd_ascii(m) py_out, py_t = bench(lev_py, a, b, repeat=3) ct_out, ct_t = bench(lev_ctypes, a, b, repeat=3) print(f"n={n} m={m}") print(f" Python : {py_t:.3f}s -> {py_out}») print(f» ctypes : {ct_t:.3f}s -> {ct_out}n»)

И каковы результаты?

Тест производительности: Python против C (ctypes) n=2000 m=2000 Python: 1,258 с -> 1769 ctypes: 0,019 с -> 1769 n=4000 m=4000 Python: 5,138 с -> 3521 ctypes: 0,035 с -> 3521

Результаты очень похожи на результаты в первом примере.

3/ Расширения Python C: lev_cext.c

Использование расширений Python C требует немного больше работы. Сначала давайте рассмотрим код C. Базовый алгоритм не изменился. Нужно лишь добавить немного дополнительных структур, чтобы код можно было вызывать из Python. Он использует API CPython (Python.h) для разбора аргументов Python, запуска кода C и возврата результата в виде целого числа Python.

Функция levext_lev действует как обёртка. Она анализирует два строковых аргумента из Python (PyArg_ParseTuple), вызывает функцию C lev_impl для вычисления расстояния, обрабатывает ошибки памяти и возвращает результат в виде целого числа Python (PyLong_FromLong). В таблице «Methods» эта функция зарегистрирована под именем «levenshtein», поэтому её можно вызывать из кода Python. Наконец, функция PyInit_levext определяет и инициализирует модуль levext , делая его импортируемым в Python с помощью команды import levext.

#include #include #include static int lev_impl(const char* a, const char* b) { size_t n = strlen(a), m = strlen(b); если (n == 0) вернуть (int)m; если (m == 0) вернуть (int)n; int* prev = (int*)malloc((m + 1) * sizeof(int)); int* curr = (int*)malloc((m + 1) * sizeof(int)); если (!prev || !curr) { free(prev); free(curr); вернуть -1; } for (size_t j = 0; j <= m; ++j) prev[j] = (int)j; for (size_t i = 1; i <= n; ++i) { curr[0] = (int)i; char ca = a[i - 1]; for (size_t j = 1; j <= m; ++j) { int cost = (ca == b[j - 1]) ? 0 : 1; int del = prev[j] + 1, ins = curr[j - 1] + 1, sub = prev[j - 1] + cost; int d = del < ins ? del : ins; curr[j] = d < sub ? d : sub; } int* tmp = prev; prev = curr; curr = tmp; } int ans = prev[m]; free(prev); free(curr); return ans; } static PyObject* levext_lev(PyObject* self, PyObject* args) { const char *a, *b; если (!PyArg_ParseTuple(args, "ss", &a, &b)) return NULL; int d = lev_impl(a, b); если (d < 0) { PyErr_SetString(PyExc_MemoryError, "alloc failed"); return NULL; } return PyLong_FromLong(d); } static PyMethodDef Methods[] = { {"levenshtein", levext_lev, METH_VARARGS, "расстояние Левенштейна"}, {NULL, NULL, 0, NULL} }; static struct PyModuleDef mod = { PyModuleDef_HEAD_INIT, "levext", NULL, -1, Methods }; PyMODINIT_FUNC PyInit_levext(void) { return PyModule_Create(&mod); }

Поскольку на этот раз мы создаем не просто исполняемый файл, а собственный модуль расширения Python, нам придется построить код C по-другому.

Этот тип модуля должен быть скомпилирован с заголовками Python и соответствующим образом связан со средой выполнения Python, чтобы он вел себя как встроенный модуль Python.

Для этого мы создаём модуль Python setup.py, который импортирует библиотеку setuptools для упрощения процесса. Он автоматизирует:

• Поиск правильных путей включения для Python.h
• Передача правильных флагов компилятора и компоновщика
• Создание файла .pyd с правильным именованием для вашей версии Python и платформы

Делать это вручную с помощью команды компилятора cl было бы утомительно и подвержено ошибкам, поскольку вам пришлось бы вручную указывать все эти пути и флаги.

Вот код, который нам нужен.

из setuptools import setup, Extension setup( name=»levext», version=»0.1.0″, ext_modules=[Extension(«levext», [«lev_cext.c»], extra_compile_args=[«/O2»])], )

Мы запускаем его, используя обычный Python в командной строке, как показано здесь.

(pythonc) c:> python setup.py build_ext —inplace #вывод запуск build_ext копирование buildlib.win-amd64-cpython-312levext.cp312-win_amd64.pyd ->

Сравнительный анализ кода расширений Python C

Теперь, вот код Python для вызова нашего C. Опять же, я опустил две вспомогательные функции Python, которые не изменились по сравнению с предыдущими примерами.

# c-ext benchmark import time, random, string import numpy as np import levext # убедитесь, что levext.cp312-win_amd64.pyd собран и его можно импортировать def lev_extension(a: str, b: str) -> int: return levext.levenshtein(a, b) def bench(fn, *args, repeat=3, warmup=1): for _ in range(warmup): fn(*args) best = float(«inf»); out_best = None for _ in range(repeat): t0 = time.perf_counter(); out = fn(*args); dt = time.perf_counter() — t0 if dt < best: best, out_best = dt, out return out_best, best if __name__ == "__main__": cases = [(2000, 2000), (4000, 4000)] print("Тест производительности: Python против NumPy против C (расширение C)n") for n, m in cases: a, b = rnd_ascii(n), rnd_ascii(m) py_out, py_t = bench(lev_py, a, b, repeat=3) ex_out, ex_t = bench(lev_extension, a, b, repeat=3) print(f"n={n} m={m} ") print(f" Python : {py_t:.3f}s -> {py_out}») print(f» C ext : {ex_t:.3f}s -> {ex_out}n»)

Вот что получилось.

Тест производительности: Python против C (расширение C) n=2000 m=2000 Python: 1,204 с -> 1768 C ext: 0,010 с -> 1768 n=4000 m=4000 Python: 5,039 с -> 3526 C ext: 0,033 с -> 3526

Итак, это дало самые быстрые результаты. Во втором тестовом примере выше версия на C оказалась более чем в 150 раз быстрее, чем чистый Python.

Неплохо.

А как насчет NumPy?

Некоторые из вас могут задаться вопросом, почему не использовался NumPy. Что ж, NumPy отлично подходит для векторизованных числовых операций с массивами, таких как скалярные произведения, но не все алгоритмы однозначно соответствуют векторизации. Вычисление расстояний Левенштейна — это по сути последовательный процесс, поэтому NumPy не особо помогает. В таких случаях переход к C через subprocess , ctypes или нативное расширение C обеспечивает реальное ускорение выполнения, при этом сохраняя возможность вызова из Python.

P.S. Я провёл несколько дополнительных тестов, используя код, совместимый с NumPy, и неудивительно, что NumPy оказался таким же быстрым, как и вызванный код на языке C. Этого следовало ожидать, поскольку NumPy использует язык C и имеет за плечами многолетний опыт разработки и оптимизации.

Краткое содержание

В статье рассматривается, как разработчики Python могут преодолеть ограничения производительности в ресурсоёмких задачах, таких как вычисление расстояния Левенштейна — алгоритма проверки схожести строк, — интегрируя код на языке C в Python. Хотя библиотеки, такие как NumPy, ускоряют векторизованные операции, последовательные алгоритмы, такие как Левенштейн, часто остаются невосприимчивыми к оптимизации NumPy.

Чтобы решить эту проблему, я продемонстрировал три шаблона интеграции , от самого простого до самого продвинутого, которые позволяют вам вызывать быстрый код C из Python.

Подпроцесс. Скомпилируйте код C в исполняемый файл (например, с помощью gcc или Visual Studio Build Tools) и запустите его из Python с помощью модуля subprocess. Это легко настроить, и уже сейчас можно увидеть значительное ускорение по сравнению с чистым Python.

ctypes. Использование ctypes позволяет Python напрямую загружать и вызывать функции из общих библиотек C, без необходимости написания полноценного модуля расширения Python. Это значительно упрощает и ускоряет интеграцию критически важного для производительности кода C в Python, избегая накладных расходов на запуск внешних процессов и при этом сохраняя большую часть кода на Python.

Расширения Python C. Создайте полноценное расширение Python на языке C, используя API CPython (python.h). Это потребует больше настроек, но обеспечит максимальную производительность и плавную интеграцию, позволяя вызывать функции C так же, как и нативные функции Python.

Бенчмарки показывают, что реализации алгоритма Левенштейна на языке C работают более чем в 100 раз быстрее, чем на чистом Python. Хотя внешняя библиотека, такая как NumPy , отлично справляется с векторизованными числовыми операциями, она не обеспечивает значительного повышения производительности для изначально последовательных алгоритмов, таких как Левенштейн, что делает интеграцию с C более предпочтительным выбором в таких случаях.

Если вы столкнулись с ограничениями производительности в Python, перенос тяжёлых вычислений на C может обеспечить значительное повышение скорости и заслуживает внимания. Можно начать с простого subprocess, а затем перейти к ctypes или полноценным расширениям C для более тесной интеграции и повышения производительности.

Я обрисовал лишь три самых популярных способа интеграции кода C с Python, но есть еще несколько методов, с которыми я рекомендую вам ознакомиться, если эта тема вас интересует.

Источник: towardsdatascience.com