Nieoczekiwany wzrost pamięci za pomocą Control.Monad foldM

Question

Mam następujący kod, który został rozebrany i uważam, że jest tak minimalny, jak to tylko możliwe, który ma bardzo dziwne zachowanie.

Kod składa się z dwóch plików źródłowych: One zdefiniować pewne dane:

module MyFunction where 

data MyFunction = 
    MyFunction { 
     functionNumber :: Int, 
     functionResult :: IO String 
     } 

makeMyFunction :: Show a => Int -> IO a -> MyFunction 
makeMyFunction number result = MyFunction { 
    functionNumber = number, 
    functionResult = result >>= return . show } 

a druga jest główne:

module Main (main) where 

import System.CPUTime (getCPUTime) 
import Data.List (foldl') 
import Data.Foldable (foldlM) 
import Control.Monad (foldM) 
import MyFunction 

exampleFunction = do 
    --let x = foldl' (\a b -> a `seq` (a + b)) 0 [1..20000000]  -- This works 
    --x <- foldlM (\a b -> a `seq` return (a + b)) 0 [1..20000000] -- This works (*) 
    x <- foldM (\a b -> a `seq` return (a + b)) 0 [1..20000000] -- This doesn't 
    print x 
    return() 

runFunction fn = do 
    result <- functionResult fn 
    duration <- getCPUTime 
    if result /= "()" 
     then putStrLn "" 
     else return() 
    putStrLn (show (fromIntegral duration/(10^9)) ++ "ms") 
    return fn 

main = do 
    runFunction (makeMyFunction 123 exampleFunction) 
    return() 

Kod jak powyżej (skompilowany przy użyciu GHC 7.10.3 ze stosem 1.0.0 z domyślnymi flagami) ma gwałtowny wzrost wykorzystania pamięci (przekraczający 1 GB) i trwa zwykle 3,3 sekundy.

Jeśli zrobię zmian w kodzie, na przykład:

• użyć jednego z komentujących alternatyw dla linii problemu
• wykupić dowolną linię z runFunction

zużycie pamięci pozostanie minimalna i zajmie tylko około 1 sekundy.

Jedną z funkcji, która jest dla mnie najbardziej zaskakująca, jest to, że zastąpienie foldM przez foldlM (o ile wiem, foldM = foldlM) rozwiązuje problem.

Również wprowadzanie zmian w kodzie, którego nie widzę, ma związek z linią problemu kodu, również rozwiązuje problem. Na przykład usunięcie ostatniego putStrLn.

Inną osobliwością jest to, że jeśli mogę połączyć moduł MyFunction do modułu głównego, a to nie rozwiązuje problemu, to faktycznie powoduje foldlM zachowywać się jak foldM używając dużej pamięci.

W rzeczywistym kodzie, że pochodzą, mam dużą liczbę exampleFunction s, a tam jest znacznie więcej kodu Main, i tak często spotykam tego rodzaju niewyjaśnione wykorzystania pamięci z funkcji, które zazwyczaj mogą być rozwiązane przez jakiś rodzaj voodoo.

Szukam wyjaśnienia zachowania. Jeśli wiem, dlaczego tak się dzieje, mogę popatrzeć, jak tego uniknąć. Czy to może być problem z kompilatorem, czy może po prostu nieporozumienie z mojej strony?

(*) Podkreśliłem problem dodatkowy, który powoduje taki sam wzrost pamięci w przypadku foldlM.

Answer 1

Oto foldlM z Foldable.hs (ghc)

-- | Monadic fold over the elements of a structure, 
-- associating to the left, i.e. from left to right. 
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b 
foldlM f z0 xs = foldr f' return xs z0 
    where f' x k z = f z x >>= k 

i foldM z Monad.hs

foldM   :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b 
{-# INLINEABLE foldM #-} 
{-# SPECIALISE foldM :: (a -> b -> IO a) -> a -> [b] -> IO a #-} 
{-# SPECIALISE foldM :: (a -> b -> Maybe a) -> a -> [b] -> Maybe a #-} 
foldM   = foldlM 

że umieszcza te definicje oddzielnym teście modułu i testowano wykonania i bez INLINEABLE/SPESIALISE kwestia. Bez względu na przyczynę, pomijając dyrektywy SPECIALIZE, pomógł czas wykonania i użycie pamięci w foldlM.

Po nieco więcej kopania, usunięcie linii

{-# SPECIALISE foldM :: (a -> b -> IO a) -> a -> [b] -> IO a #-} 

przeprowadzić najbardziej.