如何在haskell中使用内联的相位控制？

Question

文档说,

有时您想要在GHC的管道中准确控制INLINE编译指示何时打开.

我为什么要这个？(除非我也使用RULES编译指示,在这种情况下,我可能希望推迟函数的内联,以便触发相关规则.)只有在简化过程的特定阶段才能更好地内联哪些函数？

Answer 1

正如其他人所说,你基本上回答了你自己的问题.但是我想你可能想要一个更简洁和具体的例子,说明将相位控制与RULES/ 结合使用的地方INLINE是有益的.*除了经常很复杂的高度优化的库之外,你不会看到它们,所以很容易看到较小的情况.

这是我最近使用递归方案实现的示例.我们将使用catamorphisms的概念来说明这一点.你不需要知道它们的细节,只是它们描述了'折叠'运算符.(真的,不要过多关注这里的抽象概念.这只是我拥有的最简单的例子,你可以有一个很好的加速.)

快速介绍catamorphisms

我们从Mu定点类型开始,其定义Algebra只是函数的一个奇特的同义词,该函数"解构" f a返回值的值a.

newtype Mu f = Mu { muF :: f (Mu f) }

type Algebra f a = f a -> a

现在,我们可以定义两个运营商,ffold而且fbuild,这是传统的高仿制药foldr和build针对运营商列表:

