почему haskell (ghc) так чертовски быстр?

<p>haskell (с компилятором <code>ghc</code>) - это <a href="https://wiki.haskell.org/why\_haskell\_matters#the\_speed\_of\_haskell">намного быстрее, чем вы ожидаете</a> . при правильном использовании он может приблизиться к языкам низкого уровня. (любимая вещь для haskellers - попытаться получить в пределах 5% от c (или даже побить его, но это означает, что вы используете неэффективную программу на c, поскольку ghc компилирует haskell в c).) мой вопрос: почему?</p><p>хаскель декларативен и основан на лямбда-исчислении. архитектура машин явно обязательна, грубо говоря, на основе машин тьюринга. действительно, у haskell даже нет определенного порядка оценки. кроме того, вместо того, чтобы иметь дело с типами машинных данных, вы постоянно создаете алгебраические типы данных.</p><p>самое странное, что это функции высшего порядка. вы могли бы подумать, что создание функций на лету и их использование приведет к замедлению работы программы. <a href="https://hbtvl.wordpress.com/2015/12/14/efficient-parsing-of-large-text-files-part-4-and-conclusion/">но использование функций более высокого порядка на самом деле делает haskell быстрее.</a> действительно, кажется, что для оптимизации кода на haskell вам нужно сделать его более элегантным и абстрактным, а не более машиноподобным. кажется, что ни одна из более продвинутых функций haskell даже <em> не влияет </em> на его производительность, если они не улучшают ее.</p><p>извините, если это звучит бессмысленно, но вот мой вопрос: <strong> почему haskell (скомпилирован с ghc) так быстр, учитывая его абстрактную природу и отличия от физических машин? </strong></p><p>примечание. причина, по которой я говорю, что c и другие императивные языки чем-то похожи на машины тьюринга (но не в той степени, в которой haskell похож на лямбда-исчисление) состоит в том, что в императивном языке у вас есть конечное число состояний (или номер строки) вместе с магнитной лентой (тараном), так что состояние и текущая лента определяют, что делать с лентой. смотрите статью в википедии <a href="https://en.wikipedia.org/wiki/turing\_machine\_equivalents">эквиваленты машин тьюринга</a> , чтобы перейти от машин тьюринга к компьютерам.</p>

<p>долгое время считалось, что функциональные языки не могут быть быстрыми - и особенно ленивые функциональные языки. но это было потому, что их ранние реализации были, по сути, интерпретированы и не были действительно скомпилированы.</p><p>вторая волна проектов появилась на основе сокращения графов и открыла возможность для гораздо более эффективной компиляции. саймон пейтон джонс писал об этом исследовании в своих двух книгах <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/">реализация языков функционального программирования</a> и <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/">реализация функциональных языков: учебное пособие</a> (первый с разделами уодлера и хэнкока, а также последний написан с дэвидом лестером). (леннарт огюсссон также сообщил мне, что одним из ключевых мотивов для предыдущей книги было описание того, как его компилятор lml, который не был подробно прокомментирован, выполнил свою компиляцию).</p><p>ключевое понятие, лежащее в основе подходов сокращения графов, таких как описанные в этих работах, заключается в том, что мы не думаем о программе как о последовательности инструкций, а о графе зависимостей, который <em> оценивается </em> через серию локальных сокращений. второе ключевое понимание заключается в том, что оценку такого графа <em> не нужно интерпретировать </em>, но вместо этого можно использовать сам график <em>. построен из кода </em>. в частности, мы можем представить узел графа не как "либо значение, либо" код операции и значения для работы ", но вместо этого как функцию, которая при вызове возвращает желаемое значение. в первый раз, когда он вызывается, он запрашивает у подузлов их значения, а затем воздействует на них, <em>, а затем </em> перезаписывает себя новой инструкцией, которая просто говорит "вернуть результат."</p><p>это описано в более поздней статье, в которой изложены основы того, как ghc все еще работает сегодня (хотя по модулю много различных настроек): <a href="https://www.researchgate.net/publication/220676558\_implementing\_lazy\_functional\_languages\_on\_stock\_hardware\_the\_spineless\_tagless\_g-machine">"реализация ленивых функциональных языков на стандартном оборудовании: g-машина без тегов без шпинделей".</a> , текущая модель выполнения для ghc более подробно описана в <a href="https://ghc.haskell.org/trac/ghc/wiki/commentary/rts/haskellexecution">ghc wiki</a> .</p><p>таким образом, понимание заключается в том, что строгое различие между "данными" и "кодом", которое мы считаем "фундаментальным" для работы машин, заключается не в том, как они должны работать, а навязывается нашими компиляторами. таким образом, мы можем выбросить это и иметь код (компилятор), который генерирует самоизменяющийся код (исполняемый файл), и все это может работать довольно хорошо.</p><p>таким образом, получается, что, хотя архитектуры машин в определенном смысле являются императивными, языки могут отображаться на них очень удивительными способами, которые не похожи на обычное управление потоком в стиле c, и если мы думаем достаточно низкоуровнево, это также может быть эффективный.</p><p>вдобавок к этому есть много других оптимизаций, в частности, связанных с чистотой, поскольку это позволяет расширить диапазон "безопасных" преобразований. когда и как применять эти преобразования так, чтобы они делали вещи лучше, а не хуже, это, конечно, эмпирический вопрос, и в связи с этим и многими другими небольшими вариантами годы работы были вложены как в теоретическую работу, так и в практический сравнительный анализ. так что это, конечно, тоже играет роль. хорошим примером такого рода исследований является документ " <a href="http://community.haskell.org/~simonmar/papers/evalapplyjfp06.pdf">создание быстрого карри: толчок/ввод по сравнению с оценкой/применение для языков высшего порядка".</a> </p><p>наконец, следует отметить, что эта модель все еще вводит накладные расходы из-за косвенных указаний. этого можно избежать в тех случаях, когда мы знаем, что "безопасно" строго выполнять действия и, таким образом, исключать косвенные зависимости графа. механизмы, которые определяют строгость/требование, снова подробно описаны в <a href="https://ghc.haskell.org/trac/ghc/wiki/commentary/compiler/demand">ghc wiki</a> .</p>

