5 марта 2013 в 12:21

Принципы быстрого Хаскеля под GHC tutorial

GHC (Glasgow Haskell Compiler) — стандартный компилятор Хаскеля. GHC — один из самых крутых компиляторов в мире, но к сожалению без дополнительных телодвижений скомпилированные им программы по скорости больше напоминают интерпретируемые, т. е. работают очень медленно. Однако если раскрыть весь потенциал компилятора, Хаскель приближается по производительности к аналогичному коду на C.

В этой статье я обобщаю опыт выжимания максимума из GHC при создании dataflow-фреймворка Yarr.

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

Актуальная на данный момент версия GHC — 7.6.1.

Последнее замечание: на самом деле, с GHC «по умолчанию» все не так плохо, как описано в первом абзаце, хотя бы если просто компилировать с опцией -O2. Иногда компилятор делает быстрый машинный код и без подсказок программиста, но это зависит исключительно от положения звезд, бывает достаточно поправить в программе одну букву, чтобы GHC вдруг перестал понимать, как ее оптимизировать.



Можно выделить 2 основных направления оптимизаций, которые проводит GHC:
  • Расщепление типов данных на элементарные кусочки и преобразование функций для непосредственной работы с ними (см. Unboxed types and primitive operations)
  • Встраивание (inline) и специализация функций

Они поддерживают друг друга, т. е. если структуры данных не расщепляются, то хуже и встраиваются функции, и наоборот. Поэтому бессмысленно следовать только паре нижеследующих советов, результата почти не будет.

Типы данных


Избегайте типов данных с несколькими конструкторами

В том числе Maybe, Either и списков, какими бы «стандартными» они не были. Причина очевидна — такие типы данных нельзя разложить на составляющие, потому что статически не известно, какая у них вообще структура.

Единственное исключение — типы-перечисления с несколькими конструкторами без параметров: Bool, Ordering и т. д.

Если вдуматься, списки в Хаскеле — суть односвязные, которые практически не используются в императивных языках из-за своей медлительности. Так почему бы и в Хаскеле не использовать вместо них вектора (вместо стандартных строк — ByteString), едва ли уступающие спискам по удобству и возможностям. Для замены коротких списков в несколько элементов еще лучше подойдут вектора статически известной длины.

См. также: HaskellWiki — Performance/Data types.

Объявляйте поля в структурах строгими, если точно не знаете, почему они должны быть ленивыми

