Какую оптимизацию можно ожидать от GHC для надежной работы?

У GHC есть много оптимизаций, которые он может выполнять, но я не знаю, что это все, и насколько они вероятны, и при каких обстоятельствах.

Мой вопрос: какие преобразования я могу ожидать, что он будет применяться каждый раз, или почти так? Если я посмотрю на фрагмент кода, который будет выполняться (оцениваться) часто, и моя первая мысль "хм, может быть, я должен это оптимизировать", в каких случаях должна быть моя вторая мысль: "Даже не думай об этом, GHC получил это??

Я читал статью Stream Fusion: от списков до потоков до ничего вообще и метод, используемый для обработки переписывающих списков в другая форма, которую нормальная оптимизация GHC надежно оптимизировала бы до простых циклов, была для меня новой. Как я могу сказать, когда мои собственные программы имеют право на такую оптимизацию?

Там некоторая информация в руководстве GHC, но это лишь часть пути ответа на вопрос.

EDIT: Я начинаю щедрость. Я бы хотел, чтобы список преобразований более низкого уровня, таких как lambda/let/case-floating, спецификация аргументов типа/конструктора/функции, анализ строгости и распаковки, рабочий/обертка и все остальное значимое GHC, которое я забыл, наряду с пояснениями и примерами кода ввода и вывода и идеально иллюстрирует ситуации, когда общий эффект больше, чем сумма его частей. И в идеале, некоторые упоминания о том, когда трансформаций не произойдет. Я не ожидаю объяснений новой длины для каждой трансформации, может быть достаточно нескольких предложений и примеров внутристрочного кода с одним слоем (или ссылки, если это не двадцать страниц научной статьи), если общая картина ясно до конца. Я хочу, чтобы иметь возможность взглянуть на кусок кода и быть в состоянии дать хорошее представление о том, будет ли он скомпилирован до жесткой петли, или почему бы нет, или что я должен был бы изменить, чтобы сделать это. (Мне неинтересно так много здесь, в больших оптимизационных средах, таких как stream fusion (я только что прочитал статью об этом), больше в том знании, которое люди, пишущие эти рамки, имеют.)

Ответы

Ответ 1

Эта страница GHC Trac также хорошо объясняет проходы. Эта страница объясняет порядок оптимизации, хотя, как и большинство Wiki Trac, она устарела.

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

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43
wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
*** Chasing dependencies:
Chasing modules from: *SleepSort.hs
Stable obj: [Main]
Stable BCO: []
Ready for upsweep
  [NONREC
      ModSummary {
         ms_hs_date = Tue Oct 18 22:22:11 CDT 2011
         ms_mod = main:Main,
         ms_textual_imps = [import (implicit) Prelude, import Control.Monad,
                            import Control.Concurrent, import System.Environment]
         ms_srcimps = []
      }]
*** Deleting temp files:
Deleting: 
compile: input file SleepSort.hs
Created temporary directory: /tmp/ghc4784_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main             ( SleepSort.hs, SleepSort.o )
*** Parser:
*** Renamer/typechecker:
*** Desugar:
Result size of Desugar (after optimization) = 79
*** Simplifier:
Result size of Simplifier iteration=1 = 87
Result size of Simplifier iteration=2 = 93
Result size of Simplifier iteration=3 = 83
Result size of Simplifier = 83
*** Specialise:
Result size of Specialise = 83
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = False}) = 95
*** Float inwards:
Result size of Float inwards = 95
*** Simplifier:
Result size of Simplifier iteration=1 = 253
Result size of Simplifier iteration=2 = 229
Result size of Simplifier = 229
*** Simplifier:
Result size of Simplifier iteration=1 = 218
Result size of Simplifier = 218
*** Simplifier:
Result size of Simplifier iteration=1 = 283
Result size of Simplifier iteration=2 = 226
Result size of Simplifier iteration=3 = 202
Result size of Simplifier = 202
*** Demand analysis:
Result size of Demand analysis = 202
*** Worker Wrapper binds:
Result size of Worker Wrapper binds = 202
*** Simplifier:
Result size of Simplifier = 202
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = True}) = 210
*** Common sub-expression:
Result size of Common sub-expression = 210
*** Float inwards:
Result size of Float inwards = 210
*** Liberate case:
Result size of Liberate case = 210
*** Simplifier:
Result size of Simplifier iteration=1 = 206
Result size of Simplifier = 206
*** SpecConstr:
Result size of SpecConstr = 206
*** Simplifier:
Result size of Simplifier = 206
*** Tidy Core:
Result size of Tidy Core = 206
writeBinIface: 4 Names
writeBinIface: 28 dict entries
*** CorePrep:
Result size of CorePrep = 224
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:
*** Assembler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-I.' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' 'SleepSort.o'
Upsweep completely successful.
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s
Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c
link: linkables are ...
LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main
   [DotO SleepSort.o]
