GHC:对于具有固定值的呼叫，是否有一致的记忆规则

在我理解和利用GHC自动记忆的过程中，我遇到了一堵墙：当纯函数被调用时，像fib 42这样的固定值，它们有时很快，有时很慢。如果它们被简单地称为fib 42或通过一些数学隐含地调用，例如(x -> fib (x - 1)) 43.这些案例似乎没有押韵或理由，所以我会提出它们，目的是询问行为背后的逻辑是什么。

考虑一个缓慢的斐波那契实现，这在记忆工作时很明显：

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记忆的任何解释中，我找不到任何理由，这通常会使显式变量(例如这里，这里和这里)有罪。这就是为什么我预计fib_plus_40不会记住。

为了详细说明，以防从@amalloy的回答中不清楚，问题是你在这里混淆了两件事 - 隐式记忆行为(人们在谈论Haskell的"自动记忆"时的意思，尽管它不是真正的记忆！)直接来自基于thunk的惰性计算，以及编译器优化技术，基本上是一种常见的子表达式消除形式。前者是可以预测的，或多或少;后者由编译器一时兴起。

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

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

当将来某个时候需要实际值时，thunk 被强制(这实际上会导致原始函数调用发生)，并且 thunk 会用该值更新。如果以后再次需要相同的值，则该值已经可用，因此不需要再次强制 thunk。这就是"自动记忆"。请注意，它发生在"结果"级别而不是"函数"级别 - 函数应用程序的结果会记住其值;函数不记得它以前产生的结果。

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

区别在于惰性求值，它允许我们编写如下内容：

stuff = map expensiveComputation [1..10000]

它会立即返回一个 thunk，而无需执行任何昂贵的计算。之后：

f n = stuff !! n

神奇地创建了一个记忆函数，不是因为 GHC 在f的实现中生成代码以以某种方式记忆调用f 1000，而是因为f 1000强制(一堆列表构造函数扔掉然后)一个返回值被"记忆"为列表stuff中索引 1000 处的值的单个expensiveComputation——这是一个笨蛋，但是在被迫之后，它会记住自己的价值，就像严格语言中的任何价值一样。

所以，鉴于你对slow_fib的定义，你的例子都没有真正利用人们通常意义上的哈斯克尔的自动记忆。您看到的任何加速都是各种编译器优化的结果，这些优化正在(或没有)识别公共子表达式或内联/解包短循环。

要编写一个记忆fib，你需要像在严格的语言中一样明确地做到这一点，通过创建一个数据结构来保存记忆值，尽管惰性求值和相互递归的定义有时会让它看起来像是"自动的"：

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

最后链接的所有示例都采用了相同的技术：它们不是直接实现函数f，而是首先引入一个列表，其内容是所有可以进行的f调用。该列表仅延迟计算一次;然后使用该列表中的简单查找作为面向用户的函数的实现。因此，他们不依赖于 GHC 的任何缓存。

你的问题是不同的：你希望调用某个函数会自动为你缓存，一般来说这不会发生。真正的问题是为什么你的任何结果都很快。我不确定，但我认为这与恒定应用形式 (CAF) 有关，GHC 可以自行决定在多个使用站点之间共享。

这里 CAF 最相关的功能是"常量"部分：GHC 只会为在整个程序运行过程中值恒定的表达式引入这样的缓存，而不仅仅是针对某些特定范围。因此，您可以确定f x <> f x永远不会重用f x的结果(至少不是由于CAF折叠;也许GHC可以找到其他借口来记住某些功能，但通常不会)。

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

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

为了证实这一点，我接受了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 节中的表达式也为我缓存。

相关内容

最新更新

热门标签：