GHC可以预期哪些优化能够可靠地执行？
GHC有很多可以执行的优化，但我不知道它们是什么，也不知道它们在什么情况下执行的可能性。
我的问题是：我可以期待它每次或几乎都能应用什么样的转换？ 如果我看一段经常执行（评估）的代码，我的第一个想法是“嗯，也许我应该优化它”，在这种情况下，我应该第二个想法是“甚至不要考虑它， GHC得到了这个“？
我正在阅读Stream Fusion：From Lists to Streams到Nothing，以及他们用于将列表处理重写为不同形式的技术，GHC的正常优化将可靠地优化为简单循环，这对我而言是新颖的。 我怎么知道我的程序何时有资格进行这种优化？
GHC手册中提供了一些信息，但它只是回答问题的一部分。
编辑：我开始赏金。 我想要的是像lambda / let / case-floating，类型/构造函数/函数参数专门化，严格分析和拆箱，worker / wrapper以及我忽略的其他重要GHC的其他更低级别转换的列表，以及输入和输出代码的解释和例子，并且理想地说明当总效应大于其部分总和时的情况。 最理想的情况是提及何时不会发生转变。 我并不期望每一次转换都有长篇大论的解释，只要大局就是这样，一些句子和内联单行代码示例就足够了（或者链接，如果它不是20页的科学论文）清除它的结尾。 我希望能够查看一段代码，并能够很好地猜测它是否会编译成一个紧密的循环，或者为什么不是，或者我将不得不改变以实现它。 （我对流融合等大型优化框架（我只是阅读一篇关于这方面的文章）感兴趣的不止这些;更多的是写这些框架的人所拥有的知识。）
这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:到最后，所有优化阶段发生的地方，我们看到了很多。
首先，简化器几乎在所有阶段之间运行。 这使得写许多遍更容易。 例如，在实施许多优化时，他们只需创建重写规则来传播更改，而不必手动进行更改。 简化器包含许多简单的优化，包括内联和融合。 我知道的主要限制是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工作的东西，这比原始东西快得多。 另一种查看专业化的方法是对类型字典和类型变量进行部分应用。
这里的信息来源有很多笔记。
漂浮
编辑：我显然以前误解了这一点。 我的解释完全改变了。
这个基本思想是移动不应该重复出功能的计算。 例如，假设我们有这个：
x -> let y = expensive in x+y
在上面的lambda中，每次调用函数时，都会重新计算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
再一次，保存了重复的计算。
在这种情况下，源代码非常易读。
目前，两个相邻的lambda之间的绑定不会浮动。 例如，这不会发生：
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 ，这大概是一个大的thunk，我们浪费了时间和空间。 向内浮动解决了这个问题，产生了这样的结果：
case v of
True -> let x = big in x + 1
False -> let x = big in 0
，随后被简化器替换
case v of
True -> big + 1
False -> 0
本文虽然涵盖了其他主题，但给出了相当清晰的介绍。 请注意，尽管名称不同，浮动和浮动不会陷入无限循环，原因有二：
case语句，同时抛出函数的处理。 需求分析
需求分析或严格分析不像一个信息收集过程那样是一种转变，更像名称所暗示的那样。 编译器查找总是评估其参数（或至少其中一些参数）的函数，并使用按值调用而不是按需调用来传递这些参数。 既然你避免了thunk的开销，这通常要快得多。 Haskell中的许多性能问题都是由于这种传递失败或者代码不够严格造成的。 一个简单的例子是使用foldr ， foldl和foldl'来总结整数列表之间的区别 - 第一个原因导致堆栈溢出，第二个导致堆溢出，最后一次运行正常，因为严格。 这可能是所有这些方面最容易理解和最好的记录。 我相信多态和CPS代码经常会打败这个。
工人包装绑定
worker / wrapper转换的基本思想是在简单的结构上进行紧密的循环，转换为两端结构。 例如，用这个函数计算一个数的阶乘。
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
使用GHC中的Int定义，我们有
factorial :: Int -> Int
factorial (I# 0#) = I# 1#
factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
I# down# -> down#)
注意代码在I#被覆盖了吗？ 我们可以通过这样删除它们：
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由许多启发式方法控制。 文中提到的是这样的：
a 。 然而，启发式几乎肯定会改变。 事实上，该论文提到了另一种第六种启发式：
只有在x仅由一个case仔细检查并且不会传递给普通函数或作为结果的一部分返回时专用于参数x 。
这是一个非常小的文件（12行），因此可能没有触发许多优化（尽管我认为它完成了所有的优化）。 这也没有告诉你为什么选择这些通行证，以及为什么它按照这个顺序。
怠惰
这不是一个“编译器优化”，但它是由语言规范保证的，所以你可以随时指望它发生。 实质上，这意味着只有在“结果”时才能执行工作。 （除非你有几件事要故意关闭懒惰。）
显然，这本身就是一个完整的话题，因此SO已经有很多问题和答案。
在我有限的经验中，让你的代码太懒或太严格的性能处罚（时间和空间）比我将谈论的其他任何东西都要大得多......
严格分析
除非有必要，懒惰是为了避免工作。 如果编译器可以确定给定的结果将会“始终”需要，那么它不会费心存储计算并稍后执行; 它会直接执行，因为这样更有效率。 这就是所谓的“严格分析”。
显而易见的是，编译器不能始终检测什么时候可以严格执行。 有时你需要给编译器一些提示。 （我不知道有什么简单的方法可以确定严格分析是否完成了您认为的那样，除了涉及Core输出。）
内联
如果你调用一个函数，并且编译器可以告诉你正在调用哪个函数，它可能会尝试“内联”那个函数 - 也就是用函数本身的副本替换函数调用。 函数调用的开销通常很小，但内联经常会使其他优化发生，否则就不会发生，所以内联可能是一个巨大的胜利。
如果函数“足够小”（或者如果添加特别要求内联的编译指示），则只能内联函数。 另外，如果编译器能够告诉你正在调用哪个函数，函数只能被内联。 编译器无法说明两种主要方式：
如果你调用的函数是从其他地方传入的。 例如，当编译filter函数时，不能内联过滤器谓词，因为它是用户提供的参数。
如果你调用的函数是一个类方法，并且编译器不知道涉及哪种类型。 例如，编译sum函数时，编译器不能内联+函数，因为sum可以处理几种不同的数字类型，每种类型都有不同的+函数。
在后一种情况下，可以使用{-# SPECIALIZE #-}编译指示来生成硬编码为特定类型的函数版本。 例如， {-# SPECIALIZE sum :: [Int] -> Int #-}将为Int类型编译硬编码的sum版本，这意味着+可以在此版本中内联。
但是请注意，我们的新special- 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"
这不太直观，但更有效。 因为编译器可以轻松完成这种转换，所以您不必担心它。 只需以最直观的方式编写模式匹配; 编译器非常擅长重新排序和重新排列，以尽可能快地完成。
聚变
用于列表处理的标准Haskell成语是将具有一个列表并产生新列表的函数链接在一起。 规范的例子是
map g . map f
不幸的是，尽管懒惰保证跳过不必要的工作，但中间列表的所有分配和释放都会影响性能。 “融合”或“毁林”是编译器试图消除这些中间步骤的地方。
麻烦的是，这些功能大部分都是递归的。 如果没有递归，这将是内联的一个基本练习，将所有函数压缩成一个大代码块，在其上运行简化器并生成真正优化的代码，而不需要中间列表。 但由于递归，这是行不通的。
您可以使用{-# RULE #-}编译指示来修复其中的一些问题。 例如，
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}
现在每次看到GHC时间map应用到map ，它squishes它变成一个传过来的名单，省去了中间列表。
麻烦的是，这只适用于map后跟map 。 还有很多其他的可能性 - map紧接着是filter ， filter紧跟map等。与其为每个解决方案手动编码，发明了所谓的“流融合”。 这是一个更复杂的技巧，我在这里不会描述。
它的长短是：这些都是程序员编写的特殊优化技巧。 GHC本身对融合一无所知; 它都在列表库和其他容器库中。 那么什么样的优化发生取决于你的容器库是如何写入的（或者更现实的说，你选择使用哪个库）。
例如，如果你使用Haskell '98数组，不要期待任何形式的融合。 但我明白， vector库具有广泛的融合功能。 这些都是关于图书馆的; 编译器只提供了RULES编译指示。 （顺便说一句，这是非常强大的功能，作为一个图书馆作者，你可以用它来重写客户端代码！）
元：
我同意那些说“先编码，简介第二，优化第三”的人。
我也同意人们的看法：“对于给定的设计决策花费多少成本，有一个智力模型是有用的”。
在所有事情上平衡，以及所有......
如果仅在一个地方使用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，其中包含更多关于内联的信息。
链接地址: http://www.djcxy.com/p/1147.html上一篇: What optimizations can GHC be expected to perform reliably?