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

Ответ 1

Я думаю, что это немного основано на мнениях. Но я постараюсь ответить.

Я согласен с Dietrich Epp: это комбинация нескольких вещей, которые быстро ускоряют GHC.

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

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

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

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

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

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

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

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

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

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

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

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

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

Но я думаю, что только мое мнение & hellip;

Ответ 2

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

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

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

Это описано в более позднем документе, в котором излагаются основы для того, как GHC по-прежнему работает сегодня (хотя и по модулю многих различных настроек): "Внедрение ленивых функциональных языков на складе Оборудование: без спины Tagless G-Machine." . Текущая модель исполнения для GHC более подробно описана в GHC Wiki.

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

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

Кроме того, в частности, существует множество других оптимизаций, открытых чистотой, поскольку это позволяет расширить диапазон "безопасных" преобразований. Когда и как применять эти преобразования, чтобы они делали все лучше и не хуже, это, конечно, эмпирический вопрос, и по этому и многим другим небольшим выборам годы работы были включены как в теоретическую работу, так и в практический бенчмаркинг. Так что это, конечно же, играет свою роль. Документ, который является хорошим примером такого рода исследований, - "Создание быстрого карри: Push/Enter vs. Eval/Apply для языков более высокого порядка.

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

Ответ 3

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

Used correctly, it can get close-ish to low-level languages.

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

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

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

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

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

На самом деле, у Хаскелла даже нет определенного порядка оценки.

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

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