Почему Haskell (GHC) так чертовски быстр?

Haskell (с GHCкомпилятором) работает намного быстрее, чем вы ожидаете . При правильном использовании он может приблизиться к языкам низкого уровня. (Любимая вещь для Haskellers - попытаться получить в пределах 5% от C (или даже побить его, но это означает, что вы используете неэффективную программу на C, поскольку GHC компилирует Haskell в C).) Мой вопрос: почему?

Хаскель декларативен и основан на лямбда-исчислении. Архитектура машин явно обязательна, так как примерно основана на машинах Тьюринга. Действительно, у Haskell даже нет определенного порядка оценки. Кроме того, вместо того, чтобы иметь дело с типами машинных данных, вы постоянно создаете алгебраические типы данных.

Самое странное, что это функции высшего порядка. Вы могли бы подумать, что создание функций на лету и их использование приведет к замедлению работы программы. Но использование функций более высокого порядка на самом деле делает Haskell быстрее. Действительно, кажется, что для оптимизации кода на Haskell вам нужно сделать его более элегантным и абстрактным, а не более машиноподобным. Ни одна из более продвинутых функций Haskell, похоже, даже не повлияет на его производительность, если они не улучшат ее.

Извините, если это звучит бессмысленно, но вот мой вопрос: почему Haskell (скомпилирован с GHC) так быстр, учитывая его абстрактную природу и отличия от физических машин?

Примечание. Причина, по которой я говорю, что C и другие императивные языки чем-то похожи на машины Тьюринга (но не в той степени, в которой Haskell похож на лямбда-исчисление) заключается в том, что в императивном языке у вас есть конечное число состояний (или номер строки) вместе с магнитной лентой (тараном), так что состояние и текущая лента определяют, что делать с лентой. См. Статью Википедии « Эквиваленты машин Тьюринга» для перехода от машин Тьюринга к компьютерам.

Я согласен с Дитрихом Эппом: это сочетание нескольких вещей, которые делают GHC быстрым.

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

Подумайте о SQL. Теперь, когда я пишу SELECTзаявление, это может выглядеть как императивный цикл, но это не так . Может показаться, что он перебирает все строки в этой таблице, пытаясь найти ту, которая соответствует указанным условиям, но на самом деле «компилятор» (механизм БД) может вместо этого выполнять поиск индекса - который имеет совершенно разные характеристики производительности. Но поскольку SQL является настолько высокоуровневым, «компилятор» может заменить совершенно разные алгоритмы, прозрачно применить несколько процессоров или каналов ввода-вывода или целых серверов и многое другое.

Я думаю о Хаскеле как о том же самом. Вы можете подумать, что просто попросили Haskell сопоставить входной список со вторым списком, отфильтровать второй список в третий список, а затем посчитать, сколько элементов получилось. Но вы не видели, чтобы GHC применял правила перезаписи потокового слияния за кулисами, превращая все это в единый узкий цикл машинного кода, который выполняет всю работу за один проход по данным без выделения ресурсов - то, что могло бы быть утомительным, подверженным ошибкам и не подлежащим ремонту, чтобы писать от руки. Это действительно возможно только из-за отсутствия низкоуровневых деталей в коде.

Другой способ взглянуть на это может быть ... почему Хаскелл не должен быть быстрым? Что он делает, что должно сделать это медленно?

Это не интерпретируемый язык, как Perl или JavaScript. Это даже не система виртуальных машин, как Java или C #. Он компилируется вплоть до машинного кода, поэтому никаких накладных расходов нет.

