当前位置：文江博客话题详情

Memoization haskell ghc

GHC Haskell 何时自动记忆？

发布于 2024-09-27 23:16:08 字数 273 浏览 1 评论 0 原文

我不明白为什么 m1 明显被记忆，而 m2 不在以下内容中：

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

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

m1 10000000 第一次调用大约需要 1.5 秒，后续调用只需要一小部分时间（大概它会缓存列表），而 m2 10000000 总是花费相同的时间（每次调用重建列表）。知道发生了什么事吗？关于 GHC 是否以及何时记忆某个函数，是否有任何经验法则？谢谢。

原文

I can't figure out why m1 is apparently memoized while m2 is not in the following:

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

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

m1 10000000 takes about 1.5 seconds on the first call, and a fraction of that on subsequent calls (presumably it caches the list), whereas m2 10000000 always takes the same amount of time (rebuilding the list with each call). Any idea what's going on? Are there any rules of thumb as to if and when GHC will memoize a function? Thanks.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不念旧人 2024-10-04 23:16:08

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 编译时的两倍。

GHC does not memoize functions.

It does, however, compute any given expression in the code at most once per time that its surrounding lambda-expression is entered, or at most once ever if it is at top level. Determining where the lambda-expressions are can be a little tricky when you use syntactic sugar like in your example, so let's convert these to equivalent desugared syntax:

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

(Note: The Haskell 98 report actually describes a left operator section like (a %) as equivalent to \b -> (%) a b, but GHC desugars it to (%) a. These are technically different because they can be distinguished by seq. I think I might have submitted a GHC Trac ticket about this.)

Given this, you can see that in m1', the expression filter odd [1..] is not contained in any lambda-expression, so it will only be computed once per run of your program, while in m2', filter odd [1..] will be computed each time the lambda-expression is entered, i.e., on each call of m2'. That explains the difference in timing you are seeing.

Actually, some versions of GHC, with certain optimization options, will share more values than the above description indicates. This can be problematic in some situations. For example, consider the function

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

GHC might notice that y does not depend on x and rewrite the function to

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

In this case, the new version is much less efficient because it will have to read about 1 GB from memory where y is stored, while the original version would run in constant space and fit in the processor's cache. In fact, under GHC 6.12.1, the function f is almost twice as fast when compiled without optimizations than it is compiled with -O2.

回复收藏 0 原文

奈何桥上唱咆哮 2024-10-04 23:16:08

m1 仅计算一次，因为它是常量应用形式，而 m2 不是 CAF，因此每次评估都会计算一次。

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

回复收藏 0 原文

叹梦 2024-10-04 23:16:08

这两种形式之间有一个关键的区别：单态限制适用于 m1 而不是 m2，因为 m2 已明确给出参数。所以 m2 的类型是通用的，而 m1 的类型是特定的。它们分配的类型是：

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

大多数 Haskell 编译器和解释器（我实际上知道的所有编译器和解释器）都不会记忆多态结构，因此 m2 的内部列表在每次调用时都会重新创建，而 m1 则不会。

There is a crucial difference between the two forms: the monomorphism restriction applies to m1 but not m2, because m2 has explicitly given arguments. So m2's type is general but m1's is specific. The types they are assigned are:

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

Most Haskell compilers and interpreters (all of them that I know of actually) do not memoize polymorphic structures, so m2's internal list is recreated every time it's called, where m1's is not.

回复收藏 0 原文

林空鹿饮溪 2024-10-04 23:16:08

我不确定，因为我自己对 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个元素。

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

I'm not sure, because I'm quite new to Haskell myself, but it appears that it's beacuse the second function is parametrized and the first one is not. The nature of the function is that, it's result depends on input value and in functional paradigm especailly it depends ONLY on the input. Obvious implication is that a function with no parameters returns always the same value over and over, no matter what.

Aparently there's an optimizing mechanizm in GHC compiler that exploits this fact to compute the value of such a function only once for whole program runtime. It does it lazily, to be sure, but does it nonetheless. I noticed it myself, when I wrote the following function:

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

Then to test it, I entered GHCI and wrote: primes !! 1000. It took a few seconds, but finally I got the answer: 7927. Then I called primes !! 1001 and got the answer instantly. Similarly in an instant I got the result for take 1000 primes, because Haskell had to compute the whole thousand-element list to return 1001st element before.

Thus if you can write your function such that it takes no parameters, you probably want it. ;)

回复收藏 0 原文

~没有更多了~