Python/Numba, Go, C++, Lisp и Julia в решении задачи о восьми ферзях

8 января 2020 года Паскаль Фуа и Кшиштоф Лис из Федеральной политехнической школы (ВУЗ) Лозанны (Швайцария), специализирующиеся на компьютерном зрении и машинном обучении, опубликовали сравнительное исследование под названием Comparing Python, Go, and C++ on the N-Queens Problem («Сравнение Python, Go и C++ в решении задачи о восьми ферзях»).

В тестах быстродействия использовался рекурсивный алгоритм, при котором затраты на решение задачи с увеличением размерности доски (и количества ферзей соответственно) растут экспоненциально.

Реализация, запущенная на обычном CPython скоростью не блистала, поэтому на функции навесили декораторы из Numba. Это действие повысило скорость выполнения кода в 33 раза.

Далее с целью сравнения производительности были написаны решения задачи на C++, Go, Lisp, Julia.
Помимо обычных тестов, проводились тесты производительности при распараллеливании.

• Авторы замечают, что в отличие от Go, С++ даёт возможность решить задачу разными средствами, однако требует взамен немалого опыта, чтобы не нарваться в ходе решения на подводные камни. Так например, C++ (в отличие от соперников) не проверяет запись за пределы массива, поэтому у авторов ненамеренно получился работающий код, выдающий бесполезные результаты.
• В случае с Numba, проверка включается при помощи параметра boundscheck. Конечно и у Numba есть ограничения: в компилируемых функциях доступно лишь ограниченное подмножество возможностей Python и NumPy, то есть, разработчику потребуется ещё удостовериться, что функция сможет собраться.
• Julia, не имея выделенного шага компиляции вполне сравнима по быстродействию с C++ и Go.
• Lisp, тоже показывает себя не худшим образом.

С++ побеждает, Go отстаёт на 6%, Numba на 12% (отставание обусловлено расходами на вызовы Numba-функции из Python).

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

Однако, в C++ и Go можно задействовать оптимизации, требующие низкоуровневого контроля. Например, аллокация массивов заданной размерности на стеке (а не динамическая генерация их в куче), при которой C++ становится быстрее Numba на a 20% (вместо изначальных 12%). Подобные наблюдения подчёркивают факт, что C++ и Go за счёт низкоуровневости дают возможность более тонкой подстройки кода, которая в некоторых случаях может оказаться полезной.

Авторы также замечают, что Go может считаться перспективной альтернативой Питону и C++: в нём есть проверки времени исполнения, он почти так же лаконичен, как Питон, и немножко быстрее него. Тут, правда, придётся поступиться удобством прототипирования, в частности из-за требований Go к определению кода внутри файлов, а также из-за усечённой поддержки классов.

Julia, показывая неплохие результаты, возможно, тоже однажды сможет стать альтернативой Питону.

Код нагрузочных тестов доступен для ознакомления на GitHub.