Linking SleepSort ...
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.c' '-o' '/tmp/ghc4784_0/ghc4784_0.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' '/tmp/ghc4784_0/ghc4784_1.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** Linker:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-o' 'SleepSort' 'SleepSort.o' '-L/usr/lib/ghc-7.4.2/base-4.5.1.0' '-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0' '-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0' '-L/usr/lib/ghc-7.4.2' '/tmp/ghc4784_0/ghc4784_0.o' '/tmp/ghc4784_0/ghc4784_1.o' '-lHSbase-4.5.1.0' '-lHSinteger-gmp-0.4.0.0' '-lgmp' '-lHSghc-prim-0.2.0.0' '-lHSrts' '-lm' '-lrt' '-ldl' '-u' 'ghczmprim_GHCziTypes_Izh_static_info' '-u' 'ghczmprim_GHCziTypes_Czh_static_info' '-u' 'ghczmprim_GHCziTypes_Fzh_static_info' '-u' 'ghczmprim_GHCziTypes_Dzh_static_info' '-u' 'base_GHCziPtr_Ptr_static_info' '-u' 'base_GHCziWord_Wzh_static_info' '-u' 'base_GHCziInt_I8zh_static_info' '-u' 'base_GHCziInt_I16zh_static_info' '-u' 'base_GHCziInt_I32zh_static_info' '-u' 'base_GHCziInt_I64zh_static_info' '-u' 'base_GHCziWord_W8zh_static_info' '-u' 'base_GHCziWord_W16zh_static_info' '-u' 'base_GHCziWord_W32zh_static_info' '-u' 'base_GHCziWord_W64zh_static_info' '-u' 'base_GHCziStable_StablePtr_static_info' '-u' 'ghczmprim_GHCziTypes_Izh_con_info' '-u' 'ghczmprim_GHCziTypes_Czh_con_info' '-u' 'ghczmprim_GHCziTypes_Fzh_con_info' '-u' 'ghczmprim_GHCziTypes_Dzh_con_info' '-u' 'base_GHCziPtr_Ptr_con_info' '-u' 'base_GHCziPtr_FunPtr_con_info' '-u' 'base_GHCziStable_StablePtr_con_info' '-u' 'ghczmprim_GHCziTypes_False_closure' '-u' 'ghczmprim_GHCziTypes_True_closure' '-u' 'base_GHCziPack_unpackCString_closure' '-u' 'base_GHCziIOziException_stackOverflow_closure' '-u' 'base_GHCziIOziException_heapOverflow_closure' '-u' 'base_ControlziExceptionziBase_nonTermination_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnMVar_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnSTM_closure' '-u' 'base_ControlziExceptionziBase_nestedAtomically_closure' '-u' 'base_GHCziWeak_runFinalizzerBatch_closure' '-u' 'base_GHCziTopHandler_flushStdHandles_closure' '-u' 'base_GHCziTopHandler_runIO_closure' '-u' 'base_GHCziTopHandler_runNonIO_closure' '-u' 'base_GHCziConcziIO_ensureIOManagerIsRunning_closure' '-u' 'base_GHCziConcziSync_runSparks_closure' '-u' 'base_GHCziConcziSignal_runHandlers_closure'
link: done
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c
*** Deleting temp dirs:
Deleting: /tmp/ghc4784_0

Взглянув с первого *** Simplifier: на последний, где все фазы оптимизации происходят, мы видим довольно много.

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

Далее мы видим полный список всех выполненных оптимизаций:

Специализируются

Основная идея специализации заключается в удалении полиморфизма и перегрузки путем определения мест, где вызывается функция, и создания версий функции, которые не являются полиморфными, - они специфичны для типов, с которыми они вызываются. Вы также можете сообщить компилятору об этом с помощью SPECIALISE прагмы. В качестве примера возьмем факторную функцию:
```
fac :: (Num a, Eq a) => a -> a
fac 0 = 1
fac n = n * fac (n - 1)
```
Поскольку компилятор не знает каких-либо свойств используемого умножения, он вообще не может его оптимизировать. Если, однако, он видит, что он используется на Int, теперь он может создать новую версию, отличающуюся только типом:
```
fac_Int :: Int -> Int
fac_Int 0 = 1
fac_Int n = n * fac_Int (n - 1)
```
Далее, правила, упомянутые ниже, могут запускаться, и вы получаете что-то, работающее на unboxed Int s, которое намного быстрее оригинала. Еще один способ взглянуть на специализацию - это частичное приложение для словарей типа и переменных типа.

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

