I was trying "all possible" tricks I came across the internet, with "all possible" combinations of !
, seq
, deepseq
, ... but I could not find the way to suppress the leaking of memory in the following program
{-# LANGUAGE BangPatterns #-}
import Data.List
import Control.DeepSeq
foldl'' f z (x:xs) = let z' = f z x in z' `deepseq` foldl'' f z' xs
foldl'' _ z [] = z
statistics :: [[Double]] -> [(Double, Double)]
statistics (z:zs) = normalize $ foldl'' go acc zs
where acc = map (\x -> (x, x^2)) z
go = zipWith (\(a, b) x -> (a + x, b + x^2))
n = 1 + (length zs)
dn = fromIntegral n
normalize = map (\(a, b) -> (a / dn, (b - a^2 / dn) / dn))
main = mapM_ (putStrLn . show) (statistics ps)
where ps = take nn $ unfoldr (Just . splitAt mm) $ map sin [1..]
nn = 1000
mm = 1000
which calculates the mean and the variance of "mm
variables from nn
measurements".
Can you give me a hint?
EDIT
As pointed out in answers, the problem is in calling length
. So the better version could be
{-# LANGUAGE BangPatterns #-}
import Data.List
import Control.DeepSeq
foldl'' f z (x:xs) = let z' = f z x in z' `deepseq` foldl'' f z' xs
foldl'' _ z [] = z
statistics :: [[Double]] -> [(Double, Double)]
statistics (z:zs) = normalize $ foldl'' go acc zs
where acc = (1, map (\x -> (x, x^2)) z)
go = \(n, abs) xs -> (n + 1, zipWith (\(a, b) x -> (a + x, b + x^2)) abs xs)
normalize (n, abs) = map (\(a, b) -> (a / n, (b - a^2 / n) / n)) abs
main = mapM_ (putStrLn . show) (statistics ps)
where ps = take nn $ unfoldr (Just . splitAt mm) $ map sin [1..]
nn = 100
mm = 1000000
but it still leaks if mm
is large because of a thunk created by zipWith
. Instead I have tried
zipWith' f xs ys = go f [] xs ys
where go f zs (a:as) (b:bs) =
let zs' = (f a b) : zs in go f zs' as bs
go _ zs _ _ = foldl' (\x y -> y : x) [] zs
but unsuccessfully.
EDIT
The profiling output for the second improved example and for nn=100
and mm=1e6
:
leak +RTS -p -h -RTS
total time = 5.18 secs (5180 ticks @ 1000 us, 1 processor)
total alloc = 4,769,555,408 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
main Main 67.4 64.0
main.ps Main 18.1 21.6
statistics.go.\ Main 6.7 11.7
statistics.go.\.\ Main 5.3 1.9
foldl'' Main 1.5 0.0
individual inherited
COST CENTRE no. entries %time %alloc %time %alloc
MAIN 46 0 0.0 0.0 100.0 100.0
main 94 0 67.4 64.0 67.4 64.0
CAF 91 0 0.0 0.0 32.6 36.0
main 92 1 0.0 0.0 32.6 36.0
main.mm 97 1 0.0 0.0 0.0 0.0
main.nn 96 1 0.0 0.0 0.0 0.0
main.ps 95 1 18.1 21.6 18.1 21.6
statistics 93 1 0.0 0.0 14.5 14.4
statistics.normalize 106 1 0.4 0.4 0.8 0.5
statistics.normalize.\ 107 100000 0.4 0.1 0.4 0.1
statistics.acc 102 1 0.2 0.3 0.3 0.3
statistics.acc.\ 104 100000 0.1 0.0 0.1 0.0
statistics.go 100 1 0.0 0.0 0.0 0.0
foldl'' 98 30 1.5 0.0 13.5 13.6
foldl''.z' 99 29 0.0 0.0 12.0 13.6
statistics.go 101 0 0.0 0.0 12.0 13.6
statistics.go.\ 103 29 6.7 11.7 12.0 13.6
statistics.go.\.\ 105 2900000 5.3 1.9 5.3 1.9
It seems, like Thomas M. DuBuisson suggested, that the "leak" is related to the construction of ps
, but how else could it be constructed?
where
clause is not aligned and uses variable names that start with a capital letter). Second, post specifics of the problem (why do you think this is a memory leak? Do you see that you are forcing the entire list into memory due to thelength
call?).zipWith
and not, say,foldr (Just . splitAt mm)
?foldl''
contains a list of 1000000 elements that you force using deepseq; that naturally causes a lot of memory consumption.nn
from 2 upwards. Also, the calculation of the state size is wrong: The list contains 1000000 tuples of Doubles, so 1000000 * (3 + 3 + 2 + 2) * 8 = 80MB, and we get (a bit) closer to 240MB. If there is another such list somewhere and we add a bit overhead for the generational GC, we might have the observed 240MB. Did you try profiling?:
constructor, 3 words for the(,)
constructor, 2 words for the leftDouble
, 2 words for the rightDouble