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

Question

文档表示，

有时候你需要精确地控制在 GHC 的管道中何时打开 INLINE pragma。

为什么我会需要这样做呢？（除非我同时使用 RULES pragma，在这种情况下，我可能需要推迟函数的内联，以便让关联的规则被触发。）哪些类型的函数最好只在简化过程的特定阶段内内联？

- leventov

---

你的要求是描述你想要什么。 - luqui

看一下 repa 的源代码：大部分函数都有不同的相位控制数字：0、1、2、4。但是包中没有任何规则。 - leventov

@leventov说："repa"可能并没有定义规则，但它基于的"vector"绝对有。不过一开始看起来并不是很清楚，因为"vector"源码也严重依赖于CPP。无论如何，"repa"的相位控制数字被调整以与"vector"使用的规则和内联函数进行交互。 - John L

+1 @luqui。你正确地推断出，只有在内联发生之前还想要有机会触发规则时，它才真正有用。 - Louis Wasserman

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：我们使用它的 cons 解构列表，我们也使用它的 cons 构建列表。这个想法是我们刚刚泛化了这些经典运算符，所以它们可以在 任何 递归数据类型上工作（如列表或树！）

最后，有一条与这两个运算符相关的法则，将指导我们的整体 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 #-}

内联万岁

现在我们有一种方法来编写我们定义的递归类型上的术语。然而，如果我们要编写像下面这样的一个术语：

lengthL . mapL (+1) $ xs

如果我们扩展这些定义，实际上就是两个ffold运算符的组合:

ffold g1 . ffold g2 $ ...

这意味着我们实际上正在摧毁结构，然后重建它并再次摧毁。 这真的很浪费。此外，我们可以使用fbuild重新定义mapL，这样它就会希望与其他函数融合。

好吧，我们已经有了我们的规则，所以需要一个RULE。 让我们将其编码：

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

接下来，为了进行融合运算，我们将使用fbuild重新定义mapL：

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 #-}

完成了，是吗？错了！

玩乐和利润的阶段

问题在于内联发生的时间没有任何限制，这将完全搞砸。考虑我们之前想要优化的情况：

lengthL . mapL2 (+1) $ xs

我们希望将lengthL和mapL2的定义内联，以便在其后面对主体进行ffold/fbuild规则调用。因此，我们要执行以下操作：

ffold f1 . fbuild g1 ...

通过内联，然后转到：

g1 f1

通过我们的RULE。

但这并不是保证的。在简化器的某个阶段中， GHC 可能不仅内联lengthL和mapL的定义，还可能在使用它们的地方内联ffold和fbuild的定义。这意味着规则将永远没有机会触发，因为该阶段“吞噬”了所有相关标识符，并将其内联为无效代码。

我们的观察是，我们希望尽可能晚地内联ffold和fbuild。因此，我们将尝试尽可能多地暴露潜在的机会来触发规则。如果规则没有生效，那么函数体将被内联，GHC 仍然会尽其所能。但最终，我们希望它晚一点内联；相比于其他聪明的编译器优化，RULE将为我们节省更多的效率。

所以这里的修复方法是注释ffold和fbuild，并指定它们只在第一阶段触发：

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

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

现在，mapL等函数将被非常早地内联，但是这些将在很晚的时候进行。GHC从某个阶段号N开始，然后阶段号递减到零。阶段1是最后一个阶段。可能会在阶段1之前即时内联fbuild/ffold，但这基本上意味着你需要开始增加阶段号来弥补它，或者确保规则始终在一些较早的阶段触发。

结论：你可以在我的代码片段中找到所有这些内容以及更多信息，其中包括所有提到的定义和示例。它还附带了我们示例的标准测试结果：使用我们的阶段注释，当RULE触发时，GHC能够将lengthL . mapL2的运行时间减半，与lengthL . mapL1相比。如果您想自己验证，请使用-ddump-simpl-stats编译代码，并查看编译流程中是否触发了ffold/fbuild规则。最后，大多数相同的原则也适用于像vector或bytestring这样的库。技巧在于您可能有多个层次的内联，以及更多规则。这是因为流/数组融合等技术通常会有效地融合循环并重用数组，而不是像这里一样仅仅是通过删除一个中间数据结构来进行经典的砍树。根据生成代码的传统“模式”（例如由于向量化并行列表理解）的情况，有时按照明显不足先后交错或专门定义优化阶段非常值得。或者为使RULE与INLINE相结合能够产生更多的RULE而进行优化（因此你有时会看到交错的阶段；这基本上交错了内联的阶段）。由于这些原因，您也可以控制RULE触发的阶段。因此，虽然具有阶段的RULE可以节省我们大量的运行时间，但它们也可能需要很长时间才能达到最佳效果。这就是为什么你通常只会在最'高性能'、高度优化的库中看到它们的原因。

注意事项：您最初的问题是“哪些函数受益于阶段控制”，这对我来说听起来像是在问“哪些函数受益于常量子表达式消除”。我不确定如何准确地回答这个问题，如果可能的话！这更像是一个编译器领域的事情，而不是任何有关函数或程序行为的理论结果 - 即使在数学定律的情况下，不是所有的“优化”都有你期望的结果。因此，答案实际上是“你写代码并对其进行基准测试时可能会知道。”

- thoughtpolice

Answer 2

首先，我应该指出，GHC的默认行为被设计为在大多数情况下都是最优的。除非您遇到问题，否则最好让那些整天考虑Haskell的非常聪明的人们大部分时间都是正确的（PS：我不是其中之一），但您问了......

据我理解，使用它有两个原因。

1. 使程序更快地收敛到最佳形式：

   Haskell 会重复尝试每个规则，只要输出的结果比开始的好得多就继续。它总会收敛，但没有任何东西可以保证它在宇宙热寂之前就能收敛。通常情况下，它不需要超过几次迭代，但有些边缘情况可能会变得非常糟糕，而这将允许您手动解决这些问题。

2. 避免收敛到局部最小值

   在某些情况下，应用规则 A 将阻止更好的规则 B 的应用。因此，很重要的是 B 在 A 之前被考虑。默认的优化规则经过精心设计，以避免出现这个问题，但正如文档所说，它们也非常保守。随着添加更多规则，您不可避免地会破坏其他可能的优化。那么，您需要找到一个规则链中不会发生这种情况的位置。据我所知，唯一的方法是通过试错。

- John F. Miller