GHC：对于具有固定值的调用，是否有一致的记忆规则？

Question

在我寻求理解和利用 GHC 自动记忆的过程中，我遇到了瓶颈：当纯函数以 fib 42 等固定值调用时，它们有时很快，再次调用时有时很慢。如果它们像 fib 42 一样被简单地调用，或者通过一些数学隐含地调用，它会有所不同，例如(\x -> fib (x - 1)) 43。这些案例似乎没有韵律或原因，所以我将提出它们，目的是询问行为背后的逻辑。

考虑一个缓慢的 Fibonacci 实现，这在记忆化工作时很明显：

slow_fib :: Int -> Integer
slow_fib n = if n < 2 then 1 else (slow_fib (n - 1)) + (slow_fib (n - 2))

我测试了三个基本问题，看看 GHC（版本 8.2.2）是否会记住带有固定参数的调用：

可以 slow_fib 访问以前对 slow_fib 的顶级调用吗？
是否为以后的重要（例如数学）顶级表达式记忆了以前的结果？
是否为以后相同的顶级表达式记忆了之前的结果？

答案似乎是：

没有
没有
是[??]

最后一个案例有效的事实让我很困惑：例如，如果我可以重新打印结果，那么我应该能够添加它们。这是显示此内容的代码：

main = do
  -- 1. all three of these are slow, even though `slow_fib 37` is 
  -- just the sum of the other two results. Definitely no memoization.
  putStrLn $ show $ slow_fib 35
  putStrLn $ show $ slow_fib 36
  putStrLn $ show $ slow_fib 37

  -- 2. also slow, definitely no memoization as well.
  putStrLn $ show $ (slow_fib 35) + (slow_fib 36) + (slow_fib 37)
  putStrLn $ show $ (slow_fib 35) + 1

  -- 3. all three of these are instant. Huh?
  putStrLn $ show $ slow_fib 35
  putStrLn $ show $ slow_fib 36
  putStrLn $ show $ slow_fib 37

然而，奇怪的是，当它嵌入递归函数时，对结果进行数学运算：这个从 Fib(40) 开始的斐波那契变体：

let fib_plus_40 n = if n <= 0
  then slow_fib 40
  else (fib_plus_40 (n - 1)) + (fib_plus_40 (n - 2))

显示如下：

main = do
  -- slow as expected
  putStrLn $ show $ fib_plus_40 0

  -- instant. Why?!
  putStrLn $ show $ fib_plus_40 1

我在 GHC 记忆化的任何解释中找不到任何理由，这通常与显式变量有关（例如 here, here, ）。这就是为什么我预计 fib_plus_40 无法记忆。

Answer 1

你最后link的所有例子都利用了相同的技术：它们不是直接实现函数f，而是首先引入一个列表，其内容是所有调用到 f 可以做到的 。该列表只懒惰地计算一次；然后使用该列表中的简单查找作为 user-facing 函数的实现。因此，他们不依赖于 GHC 的任何缓存。

你的问题是不同的：你希望调用某些函数会自动为你缓存，但通常不会发生这种情况。真正的问题是为什么 any 的结果很快。我不确定，但我认为这与 Constant Applicative Forms (CAF) 有关，GHC 可以自行决定在多个使用站点之间共享。

这里 CAF 最相关的特性是 "Constant" 部分：GHC 只会为在整个运行程序中其值保持不变的表达式引入这样的缓存，而不仅仅是对于某些特定范围。因此，您可以确定 f x <> f x 永远不会重用 f x 的结果（至少不会因为 CAF 折叠；也许 GHC 可以找到其他借口为某些函数记住它，但通常它会这样做不是）。

您程序中不是 CAF 的两件事是 slow_fib 的实现和 fib_plus_40 的递归情况。 GHC 绝对不能对这些表达式的结果进行任何缓存。 fib_plus_40 的基本情况是 CAF，main 中的所有表达式和子表达式也是如此。因此，GHC 可以选择 cache/share 这些子表达式中的任何一个，而不共享它们中的任何一个，随心所欲。可能它看到slow_fib 40是"obviously"简单到可以保存，但是对于main中的slow_fib 35表达式是否应该共享它不太确定。同时，听起来确实出于某种原因决定共享 IO 操作 putStrLn $ show $ slow_fib 35。对你我来说似乎是一个奇怪的选择，但我们不是编译器。

这里的道理是你根本不能指望这个：如果你想确保你只计算一次值，你需要将它保存在某个地方的变量中，并引用该变量而不是重新计算它。

为了证实这一点，我采纳了 luqui 的建议并查看了 -ddump-simpl 输出。以下是显示显式缓存的一些片段：

-- RHS size: {terms: 2, types: 0, coercions: 0}
lvl1_r4ER :: Integer
[GblId, Str=DmdType]
lvl1_r4ER = $wslow_fib_r4EP 40#

