gla*_*erl 177 optimization haskell ghc
GHC有很多可以执行的优化,但我不知道它们是什么,也不知道它们在多大程度上被执行的可能性.
我的问题是:我可以期望每次或几乎可以应用哪些转换？如果我查看将要经常执行(评估)的一段代码,我的第一个想法是"嗯,也许我应该优化它",在这种情况下,我的第二个想法是,"甚至不要考虑它, GHC得到了这个"？
我正在阅读文章Stream Fusion:从列表到流到没有任何东西,以及他们用于将列表处理重写为不同形式的技术,GHC的正常优化将可靠地优化为简单的循环对我来说是新颖的.如何判断自己的程序何时符合这种优化条件？
GHC手册中有一些信息,但它只是回答问题的一部分.
编辑:我正在开始赏金.我想要的是一个低级转换列表,如lambda/let/case-floating,类型/构造函数/函数参数特化,严格性分析和拆箱,worker/wrapper,以及我遗漏的任何其他重要的GHC做的事情,以及输入和输出代码的解释和示例,以及理想情况下总效应大于其各部分之和的情况.理想情况下,有些人提到何时不会发生转变.我不期待对每个转换的新颖长度的解释,一些句子和内联单行代码示例就足够了(或者链接,如果它不是20页的科学论文),只要大图是在它结束时清楚.我希望能够查看一段代码,并能够很好地猜测它是否会编译成紧密循环,或者为什么不编译,或者我需要改变它来制作它.(我对像流融合这样的大优化框架(我只是阅读了一篇关于它的论文)感兴趣;更多的是那些编写这些框架的人所拥有的知识.)
ger*_*ter 106
这个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)
由于编译器不知道要使用的乘法的任何属性,因此根本无法对此进行优化.但是,如果它看到它在a上使用Int,它现在可以创建一个新版本,仅在类型上有所不同:
fac_Int :: Int -> Int
fac_Int 0 = 1
fac_Int n = n * fac_Int (n - 1)
接下来,下面提到的规则可能会触发,并且您最终会处理未装箱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语句,而浮出浮动处理函数.需求分析
需求分析或严格性分析不是一种转变,更像是名称所暗示的信息收集过程.编译器找到总是评估其参数(或至少其中一些参数)的函数,并使用call-by-value而不是call-by-need传递这些参数.由于你可以避开thunk的开销,这通常要快得多.Haskell中的许多性能问题都来自于传递失败或代码不够严格.一个简单的例子是使用foldr,foldl和foldl'整数列表之间的区别- 第一个导致堆栈溢出,第二个导致堆溢出,最后一个运行正常,因为严格.这可能是最容易理解和最好记录的所有这些.我相信多态性和CPS代码经常打败这个.
工人包装绑定
worker/wrapper转换的基本思想是在一个简单的结构上进行紧密循环,在结尾处转换为该结构和从该结构转换.例如,使用此函数计算数字的阶乘.
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
使用IntGHC中的定义,我们有
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是Fibonacci数计算器,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只有x是仅由审查case,而不是传递给普通函数,或返回结果的一部分.
这是一个非常小的文件(12行),所以可能没有触发那么多的优化(尽管我认为它完成了所有这些).这也没有告诉你它为什么选择那些传球以及为什么它按照这个顺序排列.
Mat*_*hid 64
怠惰
它不是"编译器优化",但它是语言规范保证的东西,所以你总能指望它发生.从本质上讲,这意味着在您对结果"做某事"之前不会执行工作.(除非你做了几件事之一故意关闭懒惰.)
显然,这本身就是一个完整的主题,而且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库具有广泛的融合功能.这都是关于图书馆的; 编译器只提供RULESpragma.(顺便说一句,这是非常强大的.作为一个库作者,你可以用它来重写客户端代码!)
元:
我同意人们说"代码优先,概况第二,优化第三".
我也同意那些人说"对于给定的设计决策有多少成本的心理模型是有用的".
在所有事情上保持平衡,以及所有......
小智 8
如果只在一个地方使用let绑定v = rhs,你可以指望编译器内联它,即使rhs很大.
例外(在当前问题的上下文中几乎不是一个例外)是lambdas冒着工作重复的风险.考虑:
let v = rhs
l = \x-> v + x
in map l [1..100]
内联v将是危险的,因为一个(句法)使用将转化为对rhs的99个额外评估.但是,在这种情况下,您也不太可能想要手动内联它.所以基本上你可以使用规则:
如果您考虑内联仅出现一次的名称,编译器仍会执行此操作.
作为一个快乐的推论,使用let绑定简单地分解一个长语句(希望获得清晰度)基本上是免费的.
这来自community.haskell.org/~simonmar/papers/inline.pdf,其中包含有关内联的更多信息.