スペースリークのあるレイジーツリー

Question

おもちゃのXMLプロセッサを実装しようとしているプログラムを書いています。現在、プログラムは、文書の構造を記述するイベントのストリーム（SAXと考える）を読み込み、対応するツリーを遅延して構築することになっています。イベントは、以下のデータ型によって定義される

：

data Event = Open String 
      | Close 

可能な入力は、次のようになり：ツリーに対応する

[Open "a", Open "b", Close, Open "c", Close, Close] 

：

a 
/\ 
b c 

I希望ツリーを怠け者のように生成したいので、完全な形でメモリに存在する必要はありません いつでも。しかし、私の現在の実装では、スペースリークが発生して、もはや必要でなくなってもすべてのノードが保持されているように見えます。ここでは、コードは次のようになります。

data Event = Open String 
      | Close 

data Tree a = Tree a (Trees a) 

type Trees a = [Tree a] 

data Node = Node String 


trees [] = [] 
trees (Open x : es) = 
    let (children, rest) = splitStream es 
    in (Tree (Node x) (trees children)) : (trees rest) 

splitStream es = scan 1 es 

scan depth (s@(Open {}) : ss) = 
    let (b, a) = scan (depth+1) ss 
    in (s:b, a) 
scan depth (s@Close : ss) = 
    case depth of 
     1 -> ([], ss) 
     x -> let (b, a) = scan (depth-1) ss 
      in (s:b, a) 


getChildren = concatMap loop 
    where 
    loop (Tree _ cs) = cs 


main = print . 
     length . 
     getChildren . 
     trees $ 
     [Open "a"] ++ (concat . replicate 1000000 $ [Open "b", Close]) ++ [Close] 

機能treesはTree Nodeのリストにイベントのリストに変換します。 getChildrenは、ルート（ "a"）のすべての子ノード（ラベル "b"）を収集します。これらを数え、結果の数字が印刷されます。

GHC 7.0.4（-O2）で構築されたコンパイル済みプログラムは、ノードカウントを出力する時点までメモリ使用量を増加し続けます。私は、一方で、ほぼ一定のメモリ使用量を期待していました。

"-hd"ヒーププロファイルを見ると、ほとんどのメモリがリストコンストラクタ（:）によって取得されていることがわかります。 scanまたはtreesによって生成されたリストの1つが完全に保持されているようです。私はなぜ、なぜ、length . getChildrenが通過するとすぐに子ノードを取り除くべきなのか理解していません。

このようなスペースリークを修正する方法はありますか？

Answer 1

を私はtreesは悪男であることを疑います。 John Lが言ったように、これはおそらく、コンパイラがリークを防ぐ最適化を適用できないWadler Space Leakのインスタンスです。問題は、遅延のパターンマッチング（let式）を使用してペアを分解し、タプルのコンポーネントの1つにtreesというアプリケーションを使用してパターンマッチングを実行することです。私はまったく同じような問題があった。http://comments.gmane.org/gmane.comp.lang.haskell.glasgow.user/19129。このスレッドは、より詳細な説明も提供します。スペースリークを防ぐには、単純にcaseの式を使用して、次のようにタプルを分解してください。

trees [] = [] 
trees (Open x : es) = 
    case splitStream es of 
     (children, rest) -> Tree (Node x) (trees children) : trees rest 

この実装では、最大常駐度は38MBから28KBに低下します。

しかし、treesのこの新しい実装は、splitStreamのアプリケーションを要求するので、元のものより厳密です。したがって、場合によっては、この変換によってスペースリークが発生することさえあります。より厳密ではない実装を取り戻すには、同様の問題を引き起こすData.Listのlines関数と同様のトリックを使用することがあります。http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-List.html#linesこの場合、treesは次のようになります。

trees [] = [] 
trees (Open x : es) = 
    context (case splitStream es of 
       (children, rest) -> (trees children, trees rest)) 
where 
    context ~(children', rest') = Tree (Node x) children' : rest' 

遅延パターンマッチングを使用しないと、次の実装が得られます。ここでコンパイラは、タプルコンポーネントのセレクタを検出できます。これは、コンポーネントの1つでパターンマッチングを実行しないためです。

trees [] = [] 
trees (Open x : es) = Tree (Node x) children' : rest' 
where 
    (children', rest') = 
    case splitStream es of 
      (children, rest) -> (trees children, trees rest) 

この変換が常にこのトリックを行うかどうかは誰にも分かりますか？

Answer 2

これは"Wadler space leak"バグの例だと強く思っています。

1）これは小さいが目立ち、改善されgetChildren

getChildren' = ($ []) . foldl (\ xsf (Tree _ cs) -> xsf . (cs ++)) id 

に変更します。残念ながら、私はそれを解決する方法がわからないが、私は多少影響を緩和するいくつかのことを発見しました。

2）この例では、treesは常に単一要素リストを出力します。これはあなたのデータは常に真である場合には、明示的にリストの残りの部分をドロップすると、スペースリーク修正されています。

main = print . 
    length . 
    getChildren . 
    (:[]) . 
    head . 
    trees