LINUX.ORG.RU

Эффективная оптимизация. Что такое Cython.

 , , , ,


14

7

За последнюю неделю почему-то часто всплывал этот вопрос, поэтому распишу всё сразу в одном месте. Описывать буду на примере питона, но общие принципы применимы ко многим языкам. Итак.

Часть первая. Правила эффективной оптимизация

  1. Не думайте об оптимизации пока код не дописан. Вообще! Думайте, как написать код проще и понятнее. А про оптимизацию даже не вспоминайте, пока не запустите код. Когда код запустится, проверьте насколько быстро он отрабатывает. Если он достаточно быстр — задача решена, ничего делать не нужно. Точка. И только если код отрабатывает медленнее, чем требуют условия задачи — начинайте думать об оптимизации.
  2. Попробуйте JIT, например PyPy, если условия это позволяют (apt-get install pypy && pypy yourprogram.py). Когда не хватает совсем немного производительности — JIT ускорит в несколько раз, и этого может быть достаточно. И тогда всё, задача решена. Только если это не сработало, переходите к фактической оптимизации кода.
  3. Пройдитесь профайлером. python -m cProfile yourprogram.py Никогда не оптимизируйте код без профилирования. По профилю определите самые медленные куски кода. Если код слишком большой — разбейте на функции. Не нужно бросаться переписывать всё подряд. Изолируйте наиболее прожорливые куски кода, и работайте только с ними.
  4. Выполните высокоуровневую оптимизацию найденных медленных кусков кода. Используйте более быстрые библиотеки: gmpy2 вместо встроенной длинной арифметики, python-regex вместо встроенного re, numpy для матричных вычислений, и т.д. Замените dict на list. Вынесите все возможные вычисления за циклы. Наконец, оптимизируйте алгоритм, или попробуйте найти ему более быстрый аналог. Если что-то получилось — goto 2.
  5. Cython. Расставьте типы, пройдитесь профайлером, посмотрите annotate cython-а, какой код сгенерирован, какие куски можно ускорить (он их расцвечивает)... Ещё раз подчёркиваю, низкоуровневая оптимизация — это последний этап, когда другие варианты исчерпаны.

Часть вторая. Cython

Если мы всё-таки дошли до cython-а, то... что же он такое?

Cython - это транслятор из питона в Си. Всё. Он просто генерирует код на си.

Если в файле mymodule.py написать:

def somefunc(x):
    y = x*42
    return y
и запустить cython mymodule.py то он том же каталоге сгенерирует mymodule.c, в котором будет что-то вроде:
static PyObject *__pyx_pf_8mymodule_somefunc(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_x) {
  PyObject *__pyx_v_y = NULL, *__pyx_r = NULL, *__pyx_t_1 = NULL;

  __pyx_t_1 = PyNumber_Multiply(__pyx_v_x, __pyx_int_42);
  __Pyx_GOTREF(__pyx_t_1);
  __pyx_v_y = __pyx_t_1;
  __pyx_t_1 = 0;

  __Pyx_XDECREF(__pyx_r);
  __Pyx_INCREF(__pyx_v_y);
  __pyx_r = __pyx_v_y;

  __Pyx_XDECREF(__pyx_v_y);
  __Pyx_XGIVEREF(__pyx_r);
  return __pyx_r;
}
И, хотя это редко делают вручную, этот код можно собрать обычным компилятором: gcc -shared -O3 -o mymodule.so mymodule.c `python-config --cflags --ldflags`. Нигде в остальном коде ничего менять не надо. Обычный «import mymodule» загрузит бинарный module.so так же, как загрузил бы питоновый mymodule.py.

Да, cython позволяет скомпилировать питонокод. Но никаких глубоких интеллектуальных оптимизаций cython не делает. Он просто вызывает из libpython.so питоновые функции, такие как PyNumber_Multiply(). Без питона этот код работать не будет. (в принципе, его можно собрать статически, но обычно это не имеет смысла — реальная программа всё равно будет использовать кучу внешних либ, и ещё одна библиотека роли не сыграет)

