haskell ghc space-leak

haskell - Fuga de espacio con uso redundante de seq en intérprete de GHC



space-leak (2)

Creo que @nm tiene razón. Nada está forzando el valor en la lista, por lo que el 1 + 1 + 1 + 1 + ... thunk eventualmente mata el espacio.

Prepararé una prueba rápida.

Escribo este código en el intérprete y la memoria se consume rápidamente:

last [1..10^7] `seq` ()

No puedo ver por qué esto necesita más que O (1) espacio. Si lo hago solo (¿cuál debería ser el mismo, porque Mostrar fuerza normal de cabeza débil, entonces la secuencia es redundante?):

last [1..10^7]

...funciona bien.

No puedo reproducir esta situación fuera del intérprete.

¿Que está pasando aqui?

Aquí hay algunos casos de prueba: http://hpaste.org/69234

Cosas a tener en cuenta:

  • Al ejecutarme en el intérprete, cargo wtf.hs sin compilarlo, y escribo wtf<n> en ghci.
  • Al compilar, hago ghc --make wtf.hs && ./wtf .
  • last puede sustituirse por una sum con un acumulador estricto o una función que encuentre el elemento máximo en la lista, y la pérdida de espacio todavía ocurra
  • ¡No he visto este comportamiento cuando uso $! en lugar de seq .
  • Intenté agregar un parámetro dummy () porque pensé que quizás esto es un problema de CAF. No cambia nada.
  • Probablemente no sea un problema con las funciones en Enum , porque puedo reproducir el comportamiento con wtf5 y posteriores, que no usan Enum en absoluto.
  • Probablemente no sea un problema con Num , Int o Integer , porque puedo reproducir el comportamiento sin ellos en wtf14 y wtf16 .

Intenté reproducir el problema con la aritmética de Peano para sacar las listas y los enteros de la ecuación (obtener el final de 10 ^ 9), pero me topé con otros problemas de pérdida de espacio / uso compartido que no entiendo al intentar implementar * .

Necesitamos ver la instancia de enumFromTo para Integer, y por último:

last [] = errorEmptyList "last" last (x:xs) = last'' x xs where last'' y [] = y last'' _ (y:ys) = last'' y ys

Se define en GHC.Enum como:

enumFrom x = enumDeltaInteger x 1 enumFromThen x y = enumDeltaInteger x (y-x) enumFromTo x lim = enumDeltaToInteger x 1 lim

dónde

enumDeltaInteger :: Integer -> Integer -> [Integer] enumDeltaInteger x d = x `seq` (x : enumDeltaInteger (x+d) d) -- strict accumulator, so -- head (drop 1000000 [1 .. ] -- works

y

enumDeltaToInteger :: Integer -> Integer -> Integer -> [Integer] enumDeltaToInteger x delta lim | delta >= 0 = up_list x delta lim | otherwise = dn_list x delta lim up_list :: Integer -> Integer -> Integer -> [Integer] up_list x0 delta lim = go (x0 :: Integer) where go x | x > lim = [] | otherwise = x : go (x+delta)

last es totalmente perezoso, como se esperaba.

Para la clase Enum Integer, tenemos un acumulador estricto (explícitamente) para enumFrom . En el caso delimitado (por ejemplo, [1..n] ), llama a enumDeltaToInteger y luego a up_list , que utiliza un trabajador para desplegar una lista hasta que se alcanza su límite.

Pero up_list es estricto en x en el ayudante de go (ver la comparación con lim ).

Cuando se ejecuta en GHCi, nada de esto está optimizado, lo que produce llamadas ingenuas a enumFromTo, antes de devolver () .

let it_ax6 :: () it_ax6 = case last @ GHC.Integer.Type.Integer (GHC.Enum.enumFromTo @ GHC.Integer.Type.Integer GHC.Num.$fEnumInteger (GHC.Integer.smallInteger 1) (GHC.Real.^ @ GHC.Integer.Type.Integer @ GHC.Integer.Type.Integer GHC.Num.$fNumInteger GHC.Real.$fIntegralInteger (GHC.Integer.smallInteger 10) (GHC.Integer.smallInteger 7))) of _ -> GHC.Unit.() in GHC.Base.thenIO @ () @ [()] (System.IO.print @ () GHC.Show.$fShow() it_ax6) (GHC.Base.returnIO @ [()] (GHC.Types.: @ () it_ax6 (GHC.Types.[] @ ())))

Entonces, ¿por qué estamos reteniendo la lista en el caso de seq , y no en el caso normal? El caso normal se ejecuta bien en el espacio de construcción, confiando en la pereza de enumFromTo para Integer y para el last . El núcleo de GHCi para ese caso se ve así:

let { it_aKj :: GHC.Integer.Type.Integer [LclId, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False, ConLike=False, Cheap=False, Expandable=False, Guidance=IF_ARGS [] 170 0}] it_aKj = GHC.List.last @ GHC.Integer.Type.Integer (GHC.Enum.enumFromTo @ GHC.Integer.Type.Integer GHC.Num.$fEnumInteger (GHC.Integer.smallInteger 1) (GHC.Real.^ @ GHC.Integer.Type.Integer @ GHC.Integer.Type.Integer GHC.Num.$fNumInteger GHC.Real.$fIntegralInteger (GHC.Integer.smallInteger 10) (GHC.Integer.smallInteger 7))) } in GHC.Base.thenIO @ () @ [()] (System.IO.print @ GHC.Integer.Type.Integer GHC.Num.$fShowInteger it_aKj) (GHC.Base.returnIO @ [()] (GHC.Types.: @ () (it_aKj `cast` (UnsafeCo GHC.Integer.Type.Integer () :: GHC.Integer.Type.Integer ~ ())) (GHC.Types.[] @ ())))

Así que estos son casi idénticos, con las diferencias siendo:

  • en la versión seq , la last (enumFromTo ..) se fuerza dentro de un case .
  • En la versión regular, es un let flojo.
  • en la versión seq , el valor se calcula y luego se descarta, lo que produce un () - nada mira el resultado
  • En el caso normal, se inspecciona y se muestra.

Lo que es extraño es que no hay nada mágico en:

let x = case last (enumFromTo 1 n) of _ -> ()

Eso lo hace retener valores.

Como vemos, la implementación de up_list es estricta en su acumulador (ya que se compara con lim , y la lista se despliega perezosamente, por lo que la last debería poder consumirla en un espacio constante). Escribir la expresión a mano confirma esto.

Al hacer un perfil de pila de la ejecución de ghci, se muestra la lista completa que se conserva:

lo que nos dice al menos que no es una cadena de thunks, sino que más bien, la lista completa se está construyendo estrictamente y se mantiene hasta que se descarta.

Entonces, el misterio es: ¿qué es lo que mantiene el argumento de la lista para last en ghci, y no en ghc?

Sospecho algún detalle interno (o sutil) de ghci ahora, creo que vale la pena un boleto de ghci.