Хороший вводный текст о реализации GHC? - PullRequest
Новая
       41

Хороший вводный текст о реализации GHC?

48 голосов
/ 18 мая 2011

При программировании на Haskell (и особенно при решении задач Project Euler, где неоптимальные решения имеют тенденцию подчеркивать потребности процессора или памяти), я часто удивляюсь, почему программа ведет себя так, как она есть. Я смотрю на профили, пытаюсь ввести некоторую строгость, выбираю другую структуру данных, но в основном она нащупывает в темноте, потому что мне не хватает хорошей интуиции.

Кроме того, хотя я знаю, как обычно реализуются языки Lisp, Prolog и императивные языки, я понятия не имею о реализации ленивого языка. Мне тоже немного любопытно.

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

Вещи, которые меня интересуют:

  • какие типичные оптимизации применяются?

  • каков порядок выполнения, когда существует несколько кандидатов для оценки (хотя я знаю, что это зависит от необходимых выходных данных, все еще могут быть большие различия в производительности между первой оценкой A и затем B, или оценкой B сначала для обнаружения что вам вообще не нужен A)

  • как изображаются громоотводы?

  • как используются стек и куча?

  • что такое CAF? (профилирование иногда указывает на наличие горячей точки, но я понятия не имею)

Ответы [ 2 ]

55 голосов
/ 18 мая 2011

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

Какие типичные оптимизации применяются?

Ключевой документ по этому вопросу: Оптимизатор на основе преобразования для Haskell , SL Peyton Jones and A Santos, 1998, в которой описывается модель, которую GHC использует для применения сохраняющих тип преобразований (рефакторингов) основного языка, похожего на Haskell, для улучшения использования времени и памяти. Этот процесс называется «упрощение».

Типичные вещи, которые выполняются в компиляторе Haskell, включают:

  • Встраивание;
  • снижение бета;
  • Устранение мертвого кода;
  • Преобразование условий: падеж, исключение падежа.
  • распаковка;
  • Возврат построенного продукта;
  • Полная трансформация лени;
  • Специализация;
  • Это расширение;
  • Лямбда-лифтинг;
  • Анализ строгости.

А иногда:

  • Статическое преобразование аргумента;
  • Сборка / складка или слияние потоков;
  • Устранение общего подвыражения;
  • Специализация конструктора.

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

Каков порядок выполнения при наличии нескольких кандидатов для оценки

Предполагая, что вы используете однопроцессорный процессор, ответом будет "некоторый порядок, который компилятор выбирает статически на основе эвристики и модели спроса программы". Если вы используете спекулятивную оценку с помощью искр, тогда «какой-то недетерминированный, не по порядку шаблон выполнения».

В общем, чтобы увидеть порядок выполнения, посмотрите на ядро, например, с помощью. инструмент ghc-core . введение в Core находится в главе RWH по оптимизации.

Как изображены громоотводы?

Thunks представлены в виде данных, выделенных кучей, с указателем кода.

Heap object

См. расположение объектов кучи . В частности, см. , как изображены громоотводы .

Как используются стек и куча?

Как определено конструкцией G-машины Spineless Tagless G , в частности, со многими модификациями с момента выпуска этой бумаги. В широком смысле, модель исполнения:

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

Чтобы глубже понять модель использования стека, см. «Push / Enter против Eval / Apply» .

Что такое CAF?

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

Список литературы и дальнейшее чтение :

9 голосов
/ 18 мая 2011

Это, вероятно, не то, что вы имели в виду с точки зрения вводного текста, но Эдвард Янг постоянно публикует серию постов в блогах, в которых обсуждается куча Haskell, как реализуются thunks и т. Д.

Это интересно,как с иллюстрациями, так и с помощью объяснения, не вдаваясь в подробности для кого-то нового в Haskell.Серия охватывает многие ваши вопросы:

На более техническом уровне есть ряд статей, которые охватывают (в сочетании сдругие вещи), части того, что вы хотите знать .:

  • Бумага SPJ, Саймона Марлоу и др. о GC в Хаскеле - я не читал ее, но поскольку GC часто представляет собой хороший пример работы, которую делает Haskell, он должен дать понимание.
  • Отчет о Haskell 2010 - я уверен, что вы слышали об этом, ноэто слишком хорошо, чтобы не ссылаться на.Может использоваться для сухого чтения в некоторых местах, но это один из лучших способов понять, что делает Haskell таким, какой он есть, по крайней мере, те части, которые я прочитал.является более техническим, чем можно предположить из названия, и предлагает некоторые очень интересные взгляды на дизайн Haskell и решения, лежащие в основе дизайна.Вы не можете помочь, но лучше понять реализацию Haskell после прочтения.
...