Rec {
-- RHS size: {terms: 21, types: 4, coercions: 0}
Main.main_fib_plus_40 [Occ=LoopBreaker] :: Integer -> Integer
[GblId, Arity=1, Str=DmdType <S,U>]
Main.main_fib_plus_40 =
  \ (n_a1DF :: Integer) ->
    case integer-gmp-1.0.0.1:GHC.Integer.Type.leInteger#
           n_a1DF Main.main7
    of wild_a2aQ { __DEFAULT ->
    case GHC.Prim.tagToEnum# @ Bool wild_a2aQ of _ [Occ=Dead] {
      False ->
        integer-gmp-1.0.0.1:GHC.Integer.Type.plusInteger
          (Main.main_fib_plus_40
             (integer-gmp-1.0.0.1:GHC.Integer.Type.minusInteger
                n_a1DF Main.main4))
          (Main.main_fib_plus_40
             (integer-gmp-1.0.0.1:GHC.Integer.Type.minusInteger
                n_a1DF lvl_r4EQ));
      True -> lvl1_r4ER
    }
    }
end Rec }

这并没有告诉我们为什么 GHC 选择引入这个缓存 - 请记住，它可以为所欲为。但它确实证实了机制，它引入了一个变量来保存重复计算。我无法向您展示涉及较小数字的较长 main 的核心，因为当我编译它时，我得到了更多共享：第 2 部分中的表达式也为我缓存了。

Answer 2

为了防止@amalloy 的回答不清楚，问题是你在这里混淆了两件事——隐含的 memoization-like-behavior（人们谈论 [=67 时的意思=] 的 "automatic memoization"，尽管它不是真正的记忆！），它直接来自 thunk-based 惰性求值，以及一种编译器优化技术，它基本上是一种常见的子表达式消除形式。前者或多或少是可以预见的；后者是编译器的心血来潮。

回想一下 real memoization 是一个属性函数的实现：函数 "remembers" 计算某些参数组合的结果，并且可能当使用相同的参数多次调用时，重用这些结果而不是从头开始重新计算它们。当 GHC 为函数生成代码时，它不会自动生成代码来执行这种记忆。

相反，GHC 代码生成以实现函数 application 是不寻常的。 "result" 不是实际将函数应用于参数以生成最终结果作为值，而是立即以 thunk 的形式构造，您可以将其视为挂起的函数调用或 "promise" 到稍后提供价值。

当将来某个时候需要实际值时，将强制使用 thunk（这实际上会导致发生原始函数调用），并使用该值更新 thunk。如果稍后再次需要相同的值，则该值已经可用，因此不需要再次强制执行 thunk。这就是"automatic memoization"。请注意，它发生在 "result" 级别而不是 "function" 级别——函数应用程序的结果会记住它的值；一个函数不记得它以前产生的结果。

现在，通常 result 函数应用程序记住其值的概念是荒谬的。在严格的语言中，我们不担心在 x = sqrt(10) 之后，重用 x 会导致多次 sqrt 调用，因为 x 没有 "memoized" 自己的值。也就是说，在严格的语言中，所有函数应用程序的结果都是 "automatically memoized" 与它们在 Haskell.

中的意义相同

区别在于惰性求值，它允许我们这样写：

stuff = map expensiveComputation [1..10000]

其中 return 立即发出 thunk，无需执行任何昂贵的计算。之后：

f n = stuff !! n

神奇地创建了一个记忆函数，不是因为 GHC 在 f 的实现中生成代码以某种方式记忆调用 f 1000，而是因为 f 1000 强制（一堆列表构造函数thunks 然后）单个 expensiveComputation 其 return 值为 "memoized" 作为列表中索引 1000 处的值 stuff -- 这是一个 thunk，但在被强制之后，它会记住自己的值，就像严格语言中的任何值一样。

因此，根据您对 slow_fib 的定义，none 示例 实际上是在利用 Haskell 的自动记忆，在通常意义上人们的意思。您看到的任何加速都是各种编译器优化的结果，这些优化能够（或不能）识别常见的子表达式或内联/展开短循环。

要编写一个记忆化的 fib，您需要像在严格的语言中一样明确地完成它，通过创建一个数据结构来保存记忆化的值，尽管惰性评估和相互递归定义有时可以让它看起来像 "automatic":

import qualified Data.Vector as V
import Data.Vector (Vector,(!))

fibv :: Vector Integer
fibv = V.generate 1000000 getfib
  where getfib 0 = 1
        getfib 1 = 1
        getfib i = fibv ! (i-1) + fibv ! (i-2)

fib :: Int -> Integer
fib n = fibv ! n

GHC：对于具有固定值的调用，是否有一致的记忆规则？

GHC: Are there consistent rules for memoization for calls with fixed values?

haskell

memoization

ghc