21

文档说，

有时您想准确控制在 GHC 的管道中何时打开 INLINE pragma。

为什么我要这个？（除了当我也使用 RULES pragma 时，在这种情况下，我可能想推迟函数的内联，以便触发相关的规则。）什么样的函数只在简化过程的特定阶段内联更好？

4

2 回答 2

15

正如其他人所说，你基本上回答了你自己的问题。但我想你可能想要一个更精简和具​​体的例子，说明在哪里使用相位控制与RULES/INLINE是有益的。* 除了通常很复杂的高度优化的库之外，你看不到它们，所以很高兴看到更小的案例。

这是我最近使用递归方案实现的示例。我们将使用变质的概念来说明这一点。您不需要详细了解这些内容，只需知道它们是“折叠”运算符的特征。（真的，这里不要过分关注抽象概念。这只是我拥有的最简单的示例，您可以在其中获得很好的加速。）

快速介绍变质

我们从Mu定点类型开始，它的定义Algebra只是一个函数的奇特同义词，它“解构”了一个值f a以返回一个a。

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

type Algebra f a = f a -> a

我们现在可以定义两个运算符ffoldand 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 破坏由 an 定义的结构Algebra f a并产生 an a。fbuild而是创建一个由其定义的结构Algebra f a并产生一个Mu值。该Mu值对应于您正在谈论的任何递归数据类型。就像常规的foldrand 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 #-}

内联 FTW

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

lengthL . mapL (+1) $ xs

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

ffold g1 . ffold g2 $ ...

这意味着我们实际上是在破坏结构，然后重建它并再次破坏。真是太浪费了。此外，我们可以根据 重新定义mapL，fbuild因此它有望与其他功能融合。

好吧，我们已经有了我们的法律，所以 aRULE是有序的。让我们编码：

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

啊啊啊，我们完成了，对吧？错误的！

乐趣和利润的阶段

问题是内联发生时的约束为零，这将完全搞砸。考虑之前我们想要优化的情况：

lengthL . mapL2 (+1) $ xs

我们希望 和 的定义lengthL被mapL2内联，以便ffold/fbuild规则可以在正文之后触发。所以我们想去：

ffold f1 . fbuild g1 ...

通过内联，然后转到：

g1 f1

通过我们的RULE.

嗯，这不能保证。本质上，在简化器的一个阶段，GHC不仅lengthL可以内联和的定义mapL，而且还可以内联ffold和fbuild在其使用站点的定义。这意味着 RULE 永远不会有机会触发，因为阶段“吞噬”了所有相关标识符，并将它们内联成空。

观察结果是我们希望尽可能晚地ffold进行内联。因此，我们将尝试尽可能多地暴露我们的 RULE 触发的机会。如果不这样做，那么身体就会内联，而 GHC 仍然会尽力而为。但最终，我们希望它延迟内联；这将比任何聪明的编译器优化为我们节省更多的效率。fbuild RULE

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

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

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

现在，mapL和朋友们会很早就内联，但这些会很晚。GHC 从某个阶段数 N 开始，阶段数减少到零。阶段 1 是最后一个阶段。也可以fbuild/ffold比第 1 阶段更早进行内联，但这基本上意味着您需要开始增加阶段的数量来弥补它，或者开始确保 RULE 总是在一些早期阶段触发。

结论

您可以在我的要点中找到所有这些以及更多内容**，以及所有提到的定义和示例。它还附带了我们示例的标准基准：使用我们的阶段注释，GHC 能够在触发时将运行时间减少lengthL . mapL2一半。lengthL . mapL1RULE

如果您想亲自查看，可以使用 编译代码-ddump-simpl-stats，并查看ffold/fbuild在编译管道期间触发的规则。

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

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

笔记

  • *您最初的问题是“哪些功能受益于相位控制”，这对我来说听起来像是在问“哪些功能受益于不断的子表达式消除”。如果可能的话，我不确定如何准确回答这个问题！这更像是编译器领域的事情，而不是任何关于函数或程序行为的理论结果——即使有数学定律，也不是所有的“优化”都有你期望的结果。结果，答案实际上是“您可能会在编写和基准测试时知道”。

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

于 2013-02-05T21:08:44.600 回答
1

首先，我应该注意到，GHC 的默认行为被设计为在大多数情况下都是最优的。除非你有问题，否则你最好让那些每天都在思考 haskell 的聪明人基本上是正确的（PS 我不是那些人之一），但你问...

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

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

    Haskell 将反复尝试每条规则，只要另一端的结果严格优于它开始时的结果。它总是会收敛，但没有什么说它会在宇宙热寂之前这样做。在一般情况下，只需要一手传球就可以了，但是有些极端情况可能会变得非常糟糕。如果它们发生，这将允许您手动解决这些边缘情况。

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

    在某些情况下，应用 RuleA会阻止应用更好的 Rule B。那么重要的是B先来A。默认优化规则精心设计以避免此问题，但正如文档所述，它们也非常保守。随着您添加更多规则，您将不可避免地开始破坏其他可能的优化。然后，您需要在规则链中找到一个不会发生这种情况的地方。据我所知，唯一的判断方法是反复试验。

于 2013-02-05T06:37:29.533 回答