Бег в мешках с завязанными глазами спиной вперед

Гордость и предубеждение

Способность делать что-либо быстро всегда высоко ценится ее обладателем, зачастую независимо от качества исполнения. — Джейн Остин

На benchmarksgame часто ссылаются, чтобы доказать преимущества или недостатки того или иного языка программирования. Однако тут нужно быть аккуратным. Те, кто профессионально занимаются замерами производительности, знают, что в этом деле есть множество подводных камней, и можно легко попасть в просак. Например, виртуальной машине Java нужно некоторое время, чтобы прогреться. Соответственно на слишком коротких тестах результаты будут нерепрезентабельны. К счастью, с точки зрения статистики на сайте используется очень даже систематичный подход.

Но цифрам все равно нельзя верить, и вот почему.

Представьте, что ваш любимый язык программирования, скажем, C. При этом в одном из сравнений C уступает Java, причем существенно, в два раза. Несправедливость! Вы открываете код решения на C и видите, что он написан не очень аккуратно, и явно многое можно многое улучшить и оптимизировать. Если при этом под руку подвернулся свободный вечер, а на столе стоит пара пива, — патча не избежать. В этом подходе и есть основная проблема.

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

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

Задача: n-body

Король Швеции Оскар II был просвещенным монархом. Его волновали многие важные вопросы, например, не упадет ли Луна на Землю? В 1885 году он объявил математический конкурс, на котором была представлена Задача трех тел — моделирования системы Земля-Луна-Солнце.

Победившее решение было представлено Анри Пуанкаре, и хотя оно не являлось точным, тем не менее внесло существенный вклад в развитие математики и, в частности, теории хаоса. В общем случае задача называется проблемой N-тел.

Задача n-body на benchmarksgame представляет собой моделирование системы Солнце-Юпитер-Сатурн-Уран-Нептун методом конечных приращений. С технической точки зрения задача представляет из себя ряд арифметических операций над небольшим количеством переменных типа double во вложенном цикле.

Закономерно, что интерпретируемые языки показывают посредственные результаты: 3 минуты для Erlang, затем следуют PHP, Lua, Perl, Ruby, и завершает ряд Python с 13 минутами.

Честные решения на компилируемых языках программирования идут плотной группой от 20 до 22 секунд в следующем порядке: Chapel, C#, Go, OCaml, Swift, Java, Free Pascal. Немного отстают Node.js, TypeScript, Lisp и Dart — все в районе 27 секунд.

Лидеры

Неожиданно хороший результат показал Rust: 13 секунд при честном решении. Правда, оно представлено командой разработчиков языка Rust. Возможно, простота решения лишь кажущаяся.

Безусловный же победитель — Fortran: 8 секунд, но и здесь есть подвох. Лучшее решение — это результат четырех итераций улучшения кода различными разработчиками. Является ли конечный код типовым, который написал бы любой разработчик, вопрос все еще спорный.

Читеры

Решение на Haskell, хоть и выполняется за 21 секунду, однако утилизирует все 4-ре ядра процессора, что не совсем честно.

На C удалось оптимизировать программу до 8 секунд, за счет использования типа данных __m128d и ручного применения инструкций SSE2. Трудно назвать это честным решением. Со стандартной арифметикой C отрабатывает за те же 20 секунд.

Выводы

Компилируемые языки программирования практически одинаково быстры в математических вычислениях, к ним же можно отнести и JavaScript (V8) и смежные с ним языки. Так что, если вдруг вы захотите смоделировать движение планет в вашем приложении, делайте это в браузере. Будет так же быстро и гораздо экономичнее с точки зрения утилизации серверных ресурсов.

Задача: binary-trees

Хотя и не имеет столь же глубокого исторического контекста, но не менее любопытна, чем предыдущая. Суть задачи в последовательном построении серии полных бинарных деревьев, когда у каждого родителя есть ровно два потомка, глубиной от 6 до 22. Каждое построенное дерево необходимо обойти в глубину и вычислить простую чек-сумму, являющуюся ответом алгоритма.

Задача нацелена на то, чтобы измерить стандартные механизмы управления памятью, так что по условию требуется явно выделять и освобождать память под каждый узел, используя базовые средства языка. Соответственно, по условию явно запрещается выделить на старте массив размером на 8388608 минус 1 элемент, и все в этом духе.

Лидеры

Неудивительно, что лучший честный результат показывает Java (чуть больше 12 секунд), поскольку модель исполнения очень хорошо ложится на модель сборки мусора в jvm. Поскольку память выделяется последовательно, и затем освобождается большим куском, стоимость выделения памяти Java в куче в этом случае сравнима со стоимостью выделения памяти в стеке, т.е. практически бесплатно.

