GHC有很多可以执行的优化,但我不知道它们是什么,也不知道它们在多大程度上被执行的可能性 .
我的问题是:我可以期望每次或几乎可以应用哪些转换?如果我查看将要经常执行(评估)的一段代码,我的第一个想法是“嗯,也许我应该优化它”,在这种情况下,我的第二个想法是,“甚至不要考虑它, GHC得到了这个“?
我正在阅读论文Stream Fusion: From Lists to Streams to Nothing at All,他们使用的技术将重写列表处理转换成一种不同的形式,GHC的正常优化然后可靠地优化到简单的循环对我来说是新颖的 . 如何判断自己的程序何时符合这种优化条件?
GHC手册中有some information,但它只是回答问题的一部分 .
编辑:我遗漏了输入和输出代码的解释和示例,并且理想地说明了总效果超过其各部分之和的情况 . 理想情况下,有些人提到何时不会发生转变 . 只要大局在结尾处清楚,我就不要二十页科学论文了 . 我希望能够查看一段代码,并能够很好地猜测它是否会编译成紧密循环,或者为什么不编译,或者我需要改变它来制作它 . (我对像流融合这样的大优化框架(我只是阅读了一篇关于它的论文)感兴趣;更多的是那些编写这些框架的人所拥有的知识 . )
3 回答
This GHC Trac page也很好地解释了传球 . This page解释了优化排序,但是,与大多数Trac Wiki一样,它已经过时了 .
具体而言,最好的办法是查看特定程序的编译方式 . 查看正在执行哪些优化的最佳方法是使用
-v
标志详细编译程序 . 以我在电脑上找到的第一块Haskell为例:从第一个
*** Simplifier:
到最后一个,在所有优化阶段发生的地方,我们看到了很多 .首先,简化器几乎在所有阶段之间运行 . 这使得编写许多传递变得更加容易 . 例如,在实现许多优化时,它们只是创建重写规则来传播更改,而不必手动执行 . 简化器包含许多简单的优化,包括内联和融合 . 我知道的主要限制是GHC拒绝内联递归函数,并且必须正确地命名才能使聚合工作 .
接下来,我们会看到所有优化的完整列表:
专业化的基本思想是通过识别调用函数的位置来删除多态和重载,并创建非多态的函数版本 - 它们特定于调用它们的类型 . 您也可以使用
SPECIALISE
pragma告诉编译器执行此操作 . 例如,采用阶乘函数:由于编译器不知道要使用的乘法的任何属性,因此根本无法对此进行优化 . 但是,如果它看到它在
Int
上使用,它现在可以创建一个新版本,仅在类型上有所不同:接下来,下面提到的规则可能会触发,你最终会在未装箱的
Int
上工作,这比原来快得多 . 查看特化的另一种方法是对类型类字典和类型变量进行部分应用 .source这里有大量的笔记 .
编辑:我之前显然误解了这一点 . 我的解释完全改变了 .
这个的基本思想是移动不应该从函数中重复的计算 . 例如,假设我们有这个:
在上面的lambda中,每次调用该函数时,都会重新计算
y
. 浮动产生的更好的功能是为了促进该过程,可以应用其他变换 . 例如,发生这种情况:
再次,保存重复计算 .
在这种情况下,source非常易读 .
目前,两个相邻的lambda之间的绑定没有浮动 . 例如,这不会发生:
即将
引用源代码,
floatInwards
的主要目的是浮动到案例的分支中,这样我们就不需要在所选分支中使用't allocate things, save them on the stack, and then discover that they aren' .举个例子,假设我们有这个表达式:
如果
v
评估为False
,那么通过分配x
(可能是一个大thunk),我们浪费了时间和空间 . 浮动向内修复此问题,产生以下结果:,随后用简化器代替
This paper虽然涵盖了其他主题,但却给出了相当清晰的介绍 . 请注意,尽管它们的名称,浮动和浮动不会进入无限循环,原因有两个:
Float in floats允许
case
语句,而float out处理函数 .有一个固定的通行顺序,所以它们不应无限交替 .
需求分析
需求分析或严格性分析不是一种转变,更像是名称所暗示的信息收集过程 . 编译器找到总是评估其参数(或至少其中一些参数)的函数,并使用call-by-value而不是call-by-need传递这些参数 . 由于你可以避开thunk的开销,这通常要快得多 . Haskell中的许多性能问题都来自于传递失败或代码不够严格 . 一个简单的例子是使用
foldr
,_foldl
和foldl'
来求和整数列表之间的区别 - 第一个导致堆栈溢出,第二个导致堆溢出,最后一个运行正常,因为严格 . 这可能是最容易理解和最好记录的所有这些 . 我相信多态性和CPS代码经常打败这个 .worker / wrapper转换的基本思想是在一个简单的结构上进行紧密循环,在结尾处转换为该结构和从该结构转换 . 例如,使用此函数计算数字的阶乘 .
在GHC中使用
Int
的定义,我们有请注意
I#
中是否包含代码?我们可以通过这样做删除它们:虽然这个特定的例子也可以由SpecConstr完成,但是worker / wrapper转换在它可以做的事情上非常通用 .
这是另一个非常有效的非常简单的优化,如严格性分析 . 基本思想是,如果你有两个相同的表达式,它们将具有相同的值 . 例如,如果
fib
是斐波那契数字计算器,CSE将进行转换成
这将计算量减少了一半 . 不幸的是,这有时会妨碍其他优化 . 另一个问题是两个表达式必须在同一个地方,并且它们必须在语法上相同,而不是相同的值 . 例如,如果没有一堆内联,CSE将不会在以下代码中触发:
但是,如果通过llvm进行编译,由于其全局值编号通过,您可能会将其中一些组合在一起 .
除了可能导致代码爆炸的事实之外,这似乎是一个非常文档化的转换 . 这是我发现的小文档的重新格式化(并略微重写)版本:
该模块遍历
Core
,并在自由变量上查找case
. 标准是:如果在递归调用的路由上有一个自由变量case
,那么递归调用将被替换为展开 . 例如,在内部
f
被替换 . 制作注意需要阴影 . 简化,我们得到
这是更好的代码,因为
a
在内部letrec
内是空闲的,而不是需要v
的投影 . 请注意,这与自由变量有关,与SpecConstr不同,后者处理已知形式的参数 .有关SpecConstr的更多信息,请参见下文 .
成
作为扩展示例,请使用
last
的此定义:我们首先将其转换为
接下来,简化程序运行,我们有
请注意,程序现在更快,因为我们不会反复装箱和拆箱列表的前面 . 还要注意内联是至关重要的,因为它允许实际使用新的,更有效的定义,以及进行递归定义更好 .
SpecConstr由许多启发式控制 . 文中提到的那些是这样的:
lambdas是明确的,arity是
a
.右侧是"sufficiently small,"由旗帜控制的东西 .
该函数是递归的,并且右侧使用了specializable调用 .
该函数的所有参数都存在 .
至少有一个参数是构造函数应用程序 .
该参数在函数中的某处进行了案例分析 .
然而,启发式几乎肯定会改变 . 事实上,该论文提到了另一种第六种启发式方法:
仅当
x
仅由case
仔细检查时才专注于参数x
,并且不会传递给普通函数,或作为结果的一部分返回 .这是一个非常小的文件(12行),所以可能没有触发那么多的优化(尽管我认为它完成了所有这些) . 这也没有告诉你它为什么选择那些传球以及为什么它按照这个顺序排列 .
Laziness
它不是“编译器优化”,但它是语言规范保证的东西,所以你总能指望它发生 . 从本质上讲,这意味着在您对结果“做某事”之前不会执行工作 . (除非你做了几件事之一故意关闭懒惰 . )
显然,这本身就是一个完整的主题,而且SO已经有很多问题和答案 .
在我有限的经验中,使你的代码太懒或太严格,比我要谈论的任何其他东西都要大得多的性能损失(时间和空间)......
Strictness analysis
除非有必要,否则懒惰就是避免工作 . 如果编译器可以确定“总是”需要给定的结果,那么它将不会打扰存储计算并在以后执行它;它只是直接执行它,因为它更有效 . 这就是所谓的“严格性分析” .
显然,问题是编译器无法始终检测何时可以严格控制某些内容 . 有时你需要给编译器一些提示 . (我不知道有什么简单的方法来确定严格性分析是否已经完成了你认为的那样,除了涉及核心输出 . )
Inlining
如果你调用一个函数,并且编译器可以告诉你正在调用哪个函数,它可能会尝试“内联”该函数 - 也就是说,用函数本身的副本替换函数调用 . 函数调用的开销通常很小,但内联通常会使其他优化发生,否则就不会发生,因此内联可能是一个巨大的胜利 .
如果函数“足够小”(或者如果添加专门要求内联的编译指示),则仅内联函数 . 此外,如果编译器可以告诉您正在调用的函数,则只能内联函数 . 编译器有两种主要方式无法分辨:
如果您正在调用的函数是从其他地方传入的 . 例如,当编译
filter
函数时,您可以't inline the filter predicate, because it'是用户提供的参数 .如果您正在调用的函数是类方法,并且编译器不知道涉及哪种类型 . 例如,当编译
sum
函数时,编译器不能内联+
函数,因为sum
适用于几种不同的数字类型,每种类型都有不同的+
函数 .在后一种情况下,您可以使用
{-# SPECIALIZE #-}
pragma生成硬编码为特定类型的函数版本 . 例如,{-# SPECIALIZE sum :: [Int] -> Int #-}
将为Int
类型编译sum
的硬编码版本,这意味着+
可以在此版本中内联 .但请注意,只有当编译器告诉我们正在使用
Int
时才会调用我们的新特殊sum
函数 . 否则调用原始的多态sum
. 同样,实际的函数调用开销相当小 . 这是额外的优化,内联可以实现哪些是有益的 .Common subexpression elimination
如果某个代码块计算两次相同的值,则编译器可以用相同计算的单个实例替换它 . 例如,如果你这样做
那么编译器可能会优化它
您可能希望编译器始终执行此操作 . 然而,显然在某些情况下,这可能导致性能更差,而不是更好,因此GHC并不总是这样做 . 坦白说,我不是很难手动做到这一点 . (如果它不重要,你为什么担心呢?)
Case expressions
考虑以下:
前三个等式都检查列表是否为非空(等等) . 但检查同样的事情三次是浪费 . 幸运的是,编译器很容易将其优化为几个嵌套的case表达式 . 在这种情况下,像
这不太直观,但效率更高 . 因为编译器可以轻松地进行此转换,所以您不必担心它 . 只需以最直观的方式编写模式匹配;编译器非常擅长重新排序和重新排列,以使其尽可能快 .
Fusion
用于列表处理的标准Haskell习惯用法是将带有一个列表并生成新列表的函数链接在一起 . 典型的例子是
不幸的是,虽然懒惰保证跳过不必要的工作,但中间列表的所有分配和解除分配都会降低性能 . “Fusion”或“砍伐森林”是编译器试图消除这些中间步骤的地方 .
麻烦的是,大多数这些函数都是递归的 . 如果没有递归,那么将所有函数压缩成一个大代码块,在其上运行简化并生成没有中间列表的真正最佳代码将是一个基本练习 . 但由于递归,这是行不通的 .
您可以使用
{-# RULE #-}
pragma来修复其中的一部分 . 例如,现在,每当GHC看到
map
应用于map
时,它就会将其收集到列表中的单个传递中,从而消除了中间列表 .麻烦的是,这仅适用于
map
,后跟map
. 还有许多其他的可能性 -map
后跟filter
,filter
后跟map
等 . 而不是为每个人手动编码解决方案,所以发明了所谓的"stream fusion" . 这是一个更复杂的技巧,我在此不再赘述 .它的长短是:这些都是程序员编写的特殊优化技巧 . GHC本身对融合一无所知;它位于列表库和其他容器库中 . 那么优化的发生取决于你的容器库的编写方式(或者更现实地说,你选择使用哪些库) .
例如,如果您使用Haskell '98 arrays, don' t期望任何类型的融合 . 但我知道
vector
库具有广泛的融合功能 . 这都是关于图书馆的;编译器只提供RULES
pragma . (顺便说一句,这是非常强大的 . 作为一个库作者,你可以用它来重写客户端代码!)元:
我同意人们说“代码优先,概况第二,优化第三” .
我也同意那些人说“给出一个给定设计决策花费多少成本的心智模型是有用的” .
在所有事情上保持 balancer ,以及所有......
如果只在一个地方使用let绑定v = rhs,你可以指望编译器内联它,即使rhs很大 .
例外(在当前问题的上下文中几乎不是一个例外)是lambdas冒着工作重复的风险 . 考虑:
内联v将是危险的,因为一个(句法)使用将转化为对rhs的99个额外评估 . 但是,在这种情况下,您也不太可能想要手动内联它 . 所以基本上你可以使用规则:
如果您考虑内联仅出现一次的名称,编译器仍会执行此操作 .
作为一个快乐的推论,使用let绑定简单地分解一个长语句(希望获得清晰度)基本上是免费的 .
这来自community.haskell.org/~simonmar/papers/inline.pdf,其中包含有关内联的更多信息 .