ffold :: Functor f => Algebra f a -> Mu f -> a
ffold h = go h 
  where go g = g . fmap (go g) . muF
{-# INLINE ffold #-}

fbuild :: Functor f => (forall b. Algebra f b -> b) -> Mu f
fbuild g = g Mu
{-# INLINE fbuild #-}

粗略地说,ffold 破坏由a定义的结构Algebra f a并产生一个a.fbuild而是创建一个由它定义的结构Algebra f a并产生一个Mu值.该Mu值对应于您正在谈论的任何递归数据类型.就像常规foldr和build:我们使用它的缺点解构一个列表,我们也使用它的缺点构建一个列表.这个想法是我们只是概括了这些经典运算符,因此它们可以处理任何递归数据类型(如列表或树!)

最后,这两个运营商都有一条法律,它将指导我们的整体RULE:

forall f g. ffold f (build g) = g f

该规则基本上概括了砍伐森林/融合的优化 - 中间结构的去除.(我认为所述法律的正确性证明留给读者.通过等式推理应该相当容易.)

我们现在可以使用这两个组合器Mu来表示递归数据类型,如列表.我们可以在该列表上编写操作.

data ListF a f = Nil | Cons a f
  deriving (Eq, Show, Functor)
type List a = Mu (ListF a)

instance Eq a => Eq (List a) where
  (Mu f) == (Mu g) = f == g

lengthL :: List a -> Int
lengthL = ffold g
  where g Nil = 0
        g (Cons _ f) = 1 + f
{-# INLINE lengthL #-}

我们也可以定义一个map函数:

mapL :: (a -> b) -> List a -> List b
mapL f = ffold g
  where g Nil = Mu Nil
        g (Cons a x) = Mu (Cons (f a) x)
{-# INLINE mapL #-}

FTW内联

我们现在有一种方法可以在我们定义的这些递归类型上编写术语.但是,如果我们写一个像这样的术语

lengthL . mapL (+1) $ xs

然后,如果我们扩展定义,我们基本上得到两个ffold运算符的组合:

ffold g1 . ffold g2 $ ...

这意味着我们实际上正在破坏结构,然后重建并再次摧毁.这真的很浪费.另外,我们可以重新定义mapL来讲fbuild,所以它会希望与其他功能的融合.

好吧,我们已经有了我们的法律,所以a RULE是有序的.让我们编纂:

{-# RULES
-- Builder rule for catamorphisms
"ffold/fbuild" forall f (g :: forall b. Algebra f b -> b).
                  ffold f (fbuild g) = g f
-}

接下来,我们将mapL根据fbuild融合目的重新定义:

mapL2 :: (a -> b) -> List a -> List b
mapL2 f xs = fbuild (\h -> ffold (h . g) xs)
  where g Nil = Nil
        g (Cons a x) = Cons (f a) x
{-# INLINE mapL2 #-}

Aaaaa和我们完成了,对吧？错误!

乐趣和利润的阶段

问题是内联发生时没有任何限制,这将完全搞砸了.考虑一下我们想要优化的情况:

lengthL . mapL2 (+1) $ xs

我们希望定义lengthL和mapL2内联,以便ffold/fbuild规则可以在身体之后触发.所以我们想去:

ffold f1 . fbuild g1 ...

通过内联,然后转到:

g1 f1

通过我们的RULE.

嗯,这不能保证.从本质上讲,在简化器的一个阶段,GHC可能不只是内联的定义lengthL和mapL,但它也可以内联的定义ffold,并fbuild在其使用的网站.这意味着RULE将永远不会有机会发射,因为阶段'吞噬'所有相关标识符,并将它们内嵌到任何内容中.

观察是我们希望内联ffold并fbuild 尽可能晚.因此,我们将尝试尽可能多地为我们的RULE揭开可能的机会.如果没有,那么身体将被内联,GHC仍然会发挥最大作用.但最终,我们希望它能延迟上线; 这RULE将比任何聪明的编译器优化节省更多的效率.

所以这里的修复是注释ffold并fbuild指定它们只应在第1阶段触发:

ffold g = ...
{-# INLINE[1] ffold #-}

fbuild g = ...
{-# INLINE[1] fbuild #-}

现在,mapL朋友们很早就会上线,但这些都会很晚才会出现.GHC从某个阶段编号N开始,阶段编号减少到零.第1阶段是最后阶段.也可以fbuild/ffold比第1阶段更快地内联,但这实际上意味着你需要开始增加阶段的数量以弥补它,或者开始确保规则总是在某些早期阶段触发.

结论

您可以在我的要点中找到所有这些以及更多内容**,其中包含所有提到的定义和示例.它还附带了我们示例的标准基准:通过我们的阶段注释,GHC能够将火灾时的运行时间减少lengthL . mapL2一半.lengthL . mapL1RULE

如果您希望自己看到这个,可以使用编译代码-ddump-simpl-stats,并查看ffold/fbuild在编译管道中触发的规则.

最后,大多数相同的原则适用于像vector或bytestring这样的库.诀窍是,你可能有内联在这里的多层次,和很多更多的规则.这是因为像流/阵列融合这样的技术倾向于有效地融合循环和重用数组 - 而不是在这里,我们只是通过删除中间数据结构来进行经典的森林砍伐.根据生成的代码的传统"模式"(例如,由于矢量化,并行列表理解),以早期消除明显缺陷的方式交​​错或特定阶段优化可能是非常值得的.或者,对于RULE与a 组合INLINE会产生更多RULEs的情况进行优化(因此有时你会看到交错的阶段 - 这基本上会交错一个内联阶段.)由于这些原因,你也可以控制RULE着火的阶段.

因此,虽然RULE带有阶段的s可以为我们节省大量的运行时间,但它们也可能需要花费大量时间才能正确运行.这就是为什么您经常只在最"高性能",高度优化的库中看到它们.

笔记

• *您最初的问题是"哪种类型的功能受益于相位控制",这听起来像是在询问"哪些功能可以从不断的子表达式消除中受益".如果可能的话,我不确定如何准确地回答这个问题!这是一个编译器领域的事情,而不是关于函数或程序如何表现的任何理论结果 - 即使使用数学定律,并非所有'优化'都具有您期望的结果.因此,答案实际上是"您可能知道何时编写和基准测试."

• **您可以安全地忽略文件中的许多其他内容; 它主要是一个游乐场,但也可能对你很有趣.还有其他的例子,如自然和二叉树 - 你可能会发现尝试利用它们来利用各种其他融合机会是值得的.