performance - 如何在Haskell中使用内联的相位控制？

Question

文档says，

Sometimes you want to control exactly when in GHC's pipeline the INLINE pragma is switched on.

为什么我要这个？ (除了我也使用RULES pragma时，在这种情况下，我可能希望推迟函数的内联以触发关联的规则。)哪种类型的函数最好仅在简化过程的特定阶段内联？

Answer 1

正如其他人所说，您基本上回答了自己的问题。但是我想您可能想要一个更简化的具体示例，说明将相位控制与RULES / INLINE结合使用是有益的。*在经过高度优化的库(它们通常很复杂)之外，您看不到它们，因此看到较小的库很高兴案件。

这是我最近使用递归方案实现的示例。我们将使用变态的概念来说明这一点。您不需要知道那些详细信息，只需知道它们代表“折叠”运算符即可。 (确实，这里不要过多地关注抽象概念。这只是我所拥有的最简单的示例，您可以在其中获得不错的加速。)

快速入门介绍

我们从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破坏了 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，因此希望它将与其他功能融合。

好了，我们已经有了法律，所以 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的定义。这意味着该规则永远不会被触发，因为该阶段“吞噬”了所有相关的标识符，并将其内联为空。

观察到的是，我们希望尽可能晚地内联 ffold和 fbuild。因此，我们将尝试为RULE开火尽可能多的机会。如果没有，则 body 会内联，而GHC仍会尽力而为。但是最终，我们希望它可以内联到最后；与任何聪明的编译器优化相比， RULE将为我们节省更多的效率。

因此，此处的解决方法是注释 ffold和 fbuild并指定它们仅应在阶段1触发:

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

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

现在， mapL和 friend 将很早就内联，但是这些会很晚。 GHC从某个相数N开始，并且相数减少到零。阶段1是最后一个阶段。也可以在阶段1之前内联 fbuild/ffold，但这实际上意味着您需要开始增加阶段数来弥补它，或者开始确保RULE总是在较早的阶段触发。

结论

您可以在此处找到 all of this and more in a gist of mine **，以及所有提到的定义和示例。它还带有一个示例示例的标准基准:当 lengthL . mapL2触发时，GHC可以通过阶段注释将 lengthL . mapL1的运行时间减少到 RULE的一半。

如果您想亲自看一下，可以使用 -ddump-simpl-stats编译代码，并看到在编译管道中触发了 ffold/fbuild规则。

最后，大多数相同的原理适用于 vector 或字节串之类的库。诀窍是您可能在此处具有多个内联级别，并且包含更多规则。这是因为像流/数组融合之类的技术倾向于有效地融合循环并重用数组-与这里相反，在这里我们只是通过删除中间数据结构来进行经典的森林砍伐。根据所生成代码的传统“模式”(例如，由于矢量化的并行列表理解)，以早期消除明显缺陷的方式对交错优化或特定相位优化可能非常值得。或者，针对将 RULE与 INLINE结合使用会产生更多 RULE的情况进行优化(因此，您有时会看到交错的阶段-这基本上交错了内联的阶段。)由于这些原因，您还可以控制其中的阶段触发 RULE。

因此，虽然带有阶段的 RULE可以为我们节省很多运行时间，但它们也可能需要大量时间才能正确完成。这就是为什么您通常只在最“高性能”，经过高度优化的库中看到它们的原因。

笔记

*您最初的问题是“哪些功能可以从相位控制中受益”，对我来说，这听起来像是在询问“哪些功能受益于恒定的子表达式消除”。如果有可能，我不确定如何正确回答!这更多是关于编译器 Realm 的事情，而不是有关函数或程序如何行为的任何理论结果-即使采用数学定律，并非所有“优化”都具有您所期望的结果。结果，答案实际上是“您可能会在编写和进行基准测试时知道”。

**您可以放心地忽略文件中的许多其他内容；它主要是一个操场，但可能对您也很有趣。那里还有其他示例，例如自然和二叉树-您可能会发现尝试利用它们进行各种其他融合的机会值得。