EDIT: Я, по-видимому, неправильно понял это раньше. Мое объяснение полностью изменилось.

Основная идея состоит в том, чтобы переместить вычисления, которые не должны повторяться из функций. Например, предположим, что у нас было это:
```
\x -> let y = expensive in x+y
```
В приведенной выше лямбде каждый раз, когда вызывается функция, y пересчитывается. Лучшая функция, которая производит плавание, составляет
```
let y = expensive in \x -> x+y
```
Чтобы облегчить процесс, могут быть применены другие преобразования. Например, это происходит:
```
 \x -> x + f 2
 \x -> x + let f_2 = f 2 in f_2
 \x -> let f_2 = f 2 in x + f_2
 let f_2 = f 2 in \x -> x + f_2
```
Снова повторяется повторное вычисление.

Источник в этом случае очень читаем.

В настоящий момент привязки между двумя соседними лямбдами не плавают. Например, этого не происходит:
```
\x y -> let t = x+x in ...
```
будет
```
 \x -> let t = x+x in \y -> ...
```
Поплавок внутрь

Цитата исходного кода,

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

В качестве примера предположим, что мы имеем это выражение:
```
let x = big in
    case v of
        True -> x + 1
        False -> 0
```
Если v оценивается как False, то, выделяя x, предположительно какой-то большой кусок, мы потратили впустую время и пространство. Плавающий внутрь исправляет это, производя это:
```
case v of
    True -> let x = big in x + 1
    False -> let x = big in 0
```
который впоследствии заменяется упростителем с
```
case v of
    True -> big + 1
    False -> 0
```
Эта статья, хотя и охватывает другие темы, дает довольно четкое представление. Обратите внимание, что, несмотря на их имена, плавающие и плавающие не попадают в бесконечный цикл по двум причинам:
- Float in floats позволяет в операторах case, а float out - с функциями.
- Существует фиксированный порядок проходов, поэтому они не должны чередоваться бесконечно.

Анализ спроса

Анализ спроса или анализ строгости - это не просто трансформация, а больше, как, например, название, означает пропуск сбора информации. Компилятор находит функции, которые всегда оценивают свои аргументы (или, по крайней мере, некоторые из них), и передают эти аргументы, используя call-by-value, а не call-by-need. Поскольку вы избегаете накладных расходов, это часто намного быстрее. Многие проблемы с производительностью в Haskell возникают из-за сбоя этого прохода, или кода просто недостаточно строго. Простым примером является различие между использованием foldr, foldl и foldl', чтобы суммировать список целых чисел - первый вызывает переполнение стека, второе вызывает переполнение кучи, а последнее работает нормально, из-за строгости. Это, вероятно, самый простой способ понять и лучше всего документировать из всех этих. Я считаю, что полиморфизм и код CPS часто побеждают это.
Рабочий Wrapper связывает

Основная идея преобразования worker/wrapper заключается в том, чтобы сделать жесткий цикл на простой структуре, конвертируя ее в и из этой структуры на концах. Например, возьмите эту функцию, которая вычисляет факториал числа.
```
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
```
Используя определение Int в GHC, имеем
```
factorial :: Int -> Int
factorial (I# 0#) = I# 1#
factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
    I# down# -> down#)
```
Обратите внимание, как код распространяется в I# s? Мы можем удалить их, выполнив следующие действия:
```
factorial :: Int -> Int
factorial (I# n#) = I# (factorial# n#)

factorial# :: Int# -> Int#
factorial# 0# = 1#
factorial# n# = n# *# factorial# (n# -# 1#)
```
Хотя этот конкретный пример также мог быть выполнен с помощью SpecConstr, преобразование рабочего/обертки является очень общим в том, что он может сделать.
Общее подвыражение

Это еще одна очень простая оптимизация, которая очень эффективна, как анализ строгости. Основная идея состоит в том, что если у вас есть два выражения, которые одинаковы, они будут иметь одинаковое значение. Например, если fib является калькулятором числа Фибоначчи, CSE преобразует
```
fib x + fib x
```
в
```
let fib_x = fib x in fib_x + fib_x
```
который сокращает вычисление пополам. К сожалению, это может иногда мешать другим оптимизации. Другая проблема заключается в том, что два выражения должны быть в одном месте и что они должны быть синтаксически одинаковыми, а не одинаковыми по значению. Например, CSE не будет запускаться в следующем коде без связки:
```
x = (1 + (2 + 3)) + ((1 + 2) + 3)
y = f x
z = g (f x) y
```
Однако, если вы скомпилируете через llvm, вы можете получить некоторые из этих объединений из-за своего пропущенного номера глобальной стоимости.
Освободите дело

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