В отличие от ОО-языков [Java, C #, JavaScript…], Haskell имеет полное стирание типов [например, C, C ++, Pascal…]. Вся проверка типов происходит только во время компиляции. Так что нет никакой проверки типов во время выполнения, чтобы замедлить вас. (Никаких проверок нулевого указателя, в этом отношении. В Java, скажем, JVM должна проверять нулевые указатели и выдавать исключение, если вы уважаете один. Haskell не должен беспокоиться об этой проверке.)

Вы говорите, что звучит медленно «создавать функции на лету во время выполнения», но если вы посмотрите очень внимательно, вы на самом деле этого не делаете. Это может выглядеть так, как ты, но не так. Если вы говорите (+5), ну, это жестко запрограммировано в вашем исходном коде. Это не может измениться во время выполнения. Так что это не совсем динамическая функция. Даже функции с карри на самом деле просто сохраняют параметры в блок данных. Весь исполняемый код фактически существует во время компиляции; нет интерпретации во время выполнения. (В отличие от некоторых других языков, которые имеют «функцию eval».)

Подумай о Паскале. Он старый и никто его больше не использует, но никто не будет жаловаться, что Паскаль медленный . Есть много вещей, которые могут не понравиться, но медлительность на самом деле не одна из них. На самом деле, Haskell не сильно отличается от Pascal, за исключением сбора мусора, а не ручного управления памятью. А неизменяемые данные позволяют несколько оптимизаций движку GC [что ленивая оценка затем несколько усложняет].

Я думаю, дело в том, что Haskell выглядит продвинутым, утонченным и высокоуровневым, и все думают: «Ого, это действительно мощно, это должно быть удивительно медленно! » Но это не так. Или, по крайней мере, это не так, как вы ожидаете. Да, у него есть удивительная система типов. Но вы знаете, что? Это все происходит во время компиляции. Во время выполнения это ушло. Да, это позволяет вам создавать сложные ADT со строкой кода. Но вы знаете, что? ADT - это просто обычный C unionиз structs. Ничего более.

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

Например, я написал небольшую простую программу, которая подсчитывает, сколько раз каждый байт появляется в файле. Для входного файла размером 25 КБ программе потребовалось 20 минут, чтобы проглотить 6 гигабайт оперативной памяти! Это абсурд !! Но потом я понял, в чем проблема, добавил один паттерн взрыва, и время выполнения упало до 0,02 секунды .

Это где Haskell идет неожиданно медленно. И, конечно, потребуется время, чтобы привыкнуть к этому. Но со временем становится проще писать действительно быстрый код.

Что делает Хаскелл так быстро? Чистота. Статические типы. Лень. Но, прежде всего, это достаточно высокий уровень, чтобы компилятор мог радикально изменить реализацию, не нарушая ожиданий вашего кода.

Но я думаю, что это только мое мнение ...

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

Вторая волна проектов возникла на основе сокращения графов и открыла возможность для гораздо более эффективной компиляции. Саймон Пейтон Джонс писал об этом исследовании в двух своих книгах «Реализация языков функционального программирования и реализация функциональных языков: учебник (первый с разделами Уодлера и Хэнкока, а второй с Дэвидом Лестером). (Леннарт Огюсссон также сообщил мне, что одним из ключевых мотивов для предыдущей книги было описание того, как его компилятор LML, который не был подробно прокомментирован, выполнил свою компиляцию).

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

Это описано в более поздней статье, в которой изложены основы того, как GHC все еще работает сегодня (хотя и по модулю многих различных настроек): «Внедрение ленивых функциональных языков на стандартном оборудовании: G-машина без тегов Spineless». , Текущая модель выполнения для GHC более подробно описана на вики GHC .

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

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

Вдобавок к этому есть много других оптимизаций, в частности, связанных с чистотой, поскольку это позволяет расширить диапазон «безопасных» преобразований. Когда и как применять эти преобразования так, чтобы они делали вещи лучше, а не хуже, - это, конечно, эмпирический вопрос, и в этом и многих других небольших вариантах работы были вложены как в теоретическую работу, так и в практический сравнительный анализ. Так что это, конечно, тоже играет роль. Хорошим примером такого рода исследований является документ « Создание быстрого карри: толчок / ввод по сравнению с оценкой / применение для языков высшего порядка».

Наконец, следует отметить, что эта модель все еще вводит накладные расходы из-за косвенных указаний. Этого можно избежать в тех случаях, когда мы знаем, что «строго» делать вещи строго и, таким образом, исключать косвенные зависимости графа. Механизмы, которые определяют строгость / требование, снова подробно описаны в вики GHC .

Ну, тут есть что комментировать. Я постараюсь ответить как можно больше.

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

По моему опыту, во многих случаях обычно можно получить в 2 раза больше производительности Rust. Но есть также некоторые (широкие) случаи использования, когда производительность низкая по сравнению с языками низкого уровня.

или даже побить его, но это означает, что вы используете неэффективную программу на C, поскольку GHC компилирует Haskell в C)

