GHC Haskell中的自动记忆化是在何时进行的？

Question

我无法理解为什么在下面的代码中m1被记忆化了，而m2没有：

m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)

对于m1 10000000，第一次调用大约需要1.5秒钟，随后的调用只需要一小部分时间（可能缓存了该列表），而对于m2 10000000，每次调用都需要相同的时间（每次重建列表）。有什么想法吗？是否存在关于何时和何时不会进行函数记忆化的经验法则？谢谢。

- Jordan

Answer 1

GHC不会对函数进行记忆化。

它会在每次进入其周围的lambda表达式时计算任何给定的代码中的表达式，或者如果它位于顶层，则最多计算一次。确定lambda表达式的位置可能有点棘手，特别是在使用语法糖的情况下，比如你的例子，因此让我们将它们转换为等效的非糖语法：

m1' = (!!) (filter odd [1..])              -- NB: See below!
m2' = \n -> (!!) (filter odd [1..]) n

（注意：Haskell 98报告实际上将左操作符部分描述为(a %)等价于\b -> (%) a b，但 GHC 将其展开为(%) a。这些在技术上是不同的，因为它们可以通过seq区分。我想我可能提交了一个有关此事的 GHC Trac 票。）

鉴于此，你可以看到在m1'中，表达式filter odd [1..]不包含在任何 lambda 表达式中，因此它每次运行程序时只会计算一次，而在m2'中，filter odd [1..]将在每次进入 lambda 表达式时计算，即每次调用m2'时。这解释了你所看到的时间差异。

---

实际上，某些版本的 GHC（带有某些优化选项）将共享比上述描述更多的值。这在某些情况下可能会有问题。例如，请考虑以下函数。

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x])

GHC 可能会注意到 y 不依赖于 x，并将函数重写为：

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x])

在这种情况下，新版本的效率要低得多，因为它将不得不从存储y的内存中读取约1 GB的数据，而原始版本将在恒定的空间内运行，并适合处理器的缓存。事实上，在GHC 6.12.1下，当不使用优化编译函数f时，它的速度几乎比使用-O2编译慢一倍。

- Reid Barton

---

评估（过滤奇数[1..]）表达式的成本几乎为零 - 毕竟它是惰性列表，因此实际成本在(x !! 10000000)应用程序中，当列表实际被评估时。此外，使用-O2和-O1（在我的ghc 6.12.3上）测试中，m1和m2似乎只被评估一次（test = m1 10000000 seq m1 10000000）。不过，当没有指定优化标志时会有所不同。顺便说一下，您“f”的两个变体无论是否进行了优化，最大驻留量均为5356字节（使用-O2时总分配较少）。 - Ed'ka

@Ed'ka：尝试使用上面定义的 f，运行以下测试程序：main = interact $ unlines . (show . map f . read) . lines；可以选择编译时加或不加 -O2；然后执行 echo 1 | ./main。如果你编写一个像 main = print (f 5) 的测试，那么 y 可以被垃圾回收，因为它被使用了，两个 f 之间没有区别。 - Reid Barton

嗯，当然应该是 map (show . f . read)。现在我已经下载了 GHC 6.12.3，发现与 GHC 6.12.1 中的结果相同。是的，你对于原始的 m1 和 m2 是正确的：启用优化的 GHC 版本将把 m2 转换为 m1。 - Reid Barton

是的，现在我看到了区别（-O2明显更慢）。谢谢你提供的例子！ - Ed'ka

Answer 2

m1仅被计算一次，因为它是一个常量应用形式（CAF），而m2不是CAF，因此每次评估都需要计算。

请参阅有关CAF的GHC维基：http://www.haskell.org/haskellwiki/Constant_applicative_form

- sclv

---

“m1 is computed only once because it is a Constant Applicative Form”这个解释对我来说没有意义。因为我认为，无论它们是CAF还是不是，假设m1和m2都是顶级变量，那么这些函数只会被计算一次。区别在于列表[1 ..]是否在程序执行期间只计算一次，或者在每个函数应用中计算一次，但这与CAF有关吗？ - Tsuyoshi Ito

从链接页面中： "CAF ...可以编译成一段图形，该图形将由所有使用者共享，或者编译成一些共享代码，该代码将在第一次评估时用某些图形覆盖自身"。由于m1是一个CAF，因此适用第二种情况，并且仅计算一次filter odd [1..]（而不仅仅是[1..]！）。 GHC还可以注意到m2引用了filter odd [1..]，并将链接放置在m1中使用的相同thunk中，但这是一个坏主意：在某些情况下，它可能会导致大量的内存泄漏。 - Alexey Romanov

@Alexey：感谢您对[1..]和filter odd [1..]的更正。但就其余部分而言，我仍然不太确定。如果我没有弄错，CAF只在我们想要证明编译器可以将m2中的filter odd [1..]替换为全局thunk（甚至可能是与m1中使用的相同thunk）时才相关。但在提问者的情况下，编译器并没有进行这种“优化”，我看不出它与问题有什么关系。 - Tsuyoshi Ito

它能够替换m1中的内容，这一点非常重要，并且它已经实现了。 - Alexey Romanov

Answer 3

两种形式之间存在关键差异：单态限制适用于m1但不适用于m2，因为m2具有显式给定的参数。 因此，m2的类型是通用的，而m1的类型是具体的。 它们分配的类型如下：

m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a

大多数Haskell编译器和解释器(我所知道的全部)都不会对多态结构进行记忆化处理，因此每次调用m2时其内部列表都会被重新创建，而m1的则不会。

- mokus

---

在GHCi中玩弄这些东西时，似乎也依赖于let-floating转换（GHC中未在GHCi中使用的优化过程之一）。当然，在编译这些简单函数时，优化器能够使它们表现出相同的行为（根据我运行的某些标准测试，将函数放在一个单独的模块中并用NOINLINE pragma标记）。这可能是因为列表生成和索引被融合成一个超紧密的循环。 - mokus

Answer 4

我不太确定，因为我自己对Haskell也很新，但似乎是因为第二个函数是参数化的，而第一个函数不是。函数的性质是，它的结果取决于输入值，在函数式编程中特别是仅取决于输入值。显然的含义是，没有参数的函数总是返回相同的值，无论如何。

显然，在GHC编译器中有一种优化机制，利用这一事实仅计算这样一个函数的值一次，整个程序运行时都可以使用。它懒惰地执行，但确实执行了。当我编写以下函数时，我注意到了这一点：

primes = filter isPrime [2..]
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n]
        where f `divides` n = (n `mod` f) == 0

然后为了测试它，我输入了GHCI并写下： primes !! 1000。它花了几秒钟，但最终我得到了答案：7927。然后我调用primes !! 1001并立即得到答案。同样地，我立刻得到了take 1000 primes的结果，因为Haskell必须计算整个包含一千个元素的列表才能返回第1001个元素之前的内容。

因此，如果您可以编写一个不需要参数的函数，那么您可能需要它。;)

- Sventimir