Abr*_*m P 30 optimization haskell ghc stream-fusion
我不时地在Haskell文档中注意到以下内容:(例如在Data.Text)中:
融合
什么是融合,我该如何使用它？
Ale*_*lec 55
通常,融合是指转换,其目的是摆脱中间数据结构.你融合导致浪费的内存分配到的东西更高效的函数调用.这实际上是IMO Haskell最纯粹的应用之一.你几乎不需要做任何事情来获得它,它通过GHC编译器免费提供.
因为Haskell是纯粹的,所以我们得到称为引用透明性的东西,它(来自链接)意味着"表达式总是在任何上下文中评估相同的结果" 1.这意味着我可以在不改变程序实际输出内容的情况下进行非常一般的程序级操作.例如,即使不知道是什么x,y,z而且w是我一直都知道
((x ++ y) ++ z) ++ w
将评估为同样的事情
x ++ (y ++ (z ++ w))
然而第二个实际上将涉及更少的内存分配(因为x ++ y需要重新分配输出列表的整个前缀).
事实上,也有一大堆这种优化,我们可以做的,而且,由于Haskell是纯粹的,我们基本上可以只左右移动(更换整个表达式x,y,z,或w用于计算结果为列表中的示例实际列表或表达式以上没有变化).这成为一个非常机械的过程.
此外,事实证明,你可以为更高阶函数提出许多等价物(免费定理!).例如,
map f (map g xs) = map (f . g) xs
无论什么f,g和xs,(双方在语义上是平等的).然而,虽然这个等式的两边产生相同的值输出,但左边的效率总是更差:它最终为中间列表分配空间map g xs,然后立即丢弃.我们想告诉编译器,只要遇到类似的东西map f (map g xs),就用它替换它map (f . g) xs.并且,对于GHC,这是通过重写规则:
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}
的f,g以及xs可以对任何表达式,而不只是变量(所以像匹配map (+1) (map (*2) ([1,2] ++ [3,4]))被转化成map ((+1) . (*2)) ([1,2] ++ [3,4]).(似乎没有要搜索重写规则的好方法,所以我整理了一个列表).本文介绍GHC重写规则的动机和运作.
map？实际上,并不完全.上面的东西是捷径融合.名称类型意味着缺点:它不能很好地扩展,并且调试很烦人.您最终必须为相同的常用功能的所有安排编写大量的临时规则.然后,您希望重复应用重写规则可以很好地简化表达式.
事实证明,在某些情况下,我们可以通过组织我们的重写规则来做得更好,这样我们就可以建立一些中间正规形式,然后制定针对该中间形式的规则.这样,我们开始获得重写规则的"热门"路径.
这些系统中最先进的可能是针对共同序列的流融合(基本上是像列表一样的懒惰序列).看看这篇论文和本文(实际上几乎是如何实现vector包).例如,在vector您的代码首先转换为涉及Streams和Bundles 的中间形式,以该形式进行优化,然后转换回向量.
Data.Text？Data.Text使用流融合来最小化发生的内存分配数量(我认为这对于严格的变体尤为重要).如果检查出的来源,你会发现功能"主题融合"实际上操纵Stream小号大部分(它们是一般形式的unstream . (stuff manipulating stream) . stream),并有一堆的RULES转化编译指示Stream秒.最后,这些函数的任何组合都应该融合,以便只需要进行一次分配.
了解代码何时融合的唯一真正方法是充分了解所涉及的重写规则,并充分了解GHC的工作原理.也就是说,有一件事你应该做:尽可能尝试使用非递归的高阶函数,因为这些函数可以(至少现在,但通常总是会更多)容易融合.
因为Haskell中的融合是通过重复应用重写规则而发生的,所以足以说服自己每个重写规则的正确性,以便知道整个"融合"程序与原始程序完全相同.除了与程序终止有关的边缘情况.例如,有人可能会这么认为
reverse (reverse xs) = xs
但这显然不是真的,因为它head $ reverse (reverse [1..])不会终止head [1..].来自Haskell Wiki的更多信息.
1这实际上只有在这些上下文中表达式保持相同类型时才是真实的.