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

    Какой язык программирования самый быстрый — не всегда практичный, но крайне любопытный вопрос. Сайт benchmarksgame как раз об этом. Суть проекта в сравнении скорости языков программирования на ряде типовых задач. Надо сказать, что результаты не всегда предсказуемы. Что, если JavaScript такой же быстрый, как и C? Это же скандал!

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


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

    На 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, не верьте, смотрите код.
    Wrike 146,73
    Wrike делает совместную работу над проектами проще
    Поделиться публикацией
    Комментарии 19
      +1
      Так что, если вдруг вы захотите смоделировать движение планет в вашем приложении, делайте это в браузере.

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

        +12
        Представьте, что ваш любимый язык программирования, скажем, C. При этом в одном из сравнений C уступает Java, причем существенно, в два раза. Несправедливость! Вы открываете код решения на C и видите, что он написан не очень аккуратно, и явно многое можно многое улучшить и оптимизировать. Если при этом под руку подвернулся свободный вечер, а на столе стоит пара пива, — патча не избежать. В этом подходе и есть основная проблема.
        Мне кажется, сначала надо определиться, что считать честным. Если ставить задачу как «определить, какой язык самый быстрый», то тут как раз логично найти спеца по этому языку и дать ему возможность выжать все соки. Тогда мы будем сравнивать именно языки. А если вы говорите
        Является ли конечный код типовым, который написал бы любой разработчик
        то получается, что мы сравниваем типовых разработчиков. Не говоря уже о том, что понятия «типовой код» и «любой разработчик» — очень размытые.
        Я готов только согласиться с тем, что недопустимы хаки, которые подменяют исходную задачу на другую, очень похожую на исходную, но которую очень легко разогнать (и при этом задачу именно в исходной постановке разогнать тем же способом нельзя). И с тем, что количество используемых процессоров тоже лучше сделать одинаковым для всех.
          +1
          Скорее всего, автор имел ввиду, что алгоритм должен быть как можно более стандартизован, а уже реализацию отдать на откуп языку+стандартные библиотеки и не использовать явных хаков.
            +1
            А что это даст? Вот тут автор очень напирает на то, что Java — очень быстро работает с деревьями, а malloc и free — «тормозят». Но я как раз с алгоритмами на деревьях (очень разнообразными) работаю в C и C++ последние 10 лет (в разных проектах, я знаю, что это не один язык). И я нигде не видел голого использования malloc и free — во всяком случае в тех частях, где была важна скорость. Часть кода была на Java, впрочем… и даже там были арены! Ну просто дорого выделять миллионы обьектов в «куче» — на любом языке!

            Можно ли назвать код, который не используется в реальных проектах «типовым» и код, который используется «читерским»? Вопрос, до некоторой степени, риторический…
              +1
              Безусловно, алгоритмы должны быть максимально идентичны.
              Конечно это не мое требование, а требование сайта: benchmarksgame.alioth.debian.org/u64q/nbody-description.html#nbody
              We ask that contributed programs not only give the correct result, but also use the same algorithm to calculate that result.
              0
              И с тем, что количество используемых процессоров тоже лучше сделать одинаковым для всех.

              Ну в таком случае если так получается, что твой язык не даёт возможности параллелить, а другой — даёт, не значит, что всё нужно в одном треде делать. Но вот максимальное число процессов было бы хорошо ограничить. Это да
              +1
              #pragma omp к препроцессору отношения не имеет. Это OpenMP, одна из техник параллелизации.
                +1
                Надо запилить решение второй задачи на С++ на шаблонах. Там можно и 0 секунд получить)
                  0
                  компилтайм решение — чит.
                  и вобще надо учитывать время компиляции
                  0
                  Насколько я помню, там всё запускается на древнем core 2 duo. Поэтому об автоматических векторных оптимизациях (которые делает JVM) можно забыть.

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

                  Но всё равно полезно посмотреть, что примерно может каждый ЯП.
                    0
                    Вопрос читерства в таких задачах ооочень интересный — считать ли читерством использование возможностей языка или может сразу банить весь язык, позволяющий тонкое манипулирование?
                    И какие трики являются читерскими для данной задачи, а какие нет — бывает трудно разделить.

                    Я смотрел там ранее исходники и отмечал подобные вещи. Но:

                    — если почитать на сайте stories, то кое что прояснится — сайт был создан для сравнения скриптовых языков, которым жесткие оптимизации обычно не свойственны (но люди нашли способы — молодцы)

                    — более важным для широкого ряда задач считаю использование объемов памяти, нежели возможности подобного читерства

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

                      Банить языки программирования позволяющие оптимизации безусловно не нужно,
                      более того глупо. Однако, если мы будем целенаправленно оптимизировать программы
                      под задачи и возможности языка, мы получим конкурс программистов — кто лучше оптимизирует, а это совсем другой жанр. То что именно так все и происходит безусловно удручает.
                      +2
                      Решения на Erlang — 43 секунды… в зачет не идут, поскольку по факту при их исполнении было задействовано ровно одно процессорное ядро

                      Вообще, Эрлангу было разрешено использовать 4 ядра:
                      Erlang/OTP 20 [erts-9.1] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:10] [hipe] [kernel-poll:false]

                      Ну и вы уж определитесь, что считать честным, а что читерством. Модель аллокации памяти в Java, видите ли честная и хорошая, а модель потоков в Эрланге — читерство?
                        +2
                        Спасибо за комментарий, я уже начал беспокоиться что никто так и не заступится за erlang :)

                        С одной стороны вы правы, в решении erlang нет явного читерства, в отличии от Go,
                        просто исполняющая платформа достаточно умная чтобы понять что на одном ядре
                        данная программа будет выполнена быстрее. Платформа Erlang в этом смысле достаточно
                        умная, факт.

                        Тем не менее другой факт состоит в том что вся логика была выполнена на одном
                        процессорном ядре, таким образом мы ничего не узнали о том какие накладные расходы
                        в Erlang на взаимодействие между физическими процессорами.
                        А ведь именно это и интересно.

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

                        Было бы правильно изменить условие задачи, например сказав что по кольцу нужно крутить
                        5-ть сообщений, с шагом в 101. Тогда появился бы практический смысл утилизировать
                        все процессорные ядра.

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

                        Таким образом, в задаче с деревом по Java можно говорить что однопоточное решение
                        будет практически таким же быстрым как и с параллельной сборкой мусора, по этому
                        я считаю что такое решение можно засчитать. А в erlang мы так и не увидели накладные
                        расходы на межроцессорную коммуникацию, соответственно было бы неправильно
                        экстраполировать что решение на Erlang для нескольких процессорных ядер будет
                        работать также быстро.
                          +1
                          в результате мы не узнали про Erlang то что хотели — как там реальные межпроцессорные коммуникации.

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

                          Если хочется межпроцессорные коммуникации считать, то надо писать под это конкретный бенчмарк, с жестким распределением процессов по ядрам, и пересылкой сообщений между ядрами на каждой итерации.
                            0
                            Аналогичный вопрос на самом деле и про Haskell. Я глянул быстренько код — оно честно создаёт четыре ОС-треда и честно на них гоняет данные через этакий аналог канала. Просто действительно рантайм умный.

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

                            Итого — да, согласен с соседним комментатором, бенчмарк нерелевантен.
                          0
                          На мой взгляд тест хорош тем, что позволяет использовать разные возможности языка программирования при выполненении одинаковых задач.
                            0
                            Как по мне все честно. Все языки программирования разные, у них разные задачаи и разные сферы применения, я лично не ожидаю увидеть одну и ту же реализацию решения. Если язык позволяет использовать все 4 процессора пусть использует, позволяет использовать горутины, пусть использует. Если этого функционала нет в других языках, это их проблемы. Все молотки разные.
                              +1

                              Чего мне не хватает на BenchmarkGame, так это трекинга версии компилятора/рантайма. На сайте всегда указаны результаты работы на последней версии gcc/GHC/ocamlopt/sbcl/… Иногда при обновлении, к примеру, GHC, ломаются оптимизации, в OCaml в 4.06 сломали обратную совместимость Strings, из-за чего половина программ перестала компилироваться, etc. Я считаю, нужно сделать версию компилятора частью "первичного ключа" (т.е. чтобы ключ был (lang, lang_version, problem_name, solution_version)), это позволит избежать поломки решений и позволит увидеть, как прогрессируют компиляторы со временем.

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

                              Самое читаемое