5 
module Has (r,p,s) where

import Prelude ((==),Bool(..),otherwise,(||),Eq)
import qualified Data.List as L

filter :: (a -> Bool) -> [a] -> [a]
filter _pred []    = []
filter pred (x:xs)
  | pred x         = x : filter pred xs
  | otherwise      = filter pred xs

問題1：これfilterはのライブラリからコピーされますが、一定数のメモリを消費する直接インポートされたとは対照的にGHC、なぜそれがますます多くのメモリを消費するのですか。filter

elem :: (Eq a) => a -> [a] -> Bool
elem _ []       = False
elem x (y:ys)   = x==y || elem x ys

問題2：これfilterはのライブラリからコピーされますが、直接使用されるようにGHCメモリの消費量が増えるのはなぜですか。直接インポートされるのとは対照的に、メモリの消費量も増えます。elemfilter

r = L.filter (==1000000000000) [0..]
p = filter (==1000000000000) [0..]
s = 1000000000000 `elem` [0..]

GHCバージョン：7.4.2OS：Ubuntu12.10最適化のために-O2とコンパイル

上記filterとのelem定義は両方を意味するp = filter (==1000000000000) [0..]ので、とは徐々にガベージコレクションする必要があります。しかし、両方とも、ますます多くのメモリを消費します。そして、直接インポートされたもので定義されるものは、一定数のメモリを消費します。s = 1000000000000 `elem` [0..][0..]psrfilter

私の質問は、GHCに直接インポートされた関数が、GHCライブラリからコピーされたソースコードを使用して記述した関数と大きく異なる理由です。GHCに何か問題があるのだろうか？

さらに質問があります。上記のコードは、私が作成したプロジェクトから抽象化されたものであり、プロジェクトは「理論的にはガベージコレクションされるはずのメモリの消費量が増える」という問題にも直面しています。したがって、GHCでどの変数が非常に多くのメモリを使用しているかを見つける方法があることを知りたいと思います。

読んでくれてありがとう。

4

1 に答える 1

1

ghciのメモリ消費の原因は、filterまたはのコードではありませんelem。filter（ただし、 inの書き換えルールGHC.Listにより、通常は少し良くなります。）

-O2（ ）で生成されたコアghc-7.4.2（の一部）を見てみましょう-ddump-simpl。最初にr、を使用してGHC.List.filter：

Has.r1
  :: GHC.Integer.Type.Integer
     -> [GHC.Integer.Type.Integer] -> [GHC.Integer.Type.Integer]
[GblId,
 Arity=2,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [0 0] 60 30}]
Has.r1 =
  \ (x_awu :: GHC.Integer.Type.Integer)
    (r2_awv :: [GHC.Integer.Type.Integer]) ->
    case GHC.Integer.Type.eqInteger x_awu Has.p5 of _ {
      GHC.Types.False -> r2_awv;
      GHC.Types.True ->
        GHC.Types.: @ GHC.Integer.Type.Integer x_awu r2_awv
    }

Has.r :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 40 0}]
Has.r =
  GHC.Enum.enumDeltaIntegerFB
    @ [GHC.Integer.Type.Integer] Has.r1 Has.p3 Has.p2

Has.p3、、です。0 :: Integer_ 書き換えルール（forと）はそれを（短い名前で）に変えましたHas.p21 :: IntegerfilterenumDeltaInteger

r = go fun 0 1
  where
    go foo x d = x `seq` (x `foo` (go foo (x+d) d))

fun n list
    | n == 1000000000000 = n : list
    | otherwise          = list

funインライン化されていればもう少し効率的かもしれませんが、要点は、filter編集されるリストがそのように存在しないため、融合されたということです。

p一方、書き換えルールがないと、次のようになります。

Has.p1 :: [GHC.Integer.Type.Integer]
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p1 = GHC.Enum.enumDeltaInteger Has.p3 Has.p2

Has.p :: [GHC.Integer.Type.Integer]
[GblId,
 Str=DmdType,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Has.p = Has.filter @ GHC.Integer.Type.Integer Has.p4 Has.p1

[0 .. ]リスト（Has.p1）の最上位CAFであり、リストにHas.filter適用され(== 1000000000000)ます。

したがって、これはフィルタリングされる実際のリストを作成します-したがって、効率がやや低下します。

しかし、通常（コンパイルされたバイナリを実行する）、リストは消費されるときにガベージコレクションされるため、メモリ消費の観点からは問題ありません。ただし、私を超えた理由で、ヒーププロファイルから収集できるように（評価しているので、1つしかない）、ghciは[0 .. ]評価するときにリストを保持しpますs（ただし、それは独自のコピーを持っているので、ここで共有する必要はありません）。リストセルの可能なソース。ghciはで呼び出されたため、メモリ使用量が300Mに達した直後に、ghciは終了しました）：[0 .. ]-hTs+RTS -M300M -hT -RTS

ここに画像の説明を入力してください

したがって、ghciでのメモリ消費の原因は、フィルタリングされるリストのハードコーディングです。プロンプトで提供されるリストを使用する場合Has.filter、メモリ使用量は予想どおり一定です。

リストを保持しているghci[0 .. ]がバグなのか、意図した動作なのかわかりません。

于 2013-03-26T15:46:43.950 に答える