Этот модуль проходит Core и ищет case для свободных переменных. Критерием является: если на пути к рекурсивному вызову есть case на свободной переменной, то рекурсивный вызов заменяется разворачиванием. Например, в
```
f = \ t -> case v of V a b -> a : f t
```
внутренний f заменяется. сделать
```
f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t
```
Обратите внимание на необходимость затенения. Упрощая, получаем
```
f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)
```
Это лучший код, потому что a свободен внутри внутреннего letrec, вместо того, чтобы проектировать его из v. Обратите внимание, что это касается свободных переменных, в отличие от SpecConstr, который имеет дело с аргументами известной формы.

См. ниже дополнительную информацию о SpecConstr.
SpecConstr - это преобразование программ типа
```
f (Left x) y = somthingComplicated1
f (Right x) y = somethingComplicated2
```
в
```
f_Left x y = somethingComplicated1
f_Right x y = somethingComplicated2

{-# INLINE f #-}
f (Left x) = f_Left x
f (Right x) = f_Right x
```
В качестве расширенного примера возьмите это определение last:
```
last [] = error "last: empty list"
last (x:[]) = x
last (x:x2:xs) = last (x2:xs)
```
Сначала преобразуем его в
```
last_nil = error "last: empty list"
last_cons x [] = x
last_cons x (x2:xs) = last (x2:xs)

{-# INLINE last #-}
last [] = last_nil
last (x : xs) = last_cons x xs
```
Далее, выполняется упрощение, и мы имеем
```
last_nil = error "last: empty list"
last_cons x [] = x
last_cons x (x2:xs) = last_cons x2 xs

{-# INLINE last #-}
last [] = last_nil
last (x : xs) = last_cons x xs
```
Обратите внимание, что программа работает быстрее, поскольку мы не многократно боксируем и распаковываем переднюю часть списка. Также обратите внимание, что вложение имеет решающее значение, поскольку оно позволяет использовать новые более эффективные определения, а также делать рекурсивные определения лучше.

SpecConstr управляется несколькими эвристиками. Те, что упоминаются в документе, таковы:
- Ярлыки явны и arity a.
- Правая сторона "достаточно мала", что-то контролируется флагом.
- Функция рекурсивна, и специализированный вызов используется в правой части.
- Все аргументы функции присутствуют.
- По крайней мере один из аргументов - это приложение-конструктор.
- Этот аргумент анализируется случайным образом в функции.
Однако эвристика почти наверняка изменилась. Фактически, в документе упоминается альтернативная шестая эвристика:

Специализируйте аргумент x, только если x проверяется только case и не передается обычной функции или не возвращается как часть результата.

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

Ответ 2

Лень

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

Это, очевидно, целая тема сама по себе, и у SO есть много вопросов и ответов об этом уже.

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

Анализ строгости

Лень - это отказ от работы, если это не необходимо. Если компилятор может определить, что данный результат будет "всегда" нужен, он не захочет хранить вычисления и выполнять его позже; он будет просто выполнять его напрямую, потому что это более эффективно. Это так называемый "анализ строгости".

В результате, очевидно, что компилятор не всегда может обнаружить, когда что-то можно сделать строгим. Иногда вам нужно дать компилятору небольшие намеки. (Я не знаю, какой простой способ определить, сделал ли анализ строгости то, что, по вашему мнению, имеет, кроме прошивки через вывод Core.)

Встраивание

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

Функции только встроены, если они "достаточно малы" (или если вы добавляете прагму, специально запрашивающую вложение). Кроме того, функции могут быть включены только в том случае, если компилятор может определить, какую функцию вы вызываете. Существует два основных способа, которые компилятор не может сказать:

Если функция, которую вы вызываете, передается из другого места. Например, когда функция filter скомпилирована, вы не можете встроить предикат фильтра, поскольку это аргумент, предоставленный пользователем.
Если функция, которую вы вызываете, является методом класса, а компилятор не знает, какой тип задействован. Например, когда функция sum компилируется, компилятор не может встроить функцию +, потому что sum работает с несколькими разными типами номеров, каждая из которых имеет другую функцию +.

