可以期望GHC可靠地执行哪些优化？

Question

GHC有很多可以执行的优化，但我不知道它们都是什么，也不知道它们在什么情况下执行的可能性有多大。

我的问题是：我可以期望它每次应用什么转换，或者几乎如此？如果我看一段经常执行（评估）的代码，我的第一个想法是“嗯，也许我应该优化它”，在这种情况下，我的第二个想法应该是“不要想它，GHC得到了这个”？

我在读《流融合：从列表到流再到什么都没有》这篇论文，他们使用的将列表处理改写成另一种形式的技术，GHC的正常优化将可靠地优化成简单的循环，这对我来说很新奇。我如何判断我自己的程序何时符合这种优化条件？

GHC手册中有一些信息，但它只是回答问题的一部分。

编辑：我开始悬赏了。我想要的是一个较低级别转换的列表，如lambda/let/case-浮动、类型/构造函数/函数参数专业化、严格性分析和拆箱、工人/包装器，以及我遗漏的任何其他重要的GHC功能，以及输入和输出代码的解释和示例，理想情况下，当总效果超过其各部分的总和时。理想情况下，提到转换何时不会发生。我不指望对每一个转换都有新颖的解释，几个句子和内联的一行代码示例就足够了（或者一个链接，如果不是20页的科学论文的话），只要大局在结尾时是清晰的。我希望能够看到一段代码，并且能够很好地猜测它是否会编译成一个紧密的循环，或者为什么不html" target="_blank">编译，或者我必须改变什么才能编译它。（我对像流融合这样的大型优化框架不太感兴趣（我刚刚读了一篇关于这个的论文）；更多的是编写这些框架的人所拥有的知识。）

Answer 1

如果let binding 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其中包含了更多关于内联的信息。

Answer 2

懒惰

这不是“编译器优化”，但它是由语言规范保证的，所以你总是可以指望它发生。本质上，这意味着工作直到你用结果“做某事”才会执行。（除非你做了几件事中的一件来故意关掉懒惰。）

很明显，这本身就是一个完整的主题，SO已经有了很多关于它的问题和答案。

在我有限的经验中，让你的代码太懒或太严格会比我将要谈论的任何其他东西有更大的性能损失（在时间和空间上）...

严格性分析

懒惰是指除非必要，否则避免工作。如果编译器能够确定一个给定的结果“总是”需要，那么它就不会麻烦存储计算并在以后执行它；它会直接执行，因为这样效率更高。这就是所谓的“严格性分析”。

显然，问题是编译器不能总是检测什么时候可以严格执行。有时需要给编译器一些提示。（我不知道有什么简单的方法来确定严格性分析是否已经完成了你认为它已经完成的工作，除了涉水通过核心输出。）

内联

如果您调用一个函数，并且编译器可以告诉您正在调用哪个函数，它可能会尝试“内联”该函数——也就是说，用函数本身的副本替换函数调用。函数调用的开销通常很小，但是内联通常能够实现其他优化，这在其他情况下是不会发生的，因此内联可能是一个巨大的胜利。

函数只有在“足够小”（或者如果您添加了专门要求内联的pragma）时才内联。此外，只有当编译器能够告诉您调用的函数时，函数才能内联。编译器有两种主要方法无法分辨：

>

如果您调用的函数是从其他地方传入的。例如，编译filter函数时，不能内联筛选器谓词，因为它是用户提供的参数。

如果您调用的函数是类方法，而编译器不知道所涉及的类型。例如，当编译sum函数时，编译器不能内联函数，因为sum使用几种不同的数字类型，每种类型都有不同的函数。

