GHC有很多可以执行的优化,但我不知道它们是什么,也不知道它们在多大程度上被执行的可能性。
我的问题是:我可以期望每次或几乎可以应用哪些转换?如果我查看将要经常执行(评估)的一段代码,我的第一个想法是“嗯,也许我应该优化它”,在这种情况下,我的第二个想法是,“甚至不要考虑它, GHC得到了这个“?
我正在阅读论文Stream Fusion: From Lists to Streams to Nothing at All,他们使用的技术将重写列表处理转换为一种不同的形式,GHC的正常优化然后可靠地优化到简单的循环对我来说是新颖的。如何判断自己的程序何时符合这种优化条件?
在GHC手册中有some information,但它只是回答问题的一部分。
编辑:我正在开始赏金。我想要的是一个低级转换列表,如lambda / let / case-floating,类型/构造函数/函数参数特化,严格性分析和拆箱,工作者/包装器,以及我遗漏的任何其他重要的GHC做的事情,以及输入和输出代码的解释和示例,以及理想情况下总效应大于其各部分之和的情况。理想情况下,有些人提到何时不会发生转变。我不期待对每个转换的新颖长度的解释,一些句子和内联单行代码示例就足够了(或者链接,如果它不是20页的科学论文),只要大图是在它结束时清楚。我希望能够查看一段代码,并能够很好地猜测它是否会编译成紧密循环,或者为什么不编译,或者我需要改变它来制作它。 (我对像流融合这样的大优化框架(我只是阅读了一篇关于它的论文)感兴趣;更多的是那些编写这些框架的人所拥有的知识。)
This GHC Trac page也很好地解释了传球。 This page解释了优化排序,但是,就像大多数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)
接下来,下面提到的规则可以触发,你最终会在未装箱的Int
s上工作,这比原来快得多。查看特化的另一种方法是对类型类字典和类型变量进行部分应用。
这里的source有很多笔记。\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
再次,保存重复计算。
在这种情况下,source非常易读。
目前,两个相邻的lambda之间的绑定没有浮动。例如,这不会发生:
\x y -> let t = x+x in ...
即将
\x -> let t = x+x in \y -> ...
floatInwards
的主要目的是浮动到一个case的分支,这样我们就不会分配东西,将它们保存在堆栈中,然后发现它们在所选分支中不需要。
举个例子,假设我们有这个表达式:
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
This paper虽然涵盖了其他主题,但却给出了相当清晰的介绍。请注意,尽管它们的名称,浮动和浮动不会进入无限循环,原因有两个:
漂浮在浮点数允许进入case
语句,而浮出处理函数。
有一个固定的通过顺序,所以它们不应无限交替。foldr
,foldl
和foldl'
来求和整数列表之间的区别 - 第一个导致堆栈溢出,第二个导致堆溢出,最后一个运行正常,因为严格。这可能是最容易理解和最好记录的所有这些。我相信多态性和CPS代码经常打败这个。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进行编译,由于其全局值编号通过,您可能会将其中一些组合在一起。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的更多信息,请参见下文。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由许多启发式控制。文中提到的那些是这样的:
lambdas是明确的,arity是a
。
右手边是“足够小”,由旗帜控制。
该函数是递归的,并且在右侧使用特殊调用。
该函数的所有参数都存在。
至少有一个参数是构造函数应用程序。
该论证在函数中的某处进行了案例分析。
然而,启发式几乎肯定会改变。事实上,该论文提到了另一种第六种启发式方法:
仅当x
仅由x
审查时才专注于case
参数,并且不会传递给普通函数,或作为结果的一部分返回。这是一个非常小的文件(12行),所以可能没有触发那么多的优化(虽然我认为它完成了所有这些)。这也没有告诉你它为什么选择那些传球以及为什么它按照这个顺序排列。
怠惰
它不是“编译器优化”,但它是语言规范保证的东西,所以你总能指望它发生。从本质上讲,这意味着在您对结果“做某事”之前不会执行工作。 (除非你做了几件事之一故意关闭懒惰。)
显然,这本身就是一个完整的主题,而且SO已经有很多问题和答案。
在我有限的经验中,使你的代码过于懒惰或过于严格,其性能损失(时间和空间)远远超过我要谈论的任何其他内容......
严格性分析
除非有必要,否则懒惰就是避免工作。如果编译器可以确定“总是”需要给定的结果,那么它将不会打扰存储计算并在以后执行它;它只是直接执行它,因为它更有效。这就是所谓的“严格性分析”。
显然,问题是编译器无法始终检测何时可以严格控制某些内容。有时你需要给编译器一些提示。 (我不知道有什么简单的方法来确定严格性分析是否已经完成了你认为的那样,除了涉及核心输出。)
内联
如果你调用一个函数,并且编译器可以告诉你正在调用哪个函数,它可能会尝试“内联”该函数 - 也就是说,用函数本身的副本替换函数调用。函数调用的开销通常很小,但内联通常会使其他优化发生,否则就不会发生,因此内联可能是一个巨大的胜利。
如果函数“足够小”(或者如果添加专门要求内联的编译指示),则仅内联函数。此外,如果编译器可以告诉您正在调用的函数,则只能内联函数。编译器有两种主要方式无法分辨:
filter
函数时,您不能内联过滤谓词,因为它是用户提供的参数。sum
函数时,编译器不能内联+
函数,因为sum
使用几种不同的数字类型,每种类型都有不同的+
函数。在后一种情况下,您可以使用{-# SPECIALIZE #-}
pragma生成对特定类型进行硬编码的函数版本。例如,{-# 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"
这不太直观,但效率更高。因为编译器可以轻松地进行此转换,所以您不必担心它。只需以最直观的方式编写模式匹配;编译器非常擅长重新排序和重新排列,以使其尽可能快。
聚变
用于列表处理的标准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
编译指示。 (顺便说一句,这是非常强大的。作为一个库作者,你可以用它来重写客户端代码!)
元:
在所有事情上保持平衡,以及所有......
如果只在一个地方使用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,其中包含有关内联的更多信息。