Так как все вызовы питоновых функций остались, то просто сборка cython-ом большого ускорения не даст, может, раза в два. Но! Cython-у можно указать, где использовать сишные типы вместо питоновых! В примере выше, если расставить типы:

cdef double somefunc(double x):
    cdef double y = x*42
    return y
то cython mymodule.pyx сгенерирует в mymodule.c код:
static double __pyx_f_8mymodule_somefunc(double __pyx_v_x) {
  double __pyx_v_y, __pyx_r;

  __pyx_v_y = (__pyx_v_x * 42.0);

  __pyx_r = __pyx_v_y;

  return __pyx_r;
}
По сути, это чистый код на си. Быстрее некуда. А с параметром --annotate cython -a mymodule.pyx дополнительно сгенерирует «mymodule.html», в котором раскрасит код цветами. По нему легко смотреть, какие части кода ещё стоит оптимизировать. Но так как после расстановки типов обычным питоном такой код уже не запустится, его традиционно сохраняют в файле с расширением .pyx вместо .py.

Вот так, не написав ни одной строчки на си, а просто расставив типы, медленный питоновый код превращается в быстрый сишный.

В целом, это всё.

PS: Это не все возможности cython-а. В нём можно использовать плюсовые типы, например std::vector. Причём можно даже писать: cdef vector[double] sqrs = [x*x for x in somelist] и всё преобразование из питоновых типов в плюсовые и обратно cython возмёт на себя. Можно вызывать и внешний код на си (cdef extern from).

Есть и более тонкие оптимизации, например мелким функциям можно расставлять inline (хотя с этим и gcc обычно справляется). А ещё код, не использующий питоновые объекты, не блокирует GIL! А значит отлично подходит для многопоточных вычислений. В cython-е есть и модули для параллельных вычислений.

Да и сами .pyx файлы обычно компилируются не руками, а как часть скрипта distutils/setuptool. А в отладочных целях import pyximport; pyximport.install() и после этого обычный import mymodule сможет импортировать не только .py, но и .pyx файлы.

Полезные ссылки

Итого: Оптимизировать надо только когда иначе нельзя, и только то, что необходимо. Низкоуровневая оптимизация делается в последнюю очередь. Но если мы её таки делаем, то cython позволяет сделать её максимально легко — просто расставив типы.

PPS: Питон в этом не уникален. Почти во всех языки есть возможности низкоуровневой оптимизации, расширения на си через FFI/JNI/и т.д. Есть unsafe код в rust и c#. Даже в паскале и си есть ассемблерные вставки. Не удивительно, что кто-то придумал аналог и для питона. Так что эти же принципы оптимизации применимы и к другим языкам.

Если он достаточно быстр на вашем 9900k@5GHz — задача решена, ничего делать не нужно. Точка.

Суровая реальность современной разработки.

devl547 ★★★★★ ()

Ну можно добавить очевидного в 3: скажем взять pycurl, lxml и uvloop — выкинуть питонопарашу и использовать компилируемые батарейки.

anonymous ()

[япознаюмир] ЛОР — не блог.

Numba даже не упомянута.

В целом, это всё.

Ахахахахахахахаха.

А ещё код, не использующий питоновые объекты, не блокирует GIL!

Кхм.

Есть unsafe код в rust … Не удивительно, что кто-то придумал аналог и для питона.

«Аналог» вдвое старше раста, это ли не удивительно? XD

t184256 ★★★★★ ()
Ответ на: комментарий от KivApple

Согласен, вообще обалдели. На тот момент уже минус 12 лет как устоялся синтаксис, а они развели какую-то самодеятельность.

t184256 ★★★★★ ()
Последнее исправление: t184256 (всего исправлений: 1)
Ответ на: комментарий от t184256

По-моему в цитоне гил надо освобождать отдельно, использовать питоновые объекты в это время конечно нельзя. В сишных модулях с этим попроще.

anonymous ()
Ответ на: комментарий от Moondancer

ЛОР — не блог

Тем не менее, спасибо автору темы. Узнал что-то новое и видимо даже полезное. А то разводить сра на 22 стр - можно, а такие темы - так сразу ни (и это на фоне одного пациента с рецидивами).

