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.

2 つの質問があります。

  1. スタック スペースの使用量の原因は何ですか?
  2. コンパイルされたバージョンが解釈されたバージョンと異なるのはなぜですか? どうすればよいですか?

ありがとう！

編集：

理由はわかりましたマップですが、遅延バイト文字列を使用する変更されたバージョンは次のとおりです。

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)

結果は同じです。合計を使用していないにもかかわらず、バイナリ バージョンはスタック スペースを使い果たします。

4

3 に答える 3

1

#haskell で人々と議論しました。ByteString バージョンでスタック オーバーフロー エラーが発生する理由は、内部部分が厳密に評価されないネストされた Just (Sum Num) が原因です。

基本的に、2 つの Maybe (Just Num)、たとえば Just (Sum 2) と Just (Sum 3) をマップする場合、foldl' は seq を使用して Just ((Sum 2) mappend (Sum 3)) を生成します。seq は、最も外側のコンストラクターを厳密に評価しました (Just (Monoid) を生成するために 2 つの Just (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

この本のオンライン版をチェックアウトしました。そのプログラムの下でいくつかの議論があり、スタックスペースを使用する理由はマップによるもので、マップをfoldlに置き換えると問題が解決します。

于 2012-08-18T12:18:50.893 に答える
0

まず、簡単な説明: ghc ランタイムのスタックはスタック セグメントを処理するものは何もありません。これはランタイムの内部構造であり、これはバッファ オーバーフロー タイプの攻撃の原因ではありません。

2番。Haskell は怠け者です。Lazy io (getContents) は遅延リストを生成します。sum は遅延して結果を生成します。ただし、合計の結果が要求されると、再帰的にリストを掘り下げる必要があり、すぐにスタック領域を使い果たします (必要に応じてソースを調べることができます)。

それを避けるには、厳密なバージョンの合計を使用する必要があります。これにより、問題が解消されるはずです。標準ライブラリには、そのような場合のための特別な関数、foldl' (foldl の厳密なバージョン) があります。合計の代わりに使用foldl' (+) 0すると、問題が解消されます

三番。スタック スペース リークは、遅延 IO を使用する場合によくある問題です。iteratee ベースの IO に切り替えると解決する場合があります。それ以外の場合は、必要に応じて厳密性注釈を追加する方法を学ぶ必要があります。

ああ。ところで。GHCはコンパイラを最適化しています。一般的ではありませんが、コンパイルされたプログラムでメモリリークの問題が発生し、ghci では問題が発生しない、またはその逆の可能性があります。

于 2012-08-18T12:23:52.310 に答える