Еще быстрее можно было бы отработать только включив Zero GC, т.е. полностью отключив сборщик мусора. Почему нет, если памяти достаточно. Идея, к слову, не нова. Первая реализация Lisp, 1958, использовала именно такой garbage collector. Память выделялась до тех пор, пока в системе была свободная память, а реализация алгоритма сборки мусора была отложена до лучших времен.

Для сравнения, честное решение на C, использующее malloc и free на каждый узел, занимает целых 37 секунд. Ну что же, такая задача.

Читеры

OCaml, 10 секунд — выделяет память по слоям:
let workers = Array.init ((max_depth — d) / 2 + 1) (fun i -> let d = d + i * 2 in (d, invoke worker d))

Rust, 6 секунд — использует концепцию Arena и многопоточность:
let long_lived_arena = Arena::new(); let long_lived_tree = bottom_up_tree(&long_lived_arena, max_depth);
…
thread::spawn(move || inner(depth, iterations))

Еще раз Rust, 4 секунды — использует Arend и параллельный итератор (rayon::prelude):
let arena = Arena::new();
let depth = max_depth + 1;
let tree = bottom_up_tree(&arena, depth);
…
let chk: i32 = (0… iterations).into_par_iter().map(|_| {
…

И наконец C, 2 с половиной секунды — использует apr_pools и оптимизации препроцессора:
apr_pool_t * thread_Memory_Pool; apr_pool_create_unmanaged(&thread_Memory_Pool);
…
#pragma omp parallel for
for(current_Tree_Depth=minimum_Tree_Depth; …

Выводы

Модель управления памятью со сборщиком мусора аля Java/C# может быть существенно эффективнее наивного ручного управления памятью, в определенных задачах.

Управление сборкой мусора в Dart, Node.js и Go возможно требует улучшений: результат около 40 секунд, а они вполне могли бы отработать так же быстро как и Java. Хотя, есть вероятность, что скорость сборщика мусора в этих языках сознательно принесена в жертву минимизации потребления памяти.

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

Задача: thread-ring

Необходимо создать 503 потока, связанных в кольцо. Соответственно 1-й поток ссылается на 2-й, 2-й на 3-й и так далее, 503-й ссылается на 1-й. Необходимо передать токен между потоками 50000000 раз по порядку, после чего напечатать номер процесса получившего токен последним. Эдакая игра в картошку.

Честные решения

Аккуратным решением было бы создать 503 потока, соединить их в кольцо 503 каналами и передавать через них сообщение по кругу. Для Java это были бы BlockingQueue, для Go — channel, для Erlang — встроенные межпроцессные сообщения.

Для Rust это около 3-х минут, Ruby — 5 минут, для C# — 6 минут. К сожалению для других языков честных решений в общем-то и нет.

Читеры

Java, используя LockSupport.park() и volatile удалось добиться 3-х с копейками минут. Аналогичный подход (используя Mutex) для Python 3, OCaml, Lisp и C отрабатывает вплоть до 2 с половиной минут. Любопытно, что во всех случаях четыре процессора загружены в среднем на 30%, т.е. накладные расходы на полуактивное ожидание около 5%.

Решения на Erlang — 43 секунды, Smalltalk — 39 секунд, Chapel — 27 секунд, Go — 13 секунд и Haskell — 9 секунд в зачет не идут, поскольку по факту при их исполнении было задействовано ровно одно процессорное ядро, что не дает никакой информации и реальной производительности межпроцессорного взаимодействия в этих языках. В решении на Go вообще указано: runtime.GOMAXPROCS(1), это несерьезно. С тем же успехом можно было просто провернуть цикл на пятьдесят миллионов итераций.

Еще один хак — C++: 29 секунд. Решение построено на базе asio.hpp, библиотеке асинхронного ввода вывода, что само по себе любопытно, однако не имеет никакого отношения к поставленной задаче передать сообщение между потоками. По всей видимости, решение на F# — 18 секунд — работает по тому же принципу, поскольку там используется примитив async для определения отложенной функции вместо потока.

Выводы вместо лидера

Лидера, увы, нет, поскольку для языков вроде Go или Erlang, для которых честное решение должно было бы показать хорошие результаты, такового решения не представлено.

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

Асинхронный ввод-вывод вместо реальных потоков — это отличная штука, но мы это и так знали со времен nginx и node.js.

Общие итоги

Я быстрый, я очень быстрый… В спальне перед сном я бью по выключателю и успеваю лечь в постель пока не погаснет свет… я очень быстрый. — Мохаммед Али

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

Что касается различных исследований на базе benchmarksgame, не верьте, смотрите код.