I-Love-Microsoft ★★★★★ ()
Последнее исправление: I-Love-Microsoft (всего исправлений: 1)

Вот так, не написав ни одной строчки на си, а просто расставив типы, медленный питоновый код превращается в быстрый сишный

Который вкупе с оставшимся питоническим кодом не обязательно будет работать быстрее PyPy, следует это учитывать.

Оптимизировать надо только когда иначе нельзя

А обоснование-то где? Вижу только описание разумного подхода к оптимизации, но не вижу обоснования почему её не следует делать.

WitcherGeralt ★★ ()
Ответ на: комментарий от anonymous

Нуитка либо пока не допилена, либо не нужна вовсе. Я недавно тыкал, получается в разы медленней Pypy и Cython, а шедскин не очень жив и до сих пор не готов.

Когда задумываться об альтернативных реализациях на жвм?

Если речь про Jython, то он медленный, Iron, вроде бы, быстрее, но тоже не особенно нужен.

WitcherGeralt ★★ ()
Ответ на: комментарий от Moondancer

Если задача не требует, чтобы код летал, как KolibriOS, то постановщик задачи — чудак на букву Шаман.

Да, хорошо бы, чтобы код не тормозил. Но оптимизировать можно вплоть до ассемблера со специальными префиксами под конвейеры отдельных процессоров. И в будущем развивать такой предельно оптимизированный код не сможет никто, даже его автор. Поэтому надо где-то провести черту, определить, когда код «достаточно быстр».

pynonymous ()

Про программирование и кодинг

Не думайте об оптимизации пока код не дописан. Вообще! Думайте, как написать код проще и понятнее. А про оптимизацию даже не вспоминайте, пока не запустите код.

Часто встречаю это утверждение. Уверен, что оно родилось в мире веб-кодинга, где критично важно быстро выпустить продукт, да обязательно так, чтобы в твоём коде могли быстро разобраться другие.

Главное — не переносить эти принципы с веба на другие области. Уже в Python, но в других областях, эти принципы могут быть вредными. И они совершенно точно не переносятся на программирование в целом.

Кстати, любопытный факт: в стартовом посте корень «код» упомянут 26 раз, а корень от «программа» только 1 раз. Некоторые говорят, что есть кодинг, а есть программирование. Кодер занимается кодингом и пишет, вы не поверите, код. А программист пишет программы. Разница тонкая, однако...

Программа должна корректно выполнять свою задачу (и не содержать багов) и быть эффективной. Вот критерии качества программы. Две программы можно сравнить по этим критериям: например программа bubblesort хуже программы qsort, потому что менее эффективно выполняет свою задачу — сортировать массив. Программист должен стараться писать хорошие программы сразу. Например, базовое знание Computer Science позволит сразу взять правильный алгоритм или подходящую структуру данных. Знание принципов работы кэша позволит делать cache-friendly обход. Знание внутренней «кухни» компилятора позволит обойтись без лишних выделений памяти и соптимизировать рекурсию (которая сразу будет написана хвостовой). И так далее.

А кодинг... Тут у нас что? Соответствие кодстайлу, хорошие комментарии, даже и SLOC можно помериться. Оптимизации отходят на второй план. О ней предлагается подумать потом, когда дойдут руки. Часто руки не доходят никогда, т.к. бизнес требует всё нового и нового кодинга, не оставляя времени на программирование. Появляются мудрые кодеры-сеньоры, говорящие кодерам-новичкам «даже не вспоминай про оптимизацию, лучше напиши быстро и понятно». А может быть стоит хотя бы на минуточку о ней вспомнить, пока пальцы набивают в IDE незнамо что?

Хорошо это или плохо? Не мне решать. Но я совершенно точно хочу, чтобы каждое такое «сначала код, потом оптимизация» из стартового поста было уравновешено «код одновременно с оптимизацией» из этого. Точно так же, как в программисте стремление к красоте кода должно быть сбалансировано стремлением к эффективной программе.

Crocodoom ★★ ()
Ответ на: Про программирование и кодинг от Crocodoom