在后一种情况下，可以使用{-#SPECIALIZE#-}pragma生成硬编码为特定类型的函数版本。例如，{-#专门化和：：[Int]-

请注意，只有当编译器可以告诉我们正在使用Int时，才会调用我们的新特殊函数。否则，原始的多态和将被调用。同样，实际的函数调用开销相当小。内联可以实现的额外优化是有益的。

公共子表达式消除

如果某个代码块计算相同的值两次，编译器可以用同一计算的单个实例替换该值。例如，如果你

(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

不幸的是，虽然懒惰会保证跳过不必要的工作，但所有中间分配和解除分配都会列出sap性能。“融合”或“毁林”是编译器试图消除这些中间步骤的地方。

麻烦的是，这些函数大多是递归的。如果没有递归，将所有函数压缩到一个大代码块中，在它上面运行简化器，并在没有中间列表的情况下产生真正最优的代码将是内联的基本练习。但是由于递归，这是行不通的。

您可以使用{-#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库具有广泛的融合功能。都是关于图书馆的；编译器只提供规则pragma。（顺便说一句，它非常强大。作为库作者，您可以使用它重写客户端代码！）

元：

>

我同意人们所说的代码第一，配置文件第二，优化第三。

我也同意人们所说的“对于一个给定的设计决策有多少成本，有一个心智模型是有用的”。

在所有事情上保持平衡，所有这些。。。

Answer 3

这个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拒绝内联递归函数，并且必须正确命名才能使融合工作。

接下来，我们将看到执行的所有优化的完整列表：

>

专精

专门化的基本思想是通过识别函数被调用的地方并创建函数的非多态版本来消除多态和重载——它们特定于被调用的类型。您还可以告诉编译器使用SPECIALISEPragma执行此操作。以阶乘函数为例：

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)

接下来，下面提到的规则可能会触发，您最终会在unboxInts上工作，这比原来的要快得多。另一种看待专业化的方法是对类型类字典和类型变量的部分应用。

这里的来源有一大堆笔记。

浮出

编辑：我以前显然误解了这一点。我的解释完全变了。

其基本思想是将不应重复的计算移出函数。例如，假设我们有：

\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，这大概是一些很大的轰动，我们浪费了时间和空间。向内浮动修正了这个问题，产生了这个：

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. 浮点数允许进入case语句，而浮点数处理函数。
2. 传球的顺序是固定的，所以它们不应该无限交替。

>

需求分析

需求分析或严格性分析与其说是一种转换，不如说是一种信息收集途径。编译器找到总是计算它们的参数（或至少其中一些）的函数，并使用按值调用而不是按需要调用传递这些参数。因为你可以避开雷声的开销，这通常要快得多。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#s中是如何涵盖代码的？我们可以通过执行以下操作来删除它们：

factorial :: Int -> Int
factorial (I# n#) = I# (factorial# n#)

factorial# :: Int# -> Int#
factorial# 0# = 1#
factorial# n# = n# *# factorial# (n# -# 1#)

虽然这个特定的示例也可以由SpecConstr完成，但是worker/wrapper转换在它可以完成的事情上是非常通用的。

公共子表达式

这是另一个非常简单的优化，非常有效，就像严格性分析一样。基本思想是，如果你有两个相同的表达式，它们将具有相同的值。例如，如果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编译，由于其全局值编号传递，您可能会得到一些组合。

解放案件

这似乎是一个非常有文档记录的转换，除了它可能导致代码爆炸这一事实之外。以下是我发现的小文档的重新格式化（并稍微重写）版本：

本模块浏览核心，并查找自由变量的案例。标准是：如果在递归调用的路由上的自由变量上存在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，它处理已知形式的参数。

有关SPECCONTR的更多信息，请参见下文。

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. lambdas是显式的，它是a。
2. 右手边是足够小的，由旗帜控制的东西。
3. 该函数是递归的，可专门化的调用在右侧使用。
4. 函数的所有参数都存在。
5. 至少有一个参数是构造函数应用程序。
6. 该参数在函数中的某个地方进行了案例分析。

然而，启发式几乎肯定已经改变了。事实上，这篇论文提到了另一种第六启发式：

仅当x仅由案例检查，且未传递给普通函数或作为结果的一部分返回时，才专门研究参数x。

这是一个非常小的文件（12行），因此可能没有触发那么多优化（尽管我认为它完成了所有优化）。这也不能告诉你为什么它会选择这些传球，为什么它会按顺序排列。