Это не совсем правильно. Haskell компилируется в C-- (подмножество C), который затем компилируется с помощью генератора собственного кода для сборки. Генератор собственного кода обычно генерирует более быстрый код, чем компилятор C, потому что он может применять некоторые оптимизации, которые не может сделать обычный компилятор C.

Архитектура машин явно обязательна, так как примерно основана на машинах Тьюринга.

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

Действительно, у Haskell даже нет определенного порядка оценки.

На самом деле, Haskell имеет неявно определяет порядок оценки.

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

Они соответствуют во многих случаях, если у вас достаточно продвинутый компилятор.

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

Haskell скомпилирован, и поэтому функции высшего порядка фактически не создаются на лету.

похоже, что он оптимизирует код на Haskell, вам нужно сделать его более элегантным и абстрактным, а не похожим на машинный.

В целом, сделать код более «машиноподобным» - непродуктивный способ повысить производительность в Haskell. Но сделать его более абстрактным тоже не всегда хорошая идея. Что является хорошей идеей является использование общих структур и функций , которые были сильно оптимизированы (например, связанные списки) данных.

f x = [x]и f = pureточно так же в Хаскеле, например. Хороший компилятор не даст лучшей производительности в первом случае.

Почему Haskell (скомпилирован с GHC) так быстр, учитывая его абстрактную природу и отличия от физических машин?

Короткий ответ: «потому что он был разработан именно для этого». GHC использует бесхребетный G-станок без меток (STG). Вы можете прочитать статью об этом здесь (это довольно сложно). GHC также делает много других вещей, таких как анализ строгости и оптимистическая оценка .

Причина, по которой я говорю, что C и другие императивные языки чем-то похожи на машины Тьюринга (но не в той степени, в которой Haskell похож на лямбда-исчисление) состоит в том, что в императивном языке у вас есть конечное число состояний (или номер строки), а также с лентой (плунжер), так что состояние и текущая лента определяют, что делать с лентой.

Является ли смысл путаницы, что изменчивость должна привести к замедлению кода? Лень в Haskell на самом деле означает, что изменчивость не так важна, как вы думаете, плюс она высокого уровня, поэтому компилятор может применить множество оптимизаций. Таким образом, изменение записи на месте редко будет медленнее, чем в языке, таком как C.

Почему Haskell (GHC) так чертовски быстр?

Должно быть, что-то кардинально изменилось с тех пор, как я в последний раз измерял производительность Haskell. Например:

• Тест обработки файлов RRD, где автор обнаружил, что Haskell потребовалось больше времени для разработки и работает медленнее (1020 с), чем Go (130 с) и OCaml (67 с), т.е. в 15 раз медленнее, чем OCaml.
• Простой словарь тест показал Haskell работает ~ 10x медленнее , чем F #.
• Ray Tracer Язык Сравнение является еще одним примером , когда Haskell был медленнее , чем C ++, OCaml и даже Java и Lisp.
• Параллельная родовая быстрая сортировка в Haskell составила 55% медленнее , чем F # и требует существенно больше коды.

Так что изменилось? Я заметил, что ни вопрос, ни какие-либо из его текущих ответов не относятся к каким-либо проверяемым тестам или даже коду.

Любимая вещь для Haskellers, чтобы попытаться получить в пределах 5% C

Есть ли у вас какие-либо ссылки на поддающиеся проверке результаты, когда кто-нибудь когда-либо приближался к этому?