Haskell 空间溢出

Question

Haskell 空间溢出

9

我已经编译了这个程序并尝试运行它。

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Int -> Int
collatzLength = Memo.arrayRange (1, 1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ maximumBy (comparing fst) $ [(collatzLength n, n) | n <- [1..1000000]]

我从GHC得到了以下内容

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

我猜这是我听说的“空间溢出”之一。(我对Haskell还相当新。) 我该如何解决它？我需要重写collatzLength成尾递归吗？

- afkbowflexin

你是如何运行这个程序的？当使用ghc-7.0.4编译并加上-O选项时，它可以在我的电脑上正常工作。 - John L

@yairchu：我不同意；没有一个答案真的很好，但是Henning的答案是准确的。给定的代码根据位大小具有不同的行为；当使用32位整数（来自32位ghc或显式使用Int32）时，会出现堆栈溢出。 - John L

@John L：明白了，我误解了。在这种情况下，hammar的答案是全面的，应该标记。 - yairchu

-O或-O2具体进行了哪些优化，以至于可以神奇地解决这个问题？ - Dan Burton

4个回答

7

这里有一个更简短的程序，以相同的方式失败了：

main = print (maximum [0..1000000])

没问题。

是的。

$ ghc --make harmless.hs && ./harmless
[1 of 1] Compiling Main             ( harmless.hs, harmless.o )
Linking harmless ...
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

使用-O2参数可以解决问题。我不知道这是什么意思 :( 这些空间的谜团真是一个严重的陷阱。

编辑：感谢hammar指出了罪魁祸首。

将您的程序更改为使用

maximum' = foldl1' max

使其在没有-O2的情况下工作。 Prelude中的maximum实现是惰性的，因此在没有编译器魔法粉尘的情况下无法完全处理长列表。

- yairchu

2

确实，maximum和maximumBy都是非严格的，因此在没有严格性分析的情况下，这将导致堆栈溢出。很好的发现！我使用严格的foldl1'手动版本，在没有优化的情况下工作。 - hammar

1

@hammar，那很有道理。把它写成答案吧！ - hmakholm left over Monica

6

我认为最有可能的情况是，在某些Collatz序列中发生了整数溢出，并最终进入一个“人工”循环，其中包含溢出但从未达到1。这将产生无限递归。

请记住，有些Collatz序列在最终（？）达到1之前会变得非常大。

尝试看看是否使用Integer而不是Int可以解决您的问题。

- hmakholm left over Monica

这不是它（根据理论和测试）。只是没有尾递归和智能优化，所以他正在创建一个非常深的堆栈。 - Thomas M. DuBuisson

@Thomas，这也是我的第一个猜测，但是根据维基百科的说法，没有小于十亿的起始点需要超过1000步才能到达1。而且即使使用最不优化的执行策略，递归深度为1000也不应该产生8兆字节的堆栈。（是最后的百万元素列表理解在没有优化的情况下无法保持恒定空间吗？） - hmakholm left over Monica

嗯，那就不确定了。我读到的答案是交换的（如果你看到我之前的评论就知道了），所以我在这里看到的最大深度是525。不过，如果你不使用优化，交换会在完成之前增长超过70M。 - Thomas M. DuBuisson

当使用-O2编译时，它可以正常工作，因此可能不是无限循环。 - yairchu

@hammer 在我的64位机器上，即使使用“Int”也会导致堆栈溢出。对于你来说不是这样吗？你使用相同的优化标志吗？编辑：啊，但即使进行了优化它仍然会溢出。我明白了。 - Thomas M. DuBuisson

显示剩余2条评论

4

如果你关心性能，任何时候都可以使用优化器（通过-O2标志）。 GHC的优化不仅对运行时间非常重要，而且对栈的使用也很重要。我已经在GHC 7.2上进行了测试，优化可以解决你的问题。

另外，如果你使用的是32位机器，请确保使用Int64或Word64。否则会溢出32位整数的大小并导致非终止（感谢Henning提供的信息，给他点赞）。

- Thomas M. DuBuisson

但是即使是完全天真的规约策略，也会导致溢出吗？难道备忘录中有需要优化才能工作的东西吗？ - hmakholm left over Monica

我曾经使用了-O2标志。我应该在我的帖子中指明这一点。结果是，我需要使用“Integer”类型。我忘记了即使我的系统是64位的，我现在使用的操作系统仍然是32位的。 - afkbowflexin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hammar · Accepted Answer

作为涉及代码的作者，我现在有些尴尬，因为这段代码可能存在不止一个而是两个可能导致堆栈溢出的问题。

它使用了Int类型。在32位系统中，由于考拉兹序列可以比起始数字更高得多，因此会发生溢出。这种溢出会导致函数在正负值之间来回跳跃，从而导致无限递归。

在一百万以内的数字中，最糟糕的起始点是704511，它的值可以高达56991483520，然后再回落到1。这已经超出了32位范围。
它使用了maximumBy函数。该函数不是严格的，因此在处理长列表时会导致堆栈溢出。一百万元素对于默认的堆栈大小来说已经足够使其发生。但是启用优化后，由于GHC执行的严格分析，仍然可以正常工作。

解决方法是使用严格版本。由于标准库中没有提供，我们可以自己使用严格左折叠。

这是一个更新后的版本，即使没有启用优化，也应该（希望）避免堆栈溢出。

import Data.List
import Data.Ord
import qualified Data.MemoCombinators as Memo

collatzLength :: Integer -> Integer
collatzLength = Memo.arrayRange (1,1000000) collatzLength'
  where
    collatzLength' 1 = 1
    collatzLength' n | odd n  = 1 + collatzLength (3 * n + 1)
                     | even n = 1 + collatzLength (n `quot` 2)

main = print $ foldl1' max $ [(collatzLength n, n) | n <- [1..1000000]]