В последнем случае вы можете использовать прагму {-# SPECIALIZE #-} для генерации версий функции, жестко закодированной для определенного типа. Например, {-# SPECIALIZE sum :: [Int] -> Int #-} будет компилировать версию sum жестко закодированную для типа Int, что означает, что + может быть встроена в эту версию.

Обратите внимание, что наша новая специальная функция sum вызывается только тогда, когда компилятор может сказать, что мы работаем с Int. В противном случае вызывается оригинальный, полиморфный sum. Опять же, фактическая накладная функция вызова довольно мала. Это дополнительные оптимизации, которые могут помочь встраивание, которые полезны.

Исключение общей подвыражения

Если определенный блок кода вычисляет одно и то же значение дважды, компилятор может заменить его одним экземпляром одного и того же вычисления. Например, если вы делаете

(sum xs + 1) / (sum xs + 2)

тогда компилятор может оптимизировать это для

let s = sum xs in (s+1)/(s+2)

Вы можете ожидать, что компилятор всегда это сделает. Однако, по-видимому, в некоторых ситуациях это может привести к ухудшению производительности, а не к лучшему, поэтому GHC не всегда это делает. Честно говоря, я не совсем понимаю детали этого. Но суть в том, что если это преобразование важно для вас, это не сложно сделать вручную. (И если это не важно, почему вы беспокоитесь об этом?)

Примеры выражений

Рассмотрим следующее:

foo (0:_ ) = "zero"
foo (1:_ ) = "one"
foo (_:xs) = foo xs
foo (  []) = "end"

Первые три уравнения проверяют, является ли список непустым (между прочим). Но проверка одного и того же трижды бесполезно. К счастью, компилятор очень легко оптимизировать это в несколько вложенных выражений case. В этом случае что-то вроде

foo xs =
  case xs of
    y:ys ->
      case y of
        0 -> "zero"
        1 -> "one"
        _ -> foo ys
    []   -> "end"

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

Fusion

Стандартная иксема Haskell для обработки списка состоит в объединении функций, которые берут один список и создают новый список. Канонический пример:

map g . map f

К сожалению, в то время как лень гарантирует пропущенную ненужную работу, все распределения и освобождения от промежуточного списка. "Fusion" или "обезлесение" - это то, где компилятор пытается устранить эти промежуточные шаги.

Проблема в том, что большинство из этих функций являются рекурсивными. Без рекурсии было бы элементарным упражнением в inlining, чтобы скомбинировать все функции в один большой блок кода, запустить упроститель над ним и создать действительно оптимальный код без промежуточных списков. Но из-за рекурсии это не сработает.

Вы можете использовать {-# RULE #-} прагмы, чтобы исправить часть этого. Например,

{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}

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

Проблема в том, что это работает только для map, за которой следует map. Есть много других возможностей - map, за которыми следуют filter, filter, а затем map и т.д. Вместо того, чтобы вручную вызывать решение для каждого из них, было создано так называемое "потоковое слияние". Это более сложный трюк, о котором я не опишу здесь.

Долгое и короткое: это все специальные трюки оптимизации, написанные программистом. Сам GHC ничего не знает о слиянии; все это в библиотеках списков и других библиотеках контейнеров. Итак, какие оптимизации происходят, зависит от того, как ваши библиотеки контейнеров написаны (или, что более реалистично, какие библиотеки вы хотите использовать).

Например, если вы работаете с массивами Haskell '98, не ожидайте никакого слияния. Но я понимаю, что библиотека vector обладает широкими возможностями слияния. Все о библиотеках; компилятор просто предоставляет прагму RULES. (Это, кстати, очень мощно. В качестве автора библиотеки вы можете использовать его для перезаписи клиентского кода!)

Meta:

Я согласен с людьми, говорящими "сначала код, второй профиль, оптимизируем третий".
Я также согласен с тем, что люди говорят: "Полезно иметь ментальную модель для того, сколько стоит данное дизайнерское решение".

Баланс во всех вещах и все это...

Ответ 3

Если привязка let v = rhs используется только в одном месте, вы можете рассчитывать на компилятор, чтобы вставить его, даже если rhs большой.

Исключение (что почти не относится к текущему вопросу) - это lambdas, рискующий дублированием работы. Рассмотрим:

let v = rhs
    l = \x-> v + x
in map l [1..100]

там вложение v было бы опасно, потому что одно (синтаксическое) использование перевело бы на 99 дополнительных оценок rhs. Однако в этом случае вы вряд ли захотите встроить его вручную. Поэтому вы можете использовать правило:

Если вы рассмотрите вложение имени, которое появляется только один раз, компилятор все равно сделает это.

Как счастливое следствие, использование связывания let просто для разложения длинного утверждения (с надеждой на получение ясности) является по существу бесплатным.

Это происходит из community.haskell.org/~simonmar/papers/inline.pdf который включает в себя гораздо больше информации о inlining.