Árbol difuso con una fuga de espacio

Question

Estoy escribiendo un programa que intenta implementar un procesador XML de juguete. En este momento se supone que el programa debe leer un flujo de eventos (piense en SAX) describiendo la estructura de un documento y construyendo perezosamente el árbol correspondiente.

Los eventos se definen mediante la siguiente tipo de datos:

data Event = Open String 
      | Close 

Una posible entrada entonces sería:

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

que correspondería al árbol:

a 
/\ 
b c 

lo haría gusta generar el árbol de una manera perezosa, por lo que no necesita estar presente en la memoria en forma completa en cualquier momento. Mi implementación actual, sin embargo, parece tener una fuga de espacio que hace que se conserven todos los nodos, incluso cuando ya no son necesarios. Aquí está el código:

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 La función convierte la lista de eventos en una lista de Tree Node. getChildren recoge todos los nodos secundarios (etiquetados como "b") de la raíz ("a"). Estos se cuentan y el número resultante se imprime.

El programa compilado, construido con GHC 7.0.4 (-O2), sigue aumentando su uso de memoria hasta el punto en que imprime el recuento de nodos. Esperaba, por otro lado, un uso de memoria casi constante.

En cuanto al perfil del montón "-hd", está claro que la mayoría de la memoria la toma el constructor de lista (:). Parece que una de las listas producidas por scan o por trees se conserva por completo. No entiendo por qué, sin embargo, como length . getChildren debería deshacerse de los nodos secundarios tan pronto como se atraviesan.

¿Hay alguna forma de solucionar dicha fuga de espacio?

Answer 1

Sospecho que trees es el chico malo. Como John L dijo, esto es probablemente una instancia de Wadler Space Leak en la cual el compilador no puede aplicar la optimización que previene la fuga. El problema es que utiliza una coincidencia de patrón diferida (la expresión let) para deconstruir el par y realizar la coincidencia de patrón a través de la aplicación de trees en uno de los componentes de la tupla. Tuve un problema bastante similar una vez http://comments.gmane.org/gmane.comp.lang.haskell.glasgow.user/19129. Este hilo también proporciona una explicación más detallada. Para evitar la fuga de espacio, simplemente puede usar una expresión case para deconstruir la tupla de la siguiente manera.

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

Con esta implementación, la residencia máxima se reduce de 38MB a 28KB.

Pero tenga en cuenta que esta nueva implementación de trees es más estricta que la original ya que exige la aplicación de splitStream. Por lo tanto, en algunos casos, esta transformación podría causar una fuga de espacio. Para recuperar una implementación menos estricta, puede usar un truco similar al de la función lines en Data.List que causa un problema similar http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-List.html#lines. En este caso, trees se vería de la siguiente manera.

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' 

Si desugamos la coincidencia de patrones diferidos obtenemos la siguiente implementación. Aquí el compilador puede detectar el selector al componente de tupla ya que no realizamos la coincidencia de patrones en uno de los componentes.

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

¿Alguien sabe si esta transformación siempre funciona?

Answer 2

Sospecho fuertemente que este es un ejemplo del error "Wadler space leak". Por desgracia, no sé cómo resolverlo, pero encontré algunas cosas que mitiguen los efectos algo:

1) Cambiar getChildren a

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

Este es un pequeño, pero notable, la mejora.

2) En este ejemplo trees siempre muestra una lista de elementos individuales. Si esto es siempre cierto para sus datos, cayendo de forma explícita el resto de la lista fija el espacio de fugas:

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