0

我正在阅读 << real world haskell >> Chapter 8 并想看看 SumFile.hs 程序如何处理 100 万个数字：

main :: IO ()
main = do
  contents <- getContents
  print (sumFile contents)
    where sumFile = sum . map read . words

当我向程序提供 100 万个整数时：

runhaskell SumFile.hs < data.txt，程序给出了正确的结果。

但是，当我使用 GHC 编译它时：

ghc SumFile.hs

二进制文件给出“堆栈空间溢出”错误：

./SumFile < data.txt 
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

我有两个问题：

  1. 是什么导致堆栈空间使用？
  2. 为什么编译版本与解释版本不同，我该怎么办？

谢谢！

编辑：

好吧，原因是 map，但这是一个使用惰性字节串的修改版本：

import qualified Data.ByteString.Lazy as L
import qualified Data.ByteString.Lazy.Char8 as LCHAR
import Data.Monoid
import Data.List

main :: IO ()
main = do
  contents <- L.getContents
  case sumFile contents of
    Nothing -> print "Invalid input"
    Just s -> print $ getSum s
   where sumFile = foldl' mappend (Just (Sum 0)) . map ((fmap Sum) . (fmap fst) . LCHAR.readInt) . (LCHAR.words)

结果是一样的：即使我没有使用 sum，二进制版本也会占用堆栈空间。

4

3 回答 3

1

我在#haskell 上与人们进行了讨论，ByteString 版本给出堆栈溢出错误的原因是由于内部未严格评估的嵌套 Just (Sum Num)。

本质上，当我们映射两个 Maybe (Just Num) 时，例如 Just (Sum 2) 和 Just (Sum 3)，foldl' 使用 seq 来生成 Just ((Sum 2) mappend (Sum 3))，即。seq 严格评估最外层的构造函数（映射两个 Just (Monoid) 以生成一个 Just (Monoid)）。在这种情况下，内部 Monoid 没有被严格评估，因此它们被保留为 mappend connected (Sum Num)。这导致 100 万个 mappend connected (Sum Num) 被包裹在 Just 中。

所以#haskell 上的 Saizan 给出了这个版本，它严格评估了 Maybe (Sum Num) 的内部部分

import qualified Data.ByteString.Lazy as L
import qualified Data.ByteString.Lazy.Char8 as LCHAR
import Data.Monoid
import Data.List

forceMaybe Nothing = Nothing
forceMaybe (Just x) = x `seq` (Just x)

main :: IO ()
main = do
  contents <- L.getContents
  case sumFile contents of
    Nothing -> print "Invalid input"
    Just s -> print $ getSum s
   where sumFile = foldl' (\ x y -> forceMaybe (x `mappend` y)) (Just (Sum 0)) . map ((fmap Sum) . (fmap fst) . LCHAR.readInt) . (LCHAR.words)
于 2012-08-19T02:51:06.513 回答
0

我查看了该书的在线版本，该程序下有一些讨论，它使用堆栈空间的原因是由于map，将map替换为foldl'解决了问题。

于 2012-08-18T12:18:50.893 回答
0

首先，简单说明一下：ghc runtime 中的堆栈与堆栈段无关，它是运行时的内部结构，这不是缓冲区溢出类型攻击的来源。

第二。Haskell 很懒惰。惰性 io (getContents) 产生惰性列表。sum 懒惰地产生结果。但是，一旦请求 sum 的结果，它必须递归地挖掘列表，很快就会耗尽堆栈空间（如果愿意，您可以查看源代码）

为避免它，您必须使用严格版本的 sum，它应该可以消除问题。标准库对这种情况有一个特殊的功能， foldl' - foldl 的严格版本。使用foldl' (+) 0代替 sum 应该可以消除问题

第三。当使用惰性 IO 时，堆栈空间泄漏是非常常见的问题。如果切换到基于迭代的 IO 可能会解决。否则应该学会在需要的地方添加严格性注释。

啊。顺便说一下。GHC 正在优化编译器。这并不常见，但编译程序中的内存泄漏仍然可能存在一些问题，而 ghci 则不存在这些问题，反之亦然。

于 2012-08-18T12:23:52.310 回答