<p>ну, тут есть что комментировать. я постараюсь ответить как можно больше.</p><blockquote> <p>при правильном использовании он может приблизиться к языкам низкого уровня.</p> </blockquote><p>по моему опыту, во многих случаях обычно можно в два раза увеличить производительность rust. но есть также некоторые (широкие) случаи использования, когда производительность низкая по сравнению с языками низкого уровня.</p><blockquote> <p>или даже побить его, но это означает, что вы используете неэффективную программу на c, поскольку ghc компилирует haskell в c)</p> </blockquote><p>это не совсем правильно. haskell компилируется в c <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/1992/04/spineless-tagless-gmachine.pdf">подмножество c), который затем компилируется с помощью генератора собственного кода в assembly. генератор собственного кода обычно генерирует более быстрый код, чем компилятор c, потому что он может применять некоторые оптимизации, которые не может сделать обычный компилятор c.</p><blockquote> <p>архитектура машин явно обязательна, грубо говоря, на основе машин тьюринга.</p> </blockquote><p>это не очень хороший способ думать об этом, тем более что современные процессоры будут оценивать команды не по порядку и, возможно, одновременно.</p><blockquote> <p>действительно, у haskell даже нет определенного порядка оценки.</p> </blockquote><p>на самом деле, haskell <em> </em> неявно определяет порядок оценки.</p><blockquote> <p>кроме того, вместо того, чтобы иметь дело с типами машинных данных, вы постоянно создаете алгебраические типы данных.</p> </blockquote><p>они соответствуют во многих случаях, если у вас достаточно продвинутый компилятор.</p><blockquote> <p>вы могли бы подумать, что создание функций на лету и их использование приведет к замедлению работы программы.</p> </blockquote><p>haskell компилируется, и поэтому функции высшего порядка на самом деле не создаются на лету.</p><blockquote> <p>похоже, что он оптимизирует код на haskell, вам нужно сделать его более элегантным и абстрактным, а не похожим на компьютер.</p> </blockquote><p>в целом, сделать код более "машиноподобным" - непродуктивный способ повысить производительность в haskell. но сделать его более абстрактным тоже не всегда хорошая идея. что <em> является </em> хорошей идеей - использовать общие структуры данных и функции, которые были сильно оптимизированы (например, связанные списки).</p><p>например, <code>f x = [x]</code> и <code>f = pure</code> - это одно и то же в haskell. хороший компилятор не даст лучшей производительности в первом случае.</p><blockquote> <p>почему haskell (скомпилирован с ghc) так быстр, учитывая его абстрактную природу и отличия от физических машин?</p> </blockquote><p>короткий ответ: "потому что он был разработан именно для этого". ghc использует бесхребетный g-станок без меток (stg). вы можете прочитать статью об этом --- (здесь</a> (это довольно сложно). ghc также делает много других вещей, таких как анализ строгости и <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/icfp2003.pdf">оптимистичная оценка</a> .</p><blockquote> <p>причина, по которой я говорю, что c и другие императивные языки чем-то похожи на машины тьюринга (но не в той степени, в которой haskell похож на лямбда-исчисление) состоит в том, что в императивном языке у вас есть конечное число состояний (или номер строки), а также с лентой (плунжер), так что состояние и текущая лента определяют, что делать с лентой.</p> </blockquote><p>является ли смысл путаницы, что изменчивость должна привести к замедлению кода? на самом деле лень хаскелла означает, что изменчивость не так важна, как вы думаете, плюс она высокого уровня, поэтому компилятор может применить множество оптимизаций. таким образом, изменение записи на месте редко будет медленнее, чем в языке, таком как c.</p>