Re: Про программирование и кодинг

Главное — не переносить эти принципы с веба на другие области. Уже в Python, но в других областях, эти принципы могут быть вредными. И они совершенно точно не переносятся на программирование в целом.
...
Но я совершенно точно хочу, чтобы каждое такое «сначала код, потом оптимизация» из стартового поста было уравновешено «код одновременно с оптимизацией» из этого.

Очень хочется согласиться, честно! Но тогда... в какой же момент остановиться? До каких пор оптимизировать-то?

например программа bubblesort хуже программы qsort

Но qsort хуже чем mergesort. А mergesort хуже, чем timsort (который, кстати, изобретён питоновцами). А timsort соперничает со smoothsort. Smoothsort — уникальный алгоритм, это inplace-сортировка не требующая дополнительной памяти. Но она настолько сложна, что почти никто не реализовывал её с полной оптимизацией.

И, вот, вопрос. Представь, что ты — начальник, и принимаешь код подчинённого. Какой код ты предпочтёшь принять в проект: qsort на 10 строк, mergesort на 20 строк, или smoothsort на тысячу строк, которую никто в компании не способен понять?

PS: insertsort быстрее qsort-а при небольших размерах массива.

PPS: если кто не знает, у классического qsort-а сложность до O(N²), т.е. на некоторых данных он работает медленнее, чем bubblesort, а точнее, просто вылетает со stack overflow.

pynonymous ()
Ответ на: Re: Про программирование и кодинг от pynonymous

Очень хочется согласиться, честно! Но тогда... в какой же момент остановиться? До каких пор оптимизировать-то?

Пока это не (существенно) тормозит разработку. Часто достаточно хотя бы на минутку включить мозг, немного погуглить, почитать SO и после этого написать уже нормально.

Если говорить про остальные ситуации, когда оптимизация может занять неопределенно долгий промежуток времени, то и здесь пригодится мозг и эрудиция в CS. С ними ты видишь разницу между медленным и быстрым вариантом. Ты знаешь, что осознанно пишешь неоптимально, потому что некогда реализовывать сложный алгоритм. Можно добавить соответствующий комментарий или создать задачу на будущее. Это совсем не то же самое, что просто «кодить и даже не вспоминать про оптимизацию».

Crocodoom ★★ ()
Ответ на: комментарий от anonymous

По-моему в цитоне гил надо освобождать отдельно,

«Особождать» — это пометить код как with nogil:? Смотря когда. Если это обычный питоновый threading, то отметить надо явно (пример). А если используется prange(N, nogil=True) из "модулей для параллельных вычислений.", то «with nogil» писать не надо (пример).

использовать питоновые объекты в это время конечно нельзя.

Да, причём cython сам это проверит. Если попытаться использовать питоновый объект или вызвать функцию, то он выдаст ошибку компиляции:

        result = somefunc(n)
                        ^
test.pyx:22:20: Calling gil-requiring function not allowed without gil

В сишных модулях с этим попроще.

По-моему, проще уже некуда. 😎

pynonymous ()
Ответ на: комментарий от Crocodoom

Пока это не (существенно) тормозит разработку. Часто достаточно хотя бы на минутку включить мозг, немного погуглить, почитать SO и после этого написать уже нормально.

А, ну, я и не предлагаю кодить вообще не думая. Просто мне часто встречались попытки сразу всё оптимизировать. Сразу оптимально хитро предзаполнить переменные, сразу развернуть циклы, сразу написать вычисления так, чтобы потом распараллелить их одной строкой... Код становится громоздким, его сложно читать и проверять логику. А на скорость это всё вообще не влияет, потому что основные тормоза вызваны выбранным алгоритмом, и находятся в другом конце программы.

Поэтому я и предлагаю не думать именно об оптимизации. А вместо этого думать «как написать код проще и понятнее».

Продолжая пример с сортировками... Между bubblesort, qsort, mergesort, timsort и smoothsort я выберу bubblesort, потому что она проще, конечно, если она достаточно быстра по условию задачи, например, сортировать нужно всего 5 элементов. Если потом окажется, что сортировать нужно миллион элементов, то позже, оптимизируя в п.4, я заменю несколько строк bubblesort-а на mergesort, потому что bubblesort и qsort по условию задачи не подойдут, а из оставшихся mergesort самая простая.

