Какую оптимизацию можно ожидать от GHC?

183

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

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

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

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

РЕДАКТИРОВАТЬ: я начинаю щедрость. Я хотел бы получить список низкоуровневых преобразований, таких как лямбда / let / case-floating, специализация аргументов типа / конструктора / функции, анализ строгости и распаковка, рабочий / упаковщик и все, что еще важно для GHC, которые я пропустил наряду с объяснениями и примерами ввода и вывода кода, а также идеальными иллюстрациями ситуаций, когда суммарный эффект больше, чем сумма его частей. И в идеале некоторые упоминания о том, когда преобразования не будутбывает. Я не ожидаю подробного объяснения каждой трансформации, пары предложений и примеров встроенного однострочного кода может быть достаточно (или ссылка, если не до двадцати страниц научной статьи), пока общая картина ясно к концу этого. Я хочу иметь возможность взглянуть на кусок кода и сделать правильное предположение о том, скомпилируется ли он в сжатый цикл, или почему нет, или что мне придется изменить, чтобы сделать его. (Меня не очень интересуют большие фреймворки для оптимизации, такие как потоковое слияние (я только что прочитал статью об этом); больше - знания, которыми обладают люди, пишущие эти фреймворки.)

optimization haskell ghc glaebhoerl
источник

Это самый достойный вопрос. Писать достойный ответ ... сложно.

Математическая

Действительно хорошая отправная точка - это: aosabook.org/en/ghc.html

Габриэль Гонсалес,

На любом языке, если ваша первая мысль - «возможно, мне следует оптимизировать это», вторая мысль - «Я сначала опишу».

Джон Л

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

Бен

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

glaebhoerl

Ответы:

110

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

Что касается специфики, лучшее, что можно сделать, это, вероятно, посмотреть, как конкретная программа компилируется. Лучший способ увидеть, какие оптимизации выполняются - это многословно скомпилировать программу, используя -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:на последнее, где происходят все этапы оптимизации, мы видим довольно много.

Прежде всего, 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 Ints, что намного быстрее, чем оригинал. Другой способ взглянуть на специализацию - это частичное применение словарей классов типов и переменных типов.

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

РЕДАКТИРОВАТЬ: Я, очевидно, неправильно понял это раньше. Мое объяснение полностью изменилось.

Основная идея этого состоит в том, чтобы переместить вычисления, которые не должны повторяться, из функций. Например, предположим, что у нас было это:
```
\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
```
Эта статья , хотя и охватывает другие темы, дает довольно четкое введение. Обратите внимание, что несмотря на их имена, всплывающие и всплывающие объекты не попадают в бесконечный цикл по двум причинам:
1. Float in float позволяет использовать caseоператоры, а float out - функции.
2. Существует фиксированный порядок проходов, поэтому они не должны чередоваться бесконечно.

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

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

Основная идея преобразования рабочий / упаковщик состоит в том, чтобы сделать простой цикл на простой структуре, преобразуя ее в конечную структуру и из нее. Например, возьмите эту функцию, которая вычисляет факториал числа.
```
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на пути к рекурсивному вызову имеется свободная переменная on, то рекурсивный вызов заменяется на развертывание. Например, в
```
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 контролируется рядом эвристик. Те, упомянутые в статье, таковы:
1. Лямбды явные, а арность есть a.
2. Правая сторона "достаточно мала", что-то, контролируемое флагом.
3. Функция является рекурсивной, а специализированный вызов используется в правой части.
4. Все аргументы функции присутствуют.
5. По крайней мере один из аргументов является приложением конструктора.
6. Этот аргумент анализируется регистром где-то в функции.
Однако эвристика почти наверняка изменилась. Фактически, газета упоминает альтернативную шестую эвристику:

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

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

gereeter
источник

Теперь мы куда-то добираемся! Комментарии: У вас, кажется, есть отрезанное предложение в части о Specialize. Я не вижу смысла в плавании: зачем это? Как он решает, плавать или нет (почему он не входит в цикл)? У меня создалось впечатление , что откуда - то GHC не делал CSE вообще , но , по- видимому , что ошиблась. Я чувствую, что теряюсь в деталях вместо того, чтобы видеть большую картину ... тема еще более сложна, чем я думал. Может быть, мой вопрос невозможен, и просто нет способа получить эту интуицию, кроме тонны опыта или работы над GHC самостоятельно?

glaebhoerl

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

Привет

Я исправил проблемы, которые вы упомянули.

Привет

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

Привет

Что вы подразумеваете под «вещи должны быть названы правильно, чтобы слияние сработало» точно?

Винсент Беффара

Лень

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

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

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

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

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

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

Встраивание

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

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

Если функция, которую вы вызываете, передается откуда-то еще. Например, когда 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"

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

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

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

сплавление

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

map g . map f

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

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

Вы можете использовать {-# 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прагму. (Кстати, это очень мощно. Как автор библиотеки, вы можете использовать его для перезаписи клиентского кода!)

Мета:

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

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

MathematicalOrchid
источник

it's something guaranteed by the language specification ... work is not performed until you "do something" with the result.

- не совсем. Спецификация языка обещает не строгую семантику ; это ничего не обещает о том, будет ли выполнена лишняя работа.

Дэн Бертон

@DanBurton Конечно. Но это не очень легко объяснить в нескольких предложениях. Кроме того, поскольку GHC является почти единственной существующей реализацией Haskell, тот факт, что GHC ленив, достаточно хорош для большинства людей.

Математическая

@MaturgicalOrchid: спекулятивные оценки - интересный контрпример, хотя я согласен, что для новичка это, вероятно, слишком много.

Бен Милвуд

О CSE: у меня сложилось впечатление, что это делается почти никогда, потому что это может привести к нежелательному обмену и, следовательно, к космическим утечкам.

Иоахим Брейтнер,

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

glaebhoerl

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

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

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

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

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

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

Это взято из community.haskell.org/~simonmar/papers/inline.pdf, в котором содержится гораздо больше информации о встраивании.

Даниил
источник