Ленивое дерево с космической утечкой - PullRequest
Новая
       3

Ленивое дерево с космической утечкой

10 голосов
/ 10 июля 2011

Я пишу программу, пытаясь реализовать игрушечный процессор XML.Прямо сейчас программа должна прочитать поток событий (например, SAX), описывающий структуру документа, и лениво построить соответствующее дерево.

События определяются следующим типом данных: 

data Event = Open String
           | Close

Тогда возможный ввод: 

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

, который будет соответствовать дереву: 

  a
 / \
b   c

Я бы хотел сгенерировать дерево ленивым образом, чтобыон не должен присутствовать в памяти в полной форме в любое время.Моя текущая реализация, однако, похоже, имеет утечку пространства, в результате чего все узлы сохраняются, даже когда они больше не нужны.Вот код: 

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 собирает все дочерние узлы (помеченные буквой "b") корня ("a").Затем они подсчитываются и выводится полученное число.

Скомпилированная программа, созданная с использованием GHC 7.0.4 (-O2), продолжает увеличивать использование памяти до того момента, когда она печатает число узлов.С другой стороны, я ожидал почти постоянного использования памяти.

Глядя на профиль кучи "-hd", становится ясно, что большая часть памяти занята конструктором списка (:),Похоже, что один из списков, созданных scan или trees, сохраняется полностью.Однако я не понимаю, почему length . getChildren должен избавляться от дочерних узлов, как только они пройдены.

Есть ли способ исправить такую ​​утечку пространства?

Ответы [ 2 ]

6 голосов
/ 10 июля 2011

Я подозреваю, что trees злой парень. Как сказал Джон Л., это, вероятно, случай утечки пространства Вадлера, в которой компилятор не может применить оптимизацию, предотвращающую утечку. Проблема заключается в том, что вы используете ленивое сопоставление с образцом (выражение let), чтобы деконструировать пару и выполнить сопоставление с образцом посредством применения 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

В этой реализации максимальное количество резидентов уменьшается с 38 МБ до 28 КБ.

Но учтите, что эта новая реализация trees является более строгой, чем оригинальная, поскольку требует применения splitStream. Следовательно, в некоторых случаях это преобразование может даже вызвать утечку пространства. Чтобы восстановить менее строгую реализацию, вы можете использовать трюк, аналогичный функции lines в Data.List, которая вызывает аналогичную проблему 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'

Если мы снимаем совпадение с ленивым шаблоном, мы получаем следующую реализацию. Здесь компилятор может обнаружить селектор для компонента кортежа, поскольку мы не выполняем сопоставление с шаблоном для одного из компонентов. 

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

Кто-нибудь знает, всегда ли это преобразование помогает?

5 голосов
/ 10 июля 2011

Я сильно подозреваю, что это пример "утечки пространства Вадлера" . К сожалению, я не знаю, как ее решить, но я нашел несколько вещей, которые несколько смягчают последствия:

1) Изменить getChildren на 

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

Это небольшое, но заметное улучшение.

2) В этом примере trees всегда выводит список из одного элемента. Если это всегда верно для ваших данных, явное удаление остальной части списка устраняет утечку пространства: 

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