Да, думать всё равно надо. Просто думать не о скорости, а о том, чтобы написать хороший, простой, понятный код.

pynonymous ()

«потом оптимизируем» довольно часто откладывается настолько на потом, что ведёт уже к «потом выкинем и перепишем нормально»

Если он достаточно быстр — задача решена, ничего делать не нужно. Точка. И только если код отрабатывает медленнее, чем требуют условия задачи — начинайте думать об оптимизации.

обычно под этим подразумевается «достаточно быстр на машине разработчика с точки зрения разработчика».


http://www.commitstrip.com/wp-content/uploads/2016/07/Strip-Les-Prerolls-650-...

Ford_Focus ★★★★★ ()
Последнее исправление: Ford_Focus (всего исправлений: 2)
Ответ на: комментарий от WitcherGeralt

Ну, например:

  • у тебя обычный python
  • jit, дающий скорость как у cython, или даже выше
  • можно ускорять вычисления на видеокартах
shkolnick-kun ★★★ ()
Последнее исправление: shkolnick-kun (всего исправлений: 1)
Ответ на: комментарий от WitcherGeralt

Ой как стоит. В двух словах: достигает того же самого без сношений с системой сборки и без аннотаций типов внутри кода. В остальном у нее на сегодняшний день почти feature-parity с Cython + она содержит немного сбоку-припекнутый кодогенератор в CUDA/ROCm. На работе свалил с Cython на numba, не жалуюсь.

Проверено на многих студентах — лепить на функцию декоратор @numba.jit и тут же радоваться ускорению очень приятно. Знакомство с миром ускорения питонокода провожу примерно так: даю вступление, похожее на шапку топика, показываю ускорение, объясняю, за счет чего оно взялось, показываю, какой странный становится код, а потом сразу numba и большинство на этом забывает Cython как страшный сон.

t184256 ★★★★★ ()
Ответ на: Про программирование и кодинг от Crocodoom

Часто встречаю это утверждение. Уверен, что оно родилось в мире веб-кодинга

Взоржал и дальше не читал, ибо лучшего ворнинга «я не знаю, что несу, сбейте меня палкой» даже и не припоминаю.

t184256 ★★★★★ ()

Почему бы просто не переписать прототип на Python’е на нормальный по быстродействию язык, если нужна хорошая оптимизация?

EXL ★★★★★ ()

Не думайте об оптимизации пока код не дописан. Вообще!

Т.е. не думайте вообще никогда, ибо код не бывает никогда «дописан» на 100%. Ясно-понятно.

no-such-file ★★★★★ ()

Не думайте об оптимизации пока код не дописан.

Дальше не читал. Вот так налепят алгоритмов квадратичной сложности, а потом удивляются что недоязычки тормозят.

bread ()
Ответ на: комментарий от no-such-file

Т.е. не думайте вообще никогда

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

bread ()
Ответ на: комментарий от EXL

Почему бы просто не переписать прототип на Python’е на нормальный по быстродействию язык

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

bread ()

Про зло оптимизации в подобном ключе пишут те, кто из всего творчества Кнута прочитал лишь эту фразу. Не понимая даже, о чём и в каком контексте она была написана.

Diff ★★★★ ()
Ответ на: комментарий от bread

сложность переписывания прототипа сопоставима с написанием с нуля

сразу видно человека не написавшего в своей жизни ничего сложнее hello world

anonymous ()

Cython и прочие аналоги - это костыли для поддержки изначально калечной системы. Для каких-то целей вполне пригодное решение. Но это геморой.

yvv ★★☆ ()
Ответ на: Про программирование и кодинг от Crocodoom

например программа bubblesort хуже программы qsort, потому что менее эффективно выполняет свою задачу — сортировать массив.

Нифига, пузырек лучше квика, т.к. не жрет столько памяти.

ya-betmen ★★★★★ ()