在存在一些递归情况时保持内联的潜力

Question

考虑以下数据类型，它仅用于说明：

data D where
  D1 :: Int -> D
  D2 :: String -> D
  DJ :: D -> D -> D

也许还有一个函数，比如 toString:

{-# INLINE toString #-}
toString x = case x of
  (D1 x) -> "Int: show x"
  (D2 x) -> "String: show x"
  (DJ x y) -> "(" ++ toString x ++ "," ++ toString y ++ ")"

（值得注意的是我所做的与打印无关，这只是一个说明性的例子）

所以我发现通过像这样定义 toString 可以使我的程序快 15 倍：

{-# INLINE toString #-}
toString x = case x of
  (D1 x) -> "Int: show x"
  (D2 x) -> "String: show x"
  (DJ x y) -> undefined

发生的事情是 toString 现在可以被 GHC 内联。这允许在未来进行大量优化。 DJ 案例是导致问题的原因。然后我尝试了这个：

{-# INLINE toString #-}
toString x = case x of
  (D1 x) -> intShow x
  (D2 x) -> strShow x
  _ -> go x
  where
    go (D1 x) -> intShow x
    go (D2 x) -> strShow x
    go (DJ x y) -> "(" ++ go x ++ "," ++ go y ++ ")"
    intShow x = "Int: show x"
    strShow x = "String: show x"

这实际上意味着它编译速度很快。原因是（我很确定）因为 toString 不再是递归的。 go 是，但 toString 不是。所以编译器会愉快地内联 toString，允许在未来进行更多优化。

但是上面的代码，在我看来，是丑陋的。

就像我说的，我拥有的功能比这个更复杂，而且这种问题在我的代码中时有发生。我有一个包含很多构造函数的数据类型，有些是简单的，有些是递归的。然而，每当我定义一个递归案例时，它甚至会减慢简单案例的速度。有没有办法保持 top 函数内联而不像我上面那样丑化代码？

Answer 1

我没有优雅的解决方案，但也许像这样的方法可行。未经测试。

{-# INLINE toString #-}
toString x = go (fix go)  -- equivalent to (fix go), but unrolled once
  where
  {-# INLINE go #-}
  go _ (D1 x) -> intShow x
  go _ (D2 x) -> strShow x
  go k (DJ x y) -> "(" ++ k x ++ "," ++ k y ++ ")"
  intShow x = "Int: show x"
  strShow x = "String: show x"

Answer 2

我认为您已经正确地确定了问题以及解决问题所需要做的事情，通常（我同意不是很令人满意）：

标记INLINE
eta 摆弄，以便 left-hand 端在调用站点完全应用
添加一个简单的间接层，使函数不递归

但是我认为:

{-# INLINE toString #-}
toString x = go x where
 go case x of
  (D1 x) -> "Int: show x"
  (D2 x) -> "String: show x"
  (DJ x y) -> "(" ++ go x ++ "," ++ go y ++ ")"

正如 chi 在他们的回答中指出的那样，您在这里所做的似乎是手动单级循环展开；很容易看出为什么这样会更快，比如：

(DJ (D1 0) (D2 "zero"))

但不太明显，例如，当您深度嵌套 DJ 时，这会好多少。我很想知道，并想看看你是如何进行基准测试的。

大多数时候我们关心以这种方式进行内联，因为我们的 x 是多态的，我们希望我们在主体中调用 x 的函数是专门的。或者我们希望结果保持未装箱的类型。

Answer 3

我已经给@chi 打上了他伟大的涉及 fix 的标记，它确实完成了这项工作。但有点繁琐，因为在我的例子中，我的递归是多态的（fix 单态）所以我不得不推出自己的 fix。

我还担心通过传入递归参数而不是直接调用它可能会进一步混淆递归情况的编译器。

但受到@chi 的回答的启发，并认为我基本上想要两个相同的函数，一个 non-recursive 一个和一个递归的，然后我意识到我可以这样做，就像这样：

import Data.Proxy (Proxy(Proxy))

toString x = go' (Proxy :: Proxy True)
  {-# SPECIALISE INLINE go' :: Proxy True -> String #-}
  go' :: (Proxy a) -> String
  go' _ = case x of
    (D1 x) -> "Int: show x"
    (D2 x) -> "String: show x"
    (DJ x y) -> "(" ++ go x ++ "," ++ go y ++ ")"
  go = go' (Proxy :: Proxy False)

由于 go' 的特化，编译器将发出两个 go' 函数，一个用于当 Proxy 参数为 True 时，另一个用于当它它False。

第一个，当它是True时，不是递归的，它从不调用自身（它只调用False版本）。因此，如果我们对此进行专业化，它就是不可分割的。由于 go' (True) 不是递归的，因此 toString 也是如此，因为 toString 所做的只是调用 go' (True)，因此 toString 是可内联的。

这种方法需要一点样板，但至少样板的长度是恒定的，它不会随着您需要处理的构造函数的数量而增加。

在存在一些递归情况时保持内联的潜力

Keeping the potential for inlining when there are some recursive cases

optimization

haskell

ghc