Обычное, ленивое поле — это ссылка на замыкание, которое вернет значение поля. Строгое поле — ссылка на значение поля. Встроенное (unboxed) поле — само значение (если это тоже структура, то она целиком встраивается в родительскую). Встроенное поле получается добавлением к строгому директивы {-# UNPACK #-}.

Без 1-го варианта, как и в случае со списками, на самом вполне неплохо живется. В каждом случае делайте осознанный выбор в пользу 2 или 3 варианта. Поля по ссылке иногда эффективнее по памяти, быстрее при создании структур, проверках на равенство. Встроенные поля быстрее при чтении. Если чаще нужны встроенные поля (скорее всего), компилируйте с флагом -funbox-strict-fields и добавляйте к «ссылочным» полям директиву {-# NOUNPACK #-}.

См. также: Haskell Style Guide/Dealing with laziness.

Явно вычисляйте структуры перед многократным использованием

В примере структура t много раз используется при отображении вектора:
import Data.Vector as V
...
data T = T !Int !Int
fSum (T x y) = x + y
...
    -- t :: T
    V.map (+ (fSum t)) longVectorOfInts

GHC не выносит вычисление структуры из «цикла»:
-- Как примерно GHC скомпилирует последнюю строчку
V.map (\x -> case t of (T y z) -> x + y + z) longVectorOfInts

В машинном коде на каждой итерации будет переход по ссылке и чтение одних и тех же полей.

Однако если «подсказать» компилятору снаружи цикла, он не повторяет вычисления, уже проведенные где-то выше по АСД (абстрактному синтаксическому дереву):
case t of (T x y) -> V.map (+ (fSum t)) longVectorOfInts
-- GHC скомпилирует нормально:
case t of (T x y) -> let s = x + y in V.map (\x -> x + s) longVectorOfInts

Вместо написания кейсов вручную можно использовать обобщенный control flow из пакета deepseq.

Пример не очень удачный, потому что структура t используется один раз и можно просто выделить fSum t как переменную, но думаю суть приема ясна.

Функции


Правило №1: добавляйте ко всем маленьким, часто (на рантайме) вызываемым, живущим далеко от корня АСД функциям директиву INLINE. Если функции не встраиваются, советы из этого раздела становятся вредными.

Больше функций, лямбд, каррирования!

Или, говоря по-умному, применяйте continuation passing style.

Преимущество замыканий перед структурами данных в том, что GHC гораздо положительнее настроен на их объединение и редукцию.

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


Чтобы гарантировать, что частично примененная функция будет специализирована, в определении разбейте аргументы лямбдой:
f :: A -> B -> C
{-# INLINE f #-}
f a b =
    ... -- body
  where ... -- declarations

-->

f a \b ->
    let ... -- declarations
    in ... -- body

Этот трюк описан в разделе INLINE pragma документации по GHC.

Будьте осторожны с обобщенными функциями

Вызов обобщенной функции (а-ля настоящий полиморфизм в императивных языках) не может быть заинлайнен по определению. Поэтому такие функции обязательно должны быть специализированы в месте вызова. Если GHC точно известен тип аргумента и сама обобщенная функция снабжена директивой INLINE, то он обычно делает это. При распространении обобщенности на несколько уровней функций — не специализирует.

Поднимайте на уровень типов все, что можно

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

В Yarr я использовал маркерные типы-индексы для статической двойной диспетчеризации, статическую арифметику (готовая арифметика и логика есть в библиотеке type-level) и некоторые другие вещи.

Флаги компиляции


-O2 — всегда.

О -funbox-strict-fields написано выше.

Сейчас за исключением редких случаев более быстрый машинный код генерирует бекенд LLVM: -fllvm -optlo-O3.

Чтобы GHC не занимался гаданием на кофейной гуще и встраивал все, что скажут, Ben Lippmeier рекомендует использовать флаги -funfolding-use-threshold1000 -funfolding-keeness-factor1000.
+25
6008
54
leventov 39,0 G+

Комментарии (21)

+4
VersusVoid, #
1. Уже 7.6.2
2. Вот это меня в Haskell и удручает, что для должной производительности приходится испещрять код всякими {-# INLINE f #-}, {-# UNPACK #-} и явными определениями переменных, которые нужно посчитать только один раз. Что средства, с которых начинается обучение и которые более всего свойственны языку (списки, Maybe, Either) медленны.
0
leventov, #
Да, отсутствие флага вроде -finline-functions-by-default — серьезное упущение. {-# NOINLINE #-} же есть.
0
VoidEx, #
П.2 явное преувеличение, dataflow-Фреймворки пишут не так и часто. Ну и Haskell не за производительность кода выбирают. Не встречался с обычными задачами, где тормоза были бы именно в Maybe/Either, а представить себе алгоритм, который упирался бы в обработку Maybe/Either сходу не могу.
0
leventov, #
Проблема в том, что клиентский код на этом фреймворке тоже приходится писать крайне внимательно, с прагмами и явными сигнатурами функций.
0
VoidEx, #
Это всё же достаточно специфичная задача, в таких задачах и на Си++ наивно не попишешь. То, что для такого языка можно получить быстрый код хотя бы так уже хорошо. Можно не бояться, что придётся переписывать всё из-за тормозов.
Нередко, кстати, встречается другое заблуждение, что на C++ можно получить быстрый код нахаляву, а меж тем наивный код на C++ и Haskell работают сравнимо, а именно такого кода больше всего.
Как раз скорость наивного кода более всего и интересна, т.е. насколько будет тормозить обычный код, и не придётся ли из-за этого всё переписывать.
0
leventov, #
Это надо очень сильно постараться, чтобы написать на C++ так же медленно, как на «дефолтном» Хаскеле.

И на мой взгляд вопрос в Хаскеле не сколько в наивности, столько в бойлерплейте.
+1
VoidEx, #
> Это надо очень сильно постараться, чтобы написать на C++ так же медленно, как на «дефолтном» Хаскеле.
Почему вы так считаете?

Я не делал специального сравнения, но не раз натыкался на различные типичные задачи, где наивные решения на C++ и Haskell были сравнимы с переменным лидерством.
0
leventov, #
Сомневаюсь:
1) Откажитесь почти от всего STL. std::string, std::vector и std::map — это слишком быстро для Хаскеля. Только std::forward_list, только хардкор.
2) Где в C++ обычное тело цикла, в Хаскеле вызов функции. Причем вызов в Хаскеле — это не просто аргументы на стек и call, там же еще рантайм таскает по стеку туда-сюда кучу внутренних переменных.

И так далее…
+1
VoidEx, #
Я склонен не доверять предсказаниям, потому что тормозит, как известно, не там, где думает программист.
Так что это будет верно только если считать, что в Haskell тормозит всё и везде.

Про std::forward_list не понял, если честно. Или ByteString и Text это сродни forward_list, по-вашему?
0
leventov, #
В «дефолтном» Хаскеле для строк применяется type String = [Char].
0
VoidEx, #
А причём тут дефолтный Хаскель? Речь о «наивном» реально используемом коде, а там уже давным давно стандарт ByteString/Text.
0
leventov, #
Ах, если бы. Даже на hackage меньше половины пакетов зависят от bytestring либо text. (Всего пакетов, по данным Hayoo, 4750.)
+2
VoidEx, #
Как будто оставшаяся половина активно работает со строками и String будет там тормозить.
0
leventov, #
Ок, тут вы правы, ByteString народ похоже использовать приучился :)
0
VoidEx, #
На самом деле, внятных хороших исследований этого вопроса я не видел, меряют на каких-то синтетических тестах да исходят из посылов, что на C++ всё быстрее по умолчанию, поэтому всё довольно туманно.
0
vshabanov, #
> Это надо очень сильно постараться, чтобы написать на C++ так же медленно, как на «дефолтном» Хаскеле.

Попробуйте написать не числодробильню, а какой-нибудь компилятор или хотя бы работу с графами. Скорее всего придется сильно постараться в С++, чтобы догнать Хаскелл.
+1
vshabanov, #
Не соглашусь, что стоит во всех структурах делать поля строгими. Зачастую это может ухудшить производительность, т.к. начнет вычисляться то, что могло бы и не вычисляться. UNPACK также может навредить, если его значение надо будет передавать в какую-либо ф-ю, ожидающую ленивое значение.

Вместо INLINE зачастую лучше INLINABLE, чтобы GHC сам решал инлайнить, или нет.

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

Насчет INLINABLE не согласен, GHC очень печется о лишней паре килобайт бинарника и сам почти ничего не инлайнит.
0
vshabanov, #
Тут все зависит от типа разрабатываемой программы. Для числодробильни важно инлайнить, разворачивать циклы, не делать лишних ветвлений и вообще ничего лишнего не делать. А для программ с более-менее развесистой логикой ленивость может запросто выиграть, т.к. не будет вычислять то, что не нужно.

GHC, возможно, не зря печется о лишних килобайтах, т.к. не всегда инлайн дает ускорение. Посмотрите на исходники того же Data.Map. Там именно INLINABLE и не везде.
0
leventov, #
Вообще у INLINABLE кажется немного другая семантика, с кросс-модульной компиляцией связанная. Так-то GHC и функции совсем без прагмы решает, встраивать или нет, теоретически.
0
Qrilka, #
Для строк есть Text, байтстринги (что и следует из названия) предназначены для хранения последовательностей байт, или вы за пределы ASCII не вылезаете и

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